Artificial truth

The more you see, the less you believe.

[archives] [latest] | [homepage] | [atom/rss]

Reversing re200 from Defcamp (D-CTF) final 2015 with radare2
Sun 22 November 2015 — download

It has been a long time since I posted something about how to reverse things with radare2, like crackmes, hence this writeup, about re200 from the finals of the Defcamp'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.

$ 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:

 [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:

                            =-------------------------------------=
                            | [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.

[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.

[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:

>>> # 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:

[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 about the 49.000.000th prime number, it's 961.748.927.

Here is the keygen:

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}