CSAW CTF Finals 2017 WriteUps

Sudhakar-Verma

21/11/2017

CSAW CTF Finals 2017 WriteUps

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 net year CSAW!

Latest news See all news

28-December-2019
Leipzig, Germany

Visit

Nikhil Mittal will be speaking at CCC events on the topic breaking Microsoft edge extensions security policies 

29-November-2019
Seoul, Korea

Visit

Ashfaq Ansari a.k.a &#34;HackSysTeam&#34;, will be delivering Windows Kernel Exploitation Training.

09-October-2019
Delhi, India

Visit

Sudhakar Verma and Krishnakant Patil will be delivering 2 days training on Reverse Engineering at NULLCON Delhi 2019.