网站 › 『脱壳破解区』 › 2022_SUSCTF_RE_tttree题解

zsky 发表于 2022-3-3 11:14

2022_SUSCTF_RE_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，观察执行的汇编，整理

```python
RAX是自己输入的字符                # 0x31
RDX                                       # 0X60      每一次都是固定的
RCX                                  # mov ecx, dword ptr ss:也是每次固定的数据0XC1
RCX = (RDX + 97)          # RCX的数据恰好是RDX + 97   
RCX = RAX + RCX                  # RCX = 0XC1 + 0X31 == 0XF2
RAX = RCX                         # RAX = 0XF2
EAX + i(index)                  # EAX = EAX + 0(第一次是0) EAX = (0XF2 + 0) EAX = 0XF2
RCX = i
mov dword ptr ss:, eax                # 把算好的EAX放到了某个固定的位置 放在了栈中，是个局部变量

....   
000000014001C2D6 | 48:83F8 28                        | cmp rax,0x28                # 通过这里可以看出flag的长度是40位，除去SUSCTF{} ，中间的是32位
.....      

```

将EDX里面的值提取出来，

```python
key = [0x60, 0x46, 0x62, 0x03, 0x16, 0x19, 0x1E, 0x12, 0x4D, 0x51, 0x05, 0x25, 0x38, 0x2F, 0x14, 0x4F,
       0x5B, 0x2D, 0x4C, 0x26, 0x5A, 0x0F, 0x04, 0x07, 0x5F, 0x1D, 0x48, 0x1F, 0x67, 0x44, 0x3B, 0x37]
```

可以发现，只要把加密后的enc_flag执行 `flag= - key - 97 - i for i in range(32)]` 就可以得到flag了

继续F7运行, 提取出有效的汇编指令

