Bit Flipping Attacks Against Free List Pointer Obfuscation

Dr Silvio Cesare
@silviocesare

Summary 

In this blog post, I look at attacks to make an obfuscated free list pointer, such as that used in the Linux kernel, demangle or descramble to an arbitrary address. The way I do this, is to substitute the stored and obfuscated pointer with a pointer of my choosing and then take note of errors reported by the resulting invalid pointer once it has been demangled. Using bitwise arithmetic, I am able to take these invalid pointers and construct a new substitute pointer such that demangling returns to me a near arbitrary pointer.

Introduction

Free list pointers are used in the default Linux kernel heap allocator, SLUB. A free list pointer holds the address of the next available chunk of memory. If an attacker is able to corrupt or poison this pointer, they might make a heap allocation return a somewhat arbitrary pointer. In the Linux kernel, this pointer is not entirely arbitrary because the pointer is validated to belong to the appropriate slab in question.

The latest Linux kernels use a free list pointer obfuscation technique as follows (in pseudocode):

def mangle(ptr, ptr_addr, secret):
  return ptr ^ swab(ptr_addr) ^ secret

def demangle(obfuscated_ptr, ptr_addr, secret)
  return obfuscated_ptr ^ swab(ptr_addr) ^ secret

In conjunction with an oracle that tells us invalid demangled pointers, we can construct a bit flipping attack to demangle a chosen obfuscated_ptr into an arbitrary address. Other than being able to modify or infoleak the obfuscated_ptr, an attacker doesn't have much else they can do. Thus, our attack is based around carefully selecting to substitute obfuscated_ptr in a series of demangling operations.

A Pointer Demangling Oracle

A requirement for our bit flipping attack is that we have an oracle that demangles pointers and tells us the result.

As stated earlier, the Linux kernel does the validity checks after pointer demangling to ensure the pointer is in the correct slab:

        /* Check free pointer validity */
        if (!check_valid_pointer(s, page, get_freepointer(s, p))) {
                object_err(s, page, p, "Freepointer corrupt");
                /*
                 * No choice but to zap it and thus lose the remainder
                 * of the free objects in this slab. May cause
                 * another error because the object count is now wrong.
                 */
                set_freepointer(s, p, NULL);
                return 0;
        }

If we expand object_err, we can see the following code that gets called:

static void print_trailer(struct kmem_cache *s, struct page *page, u8 *p)
{
        unsigned int off;       /* Offset of last byte */
        u8 *addr = page_address(page);

        print_tracking(s, p);

        print_page_info(page);

        pr_err("INFO: Object 0x%p @offset=%tu fp=0x%p\n\n",
               p, p - addr, get_freepointer(s, p));

So it seems in some cases, an invalid pointer allows to inspect the kernel messages for the free list pointer that is demangled to an invalid pointer.

This is enough to allow us to perform a bit flipping attack.

Bit Flipping  

Firstly, ptr and ptr_addr are almost identical. Originally, pointer mangling worked as ptr ^ ptr_addr ^ secret. Only some of the low bits between ptr and ptr_addr change since both values reside in the same slab. Thus, a simple infoleak of the obfuscated_ptr disclosed most of the secret. I disclosed that attack in an earlier blog post https://blog.infosectcbr.com.au/2020/03/weaknesses-in-linux-kernel-heap.html. A subsequent patch to remedy this problem was to use swab(ptr_addr) in the mangling operation.

OK, onto the new attack.

Let us assume we can overwrite a stored and obfuscated free list pointer. Let us overwrite this stored pointer with 0x1. We choose 0x1 because 0x0 might be interpreted as a NULL pointer. For now, we will avoid dealing or discussing NULL pointer in mangling.

When we substitute 0x1 for the obfuscated pointer, a demangle operation looks like this

ptr1 = 0x1 ^ swab(ptr1_addr) ^ secret

This pointer will almost certainly be invalid. As I showed earlier, our pointer demangling oracle will tell us what ptr1 is.

Let's now take our target_address that we want a demangle operation to result in. We XOR this with ptr1, which results in:

obfuscated_ptr2 = target_address ^ 0x1 ^ swab(ptr1_addr) ^ secret

Let's substitute another stored and obfuscated pointer with this value and demangle it.

ptr2 = (obfuscated_ptr2) ^ swab(ptr2_addr) ^ secret

Let's expand:

ptr2 = (target_address ^ 0x1 ^ swab(ptr1_addr) ^ secret) ^ swab(ptr2_addr) ^ secret

And we simplify:

ptr2 = target_address ^ 0x1 ^ swab(ptr1_addr) ^ swab(ptr2_addr) 

Now remember that ptr1_addr and ptr2_addr are almost identical since they belong in the same slab. This means that swab(ptr1_addr) ^ swab(ptr2_addr) approximately equals 0. Lets assume it does equal 0, and ptr2 is now:

ptr2 = target_address ^ 0x1

We just performed a bit flipping attack and demangled an obfuscated pointer into our target_address!

Let's see this in some Python code:

#!/usr/bin/python

import struct

def swab(i):
    return struct.unpack("<Q", struct.pack(">Q", i))[0]

def mangle(ptr, ptr_addr, secret):
    return ptr ^ swab(ptr_addr) ^ secret

def demangle(stored_value, ptr_addr, secret):
    return stored_value ^ swab(ptr_addr) ^ secret

# real-world sample data
#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)

secret = 0x86528eb656b3b59d
stored_value1 = 0x793d1135d52cda42
stored_value2 = 0x593d1135d52cda22
ptr1 = 0xffff90c22e019020
ptr2 = 0xffff90c22e019020
ptr_addr1 = 0xffff90c22e019000
ptr_addr2 = 0xffff90c22e019020

target_ptr = 0x1234567812345678

obfuscated_ptr2= demangle(0x1, ptr_addr1, secret)
x = obfuscated_ptr2 ^ target_ptr ^ 1
ptr2 = demangle(x, ptr_addr2, secret)

print("Target pointer is 0x%lx" % (target_ptr))
print("Replacing stored pointer with 0x%lx" % (x))
print("Demangled to 0x%lx" % (ptr2))

Let's run this and see our result:

infosect@ubuntu:~/InfoSect/$ ./bit-flipping.py
Target pointer is 0x1234567812345678
Replacing stored pointer with 0x94f6d9e086171c1b
Demangled to 0x3234567812345678

We can see that our demangled pointer is almost correct. Only the high bits are different. We can use our pointer oracle to brute force until we get the correct demangled pointer. Bit flipping works!

Mangling NULL Pointers

In the Linux kernel, NULL pointers can also be mangled. In the case where we can infoleak a mangled NULL pointer and then allocate that same chunk, we can perform bit flipping with 100% accuracy.

Practicality of the Attack

There's about a million easier ways to gain code execution in the Linux kernel than what I've just described. This blog post is simply to show the limits of possibility when attacking 1 particular mitigation - in this case, free list pointer obfuscation in the SLUB allocator.

Conclusion

Bit flipping attacks are known cryptographic attacks against a variety of block ciphers. Bit flipping attacks can also be used against pointer obfuscation as used in the Linux kernel. I hope this blog post inspires other people to apply cryptographic attacks in the world of memory corruption exploitation.