First Fit

Reading time: 3 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: koszy niesortowanych i fastbins.

Unsorted Bins

Kiedy zwalniasz kawałek pamięci, który nie jest szybkim kawałkiem, trafia on do kosza niesortowanego. 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 niesortowany od tyłu (do "ogona"), aby znaleźć kawałek wystarczająco duży. Jeśli kawałek z kosza niesortowanego 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), zwalniasz a i ponownie żądasz 250 bajtów (c).
• Kiedy zwalniasz a, trafia on do kosza niesortowanego.
• 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 danymi z 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.

Przykład:

• Alokujesz cztery kawałki po 20 bajtów każdy (a, b, c, d).
• Kiedy je zwolnisz w dowolnej kolejności, zwolnione kawałki są dodawane do głowy fastbina.
• Jeśli następnie poprosisz o kawałek 20-bajtowy, alokator zwróci najnowszy zwolniony kawałek z głowy fastbina.

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

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(<size>) 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 koszyka (lub tcache).
• Następnie stwórz inną notatkę (note2) o rozmiarze treś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ć Use-After-Free 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 i 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 konieczne jest zapisanie 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 ma 4 wewnątrz.