Free list poisoning in a common heap exploitation technique which corrupts a heap allocators's linked list of free chunks. A future heap allocation will return the poisoned address. The Linux kernel introduced heap hardening which obfuscates the pointers in these linked lists. Without knowing secret keys and pointer addresses, an attacker cannot reliably poison this pointer with a chosen address. In this blog post I'll show that the Linux kernel's free list pointer obfuscation has weaknesses, which in the right conditions, allows an attacker to perform free list poisoning.
Introduction
The default heap allocator in the Linux kernel is the SLUB allocator. Inside each free chunk is a pointer that is part of a linked list tracking those free chunks. Free list poisoning is a well known technique against the Linux kernel and is documented in the book, "A Guide to Kernel Exploitation: Attcking the Core", 2010. To summarize the technique, an attacker overwrites the free list pointer with a carefully crafted address. This address will subsequently be returned in a future heap allocation.
Free list poisoning has been mitigated since 2017 in the Linux kernel with the configuration option CONFIG_SLAB_FREELIST_HARDENED. The patch for this mitigation is shown in https://patchwork.kernel.org/patch/9864165/.
The important code that does the obfuscation is shown here:
*
* Returns freelist pointer (ptr). With hardening, this is obfuscated
* with an XOR of the address where the pointer is held and a per-cache
* random number.
*/
static inline void *freelist_ptr(const struct kmem_cache *s, void *ptr,
unsigned long ptr_addr)
{
#ifdef CONFIG_SLAB_FREELIST_HARDENED
return (void *)((unsigned long)ptr ^ s->random ^ ptr_addr);
#else
return ptr;
#endif
What we note is the target pointer is xored with the address of the pointer and a random value. This random value is unique per slab. We can see that we can't reveal or overwrite this pointer unless we known a secret and also have information leaks on the chunk addresses.
Attack Insight
The key to understanding my attack, is to note that the pointers to free chunks are stored inside similar free chunks. What this means in practice, is that pointers and the addresses of those pointers are almost identical. As an example, when allocating 2 16 bytes chunks of memory, it is very likely that the pointers and the addresses of the pointers only differ in their lower 12-bits (for an architecture with a 12-bit page size).
When the free list pointer is obfuscated with ptr ^ ptr_addr ^ s->random, then since ptr and ptr_addr share the same high bits, this will result in the resulting high bits of ptr ^ ptr_addr to be 0. Thus, if we have an information leak of our obfuscated pointer, then we can subsequently leak the high 52-bits of s->random.
We also note that some low bits of s->random are leaked. The SLUB allocator is a slab based allocator, which rounds allocations to the slab size. We can make some assumptions that the memory we have allocated will be aligned to the rounded up slab size. Thus, if we allocate 16 bytes of memory, the low 4 bits of our heap allocation will be 0. If we allocate 256 bytes, the low 8 bits will be 0, if we allocate 4096 bytes, the low 12 bits will be zero. However, if we mix up slab sizes, then a new s->random is present for different slabs.
The Attack
We want to perform free list poisoning. Firstly, we need an information disclosure. Let's assume we have allocated a 16 byte chunk. We need to know the memory contents of the free list pointer in this free chunk. The free list pointer is the first 8 bytes of the free chunk on a 64-bit architecture.
When we disclose this obfuscated pointer, we simply take the high 52 bits and the low 4 bits. These bits are the secret value shown earlier, that is s->random which we will call 'secret'.
Now we want to perform the free list pointer corruption. We allocate a 16-byte chunk. We free this buffer. We will corrupt its pointer. We also need to know the address of this free chunk which we will call PTR_ADDR.
Our target buffer that we will use to poison we will call TARGET_PTR. To calculate the obfuscated free list pointer we use:
When we overwrite this pointer, we still don't know the middle bits of the secret. In the case above, we only know 56 (52+4) bits of the secret and 8 bits remain unknown. However, this will suffice with arbitrary values for the middle bits.
We poison with OBFUSCATED_POINTER, and have 8 bits of entropy for where the heap allocator will return memory. However, it will still likely return an address from the same page of memory. Thus, if we are able to control the memory at each of these possible results, our attack can succeed.
Ensuring that the kernel heap is in a consistent state after free list poisoning is left to the reader and out of scope for this blog post.
Conclusion
This blog post examined the heap hardening in the SLUB allocator to obfuscate the free list pointers. I showed that there are weaknesses in the implement and secret information can be revealed within these obfuscated pointers.
Followup
A patch for the Linux kernel has been written https://git.kernel.org/pub/scm/linux/kernel/git/kees/linux.git/commit/?h=mm/slub/freelist&id=d5baf9d870941c4c5efaa6435228ae2f3382b6e2
To quote a section of the commit message,
kmalloc-32 freelist walk, before: ptr ptr_addr stored value secret ffff90c22e019020@ffff90c22e019000 is 86528eb656b3b5bd (86528eb656b3b59d) ffff90c22e019040@ffff90c22e019020 is 86528eb656b3b5fd (86528eb656b3b59d) ffff90c22e019060@ffff90c22e019040 is 86528eb656b3b5bd (86528eb656b3b59d) ffff90c22e019080@ffff90c22e019060 is 86528eb656b3b57d (86528eb656b3b59d) ffff90c22e0190a0@ffff90c22e019080 is 86528eb656b3b5bd (86528eb656b3b59d) ...
after: ptr ptr_addr stored value secret
ffff9eed6e019020@ffff9eed6e019000 is 793d1135d52cda42 (86528eb656b3b59d) ffff9eed6e019040@ffff9eed6e019020 is 593d1135d52cda22 (86528eb656b3b59d) ffff9eed6e019060@ffff9eed6e019040 is 393d1135d52cda02 (86528eb656b3b59d) ffff9eed6e019080@ffff9eed6e019060 is 193d1135d52cdae2 (86528eb656b3b59d) ffff9eed6e0190a0@ffff9eed6e019080 is f93d1135d52cdac2 (86528eb656b3b59d)
