Matriochka
[Nuit du Hack Qualifiers, 2016]
- Category: Crack Me
- Points: 50, 100, 300, 500
- Description:
Can you help me?
Recently, I found an executable binary.
As I'm a true newbie,
Certainly, to solve it, I will have difficulties.
Keep in mind, the first step is quite easy.
Maybe the last one will be quite tricky.
Emulating it could be a good idea.
The challenge is available at : http://static.quals.nuitduhack.com/stage1.bin
Write-up
So we started of with a binary and a vague description. We could see that there are 4 challenges in the scoreboard, which are all called Matriochka. We are not given a binary for the stages 3-4. As it turns out, each of the stages printed the next stage, when given the right password as command line argument.
Stage 1
This one was pretty easy: strings. My colleagues already solved this one when I started playing.
[0x00400560]> iz
[...]
vaddr=0x0040e062 paddr=0x0000e062 ordinal=4719 sz=23 len=22 section=.rodata type=ascii string=2$^HxUsage: %s <pass>\n
vaddr=0x0040e079 paddr=0x0000e079 ordinal=4720 sz=26 len=25 section=.rodata type=ascii string=Much_secure__So_safe__Wow
vaddr=0x0040e093 paddr=0x0000e093 ordinal=4721 sz=12 len=11 section=.rodata type=ascii string=Good good!\n
vaddr=0x0040e09f paddr=0x0000e09f ordinal=4722 sz=14 len=13 section=.rodata type=ascii string=Try again...\n
There were a lot of other weird strings, probably the next stage.
So let's try Much_secure__So_safe__Wow.
./stage1.bin Much_secure__So_safe__Wow 2>./stage1_out.base64
Good good!
On stderr we get some base64 encoded data, which turns out to be the next stage.
$ cat ./stage1_out.base64 | base64 -d | tar x
$ file stage2.bin
stage2.bin: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=7b2fd52d0de50c9e575793a0fd17fdd2574c5c53, stripped
Stage 2
Stage 2 again validates a password. If we look at the Control Flow Graph of the
main function (using radare VV and zooming out)
<@@@@@@>
t f
.------' '------.
| |
| |
[_072d_] [_0708_]
f t v
.-----'.' .--'
| | |
| | |
[_076b_] | |
f t | |
.----'.' | |
| | | |
| | | |
[_0784_] | | |
v | | |
'----. '. | |
| | | |
| | | |
[_078b_] | |
[...]
[_093e_] | | |
v | | |
'----. '. | |
| | | |
| | | |
[_0945_] | |
f t | |
.----'.' | |
| | | |
| | | |
[_0978_] | | |
v | | |
'----. '. | |
| | | |
| | | |
[_097f_] | |
f t | |
.------' '--. '-. |
| | | |
| | | |
[_0985_] [_099a_] |
v v |
'-----------.-----------'
|
|
[_09b3_]
We can see a very clear pattern. If we take a look at the first part
[0x0040076b 5% 230 stage2.bin]> pd $r @ main+121 # 0x40076b
│ 0x0040076b c745ec010000. mov dword [rbp - local_14h], 1
│ 0x00400772 488b45d0 mov rax, qword [rbp - local_30h]
│ 0x00400776 4883c008 add rax, 8
│ 0x0040077a 488b00 mov rax, qword [rax]
│ 0x0040077d 0fb600 movzx eax, byte [rax]
│ 0x00400780 3c50 cmp al, 0x50 ; 'P'
│ ┌─< 0x00400782 7407 je 0x40078b ;[1]
│ │ 0x00400784 c745ec000000. mov dword [rbp - local_14h], 0
│ │ ; JMP XREF from 0x00400782 (main)
│ └─> 0x0040078b 488b45d0 mov rax, qword [rbp - local_30h]
[...]
Basically here the first byte of the passed argument is checked and if it isn't
equal to P then 0 is written to [rbp - local_14h]. At the end of the
program if this is 1, the password is validated.
So I reversed the first three characters of the password, but then it got annoying. There must be a better. Now I always wanted to try angr , a symbolic/concolic execution framework by the shellphish guys. I never used it so I read some examples and quickly whipped up a script to solve this challenge:
#!/usr/bin/env python
import angr
import claripy
def long_to_str(l):
"""We get the bitvector as a python long and we need to convert it"""
x = []
while l != 0:
x.append(chr(l & 0xff))
l = l >> 8
return "".join(x)[::-1]
p = angr.Project("./stage2.bin")
# avoid the BBs that do
# mov dword [rbp - local_14h], 0
avoids = [0x400784,
0x4007a9,
0x4007e0,
0x400826,
0x400855,
0x400884,
0x4008b8,
0x4008e7,
0x400904,
0x40093e,
0x400978,
]
# target the write block
target = 0x00400993
# found through manual reversing
flaglen = 11 * 8 # in bits
# the flag is the only symbolic input
flagsym = claripy.BVS('arg1', flaglen)
# create the memory state of the program
state = p.factory.entry_state(args=['./stage2.bin', flagsym])
path = p.factory.path(state)
# launch the Explorer. angr will try to find a execution path from the
# entrypoint to the target address (the stage3 printing), while avoiding
# the basicblocks that set the found bool to 0.
# This should gather enough constraints on the symbolic flag, that there is
# only one possible input to trigger that path.
ex = p.surveyors.Explorer(find=(target, ), avoid=avoids, start=path)
ex.run()
if len(ex.found) > 0:
#print "Found path:", ex.found[0]
for flag in ex.found[0].state.se.any_n_int(flagsym, flaglen):
print "possible flag:"
print flag
print long_to_str(flag)
else:
print "Nothing found :("
Let's see the output:
$ python solve_stage2_angr.py
possible flag:
97174171495276010235913313
Pandi_panda
$ ./stage2.bin Pandi_panda 2>stage2_out.base64
Good good!
$ cat ./stage2_out.base64 | base64 -d > stage3.bin
done :)
Stage 3
This is a very interesting binary. Instead of using normal calls, the binary uses signal handlers to perform control transfers.
[0x0040114b 23% 230 stage3.bin]> pd $r @ main+90 # 0x40114b
│ 0x0040114b befd074000 mov esi, sub.signal_7fd ; "UH..H.. .}.....8 " @ 0x4007fd
│ 0x00401150 bf0b000000 mov edi, 0xb
│ 0x00401155 e866f5ffff call sym.imp.signal ;[3]
│ 0x0040115a be50104000 mov esi, sub.fwrite_50 ; "UH..H.. .}.H..>0 " @ 0x401050
│ 0x0040115f bf08000000 mov edi, 8
│ 0x00401164 e857f5ffff call sym.imp.signal ;[3]
If we look at the first signal handler, we can see that it registers another signal handler.
[0x00400836 11% 230 stage3.bin]> pd $r @ sub.signal_7fd+57 # 0x400836
│ 0x00400836 817dfce70300. cmp dword [rbp - local_4h], 0x3e7 ; [0x3e7:4]=0
│ ┌─< 0x0040083d 7e09 jle 0x400848 ;[1]
│ │ 0x0040083f 817dfce80300. cmp dword [rbp - local_4h], 0x3e8 ; [0x3e8:4]=0
│ ┌──< 0x00400846 7e02 jle 0x40084a ;[2]
│ ││ ; JMP XREF from 0x0040083d (sub.signal_7fd)
│ ┌─└─> 0x00400848 eb10 jmp 0x40085a ;[3]
│ ││ ; JMP XREF from 0x00400846 (sub.signal_7fd)
│ │└──> 0x0040084a be5c084000 mov esi, sub.signal_85c ; "UH..H.. .}..E." @ 0x40085c
│ │ 0x0040084f bf0b000000 mov edi, 0xb
│ │ 0x00400854 e867feffff call sym.imp.signal ;[4]
In total there are 22 signal handlers, which register the next signal handler on success.
> afl~signal_ | wc -l
21
fcn.0040100e is the last signal handler, which doesn't register another
signal handler. I don't know why radare didn't rename this one. So we can
assume that the password will be 22 bytes long, since every signal handlers
seems to check exactly one byte.
Using angr again is probably gonna take a
little work. Just launching an Explorer like in the previous example results
in some error, that a syscall is not implemented. I assume it's the signaling.
We could somehow patch the binary, or hook the signal calls. After some
brainstorming with a colleague, we thought that there might be some
"side-channel", we can use the bruteforce the flag byte by byte. So I
experimented with strace a little. The first thing I noticed is that there
are always 1023 calls to kill, triggering a segfault. We can confirm this
using radare, that this happens in the main function.
$ strace ./stage3.bin asdf 2>&1 | grep kill | wc -l
1024
We can also get the number of registered signals using strace:
$ strace ./stage3.bin asdf 2>&1 | grep sigaction | wc -l
2
These are the two calls to signal in the main function. If we guess a
character right we should see one more call to signal. So I whipped up a
quick shell three-liner:
$ for x in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 '{' '}' '!' '@' '#' '$' '%' '^' '&' '*' '(' ')' '-' '-' '_' '+' '=' '[' ']' '.' ';' '\\' '/' ',' '<' '>' '`' '~' "'" '"' '?'; do
echo "= $x ="; strace ./stage3.bin "$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x$x" 2>&1 | grep sigaction | wc -l
done > log; cat log | grep -B 1 "$(cat log | grep -v = | sort | uniq | tail -n 1)"
= D =
3
--
2
= 3 =
So we got the first character. I replaced the first $x with D and on to the
next character.
for x in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 '{' '}' '!' '@' '#' '$' '%' '^' '&' '*' '(' ')' '-' '-' '_' '+' '=' '[' ']' '.' ';' '\\' '/' ',' '<' '>' '`' '~' "'" '"' '?'; do
echo "= $x ="; strace ./stage3.bin "Did_you_like_signals$x" 2>&1 | grep sigaction | wc -l
done > log; cat log | grep -B 1 "$(cat log | grep -v = | sort | uniq | tail -n 1)"
= ? =
23
So the flag is Did_you_like_signals?. I feel dirty now.
$ ./stage3.bin 'Did_you_like_signals?' 2>stage3_out.base64
Good good! Now let's play a game...
$ cat stage3_out.base64 | base64 -d > stage4.bin
Stage 4
Unfortunately time ran out, so I didn't solve the challenge in time.
$ file stage4.bin
stage4.bin: DOS/MBR boot sector
$ qemu-system-i386 ./stage4.bin
...and we are presented with the following prompt:
