Unsorted Bin Attack

Reading time: 12 minutes

Grundlegende Informationen

Für mehr Informationen darüber, was ein unsorted bin ist, siehe diese Seite:

Bins & Memory Allocations

Unsorted lists sind in der Lage, die Adresse von unsorted_chunks (av) in das bk-Feld des Chunks zu schreiben. Daher, wenn ein Angreifer die Adresse des bk-Pointers in einem Chunk innerhalb des unsorted bin ändern kann, könnte er diese Adresse an eine beliebige Adresse schreiben, was hilfreich sein kann, um Glibc-Adressen zu leaken oder einige Schutzmechanismen zu umgehen.

Kurz gesagt erlaubt dieser Angriff, eine große Zahl an einer beliebigen Adresse zu setzen. Diese große Zahl ist eine Adresse, die eine Heap-Adresse oder eine Glibc-Adresse sein kann. Ein traditionelles Ziel war global_max_fast, um fast bin bins mit größeren Größen zu erlauben (und vom unsorted bin attack zu einem fast bin attack überzugehen).

• Moderne Anmerkung (glibc ≥ 2.39): global_max_fast wurde zu einer 8‑Bit-Globalvariablen. Das blinde Schreiben eines Pointers dorthin via unsorted‑bin write überschreibt angrenzende libc-Daten und erhöht das fastbin-Limit nicht mehr zuverlässig. Bevorzuge andere Ziele oder andere Primitive gegen glibc 2.39+. Siehe "Moderne Einschränkungen" weiter unten und erwäge die Kombination mit anderen Techniken wie einem large bin attack oder einem fast bin attack, sobald du ein stabiles Primitive hast.

Der Code von guyinatuxedo erklärt das sehr gut; wenn man jedoch die mallocs so ändert, dass sie Speicher groß genug allozieren, um nicht in einen Tcache zu fallen, sieht man, dass der zuvor erwähnte Fehler auftritt und diese Technik verhindert: malloc(): unsorted double linked list corrupted

Wie der Schreibvorgang tatsächlich abläuft

• Der unsorted‑bin write wird bei free ausgelöst, wenn der freigegebene Chunk am Kopf der unsorted list eingefügt wird.
• Während der Einfügung führt der Allocator aus: bck = unsorted_chunks(av); fwd = bck->fd; victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;
• Wenn du victim->bk auf (mchunkptr)(TARGET - 0x10) setzen kannst bevor du free(victim) aufrufst, wird die letzte Anweisung die Schreiboperation ausführen: *(TARGET) = victim.
• Später, wenn der Allocator das unsorted bin verarbeitet, werden Integritätsprüfungen (unter anderem) verifizieren, dass bck->fd == victim und victim->fd == unsorted_chunks(av) bevor unlinking erfolgt. Da die Einfügung bereits victim in bck->fd (unser TARGET) geschrieben hat, können diese Checks erfüllt sein, wenn der Write erfolgreich war.

Moderne Einschränkungen (glibc ≥ 2.33)

Um unsorted‑bin Writes auf aktuellen glibc zuverlässig zu verwenden:

