First Fit - HackTricks

# First Fit

> [!TIP] Learn & practice AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
> Learn & practice GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

> Support HackTricks
> - Check the subscription plans!
> - Join the 💬 Discord group or the telegram group or follow us on Twitter 🐦 @hacktricks_live.
> - Share hacking tricks by submitting PRs to the HackTricks and HackTricks Cloud github repos.

## First Fit

When you free memory in a program using glibc, different "bins" are used to manage the memory chunks. Here's a simplified explanation of two common scenarios: unsorted bins and fastbins.

### Unsorted Bins

When you free a memory chunk that's not a fast chunk, it goes to the unsorted bin. This bin acts like a list where new freed chunks are added to the front (the "head"). When you request a new chunk of memory, the allocator looks at the unsorted bin from the back (the "tail") to find a chunk that's big enough. If a chunk from the unsorted bin is bigger than what you need, it gets split, with the front part being returned and the remaining part staying in the bin.

Example:

- You allocate 300 bytes (`a`), then 250 bytes (`b`), the free `a` and request again 250 bytes (`c`).
- When you free `a`, it goes to the unsorted bin.
- If you then request 250 bytes again, the allocator finds `a` at the tail and splits it, returning the part that fits your request and keeping the rest in the bin.
  - `c` will be pointing to the previous `a` and filled with the `a's`.

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

### Fastbins

Fastbins are used for small memory chunks. Unlike unsorted bins, fastbins add new chunks to the head, creating a last-in-first-out (LIFO) behavior. If you request a small chunk of memory, the allocator will pull from the fastbin's head.

Example:

- You allocate four chunks of 20 bytes each (`a`, `b`, `c`, `d`).
- When you free them in any order, the freed chunks are added to the fastbin's head.
- If you then request a 20-byte chunk, the allocator will return the most recently freed chunk from the head of the 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

## Other References & Examples

- https://heap-exploitation.dhavalkapil.com/attacks/first_fit
- https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
  - ARM64. Use after free: Generate an user object, free it, generate an object that gets the freed chunk and allow to write to it, overwriting the position of user->password from the previous one. Reuse the user to bypass the password check
- https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
  - The program allows to create notes. A note will have the note info in a malloc(8) (with a pointer to a function that could be called) and a pointer to another malloc(<size>) with the contents of the note.
  - The attack would be to create 2 notes (note0 and note1) with bigger malloc contents than the note info size and then free them so they get into the fast bin (or tcache).
    - Then, create another note (note2) with content size 8. The content is going to be in note1 as the chunk is going to be reused, were we could modify the function pointer to point to the win function and then Use-After-Free the note1 to call the new function pointer.
- https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
  - It's possible to alloc some memory, write the desired value, free it, realloc it and as the previous data is still there, it will treated according the new expected struct in the chunk making possible to set the value ot get the flag.
- https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
  - In this case it's needed to write 4 inside an specific chunk which is the first one being allocated (even after force freeing all of them). On each new allocated chunk it's number in the array index is stored. Then, allocate 4 chunks (+ the initialy allocated), the last one will have 4 inside of it, free them and force the reallocation of the first one, which will use the last chunk freed which is the one with 4 inside of it.