Defeating lincrackme3 with radare2
Wed 22 August 2012 — download

For this crackme, I'll try to stick with radare2, instead of IDA. Why ? Because using IDA would be too easy ;)

lincrackme3, who are you?

$ file lincrackme3-32
lincrackme3-32: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.15, BuildID[sha1]=0x31febf8a1adc89e8d7b268b18df85a323704bc16, stripped
$ ./lincrackme3-32
**********************************************************************
* Welcome to lincrackme3! This is a simple linux crackme. The goal   *
* is to understand the key checking method and write your own keygen *
* for it. Keep an eye on antidebugging techniques, because thats the *
* reason for this crackmes, knowing them and the way to bypass them. *
* Key format: XXXX-YYYY-WWWW-ZZZZ with all numbers. Good luck!       *
* @author: Adrian adrianbn[at]gmail.com http://securityetalii.es     *
* ********************************************************************

Enter the key, you fool: 1111-2222-3333-4444
Wrong key! I`ve seen monkeys smarter than you...
zsh: exit 1     ./lincrackme3-3

Shared libs again? ltrace, go!

$ ltrace ./lincrackme3-32
[...]                                                                                                        = 584
printf("Enter the key, you fool: ")                                                                                                                 = 25
getchar(0xf76eaa20, 0x8048d00, 0, 0xf7593c00, 0x8048d00Enter the key, you fool: 1111-2222-3333-4444)                                                                                            = 49
getchar(0xf76eaa20, 0x8048d00, 1, 0x31593c00, 0x8048d00)                                                                                          = 49
[...]                                                                                      = 52
getchar(0xf76eaa20, 0x8048d00, 16, 0x34593c00, 0x8048d00)                                                                                           = 10
strncmp("1111222233334444", "It's not that easy, dude", 16)                                                                                         = -24
ptrace(0, 0, 1, 0, 0xffa0985c)                                                                                                                      = -1
puts("Debugger detected. Bye!"Debugger detected. Bye!
)                                                                                                                     = 24
exit(-1 <unfinished ...>
+++ exited (status 255) +++

Ho, ltrace is detected. But even more interesting, a (weird) strcmp between "It's not that easy, dude" and our key, on 16 chars. But our key must have the format XXXX-YYYY-WWWW-ZZZZ. Weird.

Anti-debugging/reversing techniques

Radare2 tells us that is the entrypoint is at 0x8048500.

$ r2 ./lincrackme3-32
[0x08048500]> pdf@0x8048500
Cannot find function at 0x08048500
Cannot find function at 0x08048500
    0x08048500  section..text:
    0x08048500     31ed             xor ebp, ebp
    0x08048502     5e               pop esi
    0x08048503     89e1             mov ecx, esp
    0x08048505     83e4f0           and esp, 0xfffffff0
    0x08048508     50               push eax
    0x08048509     54               push esp
    0x0804850a     52               push edx
    0x0804850b     68e0890408       push dword 0x80489e0
    0x08048510     68f0890408       push dword 0x80489f0
    0x08048515     51               push ecx
    0x08048516     56               push esi
    0x08048517     68b4860408       push dword 0x80486b4
    0x0804851c     e863ffffff       call dword imp.__libc_start_main
    0x08048521     f4               hlt
    ; ------------

Standard entrypoint, our main is at 0x80486b4.

[0x080486b4]> pD 512
    0x080486b4  main:
    0x080486b4     55               push ebp
    0x080486b5     89e5             mov ebp, esp
    0x080486b7     83e4f0           and esp, 0xfffffff0
    0x080486ba     57               push edi
[...]
    0x080487a2     c7442428b4850408 mov dword [esp+0x28], 0x80485b4 ; " ***********[...]***"
    0x080487aa     c70424b88a0408   mov dword [esp], 0x8048ab8
    0x080487b1     e80efdffff       call dword imp.puts
    0x080487b6     b8008d0408       mov eax, str.Enterthekey,youfool ; "Enter the key, you fool: "
    0x080487bb     890424           mov [esp], eax
    0x080487be     e8d1fcffff       call dword imp.printf
    0x080487c3     c744240411000000 mov dword [esp+0x4], 0x11
    0x080487cb     8d8424bc000000   lea eax, [esp+0xbc]
    0x080487d2     890424           mov [esp], eax
    0x080487d5     e852feffff       call dword 0x804862c ; this function check the format of our_key
    0x080487da     8944242c         mov [esp+0x2c], eax
    0x080487de     837c242c10       cmp dword [esp+0x2c], 0x10
,=< 0x080487e3     7418             jz 0x80487fd ; booh, wrong key format :<
|   0x080487e5     c704241c8d0408   mov dword [esp], str.Wrongkeyformat!KeymustbeXXXXYYYYWWWWZZZZwhereX,Y,W,Zarenumbers
|   0x080487ec     e8d3fcffff       call dword imp.puts
|   0x080487f1     c7042401000000   mov dword [esp], 0x1
|   0x080487f8     e8e7fcffff       call dword imp.exit
`-> 0x080487fd     c744240810000000 mov dword [esp+0x8], 0x10
    0x08048805     c7442404688d0408 mov dword [esp+0x4], str.Itsnotthateasy,dude
    0x0804880d     8d8424bc000000   lea eax, [esp+0xbc]
    0x08048814     890424           mov [esp], eax
    0x08048817     e8b8fcffff       call dword imp.strncmp ; strncmp(our_key, "It's not that easy dude", 0x10);
    0x0804881c     66c74424300000   mov word [esp+0x30], 0x0
    0x08048823     0fb7442430       movzx eax, word [esp+0x30]
    0x08048828     6689442432       mov [esp+0x32], ax
    0x0804882d     0fb7442432       movzx eax, word [esp+0x32]
    0x08048832     6689442434       mov [esp+0x34], ax
    0x08048837     0fb7442434       movzx eax, word [esp+0x34]
    0x0804883c     6689442436       mov [esp+0x36], ax
    0x08048841     e801000000       call dword 0x8048847
    0x08048846     e958059d00       jmp dword 0x8a18da3
    0x0804884b     0000             add [eax], al
    0x0804884d     50               push eax
    0x0804884e     c3               ret
    ; ------------