• Tcache-Interferenz: Für Größen, die in den tcache fallen, werden frees dorthin umgeleitet und berühren nicht das unsorted bin. Entweder
• mache Anfragen mit Größen > MAX_TCACHE_SIZE (≥ 0x410 auf 64‑Bit standardmäßig), oder
• fülle die entsprechende tcache-Bin (7 Einträge), sodass zusätzliche frees die global bins erreichen, oder
• wenn die Umgebung kontrollierbar ist, deaktiviere tcache (z. B. GLIBC_TUNABLES glibc.malloc.tcache_count=0).
• Integritätsprüfungen auf der unsorted list: auf dem nächsten Allocations-Pfad, der das unsorted bin prüft, kontrolliert glibc (vereinfacht):
• bck->fd == victim und victim->fd == unsorted_chunks(av); andernfalls bricht es mit malloc(): unsorted double linked list corrupted ab.
• Das bedeutet, dass die Adresse, die du targetest, zwei Writes tolerieren muss: zuerst *(TARGET) = victim zur Free‑Zeit; später, wenn der Chunk entfernt wird, *(TARGET) = unsorted_chunks(av) (der Allocator schreibt bck->fd zurück auf den Bin‑Kopf). Wähle Ziele, bei denen das Erzwingen eines großen Nicht‑Null‑Wertes nützlich ist.
• Typische stabile Ziele in modernen Exploits:
• Applikations- oder globaler Zustand, der "große" Werte als Flags/Limits behandelt.
• Indirekte Primitive (z. B. Vorbereitung für einen nachfolgenden [fast bin attack](Fast Bin Attack) oder um einen späteren write‑what‑where zu pivotieren).
• Vermeide __malloc_hook/__free_hook in neuem glibc: sie wurden in 2.34 entfernt. Vermeide global_max_fast auf ≥ 2.39 (siehe vorherige Anmerkung).
• Zu global_max_fast auf neueren glibc:
• Auf glibc 2.39+ ist global_max_fast ein 8‑Bit‑Global. Der klassische Trick, einen Heap‑Pointer dorthin zu schreiben (um fastbins zu vergrößern), funktioniert nicht mehr sauber und wird wahrscheinlich angrenzenden Allocator‑Zustand korruptieren. Bevorzuge andere Strategien.

Minimales Exploit‑Rezept (moderner glibc)

Ziel: einen einzelnen arbiträren Write eines Heap‑Pointers an eine beliebige Adresse mittels des unsorted‑bin Insertions‑Primitives erreichen, ohne das Programm abstürzen zu lassen.

• Layout/Grooming
• Alloziere A, B, C mit Größen, die groß genug sind, um tcache zu umgehen (z. B. 0x5000). C verhindert Konsolidierung mit dem top chunk.
• Korruption
• Overflow von A in Bs Chunk‑Header, um B->bk = (mchunkptr)(TARGET - 0x10) zu setzen.
• Auslösen
• free(B). Zur Einfügezeit führt der Allocator bck->fd = B aus; daher wird *(TARGET) = B.
• Fortsetzung
• Wenn du weiter alloziieren willst und das Programm das unsorted bin verwendet, erwarte, dass der Allocator später *(TARGET) = unsorted_chunks(av) setzt. Beide Werte sind typischerweise groß und können ausreichen, um Größen-/Limit‑Semantiken in Zielen zu ändern, die nur auf "groß" prüfen.

Pseudocode‑Skelett:

// 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

This is actually a very basic concept. The chunks in the unsorted bin are going to have pointers. The first chunk in the unsorted bin will actually have the fd and the bk links pointing to a part of the main arena (Glibc).
Therefore, if you can put a chunk inside a unsorted bin and read it (use after free) or allocate it again without overwriting at least 1 of the pointers to then read it, you can have a Glibc info leak.

A similar attack used in this writeup, was to abuse a 4 chunks structure (A, B, C and D - D is only to prevent consolidation with top chunk) so a null byte overflow in B was used to make C indicate that B was unused. Also, in B the prev_size data was modified so the size instead of being the size of B was A+B.
Then C was deallocated, and consolidated with A+B (but B was still in used). A new chunk of size A was allocated and then the libc leaked addresses was written into B from where they were leaked.

Referenzen & Weitere Beispiele

• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#hitcon-training-lab14-magic-heap
• Das Ziel ist, eine globale Variable mit einem Wert größer als 4869 zu überschreiben, damit es möglich ist, die Flag zu bekommen, und PIE ist nicht aktiviert.
• Es ist möglich, Chunks beliebiger Größen zu erzeugen und es gibt einen Heap-Overflow mit der gewünschten Größe.
• Der Angriff beginnt mit dem Erstellen von 3 Chunks: chunk0 zum Ausnutzen des Overflows, chunk1, das überlaufen wird, und chunk2, damit der top chunk nicht die vorherigen konsolidiert.
• Danach wird chunk1 freed und chunk0 so überlaufen, dass das bk-Pointer von chunk1 zeigt auf: bk = magic - 0x10
• Dann wird chunk3 mit derselben Größe wie chunk1 alloziiert, was den unsorted bin attack auslöst und den Wert der globalen Variable verändert, wodurch es möglich wird, die Flag zu bekommen.
• https://guyinatuxedo.github.io/31-unsortedbin_attack/0ctf16_zerostorage/index.html
• Die merge-Funktion ist verwundbar, weil, wenn beide übergebenen Indizes gleich sind, sie ein realloc darauf macht und es dann freed, aber dabei einen Pointer auf diesen freed Bereich zurückgibt, der weiterverwendet werden kann.
• Daher werden 2 Chunks erstellt: chunk0, das mit sich selbst gemerged wird, und chunk1, um eine Konsolidierung mit dem top chunk zu verhindern. Dann wird die merge-Funktion mit chunk0 zweimal aufgerufen, was zu einem use after free führt.
• Danach wird die view-Funktion mit Index 2 aufgerufen (das ist der Index des use after free Chunks), welche eine libc Adresse leaked.
• Da das Binary Protections hat, nur mallocs größer als global_max_fast zu erlauben, sodass kein fastbin verwendet wird, wird ein unsorted bin attack benutzt, um die globale Variable global_max_fast zu überschreiben.
• Danach ist es möglich, die edit-Funktion mit Index 2 (dem use after free Pointer) aufzurufen und den bk-Pointer zu überschreiben, sodass er auf p64(global_max_fast-0x10) zeigt. Dann erzeugt man einen neuen Chunk, der die zuvor kompromittierte free-Adresse (0x20) verwendet und so den unsorted bin attack auslöst, der global_max_fast mit einem sehr großen Wert überschreibt, wodurch es nun möglich ist, Chunks in fast bins zu erstellen.
• Jetzt wird ein fast bin attack durchgeführt:
• Zuerst wird entdeckt, dass es möglich ist, mit fast Chunks der Größe 200 an der Stelle von __free_hook zu arbeiten:

• 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

• Wenn es gelingt, einen fast Chunk der Größe 0x200 an dieser Stelle zu bekommen, wird es möglich sein, einen Funktionspointer zu überschreiben, der ausgeführt wird.
• Dafür wird ein neuer Chunk der Größe 0xfc erstellt und die merge-Funktion mit diesem Pointer zweimal aufgerufen; so erhält man einen Pointer auf einen freed Chunk der Größe 0xfc*2 = 0x1f8 im fast bin.
• Dann wird die edit-Funktion auf diesem Chunk aufgerufen, um die fd-Adresse dieses fast bins zu ändern, sodass sie auf das vorherige __free_hook zeigt.
• Danach wird ein Chunk mit Größe 0x1f8 alloziiert, um aus dem fast bin den vorherigen nutzlosen Chunk zu bekommen; ein weiterer Chunk der Größe 0x1f8 wird erstellt, um einen fast bin Chunk in __free_hook zu erhalten, der mit der Adresse der system-Funktion überschrieben wird.
• Und schließlich wird ein Chunk, das den String /bin/sh\x00 enthält, per delete freed, wodurch die __free_hook-Funktion aufgerufen wird, die nun auf system zeigt und /bin/sh\x00 als Parameter übergeben bekommt.
• CTF https://guyinatuxedo.github.io/33-custom_misc_heap/csaw19_traveller/index.html
• Ein weiteres Beispiel, wie ein 1B-Overflow genutzt wird, um Chunks im unsorted bin zu konsolidieren und einen libc info leak zu bekommen und anschließend einen fast bin attack durchzuführen, um malloc hook mit einem one gadget zu überschreiben.
• Robot Factory. BlackHat MEA CTF 2022
• Wir können nur Chunks der Größe größer als 0x100 alloziieren.
• Überschreibe global_max_fast mittels eines Unsorted Bin attack (funktioniert 1/16 mal wegen ASLR, weil wir 12 Bits ändern müssen, aber 16 Bits ändern).
• Fast Bin attack, um ein globales Array von Chunks zu modifizieren. Das gibt ein beliebiges read/write-Primitive, was erlaubt, die GOT zu ändern und eine Funktion auf system zu setzen.

References

• Glibc malloc unsorted-bin integrity checks (example in 2.33 source): https://elixir.bootlin.com/glibc/glibc-2.33/source/malloc/malloc.c
• global_max_fast and related definitions in modern glibc (2.39): https://elixir.bootlin.com/glibc/glibc-2.39/source/malloc/malloc.c