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.




 

An Analysis of Linux Kernel Heap Hardening

Dr Silvio Cesare
@silviocesare

Summary 

I wrote a blog post some months ago on weaknesses in the Linux kernel heap free list pointer hardening implementation. In response to that weakness, Kees Cook wrote an improved kernel patch, which I reviewed. This blog post is an analysis of that patch. I try to break it using an SMT solver and fail.

Introduction

In the original kernel slab free list hardening patch, the free list pointer was scrambled to prevent naive free list pointer corruption and poisoning.

The scrambling consisted of:

obfuscated_ptr = ptr ^ ptr_addr ^ secret

The weakness in this approach was because ptr and ptr_addr were part of the same slab, they were highly similar. In fact, only the low bits were different. As such, the obfuscated_ptr revealed almost the entire secret. The blog post where I talk about this is here https://blog.infosectcbr.com.au/2020/03/weaknesses-in-linux-kernel-heap.html.

A subsequent patch was written by Kees Cook in https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=1ad53d9fa3f6168ebcf48a50e08b170432da2257 to improve the pointer scrambling and he asked me for feedback at the time. I think this is a fantastic thing that the Linux kernel team actively works with security researchers.

The improved patch changes the use of ptr_addr:

obfuscated_ptr = ptr ^ swab(ptr_addr) ^ secret

swab swaps the byte order.

The question is, can we recover information, such as the secret or the pointer, from the obfuscated pointer?

SMT Analysis

The approach I use to analyse the patch is to represent the scrambling operation as a set of SMT constraints. I will then query the SMT solver to see if I can infer secret information.

Here are the equations:

    equations = [
        ptr & ~0xfff == ptr_addr & ~0xfff,
#        ptr == ptr_addr + 0x20,
        ptr & 0xf == 0,
        ptr_addr & 0xf == 0,
        ptr_addr_swab_0 == (LShR(ptr_addr,  0) & 0xff) << 56,
        ptr_addr_swab_1 == (LShR(ptr_addr,  8) & 0xff) << 48,
        ptr_addr_swab_2 == (LShR(ptr_addr, 16) & 0xff) << 40,
        ptr_addr_swab_3 == (LShR(ptr_addr, 24) & 0xff) << 32,
        ptr_addr_swab_4 == (LShR(ptr_addr, 32) & 0xff) << 24,
        ptr_addr_swab_5 == (LShR(ptr_addr, 40) & 0xff) << 16,
        ptr_addr_swab_6 == (LShR(ptr_addr, 48) & 0xff) <<  8,
        ptr_addr_swab_7 == (LShR(ptr_addr, 56) & 0xff) <<  0,
        ptr_addr_swab == ptr_addr_swab_0 +
                         ptr_addr_swab_1 +
                         ptr_addr_swab_2 +
                         ptr_addr_swab_3 +
                         ptr_addr_swab_4 +
                         ptr_addr_swab_5 +
                         ptr_addr_swab_6 +
                         ptr_addr_swab_7,
        stored_value == secret ^ ptr ^ ptr_addr_swab,
    ]

We will use some testing data that Kees Cook produced to go along with his kernel patch:

#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)

* The first thing we will query is can we recover the secret given only the obfuscated pointer?

The answer is No. Given only obfuscated pointer, there are a very large number of possible candidates for the secret. And there are no collisions where different secrets produce the correct result.

* The next thing we will ask, is if we have an infoleak of the pointer (ptr) and the obfuscated pointer (stored value), but not the ptr_addr, can we recover the secret?

The answer is yes. In the test data above, we can make some assumptions about ptr and ptr_addr. 1) Only the low 12 bits between them are different. 2) For this allocation pattern, since we are allocating fixed size chunks, then the very low bits to force a chunk alignment are zero.

If we ask our SMT solver what the secret is, given ptr and the stored value, there are 256 candidate secrets.

If we assume ptr_addr is offset by 0x20 to ptr, then we can come up with a single solution.

Conclusion

In this blog post, I looked at a new addition to the Linux kernel heap hardening. I tried to attack it using an SMT solver to recover the secret value used in the free list pointer scrambling. I failed. The patch represents an improvement over the previous hardening attempt.

Bypassing Pointer Guard in Linux's glibc

Dr Silvio Cesare
@silviocesare

Summary 

Pointer guard is an exploit mitigation in glibc that applies to stored pointers and especially stored function pointers. A number of library calls can register function pointers that get executed later on. An example of this is registering an exit handler with atexit(). Stored function pointers are scrambled or mangled by XORing them with a secret in the thread data (fs:0x30) and applying a bitwise rotation. This mitigates control-flow hijacking by an attacker who would otherwise be able to overwrite the stored function pointer with a location of their choosing. In this blog post, I'll present a bypass for pointer guard in multithreaded applications where an attacker knows the libc base address and has an arbitrary read.

Introduction

Pointer guard is documented in glibc reference materials https://sourceware.org/glibc/wiki/PointerEncryption. The mitigation provides a set of macros that mangle and demangle pointers. The API to use is PTR_MANGLE and PTR_DEMANGLE. For example, if an application wants to store a function pointer in *stored_ptr, they could use the following:

