Unsorted Bin Attack - HackTricks

# Unsorted Bin Attack

> [!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.

## Basic Information

For more information about what is an unsorted bin check this page:

Bins & Memory Allocations

Unsorted lists are able to write the address to `unsorted_chunks (av)` in the `bk` address of the chunk. Therefore, if an attacker can modify the address of the `bk` pointer in a chunk inside the unsorted bin, he could be able to write that address in an arbitrary address which could be helpful to leak a Glibc addresses or bypass some defense.

So, basically, this attack allows to set a big number at an arbitrary address. This big number is an address, which could be a heap address or a Glibc address. A typical target is `global_max_fast` to allow to create fast bin bins with bigger sizes (and pass from an unsorted bin atack to a fast bin attack).

> [!TIP] T> aking a look to the example provided in https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#principle and using 0x4000 and 0x5000 instead of 0x400 and 0x500 as chunk sizes (to avoid Tcache) it's possible to see that nowadays the error `malloc(): unsorted double linked list corrupted` is triggered.

> Therefore, this unsorted bin attack now (among other checks) also requires to be able to fix the doubled linked list so this is bypassed `victim->bk->fd == victim` or not `victim->fd == av (arena)`, which means that the address where we want to write must have the address of the fake chunk in its `fd` position and that the fake chunk `fd` is pointing to the arena.

> [!CAUTION] Note that this attack corrupts the unsorted bin (hence small and large too). So we can only use allocations from the fast bin now (a more complex program might do other allocations and crash), and to trigger this we must allocate the same size or the program will crash.

> Note that overwriting `global_max_fast` might help in this case trusting that the fast bin will be able to take care of all the other allocations until the exploit is completed.

The code from guyinatuxedo explains it very well, although if you modify the mallocs to allocate memory big enough so don't end in a Tcache you can see that the previously mentioned error appears preventing this technique: `malloc(): unsorted double linked list corrupted`

## Unsorted Bin Infoleak Attack

This is actually a very basic concept. The chunks in the unsorted bin are going to have pointers. The first chunk in the unsorted bin will actually have the `fd` and the `bk` links pointing to a part of the main arena (Glibc).
Therefore, if you can put a chunk inside a unsorted bin and read it (use after free) or allocate it again without overwriting at least 1 of the pointers to then read it, you can have a Glibc info leak.

A similar attack used in this writeup, was to abuse a 4 chunks structure (A, B, C and D - D is only to prevent consolidation with top chunk) so a null byte overflow in B was used to make C indicate that B was unused. Also, in B the `prev_size` data was modified so the size instead of being the size of B was A+B.
Then C was deallocated, and consolidated with A+B (but B was still in used). A new chunk of size A was allocated and then the libc leaked addresses was written into B from where they were leaked.

## References & Other examples

- https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#hitcon-training-lab14-magic-heap
  - The goal is to overwrite a global variable with a value greater than 4869 so it's possible to get the flag and PIE is not enabled.
  - It's possible to generate chunks of arbitrary sizes and there is a heap overflow with the desired size.
  - The attack starts creating 3 chunks: chunk0 to abuse the overflow, chunk1 to be overflowed and chunk2 so top chunk doesn't consolidate the previous ones.
  - Then, chunk1 is freed and chunk0 is overflowed to the `bk` pointer of chunk1 points to: `bk = magic - 0x10`
  - Then, chunk3 is allocated with the same size as chunk1, which will trigger the unsorted bin attack and will modify the value of the global variable, making possible to get the flag.
- https://guyinatuxedo.github.io/31-unsortedbin_attack/0ctf16_zerostorage/index.html
  - The merge function is vulnerable because if both indexes passed are the same one it'll realloc on it and then free it but returning a pointer to that freed region that can be used.
  - Therefore, 2 chunks are created: chunk0 which will be merged with itself and chunk1 to prevent consolidating with the top chunk. Then, the merge function is called with chunk0 twice which will cause a use after free.
  - Then, the `view` function is called with index 2 (which the index of the use after free chunk), which will leak a libc address.
  - As the binary has protections to only malloc sizes bigger than `global_max_fast` so no fastbin is used, an unsorted bin attack is going to be used to overwrite the global variable `global_max_fast`.
  - Then, it's possible to call the edit function with the index 2 (the use after free pointer) and overwrite the `bk` pointer to point to `p64(global_max_fast-0x10)`. Then, creating a new chunk will use the previously compromised free address (0x20) will trigger the unsorted bin attack overwriting the `global_max_fast` which a very big value, allowing now to create chunks in fast bins.
  - Now a fast bin attack is performed:
    - First of all it's discovered that it's possible to work with fast chunks of size 200 in the `__free_hook` location:

    -     gef➤  p &__free_hook
          $1 = (void (**)(void *, const void *)) 0x7ff1e9e607a8 <__free_hook>
          gef➤  x/60gx 0x7ff1e9e607a8 - 0x59
          0x7ff1e9e6074f: 0x0000000000000000      0x0000000000000200
          0x7ff1e9e6075f: 0x0000000000000000      0x0000000000000000
          0x7ff1e9e6076f :      0x0000000000000000      0x0000000000000000
          0x7ff1e9e6077f <_IO_stdfile_2_lock+15>: 0x0000000000000000      0x0000000000000000

      - If we manage to get a fast chunk of size 0x200 in this location, it'll be possible to overwrite a function pointer that will be executed
    - For this, a new chunk of size `0xfc` is created and the merged function is called with that pointer twice, this way we obtain a pointer to a freed chunk of size `0xfc*2 = 0x1f8` in the fast bin.
    - Then, the edit function is called in this chunk to modify the `fd` address of this fast bin to point to the previous `__free_hook` function.
    - Then, a chunk with size `0x1f8` is created to retrieve from the fast bin the previous useless chunk so another chunk of size `0x1f8` is created to get a fast bin chunk in the `__free_hook` which is overwritten with the address of `system` function.
    - And finally a chunk containing the string `/bin/sh\x00` is freed calling the delete function, triggering the `__free_hook` function which points to system with `/bin/sh\x00` as parameter.
  - CTF https://guyinatuxedo.github.io/33-custom_misc_heap/csaw19_traveller/index.html
    - Another example of abusing a 1B overflow to consolidate chunks in the unsorted bin and get a libc infoleak and then perform a fast bin attack to overwrite malloc hook with a one gadget address
- Robot Factory. BlackHat MEA CTF 2022
  - We can only allocate chunks of size greater than `0x100`.
  - Overwrite `global_max_fast` using an Unsorted Bin attack (works 1/16 times due to ASLR, because we need to modify 12 bits, but we must modify 16 bits).
  - Fast Bin attack to modify the a global array of chunks. This gives an arbitrary read/write primitive, which allows to modify the GOT and set some function to point to `system`.

> [!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.