Shattered

This was a very interesting challenge.

# Analysis

The libc version is 2.29. This implies the use of tcache bins, as well as additional protections against double-free.

As usual, the first thing we do is run checksec.

$ checksec shattered
[*] '/home/robert/writeups/binexp/hsctf20/shattered/shattered'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled

All protections enabled - it’s a typical heap exploit challenge. Then again, this is to be expected. The challenge author, poortho, is notorious for only writing glibc heap problems.

The exploit path will probably involve getting a libc leak, and then overwriting one of the hooks - __malloc_hook or __free_hook.

## Vulnerabilities

Looking through the binary, there are two key vulnerabilities to exploit.

First, note the struct of the object is as follows.

However, the object is created with malloc. Any leftover data in the chunk won’t be zeroed.

  obj = (astruct *)malloc(0x38);
  obj->left = (astruct *)0x0;
  obj->right = (astruct *)0x0;
  pcVar1 = (char *)malloc(size & 0xffffffff);
  obj->data = pcVar1;
  obj->size = size & 0xffffffff;
  force_get_data(obj->data,size & 0xffffffff,size & 0xffffffff);
  SHA1((uchar *)obj->data,size & 0xffffffff,(uchar *)obj);

The search function prints out the hash with a call to puts, as opposed to say a bounded write call. That means if the hash has no null bytes, and the original chunk was also filled with non-null bytes, the puts call could leak the ->left, or a heap address.

puts((char *)param_1);

This vulnerability allows us to get a heap leak.

The second vulnerability arises in an uninitialized variable in the allocation.

This was hinted at, with the very suspicious function at 0x100a9f which reads 100 bytes to the stack for seemingly no reason.

In 0x100b0c, the local_10 node pointer is uninitialized if there is a sha1 collision.

      if ((to_add->size == curr_node->size) &&
         (iVar1 = memcmp(to_add->data,curr_node->data,to_add->size), iVar1 == 0)) {

If this check fails, the code jumps to

add_obj(to_add,local_10);

However, local_10 is never assigned up to this point, meaning that it takes on the value of some unintialized stack variable. How convenient that the previous function lets us read 100 bytes to the stack. It’s almost as if it was intentionally left in there…

At this point, you’re probably wondering why there’s cryptography in a binary exploitation challenge. Luckily, I had some members in my team who were far better than me at crypto, and one of them easily found a sha1 collision. You can also use the strings in this writeup. For the files I used, refer to 1.txt and 2.txt.

# Exploitation

The second vulnerability gives us a limited write primitive. More formally, we get to control the 2nd parameter to 0x100b0c, the add_node function.

However, closer analysis reveals that this is actually quite limited. We are only able to overwrite null pointers, due to the additional checks before every assignment.

      if (curr_node->left == (astruct *)0x0) {
        curr_node->left = to_add;
        return;
      }

The crucial observation to make here is that we can overwrite the fd pointer of a freed tcache chunk. If there is only one chunk in a tcache bin, the fd pointer will be null. This allows us to append the to_add node variable, or a malloc(0x38) chunk, onto any tcache bin.

By appending this 0x40 (malloc(0x38) results in a chunk of size 0x40) chunk onto a tcache bin of larger size, say 0x270, we are able to get a heap overflow. When we malloc for a chunk of size 0x270, the actual size of the chunk returned will be 0x40, allowing us to overflow the chunk and modify subsequent chunks.

Getting a libc leak is still quite difficult at this point however, mainly due to the rather contrived construction of chunks and hashes. The general idea is to malloc and free a large enough chunk such that the chunk avoids the tcache and goes into the unsorted bin. Then, by overflowing into the hash of a chunk, we can extend the hash to include the fd pointer of the unsortedbin chunk.

Note that the show function only checks the first 20 bytes. Thus, we are able to leak a libc address through puts.

iVar1 = memcmp(to_add,curr_node,0x14);

In order to avoid breaking the heap after the libc leak however, we need to do some additional manipulations. For one, I chose hashes such that the structure of the binary search tree was as simple as possible. This allowed me to immediately delete the root after leaking the libc address to avoid any additional complications.

In addition, I overwrote the size header of another free chunk concurrently with the libc leak. This allowed me to malloc into it after freeing to get another heap overflow. With this heap overflow and a libc leak, I could easily modify a fd pointer of an existing free chunk to point to __free_hook.

One neat trick to save time, especially with tcache exploits, is to overwrite to __free_hook - 8 with "/bin/sh\x00" + p64(system). This allows you to immediately free the chunk, getting a shell without having to worry about the rest of the heap.