20180607
0x00 前言
这道题最后一看发现其实并不难，但是做起来怪怪的，有些本应该很简单的地方卡了很久，所以还是感觉有问题，自我总结一下。
0x01 程序逻辑
这个CrackMe咋一看很简单，关键算法就是一个三层嵌套的循环，前面有个把数字字母转成指定表下标的循环太简单了不说。
但是，这个内存布局给我的感觉就是很乱，最后我整理到后面得出如下
00000000 stack_mem struc ; (sizeof=0x140) ; XREF: check/r
00000000 u fst ? ; XREF: check+216/w
00000000 ; check+21C/w ...
00000010 input_idxes db 304 dup(?) ; XREF: check:loc_40123A/w
00000010 ; check+206/o ...
00000140 stack_mem ends
00000140
00000000 ; ---------------------------------------------------------------------------
00000000
00000000 fst union ; (sizeof=0x10) ; XREF: check+216/w
00000000 ; check+21C/w ...
00000000 arr db 16 dup(?)
00000000 i info ?
00000000 fst ends
00000000
00000000 ; ---------------------------------------------------------------------------
00000000
00000000 info struc ; (sizeof=0x10) ; XREF: fst/r
00000000 four dd ?
00000004 field_4 dd ?
00000008 key_idx db 4 dup(?)
0000000C idx dd ?
00000010 info ends
就是他循环遍历到后面，会通过这个结构体的base来访问后面的包括输入在内的数据，但是因为下标遍历从16开始，所以不会污染到下面的info里的数据。这个我不知道是怎么弄的，是否作者真的做了一个共用体来混淆。
这个弄清楚搞得我有点久，想了一下，问题就在有时候不想整理想直接通过各种强转看出逻辑，这个是不对的，至少我不行。所以有时候整理一下内存结构做个结构体真的是磨刀不误砍柴工的。
然后整理出来还有一个局部变量，有个地方他通过栈的地址强转成了int计算某个值，然后用于操作，实际上那个值就是会一直在2-11这样一直循环，这个情况很简单，调试一下，OD下个条件记录，就明了了。
所以总结
- 整理内存结构能大大加快分析效率
- 有时候静态看不出来尝试动态理解
接下来程序逻辑搞懂这些就好办了，他有一个bool_tab，一个初始化好的表，然后会根据那个东西赋值key_idx，这个是来自上一次的结果，然后这个会被计算成一个下标，访问一个char keys[64][64][64]的全局变量做一个映射。不如动态看看key_idx的值，输入abcdefghijklmnop，此时下标等于下标的数，方便分析
3rd 2nd 1st
0 key_idx = 020100 -> [0x00][0x01][0x02]
1 key_idx = 000403
2 key_idx = 000605
3 key_idx = 010705
4 key_idx = 010604
5 key_idx = 030208
6 key_idx = 040209
7 key_idx = 030A07
8 key_idx = 050C08
9 key_idx = 060D0B
10 key_idx = 070D0C
11 key_idx = 090E0B
12 key_idx = 0A080E
13 key_idx = 0A090F
14 key_idx = 0C0B0F
15 key_idx = 0E0D0F
很明显，这个bool_tab会控制这个循环，然后将上一次结果给到key_idx
虽然看起来有可能会溢出，但因为bool_tab的构造其实根本不会，其实连第4个元素都不会访问到（keys做映射只需要三个数）
然后逻辑基本上就是，根据上面来取下标，然后通过这个计算key_idx，访问keys，作为下一个结果
比方说第一个，就是取下标012，然后访问keys[[0]][[1]][[2]]作为下一个下标为0的数。
然后这么迭代19次。
0x02 暴力破解
这个爆破我还是想了很久的，满足一条限制的有4096个可能性，其实这个的规律是，如果有m个数，n条限制条件，那么可能性就是
pow(64, m-n)
通过真实写爆破验证程序观察和通过脑补，貌似都能感觉到是这个。关键是keys的映射是每64个都不一样的，才能导致这样的结果。
然后如果爆破的话，发现用前面两个爆破01234是pow(64,5-2)，然后基本上就维持在这个数了，后面多加一条限制最多也就多加一个数，所以最多需要的循环次数是0x40000000，不难爆破
所以爆破一条，找出3个元素的可能性，是这样的，能找到4096个
vector<uint32_t> find_idxes(uint8_t c)
{
vector<uint32_t> ret;
for (uint32_t i = 0; i < KEYS_LEN; i++)
{
if (keys[i] == c)
{
ret.push_back(i);
}
}
return ret;
}
然后爆破01234
inline uint8_t keys_access(uint8_t fst, uint8_t snd, uint8_t trd)
{
return keys[(fst << 12) + (snd << 6) + trd];
}
inline uint8_t fst(uint32_t idx)
{
return idx >> 12;
}
inline uint8_t snd(uint32_t idx)
{
return (idx >> 6) & 0x3f ;
}
inline uint8_t trd(uint32_t idx)
{
return idx & 0x3f;
}
vector<vector<uint8_t>> crack_01234(vector<uint8_t>& res)
{
vector<uint32_t> poss_012 = find_idxes(res[0]),
poss_340 = find_idxes(res[1]);
vector<vector<uint8_t>> ret;
for (uint32_t y : poss_012)
{
for (uint32_t x : poss_340)
{
if (fst(y) == trd(x))
{
vector<uint8_t> tmp;
tmp.push_back(fst(y));
tmp.push_back(snd(y));
tmp.push_back(trd(y));
tmp.push_back(fst(x));
tmp.push_back(snd(x));
ret.push_back(tmp);
}
}
}
return ret;
}
多加一个数，同时多加一条限制
vector<vector<uint8_t>> crack_012346(vector<uint8_t>& res)
{
vector<vector<uint8_t>> poss_01234 = crack_01234(res);
vector<uint32_t> poss_461 = find_idxes(res[4]);
vector<vector<uint8_t>> ret;
for (vector<uint8_t> y : poss_01234)
{
for (uint32_t x : poss_461)
{
if (fst(x) == y[4] && trd(x) == y[1])
{
vector<uint8_t> tmp = {y[0], y[1], y[2], y[3], y[4], snd(x)};
ret.push_back(tmp);
}
}
}
return ret;
}
然后加限制但是不加数是这样
vector<vector<uint8_t>> shrink_0123456789abcde(vector<uint8_t>& res)
{
vector<vector<uint8_t>> poss_0123456789abcde = crack_0123456789abcde(res);
vector<uint32_t> poss_e8a = find_idxes(res[12]);
vector<vector<uint8_t>> ret;
for (vector<uint8_t> y : poss_0123456789abcde)
{
for (uint32_t x : poss_e8a)
{
if (fst(x) == y[0xe] && snd(x) == y[0x8] && trd(x) == y[0xa])
{
ret.push_back(y);
}
}
}
return ret;
}
基本就这样，慢慢撸，完整代码写的又臭又长就不贴了，放在附件了
最后爆出来花的时间数了一下，VS release差不多4分钟多，没违反规则哈哈。
话说pdb路径看到个midpoint verify，不会我这个爆破的方法不是预期解吧。。。？
0x03 密室逃脱的提示
好像还真的跟提示一一对应了，这题挺有意思的