Dr
Silvio Cesare
@silviocesare
@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
