First Fit

Reading time: 4 minutes

First Fit

Lorsque vous libérez de la mémoire dans un programme utilisant glibc, différents "bins" sont utilisés pour gérer les morceaux de mémoire. Voici une explication simplifiée de deux scénarios courants : les bins non triés et les fastbins.

Bins Non Triés

Lorsque vous libérez un morceau de mémoire qui n'est pas un morceau rapide, il va dans le bin non trié. Ce bin agit comme une liste où de nouveaux morceaux libérés sont ajoutés à l'avant (la "tête"). Lorsque vous demandez un nouveau morceau de mémoire, l'allocateur examine le bin non trié depuis l'arrière (la "queue") pour trouver un morceau suffisamment grand. Si un morceau du bin non trié est plus grand que ce dont vous avez besoin, il est divisé, la partie avant étant retournée et la partie restante restant dans le bin.

Exemple :

• Vous allouez 300 octets (a), puis 250 octets (b), vous libérez a et demandez à nouveau 250 octets (c).
• Lorsque vous libérez a, il va dans le bin non trié.
• Si vous demandez à nouveau 250 octets, l'allocateur trouve a à la queue et le divise, retournant la partie qui correspond à votre demande et gardant le reste dans le bin.
• c pointera vers le précédent a et sera rempli avec les a's.

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

Fastbins

Les fastbins sont utilisés pour de petits morceaux de mémoire. Contrairement aux unsorted bins, les fastbins ajoutent de nouveaux morceaux à la tête, créant un comportement de dernier entré, premier sorti (LIFO). Si vous demandez un petit morceau de mémoire, l'allocateur prendra à partir de la tête du fastbin.

Exemple :

• Vous allouez quatre morceaux de 20 octets chacun (a, b, c, d).
• Lorsque vous les libérez dans n'importe quel ordre, les morceaux libérés sont ajoutés à la tête du fastbin.
• Si vous demandez ensuite un morceau de 20 octets, l'allocateur renverra le morceau le plus récemment libéré de la tête du fastbin.

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

Autres Références & Exemples

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Utilisation après libération : Générer un objet utilisateur, le libérer, générer un objet qui obtient le morceau libéré et permettre d'écrire dessus, écrasant la position de user->password de l'ancien. Réutiliser l'utilisateur pour contourner la vérification du mot de passe
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Le programme permet de créer des notes. Une note aura les informations de la note dans un malloc(8) (avec un pointeur vers une fonction qui pourrait être appelée) et un pointeur vers un autre malloc(<size>) avec le contenu de la note.
• L'attaque consisterait à créer 2 notes (note0 et note1) avec des contenus malloc plus grands que la taille des informations de la note, puis à les libérer pour qu'elles entrent dans le fast bin (ou tcache).
• Ensuite, créer une autre note (note2) avec une taille de contenu de 8. Le contenu va se trouver dans note1 car le morceau va être réutilisé, où nous pourrions modifier le pointeur de fonction pour pointer vers la fonction win et ensuite utiliser après libération note1 pour appeler le nouveau pointeur de fonction.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Il est possible d'allouer de la mémoire, d'écrire la valeur désirée, de la libérer, de la réallouer et comme les données précédentes sont toujours là, elles seront traitées selon la nouvelle structure attendue dans le morceau, rendant possible de définir la valeur ou d'obtenir le drapeau.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• Dans ce cas, il est nécessaire d'écrire 4 à l'intérieur d'un morceau spécifique qui est le premier alloué (même après avoir forcé la libération de tous). Pour chaque nouveau morceau alloué, son numéro dans l'index du tableau est stocké. Ensuite, allouer 4 morceaux (+ le morceau initialement alloué), le dernier contiendra 4 à l'intérieur, les libérer et forcer la réallocation du premier, qui utilisera le dernier morceau libéré, qui est celui avec 4 à l'intérieur.