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
Reversing
rabbithole
How 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 rabbithole
rabbithole: 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 = addr
e = ELF("./rabbithole")
name_addr = {}
for i in e.symbols:
if "node" in i:
name_addr[e.symbols[i]] = i
name_addr[0] = "leaf"
roots = []
idx = 0
for 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
Reversing
A Rusty Road
Traverse these roads, win and obtain the flag
nc reversing.chal.csaw.io 8079
200 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_road
rusty_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 0x7ffff6c2a300
dump binary memory R 0x7ffff6c2a580 0x7ffff6c2a800
dump binary memory L 0x7ffff6c2a800 0x7ffff6c2aa80
dump 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
Reversing
48-bit bomb lab
Its 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 4309
300 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_release
yeetlab_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_release
00000000F76FFA20 > mov eax,esp
b 80486BC
g
Welcome to the 48 bit binary bomb!
Lets start off easy with a simple strcmp!
Fun fact: the proper past tense for 'yeet' is 'yote'
aaaaaaabbbbbbbbcccccccdddddddd
00000000080486BC
Software breakpoint hit at address 00000000080486BCh, BP removed O.K.
00000000080486BC > mov r8,08048AE0
d 08048AE0
0000000008048AE0: 276F6D61-65207761-206D6F75-20736869 'omae wa mou shi
0000000008048AF0: 6E646569-72752720-274E414E-49213F27 ndeiru' 'NANI!?'
0000000008048B00: 00000000-70686173-655F325F-73656372 ....phase_2_secr
0000000008048B10: 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_release
00000000F76E8A20 > mov eax,esp
c 000000000804879C
000000000804879C mov r9,rdi
000000000804879F mov r10,rsi
00000000080487A2 mov rcx,r9
00000000080487A5 and rcx,0000FF00
00000000080487AC shr rcx,08
00000000080487B0 xor rdx,rdx
00000000080487B3 mov rax,rcx
00000000080487B6 mov rcx,00000019
c
00000000080487BD div rcx
00000000080487C0 xor r11,r11
00000000080487C3 mov rcx,r9
00000000080487C6 and rcx,00FF0000
00000000080487CD shr rcx,10
00000000080487D1 movsx rcx,cl
00000000080487D5 movzx r8,byte [r10+rcx*1]
00000000080487DA add r11,r8
c
00000000080487DD mov rcx,r9
00000000080487E0 mov r12,00000000FF000000
00000000080487EA and rcx,r12
00000000080487ED shr rcx,18
00000000080487F1 movsx rcx,cl
00000000080487F5 movzx r8,byte [r10+rcx*1]
00000000080487FA add r11,r8
00000000080487FD mov rcx,r9
c
0000000008048800 mov r12,000000FF00000000
000000000804880A and rcx,r12
000000000804880D shr rcx,20
0000000008048811 movsx rcx,cl
0000000008048815 movzx r8,byte [r10+rcx*1]
000000000804881A add r11,r8
000000000804881D mov rcx,r9
0000000008048820 mov r12,0000FF0000000000
c
000000000804882A and rcx,r12
000000000804882D shr rcx,28
0000000008048831 movsx rcx,cl
0000000008048835 movzx r8,byte [r10+rcx*1]
000000000804883A add r11,r8
000000000804883D mov rcx,r9
0000000008048840 mov r12,00FF000000000000
000000000804884A and rcx,r12
c
000000000804884D shr rcx,30
0000000008048851 movsx rcx,cl
0000000008048855 movzx r8,byte [r10+rcx*1]
000000000804885A add r11,r8
000000000804885D mov rcx,r9
0000000008048860 and rcx,000000FF
0000000008048867 movzx r8,byte [r10+rcx*1]
000000000804886C and r8,08
c
0000000008048870 cmp r8,08
0000000008048874 jnz 000000000804887F
0000000008048876 mov rax,00000001
000000000804887D jmp 0000000008048886
000000000804887F mov rax,00000006
0000000008048886 mov rdi,00000001
000000000804888D mov rsi,08048B04
0000000008048894 cmp r11,000001F2
c
000000000804889B jnz 00000000080488A1
000000000804889D syscall
000000000804889F jmp 00000000080488A3
00000000080488A1 int 80
00000000080488A3 ret
00000000080488A4 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=1
2. exit (32-bit) if eax=1
3. lstat (64-bit) if eax=6
4. 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_release
Welcome 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:
27127565009629195
Phase 2 passphrase being moved into rsi
phase_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 CSAW!