*stored_ptr = PTR_MANGLE(ptr)

And to demangle it:

ptr = PTR_DEMANGLE(*stored_ptr);

The pointer mangling works by XORing the pointer with an internal 64-bit secret, then performing a bitwise left rotatation of 0x11 bits (on x86-64). Demangling is the reverse.

Related Work

After I tweeted the requirements for this attack, I was linked to http://binholic.blogspot.com/2017/05/notes-on-abusing-exit-handlers.html. This is similar attack to the one I present with some specific differences. Interested readers are advised to review it.

The Attack

The attack is essentially a known-plaintext attack against the mangling operation. If we know the original pointer and its mangled version, we can recover the 64-bit secret.

How do we get known plaintexts? The related work linked earlier shows 1 way to identify known plaintext. I will present another approach.

Let's grep -rw PTR_MANGLE glibc/ --include '*.c' and examine each reference. I can quickly see an interesting use:

In thread initialization, we can see a function pointer table at a fixed address (__libc_pthread_functions).

If we examine what the first entry of this function pointer table, we can see that it points to __pthread_attr_destroy.

This is enough to defeat pointer guard if we know the library base from an ASLR leak. This is shown in the following pseudo code.
  
x = __libc_pthread_functions[0];
secret = rotr64(x, 0x11) ^ &__pthread_attr_destroy;

There is something else we can try. Is there a possibility that there is a mangled function pointer where the function pointer is equal to 0 or perhaps -1 or another fixed constant?

I write some test code to recover the cookie in a multithreaded application, and then i take the results of:

PTR_MANGLE(0);
PTR_MANGLE((unsigned long)-1);

In GDB using the GEF debugging plugin, I use pattern-search to find any such memory in the address space that has stored one of these mangled pointers with known plaintexts (pointers).

I find one.

__libc_pthread_functions[1] in my particular application has a mangled NULL pointer.

To defeat pointer guard then after program initialization, given the address of __libc_pthread_functions, is:

secret = rotr64(__libc_pthread_functions[1], 0x11);

From this point, an attacker can safely and correctly mangle their own pointers.

Conclusion

In this blog post, I presented an attack against the pointer guard exploit mitigation in Linux's glibc. The bypass requires the base address of libc and an arbitrary read.

Breaking Secure Checksums in the Scudo Allocator

Dr Silvio Cesare
@silviocesare

Summary 

Scudo is a hardened heap allocator used in Android. Scudo has a security mechanism where malloc chunk headers include a CRC32 checksum that incorporate the malloc chunk pointer and an out of band secret 32-bit cookie. In this blog post, I assume I am able to leak a malloc chunk header and the pointer to it. From that, I infer the secret cookie by solving a set of equations that model the checksum algorithm using the z3 and STP SMT solvers, such that I can create my own checksums for fake chunk headers.

Introduction

Scudo is a hardened allocator as used in Android. To use scudo is quite simple with the clang compiler and a compiler option.

$ clang -fsanitize=scudo test.c -o test

A malloc chunk has an 8-byte header. This header is defined as:

The 16-bit checksum uses the CRC32 algorithm and incorporates the pointer to the malloc payload and a secret 32-bit cookie that is not stored in the header. The CRC32 checksum is truncated to 16-bits and then stored in the header.

The cookie is shown below:

And the checksum code:

An attack to reveal the cookie

I can unroll the loops of the checksum algorithm and represent them as a set of SMT equations.

I can simply represent a set of header and pointer leaks as these SMT equations. From this, I can query my solver for what the cookie should be. I use the SMT solver z3.

.

Results

With 1 pointer and header leak I can generate a cookie that produces the correct checksum with my input data. That is, when the scudo checksum algorithm runs with my header leak, and I substitute my cookie with the system cookie - I generate the correct checksum!

It only takes a few seconds to run. However, it is not a unique solution. Therefore, it is only chance if it generates the same cookie as the unique system wide allocator cookie.

Initially, I thought my approach had failed. I repeatedly tried to calculate a unique solution. I added more and more leaks. I employed multicore SAT solvers and the STP SMT solver. I tried 60 leaks and a VM with 16 cores and 128Gb of memory. It crashed, running out of resources, after 3 days.

Likewise, for 1000 leaks and 10000 leaks. They all quickly ran out of memory or couldn't complete in a feasible amount of time.

It didn't matter. I have a solution.

It turns out I don't need a unique solution and my inferred cookie to match the system one. There are cookie collisions. My cookie produces the same correct checksums in future allocations like the system cookie.

In summary, I can infer a working cookie from 1 leak of a malloc chunk header and the pointer to it.

Conclusion

In this blog post I presented an attack to fake checksums in malloc chunk headers against the hardened scudo allocator. This will allow the creation of fake chunks which is a starting point for other heap attacks.

The code for the attack can be found at https://github.com/infosectcbr/scudo-checksum-attack