Unsorted Bin Attack

Reading time: 17 minutes

基本情報

For more information about what is an unsorted bin check this page:

Bins & Memory Allocations

unsorted リストはチャンクの bk アドレスに unsorted_chunks (av) のアドレスを書き込むことができます。したがって、攻撃者がunsorted bin内のチャンクの bk ポインタのアドレスを変更できるのであれば、任意のアドレスにそのアドレスを書き込むことができ、Glibc のアドレスを leak したり防御を回避したりするのに役立ちます。

基本的に、この攻撃では任意のアドレスに大きな数値を設定できます。 この大きな数値はアドレスであり、heap アドレスや Glibc アドレスになり得ます。伝統的なターゲットは global_max_fast で、fast bin を大きなサイズで作成できるようにし（unsorted bin attack から fast bin attack へ移行するため）でした。

• Modern note (glibc ≥ 2.39): global_max_fast became an 8‑bit global. Blindly writing a pointer there via an unsorted-bin write will clobber adjacent libc data and will not reliably raise the fastbin limit anymore. Prefer other targets or other primitives when running against glibc 2.39+. See "Modern constraints" below and consider combining with other techniques like a large bin attack or a fast bin attack once you have a stable primitive.

The code from guyinatuxedo explains it very well, although if you modify the mallocs to allocate memory big enough so don't end in a Tcache you can see that the previously mentioned error appears preventing this technique: malloc(): unsorted double linked list corrupted

書き込みが実際に行われる仕組み

• The unsorted-bin write is triggered on free when the freed chunk is inserted at the head of the unsorted list.
• During insertion, the allocator performs bck = unsorted_chunks(av); fwd = bck->fd; victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;
• If you can set victim->bk to (mchunkptr)(TARGET - 0x10) before calling free(victim), the final statement will perform the write: *(TARGET) = victim.
• Later, when the allocator processes the unsorted bin, integrity checks will verify (among other things) that bck->fd == victim and victim->fd == unsorted_chunks(av) before unlinking. Because the insertion already wrote victim into bck->fd (our TARGET), these checks can be satisfied if the write succeeded.

現代の制約 (glibc ≥ 2.33)

To use unsorted‑bin writes reliably on current glibc:

• Tcache の干渉: サイズが tcache に入る場合、free はそちらに流され unsorted bin に触れません。対策としては次のいずれか：
  • MAX_TCACHE_SIZE より大きいサイズのリクエストを行う（64bit のデフォルトでは ≥ 0x410）、または
  • 該当する tcache bin を満たして（7 エントリ）追加の free が global bins に到達するようにする、または
  • 環境を制御可能であれば tcache を無効化する（例: GLIBC_TUNABLES glibc.malloc.tcache_count=0）。
• unsorted リストの整合性チェック: unsorted bin を調べる次の allocation パスで、glibc は（簡略化して）次をチェックします:
  • bck->fd == victim and victim->fd == unsorted_chunks(av); otherwise it aborts with malloc(): unsorted double linked list corrupted.
• つまり、ターゲットとするアドレスは2回の書き込みを受け入れられなければなりません：最初は free 時に *(TARGET) = victim、後はチャンクが取り除かれる際に *(TARGET) = unsorted_chunks(av)（allocator が bck->fd をビンヘッドに書き戻す）となります。単純に大きな非ゼロ値を設定するだけで役に立つターゲットを選んでください。
• 現代のエクスプロイトでの典型的で安定したターゲット
  • アプリケーションやグローバル状態で「large」な値をフラグや制限として扱うもの。
  • 間接的なプリミティブ（例：後続の [fast bin attack](Fast Bin Attack) の準備や後の write-what-where をピボットするための設定）。
  • 新しい glibc では __malloc_hook/__free_hook は 2.34 で削除されているため避けること。global_max_fast は ≥ 2.39 では避けてください（次の注を参照）。
• 最近の glibc における global_max_fast について
  • glibc 2.39+ では global_max_fast は 8 ビットのグローバルです。ヒープポインタを書き込んで fastbins を拡張するという古典的手口はもはやきれいに動作せず、隣接するアロケータ状態を破壊する可能性があります。別の戦略を推奨します。

最小限のエクスプロイト手順（現代の glibc）

Goal: achieve a single arbitrary write of a heap pointer to an arbitrary address using the unsorted‑bin insertion primitive, without crashing.

• レイアウト/準備
  • A, B, C を tcache を回避するのに十分なサイズで割り当てする（例: 0x5000）。C は top chunk と合体するのを防ぎます。
• 破壊（Corruption）
  • A から B のチャンクヘッダへ overflow して B->bk = (mchunkptr)(TARGET - 0x10) を設定する。
• トリガー
  • free(B)。挿入時に allocator は bck->fd = B を実行し、したがって *(TARGET) = B となります。
• 続行
  • 割り当てを続ける予定でプログラムが unsorted bin を使用する場合、後で allocator が *(TARGET) = unsorted_chunks(av) を設定することを想定してください。両方の値は通常大きく、単に「big」かどうかだけをチェックするターゲットではサイズ/制限の意味を変えるのに十分な場合があります。

Pseudocode skeleton:

// 64-bit glibc 2.35–2.38 style layout (tcache bypass via large sizes)
void *A = malloc(0x5000);
void *B = malloc(0x5000);
void *C = malloc(0x5000); // guard

// overflow from A into B’s metadata (prev_size/size/.../bk). You must control B->bk.
*(size_t *)((char*)B - 0x8) = (size_t)(TARGET - 0x10); // write fake bk

free(B); // triggers *(TARGET) = B (unsorted-bin insertion write)

Unsorted Bin Infoleak Attack

