Unsorted Bin Attack

Reading time: 12 minutes

Información básica

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

Bins & Memory Allocations

Las listas unsorted pueden escribir la dirección de unsorted_chunks (av) en la dirección bk del chunk. Por lo tanto, si un atacante puede modificar la dirección del puntero bk en un chunk dentro del unsorted bin, podría ser capaz de escribir esa dirección en una dirección arbitraria, lo que puede ser útil para leak direcciones de Glibc o para eludir alguna defensa.

Así que, básicamente, este ataque permite establecer un número grande en una dirección arbitraria. Ese número grande es una dirección, que podría ser una dirección del heap o una dirección de Glibc. Un objetivo tradicional era global_max_fast para permitir crear fast bin bins con tamaños mayores (y pasar de un unsorted bin attack a un fast bin attack).

• Modern note (glibc ≥ 2.39): global_max_fast became an 8‑bit global. Blindly writing a pointer there via an unsorted-bin write will clobber adjacent libc data and will not reliably raise the fastbin limit anymore. Prefer other targets or other primitives when running against glibc 2.39+. See "Modern constraints" below and consider combining with other techniques like a large bin attack or a fast bin attack once you have a stable primitive.

El código de guyinatuxedo lo explica muy bien, aunque si modificas los mallocs para solicitar memoria lo bastante grande para no caer en Tcache puedes ver que aparece el error mencionado anteriormente y evita esta técnica: malloc(): unsorted double linked list corrupted

How the write actually happens

• The unsorted-bin write is triggered on free when the freed chunk is inserted at the head of the unsorted list.
• During insertion, the allocator performs bck = unsorted_chunks(av); fwd = bck->fd; victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;
• If you can set victim->bk to (mchunkptr)(TARGET - 0x10) before calling free(victim), the final statement will perform the write: *(TARGET) = victim.
• Later, when the allocator processes the unsorted bin, integrity checks will verify (among other things) that bck->fd == victim and victim->fd == unsorted_chunks(av) before unlinking. Because the insertion already wrote victim into bck->fd (our TARGET), these checks can be satisfied if the write succeeded.

Modern constraints (glibc ≥ 2.33)

To use unsorted‑bin writes reliably on current glibc:

• Tcache interference: for sizes that fall into tcache, frees are diverted there and won’t touch the unsorted bin. Either
• make requests with sizes > MAX_TCACHE_SIZE (≥ 0x410 on 64‑bit by default), or
• fill the corresponding tcache bin (7 entries) so that additional frees reach the global bins, or
• if the environment is controllable, disable tcache (e.g., GLIBC_TUNABLES glibc.malloc.tcache_count=0).
• Integrity checks on the unsorted list: on the next allocation path that examines the unsorted bin, glibc checks (simplified):
• bck->fd == victim and victim->fd == unsorted_chunks(av); otherwise it aborts with malloc(): unsorted double linked list corrupted.
• Esto significa que la dirección que apuntas debe tolerar dos escrituras: primero *(TARGET) = victim en el momento del free; después, cuando se elimina el chunk, *(TARGET) = unsorted_chunks(av) (el allocator reescribe bck->fd con la cabeza del bin). Elige objetivos donde forzar simplemente un valor grande no nulo sea útil.
• Objetivos típicos y estables en exploits modernos
• Estado de la aplicación o global que trate valores "grandes" como flags/límites.
• Primitivas indirectas (por ejemplo, preparar un subsecuente [fast bin attack](Fast Bin Attack) o pivotar a una posterior escritura write‑what‑where).
• Evita __malloc_hook/__free_hook en versiones nuevas de glibc: fueron eliminados en 2.34. Evita global_max_fast en ≥ 2.39 (ver nota anterior).
• Sobre global_max_fast en glibc reciente
• En glibc 2.39+, global_max_fast es un global de 8 bits. El truco clásico de escribir un puntero del heap allí (para ampliar fastbins) ya no funciona bien y probablemente corrompa el estado adyacente del allocator. Prefiere otras estrategias.

Minimal exploitation recipe (modern glibc)

Objetivo: lograr una única escritura arbitraria de un puntero del heap a una dirección arbitraria usando la primitiva de inserción del unsorted‑bin, sin provocar un crash.

• Layout/grooming
• Allocate A, B, C with sizes large enough to bypass tcache (e.g., 0x5000). C prevents consolidation with the top chunk.
• Corruption
• Overflow from A into B’s chunk header to set B->bk = (mchunkptr)(TARGET - 0x10).
• Trigger
• free(B). At insertion time the allocator executes bck->fd = B, therefore *(TARGET) = B.
• Continuation
• If you plan to continue allocating and the program uses the unsorted bin, expect the allocator to later set *(TARGET) = unsorted_chunks(av). Both values are typically large and may be enough to change size/limit semantics in targets that only check for "big".

Pseudocode skeleton:

// 64-bit glibc 2.35–2.38 style layout (tcache bypass via large sizes)
void *A = malloc(0x5000);
void *B = malloc(0x5000);
void *C = malloc(0x5000); // guard

// overflow from A into B’s metadata (prev_size/size/.../bk). You must control B->bk.
*(size_t *)((char*)B - 0x8) = (size_t)(TARGET - 0x10); // write fake bk

free(B); // triggers *(TARGET) = B (unsorted-bin insertion write)

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 <list_all_lock+15>: 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.

References

• Glibc malloc unsorted-bin integrity checks (example in 2.33 source): https://elixir.bootlin.com/glibc/glibc-2.33/source/malloc/malloc.c
• global_max_fast and related definitions in modern glibc (2.39): https://elixir.bootlin.com/glibc/glibc-2.39/source/malloc/malloc.c