Unsorted Bin Attack

Reading time: 18 minutes

基本情報

Unsorted bin が何かについては次のページを参照してください：

Bins & Memory Allocations

Unsorted lists はチャンクの bk アドレスに unsorted_chunks (av) のアドレスを書き込むことができます。したがって、攻撃者が unsorted bin 内のチャンクの bk ポインタのアドレスを変更できる場合、任意のアドレスにそのアドレスを書き込むことができ、Glibc addresses を 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.

書き込みが実際にどのように発生するか

• unsorted‑bin 書き込みは、解放時に解放されたチャンクが unsorted list の先頭に挿入されるときにトリガーされます。
• 挿入中、アロケータは bck = unsorted_chunks(av); fwd = bck->fd; victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim; を実行します。
• free(victim) を呼ぶ前に victim->bk を (mchunkptr)(TARGET - 0x10) に設定できれば、最後の文が書き込みを行います：*(TARGET) = victim。
• 後で、アロケータが unsorted bin を処理する際に、整合性チェックは（他のチェックとともに）bck->fd == victim と victim->fd == unsorted_chunks(av) を検証し、そうでなければ malloc(): unsorted double linked list corrupted で中止します。挿入操作は既に bck->fd（我々の TARGET）に victim を書き込んでいるため、書き込みが成功していればこれらのチェックは満たされ得ます。

モダンな制約 (glibc ≥ 2.33)

現行の glibc で unsorted‑bin 書き込みを安定して利用するには：

• 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 list に対する整合性チェック: 次に unsorted bin を検査する割り当てパスで、glibc は（単純化して）次をチェックします：

  • bck->fd == victim と victim->fd == unsorted_chunks(av)；そうでなければ malloc(): unsorted double linked list corrupted で中止。

• これはターゲットとするアドレスが二回の書き込みを許容する必要があることを意味します：まず free 時に *(TARGET) = victim、後でチャンクが取り除かれる際に *(TARGET) = unsorted_chunks(av)（アロケータは bck->fd をビンの先頭に書き戻す）。単に大きな非ゼロ値を強制するだけで有用なターゲットを選んでください。

• 現代のエクスプロイトでの典型的な安定ターゲット：

  • 「大きな」値をフラグや制限値として扱うアプリケーションやグローバルな状態。
  • 間接的なプリミティブ（例: その後の [fast bin attack](Fast Bin Attack) の準備や後続の write‑what‑where をピボットするため）。
  • 新しい glibc では __malloc_hook/__free_hook が 2.34 で削除されているため避ける。global_max_fast は ≥ 2.39 では避ける（次の注を参照）。

• global_max_fast に関して最近の glibc では

  • glibc 2.39+ では global_max_fast は 8 ビットのグローバルになりました。ここにヒープポインタを書き込んで fastbins を拡大するという古典的トリックはもはやきれいに動作せず、隣接するアロケータ状態を破壊する可能性があります。別の戦略を優先してください。

最小限のエクスプロイト手順（モダン glibc）

目的: unsorted‑bin 挿入プリミティブを使って、クラッシュさせずにヒープポインタを任意のアドレスへ単一回書き込むことを達成する。

• レイアウト／グルーミング
  • Tcache を回避するのに十分大きなサイズで A, B, C を割り当てる（例: 0x5000）。C は top チャンクとの結合を防ぎます。
• 損傷（Corruption）
  • A から B のチャンクヘッダへオーバーフローして B->bk = (mchunkptr)(TARGET - 0x10) を設定する。
• トリガ
  • free(B)。挿入時にアロケータは bck->fd = B を実行し、したがって *(TARGET) = B が行われます。
• 続行
  • もし割り当てを続ける予定でプログラムが unsorted bin を使用するなら、後でアロケータが *(TARGET) = unsorted_chunks(av) を設定することを予期してください。両方の値は通常大きく、単に「大きい」ことをチェックするターゲットのサイズ／制限の意味を変えるのに十分であることが多いです。

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つのポインタを上書きせずに再度 allocate してから読み取ることができれば、Glibc info leak を得られます。

A similar attack used in this writeup、は 4 チャンク構造（A, B, C, D — D は top chunk と consolidate するのを防ぐためだけ）を悪用するもので、B の null byte overflow を使って C が B を未使用と示すようにしました。さらに B の prev_size を改変して、サイズが B のサイズではなく A+B になるようにしました。
その後 C を deallocate して A+B と consolidate（B はまだ in use）されます。サイズ A の新しいチャンクを allocate し、そこから libc のリークしたアドレスを B に書き込んでリークを得ました。

参考と他の例

• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#hitcon-training-lab14-magic-heap
  • 目的はグローバル変数を 4869 より大きい値で上書きして flag を取得することで、PIE は有効でない。
  • 任意サイズのチャンクを生成でき、目的のサイズでの heap overflow が存在する。
  • 攻撃は 3 つのチャンクを作成するところから始まる: overflow を悪用する chunk0、overflow される chunk1、そして top chunk が前のものと consolidate しないようにする chunk2。
  • その後 chunk1 を free し、chunk0 を overflow して chunk1 の bk ポインタが指すようにする: bk = magic - 0x10
  • その後 chunk1 と同サイズの chunk3 を allocate すると unsorted bin attack が発動し、グローバル変数の値が変更されて flag を取得できるようになる。
• https://guyinatuxedo.github.io/31-unsortedbin_attack/0ctf16_zerostorage/index.html
  • merge 関数は、渡した両方のインデックスが同じ場合にその領域を realloc してから free し、free した領域へのポインタを返してしまうため脆弱である。
  • したがって、2 つのチャンクを作成する: 自分自身とマージされる chunk0 と、top chunk と consolidate しないようにする chunk1。次に、merge function を chunk0 で 2 回呼ぶと use after free が発生する。
  • その後 index 2（use after free チャンクのインデックス）で view を呼ぶと、libc アドレスが leak する。
  • バイナリには global_max_fast より大きいサイズしか malloc できない保護があるため fastbin は使われず、unsorted bin attack を使ってグローバル変数 global_max_fast を上書きする。
  • 次に、index 2（use after free ポインタ）で edit を呼び、bk を p64(global_max_fast-0x10) を指すように上書きする。すると、新しいチャンクを作ることで以前に改竄した free アドレス (0x20) が使われ、unsorted bin attack をトリガーして 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 の free チャンクへのポインタが得られる。
- 次に、そのチャンクで 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
  • 1B overflow を悪用して unsorted bin にチャンクを consolidate し libc infoleak を得て、その後 fast bin attack を行い malloc hook を one gadget アドレスで上書きする別の例。
• Robot Factory. BlackHat MEA CTF 2022
  • 0x100 より大きいサイズのチャンクしか allocate できない。
  • Unsorted Bin attack を使って global_max_fast を上書きする（ASLR のため成功率は 1/16。12 ビットを変更する必要があるが実際には 16 ビットを変更しなければならないため）。
  • Fast Bin attack でグローバルなチャンク配列を改変する。これにより任意の read/write プリミティブが得られ、GOT を変更して関数を system を指すようにできる。

参考

• Glibc malloc unsorted-bin の整合性チェック（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