これは非常に基本的な概念です。unsorted bin 内のチャンクはポインタを持ちます。unsorted bin の最初のチャンクは実際に fd と bk のリンクが main arena (Glibc) の一部を指している ことになります。
したがって、チャンクを unsorted bin に入れて読み取れる（use after free）か、少なくとも1つのポインタを上書きしないまま再度割り当ててから読み取ることができれば、Glibc info leak を得ることができます。

A similar attack used in this writeup、は4チャンク構成（A, B, C, D - Dはtop chunkとのconsolidationを防ぐためだけ）を悪用するもので、BのnullバイトオーバーフローによってCがBを未使用と示すようにし、さらにBのprev_sizeを変更してサイズがBのサイズではなくA+Bとなるようにしました。
その後CをfreeしてA+Bと統合され（ただしBはまだ使用中）、サイズAの新しいチャンクを割り当てると、libcのleakedアドレスがBに書き込まれ、そこからleakされました。

参考と他の例

• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#hitcon-training-lab14-magic-heap
  • 目的はグローバル変数を4869より大きい値で上書きしてflagを取得することで、PIEは有効ではない。
  • 任意のサイズのチャンクを生成でき、目的のサイズでヒープオーバーフローが存在する。
  • 攻撃は3つのチャンクを作成するところから始まる: chunk0（オーバーフローを悪用するため）、chunk1（オーバーフローされる対象）、chunk2（top chunkが前のものとconsolidateしないようにするため）。
  • その後chunk1をfreeし、chunk0をオーバーフローさせてchunk1のbkポインタが指す先を bk = magic - 0x10 にする。
  • 続いてchunk1と同じサイズでchunk3を割り当てるとunsorted bin attackが発動し、グローバル変数の値を変更してflagを得られるようにする。
• https://guyinatuxedo.github.io/31-unsortedbin_attack/0ctf16_zerostorage/index.html
  • merge関数は、同じインデックスが2回渡された場合にそれをreallocしてからfreeし、解放された領域のポインタを返してしまう脆弱性があるため脆弱である。
  • したがって、2つのチャンクが作成される: chunk0（自身とマージされる）と、top chunkとのconsolidationを防ぐためのchunk1。次に、merge関数をchunk0で2回呼ぶとuse after freeが発生する。
  • その後、インデックス2（use after freeチャンクのインデックス）で**view**関数を呼ぶと、libcアドレスがleakされる。
  • バイナリは global_max_fast より大きいサイズのみmallocを許可する保護があるためfastbinは使われず、unsorted bin attackを用いてグローバル変数 global_max_fast を上書きする。
  • 続けて、インデックス2（use after freeポインタ）でedit関数を呼び、bkポインタを p64(global_max_fast-0x10) を指すように上書きできる。そうして新しいチャンクを作ると、以前に改竄されたfreeアドレス(0x20) が使われ、unsorted bin attack が発動して global_max_fast を上書きする。これにより global_max_fast が非常に大きな値になり、fast bin のチャンクを作成できるようになる。
  • ここから fast bin attack が行われる:
    • まず、__free_hook の場所でサイズ200のfastチャンクを扱えることが発見される:

• gef➤  p &__free_hook
  

$1 = (void (**)(void *, const void *)) 0x7ff1e9e607a8 <__free_hook> gef➤ x/60gx 0x7ff1e9e607a8 - 0x59 0x7ff1e9e6074f: 0x0000000000000000 0x0000000000000200 0x7ff1e9e6075f: 0x0000000000000000 0x0000000000000000 0x7ff1e9e6076f <list_all_lock+15>: 0x0000000000000000 0x0000000000000000 0x7ff1e9e6077f <_IO_stdfile_2_lock+15>: 0x0000000000000000 0x0000000000000000

• この場所にサイズ0x200のfastチャンクを配置できれば、実行される関数ポインタを上書きすることが可能になる。
• そのために、サイズ 0xfc の新しいチャンクを作成し、そのポインタでmerge関数を2回呼ぶことで、fast binにサイズ 0xfc*2 = 0x1f8 の解放済みチャンクへのポインタを得る。
• そのチャンクでedit関数を呼んで、このfast binの fd を前の __free_hook を指すように変更する。
• 続いてサイズ 0x1f8 のチャンクを作ってfast binから前の無用なチャンクを取り出し、さらにもう一つサイズ 0x1f8 のチャンクを作ることで __free_hook の位置にあるfast binチャンクを取得し、これを system のアドレスで上書きする。
• 最後に /bin/sh\x00 を含むチャンクをdelete関数でfreeすると、__free_hook が system を指しているため /bin/sh\x00 を引数に system が実行される。
• CTF https://guyinatuxedo.github.io/33-custom_misc_heap/csaw19_traveller/index.html
  • 1バイトオーバーフローを悪用してチャンクをunsorted binで統合しlibcのinfoleakを得た後、fast bin attackでmalloc hookをone gadgetアドレスで上書きする別の例。
• Robot Factory. BlackHat MEA CTF 2022
  • チャンクは 0x100 より大きいサイズしか割り当てられない。
  • Unsorted Bin attack を使って global_max_fast を上書きする（ASLR のため成功確率は1/16、12ビットを変更する必要があるが16ビットを変更しなければならないため）。
  • Fast Bin attack によりグローバルなチャンク配列を改変する。これにより任意の read/write プリミティブを得られ、GOT を改変してある関数を system を指すようにできる。

参考

• Glibc malloc unsorted-bin integrity checks（2.33 のソースの例）: https://elixir.bootlin.com/glibc/glibc-2.33/source/malloc/malloc.c
• global_max_fast と関連定義（modern glibc 2.39）: https://elixir.bootlin.com/glibc/glibc-2.39/source/malloc/malloc.c