9447 CTF 2015: rev[1|70|100|160]

This bulk-writeup briefly describes the solutions for the four simpler reverse engineering tasks of the 9447 CTF 2015.

rev1 (flag-finder)

Originally being worth 70 points, we figure some drunk orga let the flag just lying around in the binary. If you execute the program and supply an arbitrary string to it, it first complains and then gives you the flag:

% flagfinder 123
Try again
9447{C0ngr47ulaT1ons_p4l_buddy_y0Uv3_solved_the_H4LT1N6_prObL3M_n1c3_} 1000024

Thanks, I’ll take great care of it! :)

rev70 (the-real-flag-finder)

Shortly thereafter another flagfinder binary appeared. This time it wouldn’t simply print the flag but after a few seconds of static analysis one could immediately tell that the program takes some hardcoded string, transforms it and compares the result to the input, meaning that we could simply break on the final comparison and examine the decoded string: (We still wonder if this was the real “fixed” binary or if there happened another mistake on the orga’s side as usually one would have expected the input to be transformed and compared to the hardcoded secret.)

% objdump -dMintel flagFinderRedux | grep memcmp
0000000000400500 <memcmp@plt>:
400703: e8 f8 fd ff ff        call   400500 <memcmp@plt>
400729: e8 d2 fd ff ff        call   400500 <memcmp@plt>
% gdb ./flagFinderRedux
gdb-peda$ b *0x400729
gdb-peda$ b *0x400703
gdb-peda$ r 123
Starting program: flagFinderRedux 123
Breakpoint 1, 0x0000000000400729 in ?? ()
gdb-peda$ x/s $rdi
0x7fffffffdc20: "9447{C0ngr47ulaT1ons_p4l_buddy_y0Uv3_solved_the_re4l__H4LT1N6_prObL3M}"

rev100 (danklang)

The challenge consists of a script called main.dc containing a program written in greentext. After translating the program in a 1:1 manner to python, we recognized that the only purpose of the script was to print the flag by calling a function called epicfail with the argument 94471337 and printing the result. Running the translated python script yielded an overflow of python’s internal call stack as the functions contained in the program recursively called each other. Additionally program execution was extremely slow due to the fail, dootdoot and brotherman function being much too inefficient. A careful examination of those three function made clear that their purpose was to check whether a number is prime, to generate the binomial coefficient $\binom{n}{5}$ (thanks, google :) ) and to calculate the $n$th fibonacci number modulo $987654321$. After replacing all three functions with more performant implementations we still needed to solve the call stack overflow. We admittedly got stuck there for several hours until we realized that the way the recursive functions worked (obviously) could be interpreted as a state machine. Another five minute implementation task yielded the following python script that printed the correct flag on the first try! (Sorry for the super ugly code, but what would you expect, starting from a meme-based esolang? :) )

% cat calc.py
#!/usr/bin/env python3

import sys
import gmpy2

def fib(n): ## Thanks, author of the "Fibbed" challenge :)
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = (v1*v1+calc) % 987654321, ((v1+v3)*v2) % 987654321, (calc+v3*v3) % 987654321
        if rec=='1': v1, v2, v3 = (v1+v2) % 987654321, v1, v2
    return v2 % 987654321

## magic number
m = 13379447
## Result sum
res = 0
## Current state (f = epicfail, b = bill, s = such)
st = 'f'

while m > 0:
    if st == 'f':
        if gmpy2.is_prime(m):
            res += 1
            nx = 'b'
            nx = 's'
    elif st == 'b':
        tmp = fib(m)
        res += tmp
        if tmp % 3 == 0:
            res += 1
            nx = 's'
            nx = 'f'
    elif st == 's':
        ## highly optimized C(n, 5) ;)
        tmp = m*(m-1)*(m-2)*(m-3)*(m-4) // 120
        res += tmp
        if tmp % 7 == 0:
            res += 1
            nx = 'b'
            nx = 'f'
        print('WTF: unknown state?')

    st = nx
    m -= 1
    if m % 10000 == 0:
        print(st, m, res)

% time ./calc.py
<% ... lots of prints ... %>
s 120000 2992959519894312914730848199083196302781
f 110000 2992959519894939307534380539116858393558
s 100000 2992959519895336863918309443590774480085
b 90000 2992959519895577556474413782572040912892
s 80000 2992959519895715573819681076539112881975
b 70000 2992959519895789722556456140079549446425
b 60000 2992959519895826277029539385865861038899
s 50000 2992959519895842195529951510593646903295
f 40000 2992959519895848106957272894690447214361
s 30000 2992959519895849827884771197661961635736
s 20000 2992959519895850168373259893694627187589
f 10000 2992959519895850200515425765461215417689
s 0 2992959519895850201020616334426464120987
./calc.py  46,98s user 0,00s system 99% cpu 47,013 total

rev160 (hellojoe)

Another binary that would ask for an flag in argv[0] and verify the result. We see six checker functions being called in random order to verify if the input is correct. Each of the checker functions allows a certain set of characters at each position of the input string, so the flag is simply the intersection of all sets. Quickly grepping out the characters at the different positions manually yields the following table (empty means “any character allowed”) and the flag (and yes, I know there’s z3, and yes, I know there’s angr either, but I needed a brainless zombie task to perform at night at 2 am and this one seemed like a perfect match (besides we were 2nd to solve this challenge :) )):

s0  s1  s2  s3  s4  s5  intersection
9                       9
4                       4
4                       4
7                       7
{                       {
        29f 79b     189 9
        14c 47f     04f 4
    5de 16e     7ef     e
    aef         02a 9ae a
        59a 5ab 57b     5
        19e ade     5ae e
    023         038 36e 3
    27d 278     02e     2
        78f 57f     8cf f
            23b 2bf 269 2
    bdf 57b bdf         b
            358 35d 5ef 5
        abe abf 7be     b
        35d     35b 349 3
        7af 67f 7de     7
    25d     bdf     6cd d
        49b 9ae     39e 9
    24a     49a     14d 4
    17d 67f     79a     7
        2ce 9de     25e e
    3ef     16e 47e     e
    18a 7ae 13a         a
        39b 34a     3bf 3
    59a 1ad         2af a
        37a 136 3ad     3
    078         28c 078 8
    49a 29d         79b 9
    39f 037         023 3
    236     26e     24b 2
        7ad 34a     ade a
    8ce 78e     2ce     e
    145     179     1be 1
}                       }
\0  \0  \0  \0  \0  \0  \0