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.




Popular posts from this blog

Empowering Women in Cybersecurity: InfoSect's 2024 Training Initiative

 InfoSect has always been committed to fostering diversity and inclusion within the cybersecurity industry, with a special focus on encouraging those who identify as women to excel in the technical streams. We're excited to announce that in 2024, we're taking our commitment to the next level. Following the resounding success of our 2022 initiative, we are proud to double our efforts and expand our training opportunities for women in cybersecurity. HackerChix: Uniting Women in Cybersecurity In 2017, InfoSect introduced HackerChix, a vibrant community that provides a platform for women to connect, support, and inspire one another in the world of cybersecurity. This initiative has been a constant presence at BSides Canberra every year.   Doubling Down on Education To empower more women with the knowledge and skills needed to excel in cybersecurity, InfoSect is thrilled to announce a significant expansion of its training offerings in 2024. Thanks to the generous sponsorshi
Read more

C++ Memory Corruption (std::string) - part 4

  Summary This is the next part of the C++ memory corruption series*. In this post, we'll look at corrupting the std:string object in Linux and see what exploitation primitives we can gain. * https://blog.infosectcbr.com.au/2020/08/c-memory-corruption-part-1.html * https://blog.infosectcbr.com.au/2022/01/c-memory-corruption-stdvector-part-2.html  *  https://blog.infosectcbr.com.au/2022/03/c-memory-corruption-stdlist-part-3.html Author: Dr Silvio Cesare Introduction C++ is a common language for memory corruption. However, there is much more literature on exploiting C programs and little on C++ programs. C++ presents new classes, objects, and data structures which can all be effectively used for building exploitation primitives. In this post, we'll look at corrupting the std::string class and see what specific primitives we can obtain. std::string We note that the object stored in memory for a basic string consists firstly of the backing pointer to the string contents. Se
Read more

C++ Memory Corruption (std::vector) - part 2

Summary This is the 2nd part of the C++ memory corruption series*. In this post, we'll look at corrupting the std::vector class in Linux and see what exploitation primitives we can gain. We'll see that we can build arbitrary read/write primitives. * https://blog.infosectcbr.com.au/2020/08/c-memory-corruption-part-1.html   Author: Dr Silvio Cesare Introduction C++ is a common language for memory corruption. However, there is much more literature on exploiting C and not C++ programs. C++ presents new classes, objects, and data structures which can all be effectively used for building exploitation primitives.  In this post, we'll look at the std::vector class and see what specific primitives we can obtain.  Let's start by looking at /usr/include/c++/bits/stl_vector.h namespace std _GLIBCXX_VISIBILITY ( default ) { _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// See bits/stl_deque.h's _Deque_base for an explanation. template < typename
Read more