CSAW CTF Finals were held from 9-11th Nov. We (chaitan94, jaiverma and sudhackar) participated as a team and finished overall 14th globally. We solved a couple of RE challenges together. So this will be a writeup on how we tackled the interesting ones.

### Rabbithole

`ReversingrabbitholeHow far down the rabbit hole can you go?150 points 46 solves`

This task had many solves from the start of the CTF, so we gave this one a try.

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

The RE part was quite easy with the symbols. We tried to do this the way it was meant to be solved.

The check algorithm was someting like this

`for(i=0; i<59; ++i){ flag &= check_value(input[i], roots[i])}`

where roots was an array of pointers to a struct that looked something like

struct node{ uint64_t ret; char check[8]; struct node * left; struct node * right;}

which we reversed from the `check_value`

function.

char check_value(unsigned __int8 input, __int64 roots){ while ( !*(_BYTE *)roots ) { if ( *(_BYTE *)(roots + 8) > input || *(_BYTE *)(roots + 9) <= input ) roots = *(_QWORD *)(roots + 24); else roots = *(_QWORD *)(roots + 16); } return *(_BYTE *)(roots + 8);}

So the `roots`

is an array of pointers to roots of fully formed binary trees where the leaves contain the return value. Traversing right or left is chosen from the 2 chars in `struct node`

from `node->check[0]`

and `node->check[1]`

. Based on where the input lies compared to both the traversal continues left or right.

In order to get correct char for `i`

position, pick the root of the tree from `roots[i]`

and traverse the tree until you find a leaf that returns `true`

. Using the path from from root to that leaf we can get constraints on the char. Sounds easier than done. Using `pwntools`

I parse the elf, build the trees and set constraints to a z3 solver.

from pwn import *class Node(object): def __init__(self, addr): self.addr = addre = ELF("./rabbithole")name_addr = {}for i in e.symbols: if "node" in i: name_addr[e.symbols[i]] = iname_addr[0] = "leaf"roots = []idx = 0for idx in xrange(59): addr = u64(e.read(e.symbols['roots']+(idx*8),8)) root = Node(addr) roots.append(root)tree = {}def form_dict(root): if not root: return chk = ord(e.read(root,1)) l = u64(e.read(root+(8*2),8)) r = u64(e.read(root+(8*3),8)) a,b = ord(e.read(root+8,1)), ord(e.read(root+9,1)) tree[root] = (l,r,a,b,chk) if not all((l,r)): return form_dict(r) form_dict(l)for idx in xrange(59): form_dict(roots[idx].addr)success("Trees formed")def print_tree(head): lvl = [head] while lvl: nxt = [] for node in lvl: print name_addr[node], if node in tree: nxt.append(tree[node][0]) nxt.append(tree[node][1]) print lvl = nxt# print_tree(roots[0].addr)from z3 import *for i in xrange(59): globals()['a%i' % i]=BitVec('a%i' %i,32)solver = Solver()def parse_forz3(idx, root, s): for i in s: if i=="L": solver.add(globals()['a%i' % idx] >= tree[root][2]) solver.add(globals()['a%i' % idx] < tree[root][3]) root = tree[root][0] if i=="R": solver.add(Or(globals()['a%i' % idx] < tree[root][2],(globals()['a%i' % idx] >= tree[root][3]))) root = tree[root][1]def preorder_solve(idx, root, gs): if not root: return if tree[root][2] == 1 and tree[root][4] == 1: parse_forz3(idx, roots[idx].addr, gs) if tree[root][0]: preorder_solve(idx, tree[root][0], gs+"L") if tree[root][1]: preorder_solve(idx, tree[root][1], gs+"R")success("Traversing and adding constraints")for i in xrange(59): preorder_solve(i, roots[i].addr,"")print solver.check()if solver.check() != sat: sys.exit(-1)modl=solver.model()flag=""for i in xrange(59): obj=globals()['a%i' % i] c=modl[obj].as_long() flag += chr(c)print flag

### Rusty Road

`ReversingA Rusty RoadTraverse these roads, win and obtain the flagnc reversing.chal.csaw.io 8079200 points 30 solves`

As the name suggests rusty road was a challenge compiled to a rust binary and both dynamic and static analysis took a lot of pain.