The start of the main puts some data on the stack, prompt a key, check it's format, exits if its format is invalid, do a strncmp that can be true, call 0x08048847, jumps to some crap at 0x8a18da3 and return.

[0x08048847]> pdf
Cannot find function at 0x08048847
Cannot find function at 0x08048847
        0x08048847     58               pop eax
        0x08048848     059d000000       add eax, 0x9d
        0x0804884d     50               push eax
        0x0804884e     c3               ret
        ; ------------

Ho, nice trick : eax is popped, 0x9d is added, and exa is pushed. When our function returns, the flow will jump to eax. Since I'm too lazy do to some voodoo static analysis, I rather go with patching anti-debugging stuffs and use gdb.

Patching gdb detection/counter-measures

xrefs (from the radare2 package) shows two xrefs for the word "Debugger" : 0x080485e2 and 0x08048612. Let's see within wich functions we land:

[0x08048847]> afl
[...]
0x080484e4     16   0  imp.exit
0x080485fc     48   3  fcn.080485fc ; gdb_trick_one
0x0804862a      2   1  loc.0804862a
0x0804862c    136  16  fcn.0804862c
[...]

0x080485e2

Rhaaaaa, crap :radare2 didn't detect the function. Since I think that the function is short, so I'll go with try'n'guess. I'll end up with this:

[0x080485e2]> pdf@0x0x080485e2 - 46
Cannot find function at 0x080485b4
Cannot find function at 0x080485b4
        0x080485b4     55               push ebp
        0x080485b5     89e5             mov ebp, esp
        0x080485b7     83ec18           sub esp, 0x18
        0x080485ba     c744240c00000000 mov dword [esp+0xc], 0x0
        0x080485c2     c744240801000000 mov dword [esp+0x8], 0x1
        0x080485ca     c744240400000000 mov dword [esp+0x4], 0x0
        0x080485d2     c7042400000000   mov dword [esp], 0x0
        0x080485d9     e886feffff       call dword imp.ptrace
        0x080485de     85c0             test eax, eax
        0x080485e0     7918             jns 0x80485fa ; jump to invert
        0x080485e2     c70424a08a0408   mov dword [esp], str.Debuggerdetected.Bye!
        0x080485e9     e8d6feffff       call dword imp.puts
        0x080485ee     c7               invalid
        0x080485ef     0424             add al, 0x24
        0x080485f1     ff               invalid
        0x080485f2     ff               invalid
        0x080485f3     ff               invalid
[0x080485e2]>

We've got what we wants: the trick. Who cares about the end of the function (If you are picky, take a look at it with IDA.)? Looks like we've got the systematically-and-too-much-used boring ptrace trick. Just replace the jns (79) by a js (78).

0x08048612

Okay, this time radare2 has detected our function : 0x080485fc, sweet !