```python
# 验证完长度是40后
# 初始位置XXXX
mov dword ptr ss:, 0x0                        
cmp dword ptr ss:, 0x20                              # i < 32?                # 地址是00000001400158B8

movsxd rax, dword ptr ss:
mov edx, dword ptr ss:                        # 取加密后的input
lea rcx, ds:                        
mov dword ptr ss:, edx
mov qword ptr ss:, rcx                                    # 00000001400073B0
sub rsp, 0x28
mov rax, qword ptr ss:                              #取出 00000001400073B0 给rax
cmp dword ptr ds:, 0x0                                                # 地址是：0000000140002A7D
je 0x00000001400122FE# 第一次是跳
#****************************************************这是跳的情况****************************************************
mov eax, dword ptr ds:         # 初始值是0
inc eax
mov dword ptr ds:, eax               # ++
   
mov rax, qword ptr ss:                              #取出 00000001400073B0 给rax   
mov ecx, dword ptr ds:   
mov dword ptr ds:, ecx                                                # 就是把 -->                

mov rax, qword ptr ss:                              # 取出 00000001400073B0 给 rax
movsxd rax, dword ptr ds:                        
imul rax, rax, 0x1C                                                                              

lea rcx, ds:
mov dword ptr ds:, 0x1
   
mov rax, qword ptr ss:                        # 取出 00000001400073B0 给rax
movsxd rax, dword ptr ds:      
imul rax, rax, 0x1C
lea rcx, ds:
mov dword ptr ds:, 0x1

mov rax, qword ptr ss:      # 取出 00000001400073B0 给rax
movsxd rax, dword ptr ds:   
imul rax, rax, 0x1C
lea rcx, ds:
   
mov edx,dword ptr ss:      #地址时: 0000000140016535 | 8B5424 38      取出EDX，即前面的加密后的input
mov dword ptr ds:, edx

mov rax, qword ptr ss:                # 取出00000001400073B0 给 RAX
mov eax, dword ptr ds:
add eax, 0x6

lea rcx, ds:                        # 0x000000014000E1B0      是输入的原始flag的全局位置
movsx eax, byte ptr ds:                        # 取出 0x31 ('1') 这是自己输入的
mov rcx, qword ptr ss:                  # 00000001400073B0 给 rcx
movsxd rcx, dword ptr ds:
imul rcx, rcx, 0x1C

lea rdx, ds:
mov dword ptr ds:, eax                # 把加密后的那个Input放到那个内存位置，像是一个结构体
   
##### 暂时不知道这一段是啥意思                (乘 0xbc8f) % 0x7FFFFFFF    谷歌搜到 # https://rvklein.me/proj/rando/rando-code.html
movsxd rax, dword ptr ds:      # 0x00000001400062C0的初始值是 0x1DF2ED66   # 本条指令地址是000000014001ABCC
imul rax, rax, 0xBC8F                #0000185591BAFD68
mov ecx, 0x7FFFFFFF                        
idiv rcx                                                # 第二轮 RAX: 00000000000030AB RDX 0000000011BB2E13(余数)这里是生成优先级，使其二叉搜索树满足堆的性质
mov rax, rdx                                       
mov dword ptr ds:, eax                              
mov eax, dword ptr ds:
#####

movsxd rcx, dword ptr ds:
lea rdx, ds:
mov dword ptr ds:, eax                  # 000000002109B018

movsxd rax, dword ptr ds:
lea rcx, ds:
mov rdx, qword ptr ss:                # 00000001400073B0 给 rdx
   
movsxd rdx, dword ptr ds:
imul rdx, rdx, 0x1C

lea r8, ds:
mov eax, dword ptr ds:               
mov dword ptr ds:, eax                # 000000002109B018

mov eax, dword ptr ds:
inc eax
mov dword ptr ds:, eax
add rsp, 0x28

mov eax, dword ptr ss:                # 一轮循环结束
inc eax   
mov dword ptr ss:, eax
   
cmp dword ptr ss:, 0x20                  # 回到了最上面的初始位置XXXX 地址：00000001400158B8

#****************************************************这是不跳的情况****************************************************
mov rax, qword ptr ss:                # 00000001400073B0      # 地址是0000000140012B60
movsxd rax, dword ptr ds:
imul rax, rax, 0x1C               
lea rcx, ds:

mov eax, dword ptr ds:
inc eax

mov rcx, qword ptr ss:
movsxd rcx, dword ptr ds:                  # 00000001400073B0
imul rcx, rcx, 0x1C
lea rdx, ds:
mov dword ptr ds:, eax                # 变为了2
mov rax, qword ptr ss:                        # 00000001400073B0
movsxd rax, dword ptr ds:   
imul rax, rax, 0x1C
lea rcx, ds:
mov edx, dword ptr ss:                        # 取出enc_input

cmp dword ptr ds:, edx
je 0x0000000140011E04   

mov rax, qword ptr ss:
movsxd rax, dword ptr ds:
imul rax, rax, 0x1C
lea rcx, ds:
mov eax, dword ptr ds:      # 取出enc_input
cmp dword ptr ss:, eax
jg 0x0000000140017AF8

mov rax, qword ptr ss:                # 00000001400073B0
movsxd rax, dword ptr ds:
imul rax, rax, 0x1C   
lea rcx, ds:
add rcx, rax
mov rax, rcx
mov edx, dword ptr ss:
mov rcx, rax
mov dword ptr ss:, edx
mov qword ptr ss:, rcx   
sub rsp, 0x28
mov rax, qword ptr ss:      #00000001400073DC

cmp dword ptr ds:, 0x0
je ****
mov eax, dword ptr ds:
inc eax   

mov dword ptr ds:, eax
```

经过无尽的调试（在判断插入节点个数那里下断点，每插入一个节点，就把0x00000001400073B0那里的数据提取出来，进行比对）就会发现，程序是把输入的flag按照Treap的特性存放在了00000001400073C0处，这里是一个长度为33的结构体数组，(第一个数组全是0，因为序号是从1开始的，序号是0表示为空，有效的就是后面32个数组)每个单元的大小是0X1C




```cpp
struct tree_node{
   0x00 DWORD 左孩子;               //0表示空
   0x04 DWORD 右孩子;
   0X08 DWORD enc_input;      //加密后的每一个字符
   0X0C DWORD 叶子个数;    //假设把此节点当做根节点，整个Tree的叶子个数
   0X10 DWORD 随机数;            //优先级
   0X14 DWORD1;               //这个没搞懂啥意思
   0X18 DWORD input;         //输入的flag的每一个字符
}
```