`$ ll rusty_road-rwxr-xr-x 1 sudhakar payatu 4.4M Nov 10 19:44 rusty_road$ file rusty_roadrusty_road: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=31fdd9bc87746e5c58d8e27aca66103474967751, not stripped`

A 4MB binary has a lot of code, however due to names in the binary it was quite easy to figure out what the code was doing. All the related functions were put in a `main`

class. `board_algo`

, `get_path`

, `main`

, `traverse`

and `win`

were in functions needed to understand the challenge.

`main`

starts by initialiing a `maps`

HashMap and getting user input from `get_path`

. Then mapping for “UDLR” chars are created in `maps`

. `board_algo`

is then called to initialize the setup. What it did was create a 10×10 size grid like the first quadrant. The initial position is set to `0,0`

with target being `9,9`

. User could input a combination of UDLR to reach `9,9`

. However there was a catch, in `board_algo`

every move you make gives you some score which is based on the x and y coordinates of the cell and the move you made previously. This score is summed for all moves you have made once you reach the target. This is then compared to a magic number 0x622c.

The grid was initialized with prime numbers and the score awarded was a function as such

`f(x,y,move)`

This was achieved using the `maps`

HashMap in the binary.

So I dumped it out after undersanding the data structure and quickly coded an all python version of the binary.

`dump binary memory U 0x7ffff6c2a080 0x7ffff6c2a300dump binary memory R 0x7ffff6c2a580 0x7ffff6c2a800dump binary memory L 0x7ffff6c2a800 0x7ffff6c2aa80dump binary memory D 0x7ffff6c2a300 0x7ffff6c2a580`

from pwn import *h ={"U":[[] for i in xrange(10)], "D":[[] for i in xrange(10)], "L":[[] for i in xrange(10)], "R":[[] for i in xrange(10)]}U = open("U","rb")D = open("D","rb")L = open("L","rb")R = open("R","rb")for i in xrange(10): for j in xrange(0x10): h["U"][i].append(u32(U.read(4)))for i in xrange(10): for j in xrange(0x10): h["D"][i].append(u32(D.read(4)))for i in xrange(10): for j in xrange(0x10): h["L"][i].append(u32(L.read(4)))for i in xrange(10): for j in xrange(0x10): h["R"][i].append(u32(R.read(4)))def f(dirn, x, y): return h[dirn][y][x]def get_sum(s): x, y = 0, 0 pathsum = 2 for i in s: # print pathsum if i == "U": y += 1 y %= 10 elif i == "D": if y > 0: y -= 1 elif i == "R": x += 1 x %= 10 elif i == "L": if x > 0: x -= 1 pathsum += f(i,x,y) return pathsum

The problem simplified to writing a combination of top 400 prime numbers following rules from the board so that their sum is 0x622c. This looked like a dp problem at first. I let my teammate come up with a memoized version while I ran a simple brute force.

from itertools import *for i in product("UR",repeat=18): if get_sum(i) == 0x622c and i.count("U")==i.count("R"): print ''.join(i)

This gave me 14 correct answers in a couple of seconds which gave us the flag.

### 48-bit bomb lab

`Reversing48-bit bomb labIts just another bomb lab.NOTE: The flag in the binary is a placeholder. Please run against the remote system to get the real flag!nc reversing.chal.csaw.io 4309300 points 16 solves`

This challenge was problematic to reverse because neither IDA nor gdb was disassembling it properly. The binary was switching between 32-bit and 64-bit modes during execution which was causing a problem.

`$ file yeetlab_releaseyeetlab_release: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=9d345605e0aef4c604da1b92f435b44b2ab7ceda, stripped`

We searched the internet and found a debugger for user-mode binary applications running in long mode. This debugger was properly disassembling the instructions and we were good to go. You can download the debugger here: fdbg. The challenge consists of 3 phases. Each phase accespts input from stdin and validates the input against some checks.

The first phase prints a prompt to the screen and asks the user for input using a call to fgets. This is done in 32-bit mode. Then the program jumps to long mode.

