Title: Reversing re200 from Defcamp (D-CTF) final 2015 with radare2
Date: 2015-11-22 10:30
It has been a long time since I posted something about how to
reverse things with radare2, like crackmes, hence this writeup,
about [re200]({static}/files/defcamp2015_re200)
from the finals of the [Defcamp]( http://def.camp )'s ctf.
This challenge could have been solved with IDA and its magical `F5`
key in a couple of minutes, but I wanted to give it a try with radare2.
```nasm
$ r2 -A -b 32 -a x86 re200
-- Of course r2 runs FreeBSD
[0x00400560]> pdf
╒ (fcn) entry0 42
│ ;-- section_end..plt:
│ 0x00400560 31ed xor ebp, ebp
│ 0x00400562 4989d1 mov r9, rdx
│ 0x00400565 5e pop rsi
│ 0x00400566 4889e2 mov rdx, rsp
│ 0x00400569 4883e4f0 and rsp, 0xfffffffffffffff0
│ 0x0040056d 50 push rax
│ 0x0040056e 54 push rsp
│ 0x0040056f 49c7c0c00840. mov r8, 0x4008c0
│ 0x00400576 48c7c1500840. mov rcx, 0x400850
│ 0x0040057d 48c7c7670740. mov rdi, main
│ 0x00400584 e897ffffff call sym.imp.__libc_start_main
╘ 0x00400589 f4 hlt
[0x00400560]>
```
Nothing fancy, a classic prolog, lets see main function:
```nasm
[0x00400560]> pdf @ main
╒ (fcn) main 227
│ ; var int local_0 @ rbp-0x0
│ ; var int local_0_1 @ rbp-0x1
│ ; var int local_1 @ rbp-0x8
│ ; var int local_2 @ rbp-0x10
│ ; var int local_3 @ rbp-0x18
│ ; var int local_3_4 @ rbp-0x1c
│ ; var int local_4 @ rbp-0x20
│ ; DATA XREF from 0x0040057d (main)
│ 0x00400767 55 push rbp
│ 0x00400768 4889e5 mov rbp, rsp
│ 0x0040076b 4883ec20 sub rsp, 0x20
│ 0x0040076f c745ec000000. mov dword [rbp - 0x14], 0
│ 0x00400776 c745e0000000. mov dword [rbp-local_4], 0
│ 0x0040077d c745e4000000. mov dword [rbp-local_3_4], 0
│ 0x00400784 c745e8020000. mov dword [rbp-local_3], 2
│ 0x0040078b c745e0020000. mov dword [rbp-local_4], 2
│ ┌─< 0x00400792 e9a2000000 jmp 0x400839
│ ┌──> 0x00400797 c745e4020000. mov dword [rbp-local_3_4], 2
│ ┌───< 0x0040079e eb13 jmp 0x4007b3
│ ┌────> 0x004007a0 8b45e8 mov eax, dword [rbp-local_3]
│ ││││ 0x004007a3 99 cdq
│ ││││ 0x004007a4 f77de4 idiv dword [rbp-local_3_4]
│ ││││ 0x004007a7 89d0 mov eax, edx
│ ││││ 0x004007a9 85c0 test eax, eax
│ ┌─────< 0x004007ab 7502 jne 0x4007af
│ ┌──────< 0x004007ad eb0f jmp 0x4007be
│ │└─────> 0x004007af 8345e401 add dword [rbp-local_3_4], 1
│ │ │└───> 0x004007b3 8b45e8 mov eax, dword [rbp-local_3]
│ │ │ ││ 0x004007b6 83e801 sub eax, 1
│ │ │ ││ 0x004007b9 3b45e4 cmp eax, dword [rbp-local_3_4]
│ │ └────< 0x004007bc 7de2 jge 0x4007a0
│ └──────> 0x004007be 8b45e4 mov eax, dword [rbp-local_3_4]
│ ││ 0x004007c1 3b45e8 cmp eax, dword [rbp-local_3]
│ ┌───< 0x004007c4 756f jne 0x400835
│ │││ 0x004007c6 e835fdffff call sym.imp.clock
│ │││ 0x004007cb 488945f0 mov qword [rbp-local_2], rax
│ │││ 0x004007cf 8345e001 add dword [rbp-local_4], 1
│ │││ 0x004007d3 bf03000000 mov edi, 3
│ │││ 0x004007d8 e873fdffff call sym.imp.sleep
│ │││ 0x004007dd e81efdffff call sym.imp.clock
│ │││ 0x004007e2 488945f8 mov qword [rbp-local_1], rax
│ │││ 0x004007e6 488b45f0 mov rax, qword [rbp-local_2]
│ │││ 0x004007ea 488b55f8 mov rdx, qword [rbp-local_1]
│ │││ 0x004007ee 4829c2 sub rdx, rax
│ │││ 0x004007f1 4889d0 mov rax, rdx
│ │││ 0x004007f4 4883f813 cmp rax, 0x13
│ ┌────< 0x004007f8 7f0a jg 0x400804
│ ││││ 0x004007fa bf00000000 mov edi, 0
│ ││││ 0x004007ff e83cfdffff call sym.imp.exit
│ └────> 0x00400804 b800000000 mov eax, 0
│ │││ 0x00400809 e802ffffff call 0x400710
│ │││ 0x0040080e 3b45e0 cmp eax, dword [rbp-local_4]
│ ┌────< 0x00400811 7f22 jg 0x400835
│ ││││ 0x00400813 8b45e8 mov eax, dword [rbp-local_3]
│ ││││ 0x00400816 89c7 mov edi, eax
│ ││││ 0x00400818 e830feffff call 0x40064d
│ ││││ 0x0040081d 85c0 test eax, eax
│ ┌─────< 0x0040081f 7414 je 0x400835
│ │││││ 0x00400821 bfdb084000 mov edi, str.Well_done_ ; "Well done! " @ 0x4008db
│ │││││ 0x00400826 e8c5fcffff call sym.imp.puts
│ │││││ 0x0040082b bf00000000 mov edi, 0
│ │││││ 0x00400830 e80bfdffff call sym.imp.exit
│ └└└───> 0x00400835 8345e801 add dword [rbp-local_3], 1
│ │└─> 0x00400839 837de000 cmp dword [rbp-local_4], 0
│ └──< 0x0040083d 0f8554ffffff jne 0x400797
│ 0x00400843 b800000000 mov eax, 0
│ 0x00400848 c9 leave
╘ 0x00400849 c3 ret
[0x00400560]>
```
There are some jumps around, and we can distinguish two loops,
likely one within the other. Time to use the magical command `VV`:
```nasm
=-------------------------------------=
| [0x400767] |
| (fcn) main 227 |
| ; var int local_0 @ rbp-0x0 |
| ; var int local_0_1 @ rbp-0x1 |
| ; var int local_1 @ rbp-0x8 |
| ; var int local_2 @ rbp-0x10 |
| ; var int local_3 @ rbp-0x18 |
| ; var int local_3_4 @ rbp-0x1c |
| ; var int counter @ rbp-0x20 |
| ; DATA XREF from 0x0040057d (main) |
| push rbp |
| mov rbp, rsp |
| sub rsp, 0x20 |
| mov dword [rbp - 0x14], 0 |
| mov dword [rbp-counter], 0 |
| mov dword [rbp-local_3_4], 0 |
| mov dword [rbp-local_3], 2 |
| mov dword [rbp-counter], 2 |
| jmp 0x400839 ;[a] |
=-------------------------------------=
v
'
.--------------------------------------------.
=-----------------------------------= |
| 0x400839 | |
| cmp dword [rbp-counter], 0 | |
| jne 0x400797 ;[b] | |
=-----------------------------------= |
t f |
.------------' '------------------------. |
=------------------------------= =----------------= |
| 0x400797 | | 0x400843 | |
| mov dword [rbp-local_3_4], 2 | | mov eax, 0 | |
| jmp 0x4007b3 ;[c] | | leave | |
=------------------------------= | ret | |
v =----------------= |
' |
.-----------------------------------------------. |
=-----------------------------------= | |
| 0x4007b3 | | |
| mov eax, dword [rbp-local_3] | | |
| sub eax, 1 | | |
| cmp eax, dword [rbp-local_3_4] | | |
| jge 0x4007a0 ;[d] | | |
=-----------------------------------= | |
t f | |
| `-----------------------------------------|-----. |
=------------------------------= | | |
| 0x4007a0 | | | |
| mov eax, dword [rbp-local_3] | | | |
| cdq | | | |
| idiv dword [rbp-local_3_4] | | | |
| mov eax, edx | | | |
| test eax, eax | | | |
| jne 0x4007af ;[e] | | | |
=------------------------------= | | |
f t | | |
.-------' '-------------. | | |
=-------------------= =------------------------------=| | |
| 0x4007ad | | 0x4007af || | |
| jmp 0x4007be ;[n] | | add dword [rbp-local_3_4], 1 || | |
=-------------------= =------------------------------=| | |
v `---------------' | |
'------------------. .------------------------------------' |
=-----------------------------------= |
| 0x4007be | |
| mov eax, dword [rbp-local_3_4] | |
| cmp eax, dword [rbp-local_3] | |
| jne 0x400835 ;[f] | |
=-----------------------------------= |
t f |
| `------------------------------. |
=-------------------------------= | |
| 0x4007c6 | | |
| call sym.imp.clock ;[g] | | |
| mov qword [rbp-local_2], rax | | |
| add dword [rbp-counter], 1 | | |
| mov edi, 3 | | |
| call sym.imp.sleep ;[h] | | |
| call sym.imp.clock ;[g] | | |
| mov qword [rbp-local_1], rax | | |
| mov rax, qword [rbp-local_2] | | |
| mov rdx, qword [rbp-local_1] | | |
| sub rdx, rax | | |
| mov rax, rdx | | |
| cmp rax, 0x13 | | |
| jg 0x400804 ;[i] | | |
=-------------------------------= | |
t f | |
| `----------------------. | |
=-------------------------= | | |
| 0x4007fa | | | |
| mov edi, 0 | | | |
| call sym.imp.exit ;[m] | | | |
=-------------------------= | | |
v .---------------------' | |
| | | |
=-------------------------------= | |
| 0x400804 | | |
| mov eax, 0 | | |
| call 0x400710 ;[j] | | |
| cmp eax, dword [rbp-counter] | | |
| jg 0x400835 ;[f] | | |
=-------------------------------= | |
f t | |
.------' '---------------------. | |
=------------------------------= | | |
| 0x400813 | | | |
| mov eax, dword [rbp-local_3] | | | |
| mov edi, eax | | | |
| call 0x40064d ;[k] | | | |
| test eax, eax | | | |
| je 0x400835 ;[f] | | | |
=------------------------------= | | |
f t | | |
.--------------------------' '----------------------. | | |
=----------------------------------------------------= | | | |
| 0x400821 | | | | |
| mov edi, str.Well_done_ ; "Well done! " @ 0x4008db | | | | |
| call sym.imp.puts ;[l] | | | | |
| mov edi, 0 | | | | |
| call sym.imp.exit ;[m] | | | | |
=----------------------------------------------------= | | | |
'-----.-----' |
=----------------------------= |
| 0x400835 | |
| add dword [rbp-local_3], 1 | |
=----------------------------= |
`--------------------------------'
```
It looks way better on my terminal, but the picture would have been a bit
unreadable, and I'm way too lazy to do something clever with GIMP.
You can of course rename variables with the `afvn` command,
but since this function is pretty straightforward,
I only renamed one, `local_4` in `counter`.
The first loop
1. moves the value `2` into the variable `local_3_4`;
2. checks if `local_3_4` is inferior to `local_3`, if it isn't, it breaks;
3. check if `local_3` is divisible by `local_3_4`, with the `idiv` instruction,
which is storing the result in `eax`, and the remainder into `edx`.
After this loop, there is a comparison between `local_3_4` and `local_3`,
to check if they are equal. If they are not, `local_3` is incremented by one,
and the loop starts over again.
Looks like a primality test on `local_3`.
Then, there are some calls to `clock` and `sleep`, but since
the first returns a number of *ticks* and the second makes the program
wait for *seconds*, it's likely obfuscation/anti-debugging things
that could be patched away. It's worth noticing that the `counter`
is incremented by one in this block. At the end of it,
there is a comparison that will always be false, leading to `exit`.
Then, a call to `fcn.00400710`, another one to `0x40064d`, and if the first one
returns a value inferior to `counter` and the second is true,
the binary will print "Well done", else, the *main loop* will start over.
```nasm
[0x00400710]> pdf fcn.00400710
╒ (fcn) fcn.00400710 85
│ ; arg int arg_6_1 @ rbp+0x31
│ ; var int local_0_1 @ rbp-0x1
│ ; var int local_1 @ rbp-0x8
│ ; var int local_2 @ rbp-0x10
│ ; var int local_2_4 @ rbp-0x14
│ ; var int local_3 @ rbp-0x18
│ ; CALL XREF from 0x00400809 (fcn.00400710)
│ 0x00400710 55 push rbp
│ 0x00400711 4889e5 mov rbp, rsp
│ 0x00400714 4883ec20 sub rsp, 0x20
│ 0x00400718 c745e8310000. mov dword [rbp-local_3], 0x31 ; [0x31:4]=0x40000000 ; '1'
│ 0x0040071f e8dcfdffff call sym.imp.clock
│ 0x00400724 488945f0 mov qword [rbp-local_2], rax
│ 0x00400728 bf05000000 mov edi, 5
│ 0x0040072d e81efeffff call sym.imp.sleep
│ 0x00400732 8b45e8 mov eax, dword [rbp-local_3]
│ 0x00400735 69c040420f00 imul eax, eax, 0xf4240
│ 0x0040073b 8945ec mov dword [rbp-local_2_4], eax
│ 0x0040073e e8bdfdffff call sym.imp.clock
│ 0x00400743 488945f8 mov qword [rbp-local_1], rax
│ 0x00400747 488b45f0 mov rax, qword [rbp-local_2]
│ 0x0040074b 488b55f8 mov rdx, qword [rbp-local_1]
│ 0x0040074f 4829c2 sub rdx, rax
│ 0x00400752 4889d0 mov rax, rdx
│ 0x00400755 4883f813 cmp rax, 0x13
│ ┌─< 0x00400759 7f07 jg 0x400762
│ │ 0x0040075b b8408af701 mov eax, 0x1f78a40
│ ┌──< 0x00400760 eb03 jmp fcn.00400765
│ │└─> 0x00400762 8b45ec mov eax, dword [rbp-local_2_4]
│ └──> 0x00400765 c9 leave
╘ 0x00400766 c3 ret
```
`fcn.00400710` features another `clock + sleep + clock` obfuscation,
with a first call to `clock`, a sleep time of 5 seconds, another call to
`clock`, and if the difference is less than `0x13`, this function
return `0x1f78a40`, if it isn't, it's `0xf4240 * 0x31` instead,
so this function will always return `49.000.000`.
```nasm
[0x00400767]> pdf @ 0x40064d
╒ (fcn) fcn.0040064d 195
│ ; arg int arg_5_1 @ rbp+0x29
│ ; var int local_0 @ rbp-0x0
│ ; var int local_0_1 @ rbp-0x1
│ ; var int local_1 @ rbp-0x8
│ ; var int local_2 @ rbp-0x10
│ ; var int local_4_4 @ rbp-0x24
│ ; CALL XREF from 0x00400818 (fcn.0040064d)
│ ; CALL XREF from 0x00400767 (fcn.0040064d)
│ 0x0040064d 55 push rbp
│ 0x0040064e 4889e5 mov rbp, rsp
│ 0x00400651 4883ec30 sub rsp, 0x30
│ 0x00400655 897ddc mov dword [rbp-local_4_4], edi
│ 0x00400658 c745ec000000. mov dword [rbp - 0x14], 0
│ 0x0040065f 8b45dc mov eax, dword [rbp-local_4_4]
│ 0x00400662 89c6 mov esi, eax
│ 0x00400664 bfd4084000 mov edi, str._ld__ ; "%ld - " @ 0x4008d4
│ 0x00400669 b800000000 mov eax, 0
│ 0x0040066e e89dfeffff call sym.imp.printf
│ ┌─< 0x00400673 eb7d jmp 0x4006f2
│ ┌──> 0x00400675 e886feffff call sym.imp.clock
│ ││ 0x0040067a 488945f0 mov qword [rbp-local_2], rax
│ ││ 0x0040067e bf05000000 mov edi, 5
│ ││ 0x00400683 e8c8feffff call sym.imp.sleep
│ ││ 0x00400688 8b4ddc mov ecx, dword [rbp-local_4_4]
│ ││ 0x0040068b ba67666666 mov edx, 0x66666667
│ ││ 0x00400690 89c8 mov eax, ecx
│ ││ 0x00400692 f7ea imul edx
│ ││ 0x00400694 c1fa02 sar edx, 2
│ ││ 0x00400697 89c8 mov eax, ecx
│ ││ 0x00400699 c1f81f sar eax, 0x1f
│ ││ 0x0040069c 29c2 sub edx, eax
│ ││ 0x0040069e 89d0 mov eax, edx
│ ││ 0x004006a0 c1e002 shl eax, 2
│ ││ 0x004006a3 01d0 add eax, edx
│ ││ 0x004006a5 01c0 add eax, eax
│ ││ 0x004006a7 29c1 sub ecx, eax
│ ││ 0x004006a9 89ca mov edx, ecx
│ ││ 0x004006ab 0155ec add dword [rbp - 0x14], edx
│ ││ 0x004006ae e84dfeffff call sym.imp.clock
│ ││ 0x004006b3 488945f8 mov qword [rbp-local_1], rax
│ ││ 0x004006b7 488b45f0 mov rax, qword [rbp-local_2]
│ ││ 0x004006bb 488b55f8 mov rdx, qword [rbp-local_1]
│ ││ 0x004006bf 4829c2 sub rdx, rax
│ ││ 0x004006c2 4889d0 mov rax, rdx
│ ││ 0x004006c5 4883f813 cmp rax, 0x13
│ ┌───< 0x004006c9 7f0c jg 0x4006d7
│ │││ 0x004006cb 8b45dc mov eax, dword [rbp-local_4_4]
│ │││ 0x004006ce 69c089000000 imul eax, eax, 0x89
│ │││ 0x004006d4 8945dc mov dword [rbp-local_4_4], eax
│ └───> 0x004006d7 8b4ddc mov ecx, dword [rbp-local_4_4]
│ ││ 0x004006da ba67666666 mov edx, 0x66666667
│ ││ 0x004006df 89c8 mov eax, ecx
│ ││ 0x004006e1 f7ea imul edx
│ ││ 0x004006e3 c1fa02 sar edx, 2
│ ││ 0x004006e6 89c8 mov eax, ecx
│ ││ 0x004006e8 c1f81f sar eax, 0x1f
│ ││ 0x004006eb 29c2 sub edx, eax
│ ││ 0x004006ed 89d0 mov eax, edx
│ ││ 0x004006ef 8945dc mov dword [rbp-local_4_4], eax
│ │└─> 0x004006f2 837ddc00 cmp dword [rbp-local_4_4], 0
│ └──< 0x004006f6 0f8579ffffff jne 0x400675
│ 0x004006fc 837dec29 cmp dword [rbp - 0x14], 0x29 ; [0x29:4]=17 ; ')'
│ ┌─< 0x00400700 7507 jne 0x400709
│ │ 0x00400702 b801000000 mov eax, 1
│ ┌──< 0x00400707 eb05 jmp 0x40070e
│ │└─> 0x00400709 b800000000 mov eax, 0
│ └──> 0x0040070e c9 leave
╘ 0x0040070f c3 ret
```
A call to `printf`, showing us the parameter of this function, aka `local_3` in
the `main` function, yet another `clock + sleep + clock` obfuscation,
and two big scary mathematical chunks in assembly.
Fortunately, it really looks like modulo or division compiled by gcc,
and if we're right, this magic Python formula should give us the divisor:
```ipython
>>> # This is a copy-paste from https://reverseengineering.stackexchange.com/questions/1397/how-can-i-reverse-optimized-integer-division-modulo-by-constant-operations
>>> import math
>>> import ctypes
>>> sar_shift = 2
>>> mod_edx = 0x66666667
>>> math.ceil(2**(32+sar_shift)/float(ctypes.c_ulong(mov_edx).value))
>>> 10
```
If you didn't know about this magic formula, or if you don't trust your mental
pattern matching against classical mathematical operations compiled by gcc,
you could have used [ESIL]( https://github.com/radare/radare2book/blob/master/esil.md ):
```nasm
[0x00400767]> s 0x0040068b
[0x0040068b]> aei # initialize the ESIL VM
[0x0040068b]> aeip # set ESIL pc to the current offset
[0x0040068b]> aer ecx = 1234 # set the ESIL ecx register to 1234
[0x0040068b]> aer edx = 0x66666667
[0x0040068b]> aer # show ESIL registers
oeax = 0x00000000
eax = 0x0000012c
ebx = 0x00000000
ecx = 0x000004d2
edx = 0x66666667
esi = 0x00000000
edi = 0x00000000
esp = 0x00000000
ebp = 0x00000000
eip = 0x0040068b
eflags = 0x00000085
[0x0040068b]> aecu 0x004006a9 # set in ESIL until 0x004006a9
[0x0040068b]> aer edx
0x00000004
```
And indeed, `1234 % 10 = 4`.
Back to the listing, we now know that we have two divisions/modulo by 10,
and since I'm quite sure that gcc would be clever enough to:
1. optimize two consecutive divisions by ten into a division by hundret,
2. optimize two consecutive modulo by 10 into a single modulo.
It really looks like this function is simply summing every digit
of the number passed as argument.
The function then return the truth value of a comparison between the aforementioned
sum and `0x29`.
Now we have everything we need to write a keygen:
1. The number must be superior to the 49.000.000th prime
2. The sum of its components must be equals to 41
I [asked Wolfram Alpha]( https://www.wolframalpha.com/input/?i=49000000th+prime+number+%3F&dont-show-dyn=on )
about the 49.000.000th prime number, it's 961.748.927.
Here is the keygen:
```python
import hashlib
def is_prime(n):
if not n%2:
return False
for i in range(3, int(n**0.5)+1, 2):
if not n%i:
return False
return True
def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n / 10
return r
a = 961748927 # 49000000th primer number
while True:
a += 1
if is_prime(a) and sum_digits(a) == 41:
print 'The number is %d' % a
print 'The flag is DCTF{%s}' % hashlib.md5(str(a)).hexdigest()
break
```
And the answer is:
```
$ python re200.py
The number is 961749023
The flag is DCTF{23226505e20dcafbfe6058ef486e3f12}
```