2022_SUSCTF_tttree题解
2022_SUSCTF_tttree题解
这道题比赛时,逆出了整个节点结构体,就是最后通过二叉树找到索引的时候不会了,只爆破出来了flag的4位,后来看了看别人的WP才发现程序中是存着节点之间的关系的(可惜啊,当时调试还是没有足够的耐心啊,这里复现下,
首先将程序去除ASLR, 用CFF Explorer打开程序,去除去除DLL Can move的属性,然后保存,这样每次程序加载的基址就不会变,就可以方便的下断点了
输入flag,按下暂停键,
然后回车,程序断下,直接ALT+F9 运行到用户代码
观察堆栈,可以发现在00014000E1B0的位置处存着输入的flag,直接转过去,下硬件断点,然后执行
发现程序是从1开始验证的,正好略过了前面的SUSCTF,也就是说他会检测SUSCTF{xxx } 里的 xxx,这里就会发现程序用了花指令,每一段里面存放着1条真正的指令
一路F7,观察执行的汇编,整理
1 | RAX是自己输入的字符 # 0x31 |
将EDX里面的值提取出来,
1 | key = [0x60, 0x46, 0x62, 0x03, 0x16, 0x19, 0x1E, 0x12, 0x4D, 0x51, 0x05, 0x25, 0x38, 0x2F, 0x14, 0x4F, |
可以发现,只要把加密后的enc_flag执行 flag = [enc_flag[i] - key[i] - 97 - i for i in range(32)]
就可以得到flag了
继续F7运行, 提取出有效的汇编指令
1 | # 验证完长度是40后 |
经过无尽的调试(在判断插入节点个数那里下断点,每插入一个节点,就把0x00000001400073B0那里的数据提取出来,进行比对)就会发现,程序是把输入的flag按照Treap的特性存放在了00000001400073C0处,这里是一个长度为33的结构体数组,(第一个数组全是0,因为序号是从1开始的,序号是0表示为空,有效的就是后面32个数组)每个单元的大小是0X1C
1 | struct tree_node{ |
在00000001400073B0处存放着根节点,00000001400073B4, 00000001400073B8处存着当前树的所有叶子个数
输入SUSCTF{01234567890122345679abcdefghijkl}
, 然后根据00000001400073C0处的数据画出自己输入的假的flag构造的二叉树
提取出00000001400073C0处有效的32个数组
1 | 00000000 00000013 000000F1 00000006 2109B018 00000001 00000030 |
一点点调试就会发现这采用了后序遍历的方式去遍历这个二叉树,
1 | ...... |
将140006040处的数据提取出来,构造二叉树
1 | encs = [0x00A2, 0x00AF, 0x009D, 0x00B7, 0x00D2, 0x00CB, 0x00C7, 0x00C6, 0x00B0, 0x00D5, 0x00DA, 0x00E3, 0x00E6, 0x00E8, 0x00E9, 0x00F3, |
flag—>加密–>按照顺序插入–>得到了这个二叉树,因此咱们现在只需要知道现在这个二叉树每个节点的索引,然后解密就可以得到原始的flag
在调试的过程中发现,如果当前比较的这个节点不是叶子节点的话,会对本节点和左孩子节点 ,本节点和右孩子节点 的关系进行验证
1 | # 比较的汇编代码在这 |
这就是我们的突破口
00000001400060C0 存放着本节点和左孩子节点的关系
00000001400061C0 存放着本节点和右孩子之间的关系
这2个数据怎么用呢?调试发现是 孩子节点序号 *0X17 + 本节点input = 关系s[本节点序号]
因此我们要得到孩子节点序号的话,需要知道本节点的Input + 本节点的序号,然后用本节点序号去索引左孩子或右孩子关系s,
1 | def get_child_xuhao(node_c, gx): |
因为Treap有堆的性质,根节点的优先级是最小的,因此我们提取出所有的优先级,对他进行排序
1 | c = [0x2109B018, 0x11BB2E13, 0x5D64CABB, 0x302F1C09, 0x02E78C02, 0x2A28B165, 0x6F018185, 0x1CF5A8D1, 0x1532F368, 0x42367652, 0x7B50B157, 0x244FA941, 0x48CB7CCC, 0x1950F130, 0x15561F1B, 0x29F35383, |
可以发现,索引是4,即序号是5的时候最小,即223的序号是5,根据5(序号)和223(enc_input)进行解密就可以得到本节点字符 ‘d’
1 | def get_real_c(_index, enc_input): |
然后写脚本递归就可以得到所有节点的字符
1 | # [本节点,左孩子,右孩子,序号,flag] |
flag为:SUSCTF{8226d8a68d25d8f03be17c4d7027b29c}