pwndbg> x/24i 0x0804864b 0x804864b: push ebp 0x804864c: mov ebp,esp 0x804864e: sub esp,0x38 0x8048651: mov eax,gs:0x14 0x8048657: mov DWORD PTR [ebp-0xc],eax 0x804865a: xor eax,eax 0x804865c: sub esp,0xc 0x804865f: push 0x8048b58 0x8048664: call 0x80484e0 <[email protected]> 0x8048669: add esp,0x10 0x804866c: sub esp,0xc 0x804866f: push 0x8048b84 0x8048674: call 0x80484e0 <[email protected]> 0x8048679: add esp,0x10 0x804867c: mov DWORD PTR [ebp-0x38],0x1 0x8048683: mov eax,ds:0x804a040 0x8048688: sub esp,0x4 0x804868b: push eax 0x804868c: push 0x22 0x804868e: lea eax,[ebp-0x34] 0x8048691: push eax 0x8048692: call 0x80484a0 <[email protected]> 0x8048697: add esp,0x10 0x804869a: jmp 0x33:0x80486a1 <-- switches to long mode here

The string the user input is compared to is moved into r8.

`$ ./fdbg yeetlab_release00000000F76FFA20 > mov eax,espb 80486BCgWelcome to the 48 bit binary bomb!Lets start off easy with a simple strcmp!Fun fact: the proper past tense for 'yeet' is 'yote'aaaaaaabbbbbbbbcccccccdddddddd00000000080486BCSoftware breakpoint hit at address 00000000080486BCh, BP removed O.K.00000000080486BC > mov r8,08048AE0d 08048AE00000000008048AE0: 276F6D61-65207761-206D6F75-20736869 'omae wa mou shi0000000008048AF0: 6E646569-72752720-274E414E-49213F27 ndeiru' 'NANI!?'0000000008048B00: 00000000-70686173-655F325F-73656372 ....phase_2_secr0000000008048B10: 65745F70-61737321-21212100-00000000 et_pass!!!!.....0000000008048B20: FB860408-00000000-23000000-00000000 ........#.......0000000008048B30: 00000000-636FF286-04080000-00002300 ....co........#.0000000008048B40: 00000000-00000000-C4880408-00000000 ................0000000008048B50: 23000000-00000000-4C657473-20737461 #.......Lets sta`

So the key for the first phase is: ‘omae wa mou shi ‘uriedn’NANI!?’

The second phase asks for a number as input and performs some checks on it.

$ ./fdbg yeetlab_release00000000F76E8A20 > mov eax,espc 000000000804879C000000000804879C mov r9,rdi000000000804879F mov r10,rsi00000000080487A2 mov rcx,r900000000080487A5 and rcx,0000FF0000000000080487AC shr rcx,0800000000080487B0 xor rdx,rdx00000000080487B3 mov rax,rcx00000000080487B6 mov rcx,00000019c00000000080487BD div rcx00000000080487C0 xor r11,r1100000000080487C3 mov rcx,r900000000080487C6 and rcx,00FF000000000000080487CD shr rcx,1000000000080487D1 movsx rcx,cl00000000080487D5 movzx r8,byte [r10+rcx*1]00000000080487DA add r11,r8c00000000080487DD mov rcx,r900000000080487E0 mov r12,00000000FF00000000000000080487EA and rcx,r1200000000080487ED shr rcx,1800000000080487F1 movsx rcx,cl00000000080487F5 movzx r8,byte [r10+rcx*1]00000000080487FA add r11,r800000000080487FD mov rcx,r9c0000000008048800 mov r12,000000FF00000000000000000804880A and rcx,r12000000000804880D shr rcx,200000000008048811 movsx rcx,cl0000000008048815 movzx r8,byte [r10+rcx*1]000000000804881A add r11,r8000000000804881D mov rcx,r90000000008048820 mov r12,0000FF0000000000c000000000804882A and rcx,r12000000000804882D shr rcx,280000000008048831 movsx rcx,cl0000000008048835 movzx r8,byte [r10+rcx*1]000000000804883A add r11,r8000000000804883D mov rcx,r90000000008048840 mov r12,00FF000000000000000000000804884A and rcx,r12c000000000804884D shr rcx,300000000008048851 movsx rcx,cl0000000008048855 movzx r8,byte [r10+rcx*1]000000000804885A add r11,r8000000000804885D mov rcx,r90000000008048860 and rcx,000000FF0000000008048867 movzx r8,byte [r10+rcx*1]000000000804886C and r8,08c0000000008048870 cmp r8,080000000008048874 jnz 000000000804887F0000000008048876 mov rax,00000001000000000804887D jmp 0000000008048886000000000804887F mov rax,000000060000000008048886 mov rdi,00000001000000000804888D mov rsi,08048B040000000008048894 cmp r11,000001F2c000000000804889B jnz 00000000080488A1000000000804889D syscall000000000804889F jmp 00000000080488A300000000080488A1 int 8000000000080488A3 ret00000000080488A4 mov rax,[rsp]00000000080488A8 ret

