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.