在00000001400073B0处存放着根节点，00000001400073B4, 00000001400073B8处存着当前树的所有叶子个数

输入`SUSCTF{01234567890122345679abcdefghijkl}`, 然后根据00000001400073C0处的数据画出自己输入的假的flag构造的二叉树

提取出00000001400073C0处有效的32个数组

```
00000000 00000013 000000F1 00000006 2109B018 00000001 00000030
0000000F 00000009 000000D9 00000018 11BB2E13 00000001 00000031
00000000 00000000 000000F7 00000001 5D64CABB 00000001 00000032
00000000 0000000B 0000009A 00000002 302F1C09 00000001 00000033
00000004 00000015 000000AF 00000020 02E78C02 00000001 00000034
00000000 00000000 000000B4 00000001 2A28B165 00000001 00000035
00000000 00000000 000000BB 00000001 6F018185 00000001 00000036
00000000 00000006 000000B1 00000002 1CF5A8D1 00000001 00000037
00000016 00000011 000000EE 0000000E 1532F368 00000001 00000038
00000000 00000000 000000F4 00000001 42367652 00000001 00000039
00000000 00000000 000000A0 00000001 7B50B157 00000001 00000030
00000007 00000000 000000C2 00000002 244FA941 00000001 00000031
00000000 00000000 000000D7 00000001 48CB7CCC 00000001 00000032
0000000C 00000014 000000CF 00000004 1950F130 00000001 00000032
00000008 00000012 000000B6 00000009 15561F1B 00000001 00000033
00000000 0000000A 000000F3 00000002 29F35383 00000001 00000034
00000001 00000020 00000101 0000000A 204017F9 00000001 00000035
0000000E 0000000D 000000D5 00000006 15686F99 00000001 00000036
00000010 0000001A 000000F6 00000005 274AD200 00000001 00000037
00000000 00000000 000000D3 00000001 650387E1 00000001 00000039
0000001B 00000019 00000130 0000001D 04C2B77D 00000001 00000061
00000017 00000000 000000E7 00000003 278451D6 00000001 00000062
00000000 00000018 000000DE 00000002 3F0318C0 00000001 00000063
00000000 00000000 000000E3 00000001 78E83012 00000001 00000064
00000000 0000001D 0000013D 00000002 0D00C42A 00000001 00000065
00000003 00000000 000000FD 00000002 537C7E9D 00000001 00000066
00000002 0000001E 0000012A 0000001A 0F8680AF 00000001 00000067
00000000 00000000 00000103 00000001 72A27C9F 00000001 00000068
00000000 00000000 0000014D 00000001 5C4909AF 00000001 00000069
00000000 00000000 0000012C 00000001 2FE974B3 00000001 0000006A
00000000 00000000 00000125 00000001 351BEA91 00000001 0000006B
0000001C 0000001F 00000123 00000003 2ADAD13B 00000001 0000006C
```



一点点调试就会发现这采用了后序遍历的方式去遍历这个二叉树，

```python
......
0000000140010DE3 | 48:6305 D265FFFF                  | movsxd rax,dword ptr ds:| 0x00000001400073BC 是比对字符的个数，估计到了32的时候就是成功的位置
000000014001C1ED | 48:8D0D 4C9EFEFF                  | lea rcx,qword ptr ds:   | 140006040存放着后续遍历的真正的数据，需要找到索引才能还原      
   ......
0000000140014ED1 | 394424 2C                         | cmp dword ptr ss:,eax                           | 最终比较
      ......

```

将140006040处的数据提取出来，构造二叉树

```python
encs = [0x00A2, 0x00AF, 0x009D, 0x00B7, 0x00D2, 0x00CB, 0x00C7, 0x00C6, 0x00B0, 0x00D5, 0x00DA, 0x00E3, 0x00E6, 0x00E8, 0x00E9, 0x00F3,
      0x00F4, 0x00EF, 0x00EE, 0x00F7, 0x00F9, 0x00FF, 0x0101, 0x00F5, 0x0109, 0x011F, 0x011A, 0x0146, 0x0124, 0x010F, 0x0106, 0x00DF]
```


