-
-
[原创]看雪6月 京东 2018CTF 第七题——有趣的密室逃脱游戏
-
2018-6-30 11:55 3067
-
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 密室逃脱的提示
好像还真的跟提示一一对应了,这题挺有意思的
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界