[0x080485fc]> pdf
/ function: fcn.080485fc (48)
|      0x080485fc  fcn.080485fc:
|      0x080485fc     55               push ebp
|      0x080485fd     89e5             mov ebp, esp
|      0x080485ff     83ec18           sub esp, 0x18
|      0x08048602     c7042403000000   mov dword [esp], 0x3
|      0x08048609     e896feffff       call dword imp.close
|      0x0804860e     85c0             test eax, eax
|  ,=< 0x08048610     7518             jnz loc.0804862a ; We must invert this jump
|  |   0x08048612     c70424a08a0408   mov dword [esp], str.Debuggerdetected.Bye!
|  |   0x08048619     e8a6feffff       call dword imp.puts
|  |   0x0804861e     c70424ffffffff   mov dword [esp], 0xffffffff
|  |   0x08048625     e8bafeffff       call dword imp.exit
|  |   0x0804862a  loc.0804862a:
|  `-> 0x0804862a     c9               leave
\      0x0804862b     c3               ret
    ; ------------

A call to close with "3" as parameter. Looks like we've got the good old file descriptor trick here. We replaces the jnz (75) with a jz (74), and it's done.

Dynamic analysis

Okay, our binary is patched, we can run it through gdb.

$ gdb lincrackme3-32_patched
Reading symbols from ./lincrackme3-32_noantidebug...(no debugging symbols found)...done
gdb $ b *0x0804884d
Breakpoint 1 at 0x804884d
gdb $ r
    **********************************************************************
    *  Welcome to lincrackme3! This is a simple linux crackme. The goal   *
    * is to understand the key checking method and write your own keygen *
    * for it. Keep an eye on antidebugging techniques, because thats the *
    * reason for this crackmes, knowing them and the way to bypass them. *
    * Key format: XXXX-YYYY-WWWW-ZZZZ with all numbers. Good luck!       *
    * @author: Adrian adrianbn[at]gmail.com http://securityetalii.es     *
    * ********************************************************************

Enter the key, you fool: 1111-2222-3333-4444
-------------------------------------------------------------------------[ regs]
        eax:080488E3 ebx:F7FB3FF4  ecx:00000049  edx:FFFFCEAC     eflags:00000212
        esi:08048E08 edi:FFFFCE78  esp:FFFFCDF0  ebp:FFFFCED8     eip:0804884D
        cs:0023  ds:002B  es:002B  fs:0000  gs:0063  ss:002B    o d I t s z A p c
[002B:FFFFCDF0]---------------------------------------------------------[stack]
FFFFCE20 : 00 00 00 00  00 00 00 00 - BE 96 96 9D  D8 D9 A0 96 ................
FFFFCE10 : 98 CE FF FF  74 DA FF F7 - B4 85 04 08  10 00 00 00 ....t...........
FFFFCE00 : 01 00 00 00  01 00 00 00 - 00 00 00 00  44 82 04 08 ............D...
FFFFCDF0 : AC CE FF FF  68 8D 04 08 - 10 00 00 00  48 AB FD F7 ....h.......H...
[002B:08048E08]---------------------------------------------------------[ data]
08048E08 : 00 00 00 00  00 00 00 00 - 00 00 00 00  00 00 00 00 ................
08048E18 : 00 00 00 00  00 00 00 00 - 00 00 00 00  00 00 00 00 ................
[0023:0804884D]---------------------------------------------------------[ code]
=> 0x804884d:   push   eax
    0x804884e:   ret
    0x804884f:   jmp    0x4ccc48dd
    0x8048854:   and    al,0x24
    0x8048856:   add    BYTE PTR [eax],al
    0x8048858:   add    BYTE PTR [eax],al
-------------------------------------------------------------------------------

Breakpoint 1, 0x0804884d in ?? ()

Yes, my gdb looks like SoftICE, and it's amazingly awesome. I'm using osxreverser's .gdbinit, you can grab it here.

So, eax equals 0x080488E3, let's continue

gdb $ ni
gdb $ ni
-------------------------------------------------------------------------[ regs]
        eax:080488E3 ebx:F7FB3FF4  ecx:00000049  edx:FFFFCEAC     eflags:00000212
        esi:08048E08 edi:FFFFCE78  esp:FFFFCDF0  ebp:FFFFCED8     eip:080488E3
        cs:0023  ds:002B  es:002B  fs:0000  gs:0063  ss:002B    o d I t s z A p c
[0023:080488E3]---------------------------------------------------------[ code]
=> 0x80488e3:   mov    ebx,DWORD PTR [esp+0x28]
    0x80488e7:   call   ebx
    0x80488e9:   jmp    0x8048850
    0x80488ee:   jmp    0x2c594002
    0x80488f3:   movzx  eax,WORD PTR ss:[esp+0x34]
    0x80488f9:   lea    ecx,[edx+eax*1]
-------------------------------------------------------------------------------
0x080488e3 in ?? ()

Ho, another call reg trick.

gdb $ ni
-------------------------------------------------------------------------[ regs]
    eax:080488E3 ebx:080485B4  ecx:00000049  edx:FFFFCEAC     eflags:00000212
    esi:08048E08 edi:FFFFCE78  esp:FFFFCDF0  ebp:FFFFCED8     eip:080488E7
    cs:0023  ds:002B  es:002B  fs:0000  gs:0063  ss:002B    o d I t s z A p c
[0023:080488E7]---------------------------------------------------------[ code]
=> 0x80488e7:   call   ebx
    0x80488e9:   jmp    0x8048850
    0x80488ee:   jmp    0x2c594002
    0x80488f3:   movzx  eax,WORD PTR ss:[esp+0x34]
    0x80488f9:   lea    ecx,[edx+eax*1]
    0x80488fc:   movzx  edx,WORD PTR [esp+0x32]
-------------------------------------------------------------------------------
0x080488e7 in ?? ()

ebx is equals to 0x080485B4, our first anti-dbg trick, let's step over and go directly to 0x8048850.

0x8048850 : The key verification routine

The key verification routine is composed of two parts:

  1. Key's checksums generation
  2. Key verification

Checksums

Legend

  • [esp+0x24] : a counter
  • [esp+eax+0xbc] : our_key[eax]
  • [esp+0x36] : checksum_one
  • [esp+0x34] : checksum_two
  • [esp+0x32] : checksum_three
  • [esp+0x30] : checksum_four
  • 0x30 : '0' in ASCII

Code

    .----> 0x08048850     89c0             mov eax, eax
    |      0x08048852     c744242400000000 mov dword [esp+0x24], 0x0 ; esp+0x24 is our counter
    |  ,=< 0x0804885a     eb7a             jmp 0x80488d6
    | .--> 0x0804885c     8b442424         mov eax, [esp+0x24]
    | ||   0x08048860     0fb68404bc000000 movzx eax, byte [esp+eax+0xbc] ; eax = our_key[eax]
    | ||   0x08048868     6698             cbw
    | ||   0x0804886a     6603442436       add ax, [esp+0x36] ; ax = ourkey + checksum_one
    | ||   0x0804886f     83e830           sub eax, 0x30      ; eax = checksum_one + our_key - '0'
    | ||   0x08048872     6689442436       mov [esp+0x36], ax ; checksum_one += our_key - '0'
    | ||
    | ||   0x08048877     8b442424         mov eax, [esp+0x24]
    | ||   0x0804887b     83c004           add eax, 0x4
    | ||   0x0804887e     0fb68404bc000000 movzx eax, byte [esp+eax+0xbc]
    | ||   0x08048886     6698             cbw
    | ||   0x08048888     6603442434       add ax, [esp+0x34]
    | ||   0x0804888d     83e830           sub eax, 0x30
    | ||   0x08048890     6689442434       mov [esp+0x34], ax
    | ||
    | ||   0x08048895     8b442424         mov eax, [esp+0x24]
    | ||   0x08048899     83c008           add eax, 0x8
    | ||   0x0804889c     0fb68404bc000000 movzx eax, byte [esp+eax+0xbc]
    | ||   0x080488a4     6698             cbw
    | ||   0x080488a6     6603442432       add ax, [esp+0x32]
    | ||   0x080488ab     83e830           sub eax, 0x30
    | ||   0x080488ae     6689442432       mov [esp+0x32], ax
    | ||
    | ||   0x080488b3     8b442424         mov eax, [esp+0x24]
    | ||   0x080488b7     83c00c           add eax, 0xc
    | ||   0x080488ba     0fb68404bc000000 movzx eax, byte [esp+eax+0xbc]
    | ||   0x080488c2     6698             cbw
    | ||   0x080488c4     6603442430       add ax, [esp+0x30]
    | ||   0x080488c9     83e830           sub eax, 0x30
    | ||   0x080488cc     6689442430       mov [esp+0x30], ax
    | ||
    | ||   0x080488d1     8344242401       add dword [esp+0x24], 0x1 ; increments the counter
    | |`-> 0x080488d6     837c242403       cmp dword [esp+0x24], 0x3 ; three tour of loop
    | `==< 0x080488db     0f8e7bffffff     jle dword 0x804885c
    |,===< 0x080488e1     eb0c             jmp 0x80488ef

Algorithm

Pretty straightforward:

checksum_one = our_key[0] - '0' +  our_key[1] - '0' +  our_key[2] - '0' +  our_key[3]
checksum_two = our_key[4] - '0' +  our_key[5] - '0' +  our_key[6] - '0' +  our_key[7]
checksum_three = our_key[8] - '0' +  our_key[9] - '0' +  our_key[10] - '0' +  our_key[11]
checksum_four = our_key[12] - '0' +  our_key[13] - '0' +  our_key[14] - '0' +  our_key[15]

Proper key verification routine

0x0804894b looks like a Badboy jump. If this is right, 0x8048986 is the Goodboy one.

         0x080488ef     0fb7542436       movzx edx, word [esp+0x36]
         0x080488f4     0fb7442434       movzx eax, word [esp+0x34]
         0x080488f9     8d0c02           lea ecx, [edx+eax]
         0x080488fc     0fb7542432       movzx edx, word [esp+0x32]
         0x08048901     0fb7442430       movzx eax, word [esp+0x30]
         0x08048906     8d0402           lea eax, [edx+eax]
         0x08048909     01c0             add eax, eax
         0x0804890b     39c1             cmp ecx, eax ; checksum_one + checksum_two = 2 * (checksum_three + checksum_four)
     ,=< 0x0804890d     753c             jnz 0x804894b ;
     |   0x0804890f     0fb7442434       movzx eax, word [esp+0x34]
     |   0x08048914     663b442432       cmp ax, [esp+0x32] ; checksum_two > checksum_three
    ,==< 0x08048919     7630             jbe 0x804894b
    ||   0x0804891b     0fb7542436       movzx edx, word [esp+0x36]
    ||   0x08048920     0fb7442430       movzx eax, word [esp+0x30]
    ||   0x08048925     8d0402           lea eax, [edx+eax]
    ||   0x08048928     83e001           and eax, 0x1
    ||   0x0804892b     84c0             test al, al ; (checksum_one + checksum_four) && 1 = 0
   ,===< 0x0804892d     751c             jnz 0x804894b
   |||   0x0804892f     66837c243605     cmp word [esp+0x36], 0x5 ; checksum_one > 0x5
  ,====< 0x08048935     7614             jbe 0x804894b
  ||||   0x08048937     66837c243618     cmp word [esp+0x36], 0x18 ; checksum_one < 0x18
 ,=====< 0x0804893d     770c             ja 0x804894b
 |||||   0x0804893f     0fb7442430       movzx eax, word [esp+0x30]
 |||||   0x08048944     83e001           and eax, 0x1
 |||||   0x08048947     85c0             test eax, eax ; checksum_four && 1 != 0
,======< 0x08048949     753b             jnz 0x8048986
|`````-> 0x0804894b     c744242000000000 mov dword [esp+0x20], 0x0
[...]