flag--->加密-->按照顺序插入-->得到了这个二叉树，因此咱们现在只需要知道现在这个二叉树每个节点的索引，然后解密就可以得到原始的flag

在调试的过程中发现，如果当前比较的这个节点不是叶子节点的话，会对本节点和左孩子节点 ，本节点和右孩子节点 的关系进行验证

```python
# 比较的汇编代码在这
000000014001B7B0 | 48:3914C1                         | cmp qword ptr ds:,rdx       | 比较右孩子
      ......
0000000140015993 | 48:3914C1                         | cmp qword ptr ds:,rdx       | 左孩子比较
      ......
```

这就是我们的突破口

1. 00000001400060C0 存放着本节点和左孩子节点的关系

2. 00000001400061C0 存放着本节点和右孩子之间的关系

这2个数据怎么用呢？调试发现是 `孩子节点序号 *0X17 + 本节点input = 关系s[本节点序号]`因此我们要得到孩子节点序号的话，需要知道本节点的Input +本节点的序号，然后用本节点序号去索引左孩子或右孩子关系s，

```python
def get_child_xuhao(node_c, gx):
    # node_c： 本节点字符
    # gx: 关系
    # 孩子节点序号 * 0x17+ 本节点input = gx
    if (gx - node_c) % 0x17 == 0:
      return int((gx - node_c) / 0x17)
    return None
```

因为Treap有堆的性质，根节点的优先级是最小的，因此我们提取出所有的优先级，对他进行排序

```python
c = [0x2109B018, 0x11BB2E13, 0x5D64CABB, 0x302F1C09, 0x02E78C02, 0x2A28B165, 0x6F018185, 0x1CF5A8D1, 0x1532F368, 0x42367652, 0x7B50B157, 0x244FA941, 0x48CB7CCC, 0x1950F130, 0x15561F1B, 0x29F35383,
   0x204017F9, 0x15686F99, 0x274AD200, 0x650387E1, 0x04C2B77D, 0x278451D6, 0x3F0318C0, 0x78E83012, 0x0D00C42A, 0x537C7E9D, 0x0F8680AF, 0x72A27C9F, 0x5C4909AF, 0x2FE974B3, 0x351BEA91, 0x2ADAD13B]
yxj = [] for i in range(len(c))]


def sort_(elem):
    return elem


yxj.sort(key=sort_)
print(yxj)
# [, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ]
```

可以发现，索引是4，即序号是5的时候最小，即223的序号是5，根据5(序号)和223(enc_input)进行解密就可以得到本节点字符 'd'

```python
def get_real_c(_index, enc_input):
    # 通过索引和enc_input得到原始input
    tmp = enc_input - 97 - key - _index
    return tmp

get_real_c(4, 223)
# 100 -->chr(100) = 'd'
```

然后写脚本递归就可以得到所有节点的字符

