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'
else:
nx = 's'
elif st == 'b':
tmp = fib(m)
res += tmp
if tmp % 3 == 0:
res += 1
nx = 's'
else:
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'
else:
nx = 'f'
else:
print('WTF: unknown state?')
st = nx
m -= 1
if m % 10000 == 0:
print(st, m, res)
print('9447{{{}}}'.format(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
9447{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
flag:
9447{94ea5e32f2b5b37d947eea3a38932ae1}