The first check consists of dividing the second least significant byte of our input with 0x19. The quotient is stored in rax and the remainder in rdx. Therefore, based on our input, we can vary rdx which will be useful for the next phase.

The remaining bytes of our input except the most significant byte are used as indexes in a hardcoded array present in the binary. Since our input bytes are sign extended and used as an index, the range for array access is [array-128, array+127].

The contents of the array are:

`[190, 201, 77, 15, 182, 4, 10, 77, 1, 195, 76, 137, 201, 73, 188, 0, 0, 0, 0, 0, 0, 255, 0, 76, 33, 225, 72, 193, 233, 48, 72, 15, 190, 201, 77, 15, 182, 4, 10, 77, 1, 195, 76, 137, 201, 72, 129, 225, 255, 0, 0, 0, 77, 15, 182, 4, 10, 73, 131, 224, 8, 73, 131, 248, 8, 117, 9, 72, 199, 192, 1, 0, 0, 0, 235, 7, 72, 199, 192, 6, 0, 0, 0, 72, 199, 199, 1, 0, 0, 0, 72, 199, 198, 4, 139, 4, 8, 73, 129, 251, 242, 1, 0, 0, 117, 4, 15, 5, 235, 2, 205, 128, 195, 72, 139, 4, 36, 195, 103, 72, 139, 125, 192, 232, 241, 255, 255, 255, 72, 137, 198, 232, 225, 254, 255, 255, 46, 72, 255, 44, 37, 72, 139, 4, 8, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 131, 236, 12, 104, 32, 140, 4, 8, 232, 1, 252, 255, 255, 131, 196, 16, 161, 64, 160, 4, 8, 131, 236, 4, 80, 106, 24, 141, 69, 220, 80, 232, 170, 251, 255, 255, 131, 196, 16, 131, 236, 8, 104, 4, 139, 4, 8, 141, 69, 220, 80, 232, 134, 251, 255, 255, 131, 196, 16, 133, 192, 117, 7, 184, 1, 0, 0, 0, 235, 5, 184, 0, 0, 0, 0, 139, 85, 244, 101, 51, 21, 20, 0, 0, 0, 116, 5, 232, 146, 251, 255, 255, 201, 195, 141, 76, 36]`

The sum is stored in r11 and compared to 0x1f2.

The last check decides whether to perform a 64-bit or 32-bit system call. Based on our input, we have the option of performing the following syscalls:

`1. write (64-bit) if eax=12. exit (32-bit) if eax=13. lstat (64-bit) if eax=64. close (32-bit) if eax=6`

The key for the next phase is stored in rsi and we can leak it if we execute the write syscall. Therefore, we want eax to contain 0x1 for which we need the least significatnt byte to have its 4’th least significant bit set. As rdx is used as a length parameter in the write syscall, we can control rdx using the second least significant byte in the first division check.

%rax | System call | %rdi | %rsi | %rdx |
---|---|---|---|---|

1 | sys_write | unsigned int fd | char *buf | size_t count |

A number which satisfies these checks is 0x6060606c05300b (27127565009629195).

Inputting this number as the key for the second phase passes the checks and prints out the key for the final phase!

`$ ./yeetlab_releaseWelcome to the 48 bit binary bomb!Lets start off easy with a simple strcmp!Fun fact: the proper past tense for 'yeet' is 'yote''omae wa mou shi 'uriedn'NANI!?'Nice work!Nice work with strings, let's try numbers now.gib number:27127565009629195Phase 2 passphrase being moved into rsiphase_2_secret_pass!!!!What's the passphrase:phase_2_secret_pass!!!!I like that number!`

Note that the key for the final phase is different for the binary running on the challenge server.

Finally this gives us the flag: flag{turns_out_heavens_gate_works_on_linux_too_yote}

See you next year