First Fit

Reading time: 8 minutes

First Fit

Wanneer jy geheue in 'n program met glibc vrymaak, word verskillende "bins" gebruik om die geheue stukke te bestuur. Hier is 'n vereenvoudigde verduideliking van twee algemene scenario's: ongesorteerde bins en vinnige bins.

Ongesorteerde Bins

Wanneer jy 'n geheue stuk vrymaak wat nie 'n vinnige stuk is nie, gaan dit na die ongesorteerde bin. Hierdie bin funksioneer soos 'n lys waar nuwe vrygemaakte stukke aan die voorkant (die "kop") bygevoeg word. Wanneer jy 'n nuwe stuk geheue aan vra, kyk die toewysingsprogram na die ongesorteerde bin vanaf die agterkant (die "stert") om 'n stuk te vind wat groot genoeg is. As 'n stuk uit die ongesorteerde bin groter is as wat jy nodig het, word dit gesplit, met die voorste deel wat teruggegee word en die oorblywende deel wat in die bin bly.

Voorbeeld:

• Jy toewys 300 bytes (a), dan 250 bytes (b), dan maak jy a vry en vra weer 250 bytes (c).
• Wanneer jy a vrymaak, gaan dit na die ongesorteerde bin.
• As jy dan weer 250 bytes vra, vind die toewysingsprogram a by die stert en split dit, terwyl dit die deel wat by jou versoek pas teruggee en die res in die bin hou.
• c sal na die vorige a wys en met die inhoud van a gevul wees.

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

Fastbins

Fastbins word gebruik vir klein geheue stukke. Anders as onsortering bins, voeg fastbins nuwe stukke by die kop, wat 'n laaste-in-eerste-uit (LIFO) gedrag skep. As jy 'n klein stuk geheue aan vra, sal die toewysingsprogram van die fastbin se kop trek.

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

🔥 Moderne glibc oorwegings (tcache ≥ 2.26)

Sedert glibc 2.26 hou elke draad sy eie tcache wat voor die ongesorteerde bin gevra word. Daarom sal 'n eerste-pas scenario slegs bereik word as:

1. Die aangevraagde grootte is groter as tcache_max (0x420 op 64-bit standaard), of
2. Die ooreenstemmende tcache bin is reeds vol of handmatig leeggemaak (deur 7 elemente toe te ken en hulle in gebruik te hou).

In werklike ontploffings sal jy gewoonlik 'n helper routine byvoeg soos:

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

Sodra die tcache uitgeput is, gaan daaropvolgende vrye na die ongesorteerde bin en klassieke eerste-pas gedrag (staartsoektog, kopinvoeging) kan weer geaktiveer word.

🚩 Skep 'n oorvleuelende-chunk UAF met eerste-pas

Die fragment hieronder (getoets op glibc 2.38) toon hoe die splitter in die ongesorteerde bin misbruik kan word om 2 oorvleuelende wysers te skep – 'n kragtige primitief wat 'n enkele vrye in 'n skryf-na-vrye omskakel.

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

Exploitasie resep (algemeen in onlangse CTFs):

1. Dreineer die tcache vir die teiken grootte.
2. Vry 'n stuk sodat dit in die ongesorteerde bin beland.
3. Toewys 'n effens kleiner grootte – die toewysingsprogram verdeel die ongesorteerde stuk.
4. Toewys weer – die oorblywende deel oorvleuel met 'n bestaande in gebruik stuk → UAF.
5. Oorskry sensitiewe velde (funksie wysers, FILE vtable, ens.)

'n Praktiese toepassing kan gevind word in die 2024 HITCON Quals Setjmp uitdaging waar hierdie presiese primitiewe gebruik word om van 'n UAF na volle beheer van __free_hook te pivot.

🛡️ Versagtings & Versterkings

• Veilige-koppeling (glibc ≥ 2.32) beskerm slegs die enkel-gelinkte tcache/fastbin lyste. Die ongesorteerde/klein/groot bins stoor steeds rou wysers, so eerste-pas gebaseerde oorvleulings bly lewensvatbaar as jy 'n heap leak kan verkry.
• Heap wysers enkripsie & MTE (ARM64) beïnvloed nog nie x86-64 glibc nie, maar distro versterkingsvlagte soos GLIBC_TUNABLES=glibc.malloc.check=3 sal aborteer op onkonsekwente metadata en kan naïewe PoCs breek.
• Vul tcache op vry (voorstel in 2024 vir glibc 2.41) sal verdere vermindering van ongesorteerde gebruik bewerkstellig; monitor toekomstige vrystellings wanneer jy generiese exploits ontwikkel.

Ander Verwysings & Voorbeelde

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Gebruik na vry: Genereer 'n gebruikersobjek, vry dit, genereer 'n objek wat die vrygestelde stuk ontvang en toelaat om daarin te skryf, oorwrite die posisie van user->password van die vorige een. Hergebruik die gebruiker om die wagwoordkontrole te omseil
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Die program laat toe om notas te skep. 'n Nota sal die nota-inligting in 'n malloc(8) hê (met 'n wys na 'n funksie wat geroep kan word) en 'n wys na 'n ander malloc() met die inhoud van die nota.
• Die aanval sou wees om 2 notas (nota0 en nota1) te skep met groter malloc-inhoud as die nota-inligting grootte en dan hulle vry te stel sodat hulle in die vinnige bin (of tcache) beland.
• Dan, skep 'n ander nota (nota2) met inhoud grootte 8. Die inhoud gaan in nota1 wees aangesien die stuk hergebruik gaan word, waar ons die funksie wys kan verander om na die wen funksie te wys en dan Gebruik-Na-Vry die nota1 om die nuwe funksie wys te bel.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Dit is moontlik om 'n bietjie geheue toe te wys, die gewenste waarde te skryf, dit vry te stel, dit weer toe te wys en aangesien die vorige data steeds daar is, sal dit behandel word volgens die nuwe verwagte struktuur in die stuk wat dit moontlik maak om die waarde te stel om die vlag te kry.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• In hierdie geval is dit nodig om 4 binne 'n spesifieke stuk te skryf wat die eerste een is wat toegewy is (selfs nadat al hulle gedwing vrygestel is). Op elke nuwe toegewyde stuk word sy nommer in die array-indeks gestoor. Dan, toewys 4 stukke (+ die aanvanklik toegewyde), die laaste een sal 4 daarin hê, vry hulle en dwing die hertoewysing van die eerste een, wat die laaste vrygestelde stuk sal gebruik wat die een met 4 daarin is.
• 2024 HITCON Quals Setjmp skrywe (Quarkslab) – praktiese eerste-pas / ongesorteerde-skeiding oorvleueling aanval: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify skrywe – misbruik van ongesorteerde-bin skeiding om libc te lek en oorvleueling te verkry: https://hackmd.io/@aneii11/H1S2snV40