To sum up:

checksum_four % 2 = 1
0x5 < checksum_one > 0x18
checksum_three < checksum_two
checksum_one + checksum_two = 2 * (checksum_three + checksum_four)
(checksum_one + checksum_four) % 2 = 0
Numbers can only be between 0 and 9, so checksums are between 0 and 36 (4*9).

Let's re-arrange this:

checksum_one % 2 = checksum_two % 2= checksum_four % 2 = 1
checksum_four = (checksum_one + checksum_two) / 2 - checksum_three

Ok, time to write a keygen !

Keygen

It may not be the quickest one or the most exhaustive, but it works.

print '.: lincrackme3 keygen :.'
print '[*] keys:\n'

def decompose(s):
    r = [0] * 4
    i = 0
    while s:
        if r[i] == 9:
            i+=1
        r[i] += 1
        s -= 1
    return ''.join(str(c) for c in r)

for s1 in xrange(7, 23, 2):
    for s2 in xrange(1, 35, 2):
        for s3 in xrange(0, s2 - 1):
            s4 = (s1+s2)/2 - s3
            if not s4 % 2:
                break
            print "%s-%s-%s-%s\n" % (decompose(s1), decompose(s2), decompose(s3), decompose(s4))

Result:

$ ./lincrackme3-32
    **********************************************************************
    * Welcome to lincrackme3! This is a simple linux crackme. The goal   *
    * is to understand the key checking method and write your own keygen *
    * for it. Keep an eye on antidebugging techniques, because thats the *
    * reason for this crackmes, knowing them and the way to bypass them. *
    * Key format: XXXX-YYYY-WWWW-ZZZZ with all numbers. Good luck!       *
    * @author: Adrian adrianbn[at]gmail.com http://securityetalii.es     *
    * ********************************************************************


Enter the key, you fool: 9930-9996-0000-9990
Good! You got it, congratz. Have you tried to keygen me? Next crackme soon ^_^

I liked a lot the obfuscated call after the strcmp (who drove me crazy for quite some time). Thank you Adrian :)