```python
# [本节点，左孩子，右孩子，序号，flag]
# 构造二叉树
treap = [
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
   
]

treap_dict = {}
for i in range(32):
    treap_dict] = treap
key = [0x60, 0x46, 0x62, 0x03, 0x16, 0x19, 0x1E, 0x12, 0x4D, 0x51, 0x05, 0x25, 0x38, 0x2F, 0x14, 0x4F,
       0x5B, 0x2D, 0x4C, 0x26, 0x5A, 0x0F, 0x04, 0x07, 0x5F, 0x1D, 0x48, 0x1F, 0x67, 0x44, 0x3B, 0x37]
encs = [0x00A2, 0x00AF, 0x009D, 0x00B7, 0x00D2, 0x00CB, 0x00C7, 0x00C6, 0x00B0, 0x00D5, 0x00DA, 0x00E3, 0x00E6, 0x00E8, 0x00E9, 0x00F3,
      0x00F4, 0x00EF, 0x00EE, 0x00F7, 0x00F9, 0x00FF, 0x0101, 0x00F5, 0x0109, 0x011F, 0x011A, 0x0146, 0x0124, 0x010F, 0x0106, 0x00DF]


# 节点和右孩子之间的关系
gxs_right = [0x00AC, 0x00FD, 0x0247, 0x0115, 0x00D4, 0x02B5, 0x01FC, 0x028B, 0x014A, 0x004C, 0x008E, 0x00E9, 0x0055, 0x012C, 0x00F5,
             0x00E3, 0x0081, 0x02E2, 0x01A8, 0x0117, 0x0152, 0x0101, 0x003A, 0x01D0, 0x00A8, 0x00CC, 0x0149, 0x0137, 0x0300, 0x01EC, 0x0276, 0x0247]

# 节点和左孩子之间的关系
gxs_left = [0x00A8, 0x0131, 0x0113, 0x0047, 0x009E, 0x003B, 0x003A, 0x00BF, 0x0092, 0x00F0, 0x0174, 0x00C3, 0x0289, 0x0104, 0x0260,
            0x004D, 0x02FB, 0x009E, 0x0191, 0x0158, 0x007D, 0x004A, 0x01E9, 0x0101, 0x00D0, 0x00FC, 0x0070, 0x011F, 0x0345, 0x0162, 0x02A4, 0x0092]


def get_child_xuhao(node_c, gx):
    # node_c： 本节点字符
    # gx: 关系
    # 孩子节点序号 * 0x17+ 本节点input = gx
    if (gx - node_c) % 0x17 == 0:
      return int((gx - node_c) / 0x17)
    return None


def get_real_c(_index, enc_input):
    # 通过索引和enc_input得到原始input
    tmp = enc_input - 97 - key - _index
    return tmp


def treap_traverse(_root):
    if _root == 0:
      return
    node_c = get_real_c(treap_dict - 1, _root)
    idx = encs.index(_root)   # 得到后续遍历后的数组中_root的索引
    # 如果左节点不为空，更新左节点的数据
    left_root = treap_dict
    right_root = treap_dict
    if left_root != 0:
      left_xh = get_child_xuhao(node_c, gxs_left)
      left_c = get_real_c(left_xh - 1, treap_dict)      # 左孩子
      treap_dict = left_xh
      treap_dict = left_c
      treap_traverse(left_root)
    if right_root != 0:
      right_xh = get_child_xuhao(node_c, gxs_right)
      right_c = get_real_c(right_xh - 1, treap_dict)   # 右孩子
      treap_dict = right_xh
      treap_dict = right_c
      treap_traverse(right_root)


treap_traverse(223)
flag = []
for _key, value in treap_dict.items():
    flag.append(, value])

flag.sort()
flag = for x in flag]
print("SUSCTF{" + "".join(map(chr, flag)) + "}")
# SUSCTF{8226d8a68d25d8f03be17c4d7027b29c}
```

flag为：SUSCTF{8226d8a68d25d8f03be17c4d7027b29c}

zsky 发表于 2022-3-3 12:59

a4849148 发表于 2022-3-3 12:52
永久禁言封IP

？？？？?

Hmily 发表于 2022-3-4 14:06

zsky 发表于 2022-3-3 17:03
最下面那张截图请忽略，，不知道为啥删不掉，可能过几天缓存没了，这个截图就没了

已经修复，之前这块修复一个安全问题导致的兼容问题。

shuwangpeng 发表于 2022-3-3 11:17

看不太懂。。。

over7700 发表于 2022-3-3 14:47

楼主有原题吗

zsky 发表于 2022-3-3 14:58

over7700 发表于 2022-3-3 14:47
楼主有原题吗

去攻防世界-竞赛-SUSCTF下载即可

a254156435 发表于 2022-3-3 16:43

好复杂啊

jessezzzz 发表于 2022-3-3 16:44

感觉很厉害

yaoxixixi 发表于 2022-3-3 16:47

好wp！！！！！！

zsky 发表于 2022-3-3 17:03

最下面那张截图请忽略，，不知道为啥删不掉，可能过几天缓存没了，这个截图就没了

heng179 发表于 2022-3-3 17:59

查看完整版本: 2022_SUSCTF_RE_tttree题解