GreHack-2013/150-1337

From aldeid
Jump to navigation Jump to search
You are here
150 - 1337

Description

GreHack CTF 2013 reverse engineering challenge (150 points).

Running the binary

Patching

The binary seems to be an ELF but with an incorrect format, as shown below:

$ file 1337
1337: ERROR: ELF 32-bit LSB executable, Intel 80386, error reading (Invalid argument)

Having a look at the header confirms that something's wrong:

$ hd 1337 | head
00000000  7f 45 4c 46 01 01 01 13  37 13 37 13 37 13 37 00  |.ELF....7.7.7.7.|
00000010  02 00 03 00 01 13 37 00  90 84 04 08 34 13 37 00  |......7.....4.7.|
00000020  d0 0b 13 37 13 37 13 37  34 00 20 00 08 00 28 00  |...7.7.74. ...(.|
00000030  1d 00 1c 00 06 13 37 00  34 13 37 00 34 80 04 08  |......7.4.7.4...|
00000040  34 80 04 08 00 01 13 37  00 01 13 37 05 13 37 00  |4......7...7..7.|
00000050  04 13 37 00 03 13 37 00  34 01 13 37 34 81 04 08  |..7...7.4..74...|
00000060  34 81 04 08 13 13 37 00  13 13 37 00 04 13 37 00  |4.....7...7...7.|
00000070  01 13 37 00 01 13 37 13  37 13 37 13 37 80 04 08  |..7...7.7.7.7...|
00000080  00 80 04 08 68 09 13 37  68 09 13 37 05 13 37 13  |....h..7h..7..7.|
00000090  37 10 13 37 01 13 37 00  68 09 13 37 68 99 04 08  |7..7..7.h..7h...|

We notice the presence of many \x13\x37 instead of \x00\x00. Let's fix it:

$ cp 1337 1337-patched
$ sed -i 's/\x13\x37/\x00\x00/g' 1337-patched

Now, it seems that the format is correct:

$ file 1337-patched
1337-patched: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.26, BuildID[sha1]=c7ce472025fcc2fda6ed2ced6f7851e05e9c981e, stripped

First run

Let's run it:

$ ./1337-patched
Ready to become 1337?
yes
fail

The executable returns "fail".

Analysis

Let's analyze it in IDA-Pro:

GreHack-2013-150-1337-graph-overview.png

There are several tests, leading to different error messages:

  • Sum test: will display "fail" in case of invalid input
  • 1337 test: will display "f41l" in case of invalid input
  • Double XOR test: will display "0xPH41L" in case of invalid input
  • Bit equality test: will also display "0xPH41L" in case of invalid input

Initialization

The program is prompting a key and saves it to [ESP+0x18]. It also computes the length of the user input at offset Template:0x80485D2 and saves it to [ESP+0x10].

.text:0804857C sub_804857C proc near
.text:0804857C push    ebp
.text:0804857D mov     ebp, esp
.text:0804857F and     esp, 0FFFFFFF0h
.text:08048582 sub     esp, 20h
.text:08048585 mov     dword ptr [esp], 539h ; size
.text:0804858C call    _malloc
.text:08048591 mov     [esp+14h], eax  ; ESP+0x14 = mypass
.text:08048595 mov     dword ptr [esp+18h], 0 ; ESP+0x18 = 0
.text:0804859D mov     dword ptr [esp], offset s ; "Ready to become 1337?"
.text:080485A4 call    _puts
.text:080485A9 mov     eax, ds:stdin
.text:080485AE mov     [esp+8], eax    ; stream
.text:080485B2 mov     dword ptr [esp+4], 539h ; n
.text:080485BA mov     eax, [esp+14h]
.text:080485BE mov     [esp], eax      ; s
.text:080485C1 call    _fgets
.text:080485C6 mov     eax, [esp+14h]
.text:080485CA mov     [esp], eax      ; s
.text:080485CD call    _strlen
.text:080485D2 mov     [esp+10h], eax  ; ESP+0x10 = strlen(mypass)
.text:080485D6 mov     dword ptr [esp+1Ch], 0 ; ESP+0x1C = 0
.text:080485DE jmp     short loc_80485F9

Sum test

Starting from offset 0x80485E0, there is a first check on the sum of all characters of the user input:

.text:080485E0 loc_80485E0:
.text:080485E0                 mov     edx, [esp+1Ch]
.text:080485E4                 mov     eax, [esp+14h]
.text:080485E8                 add     eax, edx
.text:080485EA                 movzx   eax, byte ptr [eax]
.text:080485ED                 movsx   eax, al
.text:080485F0                 add     [esp+18h], eax
.text:080485F4                 add     dword ptr [esp+1Ch], 1
.text:080485F9
.text:080485F9 loc_80485F9:
.text:080485F9                 mov     eax, [esp+1Ch]
.text:080485FD                 cmp     eax, [esp+10h]  ; loop until all chars of mypass are read
.text:08048601                 jl      short loc_80485E0
.text:08048603                 cmp     dword ptr [esp+18h], 539h      ; Sum of all chars of mypass
.text:0804860B                 jz      short loc_8048625              ; should be equal to 1337
.text:0804860D                 mov     dword ptr [esp], offset format ; If not, display "fail"
.text:08048614                 call    _printf
.text:08048619                 mov     dword ptr [esp], 1 ; status
.text:08048620                 call    _exit

The program loops through all characters of the user input and cumulates the value of the characters. If the sum (including 0xA for the trailing \n) is equal to 1337.

1337 test

Starting from offset 0x8048625, the code is checking that bit #1 of the user input is equal to 1, bit #3 to 3 and bit #7 to 7:

.text:08048625 loc_8048625:
.text:08048625                 mov     eax, [esp+14h]  ; eax = mypass
.text:08048629                 add     eax, 1
.text:0804862C                 movzx   eax, byte ptr [eax]
.text:0804862F                 cmp     al, 31h         ; mypass[1] = '1'?
.text:08048631                 jnz     short f41l
.text:08048633                 mov     eax, [esp+14h]
.text:08048637                 add     eax, 3
.text:0804863A                 movzx   eax, byte ptr [eax]
.text:0804863D                 cmp     al, 33h         ; mypass[3] = '3'?
.text:0804863F                 jnz     short f41l
.text:08048641                 mov     eax, [esp+14h]  ; same test as previously
.text:08048645                 add     eax, 3
.text:08048648                 movzx   eax, byte ptr [eax]
.text:0804864B                 cmp     al, 33h
.text:0804864D                 jnz     short f41l
.text:0804864F                 mov     eax, [esp+14h]
.text:08048653                 add     eax, 7
.text:08048656                 movzx   eax, byte ptr [eax]
.text:08048659                 cmp     al, 37h         ; mypass[7] = '7'?
.text:0804865B                 jz      short loc_8048675
.text:0804865D
.text:0804865D f41l:
.text:0804865D                 mov     dword ptr [esp], offset aF41l ; "f41l"
.text:08048664                 call    _printf
.text:08048669                 mov     dword ptr [esp], 3 ; status
.text:08048670                 call    _exit

Double XOR test

Starting from offset 0x8048675, there is a double XOR (1st XOR by 0x13 and 2nd one by 0x37) that modifies each of the characters of the user input:

.text:08048675 loc_8048675:
.text:08048675                 mov     dword ptr [esp+1Ch], 0     ; i = 0
.text:0804867D                 jmp     short loc_80486BC
.text:0804867F ; ---------------------------------------------------------------------------
.text:0804867F
.text:0804867F loc_804867F:
.text:0804867F                 mov     edx, [esp+1Ch]
.text:08048683                 mov     eax, [esp+14h]
.text:08048687                 add     edx, eax
.text:08048689                 mov     ecx, [esp+1Ch]
.text:0804868D                 mov     eax, [esp+14h]
.text:08048691                 add     eax, ecx
.text:08048693                 movzx   eax, byte ptr [eax]
.text:08048696                 xor     eax, 13h             ; mypass[i] ^= 0x13
.text:08048699                 mov     [edx], al
.text:0804869B                 mov     edx, [esp+1Ch]
.text:0804869F                 mov     eax, [esp+14h]
.text:080486A3                 add     edx, eax
.text:080486A5                 mov     ecx, [esp+1Ch]
.text:080486A9                 mov     eax, [esp+14h]
.text:080486AD                 add     eax, ecx
.text:080486AF                 movzx   eax, byte ptr [eax]
.text:080486B2                 xor     eax, 37h             ; mypass[i] ^= 0x37
.text:080486B5                 mov     [edx], al
.text:080486B7                 add     dword ptr [esp+1Ch], 1 ; i += 1
.text:080486BC
.text:080486BC loc_80486BC:
.text:080486BC                 mov     eax, [esp+1Ch]
.text:080486C0                 cmp     eax, [esp+10h]  ; while (i < len(mypass))
.text:080486C4                 jl      short loc_804867F
.text:080486C6                 mov     eax, [esp+14h]
.text:080486CA                 movzx   edx, byte ptr [eax] ; edx = xor_mypass[0]
.text:080486CD                 mov     eax, [esp+14h]
.text:080486D1                 add     eax, 2
.text:080486D4                 movzx   eax, byte ptr [eax] ; eax = xor_mypass[2]
.text:080486D7                 cmp     dl, al          ; \ if xor_mypass[0] != xor_mypass[2]
.text:080486D9                 jnz     PH41L           ; / go to PH41L

The loop can actually be simplified with a simple XOR by 0x24. The code XORs each character of the user input with 0x24 and ensures that bit #0 and bit #2 of the resulting string are equal.

Bit equality test

Starting from offset 0x80486DF, there are tests on bits to ensure equalities:

.text:080486DF                 mov     eax, [esp+14h]
.text:080486E3                 add     eax, 2
.text:080486E6                 movzx   edx, byte ptr [eax]
.text:080486E9                 mov     eax, [esp+14h]
.text:080486ED                 add     eax, 4
.text:080486F0                 movzx   eax, byte ptr [eax]
.text:080486F3                 cmp     dl, al          ; xor_mypass[2] = xor_mypass[4]
.text:080486F5                 jnz     PH41L
.text:080486FB                 mov     eax, [esp+14h]
.text:080486FF                 add     eax, 4
.text:08048702                 movzx   edx, byte ptr [eax]
.text:08048705                 mov     eax, [esp+14h]
.text:08048709                 add     eax, 5
.text:0804870C                 movzx   eax, byte ptr [eax]
.text:0804870F                 cmp     dl, al          ; xor_mypass[4] = xor_mypass[5]
.text:08048711                 jnz     PH41L
.text:08048717                 mov     eax, [esp+14h]
.text:0804871B                 add     eax, 5
.text:0804871E                 movzx   edx, byte ptr [eax]
.text:08048721                 mov     eax, [esp+14h]
.text:08048725                 add     eax, 6
.text:08048728                 movzx   eax, byte ptr [eax]
.text:0804872B                 cmp     dl, al          ; xor_mypass[5] = xor_mypass[6]
.text:0804872D                 jnz     PH41L
.text:08048733                 mov     eax, [esp+14h]
.text:08048737                 add     eax, 6
.text:0804873A                 movzx   edx, byte ptr [eax]
.text:0804873D                 mov     eax, [esp+14h]
.text:08048741                 add     eax, 8
.text:08048744                 movzx   eax, byte ptr [eax]
.text:08048747                 cmp     dl, al          ; xor_mypass[6] = xor_mypass[8]
.text:08048749                 jnz     PH41L
.text:0804874F                 mov     eax, [esp+14h]
.text:08048753                 add     eax, 8
.text:08048756                 movzx   edx, byte ptr [eax]
.text:08048759                 mov     eax, [esp+14h]
.text:0804875D                 add     eax, 9
.text:08048760                 movzx   eax, byte ptr [eax]
.text:08048763                 cmp     dl, al          ; xor_mypass[8] = xor_mypass[9]
.text:08048765                 jnz     short PH41L
.text:08048767                 mov     eax, [esp+14h]
.text:0804876B                 add     eax, 9
.text:0804876E                 movzx   edx, byte ptr [eax]
.text:08048771                 mov     eax, [esp+14h]
.text:08048775                 add     eax, 0Ah
.text:08048778                 movzx   eax, byte ptr [eax]
.text:0804877B                 cmp     dl, al          ; xor_mypass[9] = xor_mypass[10]
.text:0804877D                 jnz     short PH41L
.text:0804877F                 mov     eax, [esp+14h]
.text:08048783                 add     eax, 0Ah
.text:08048786                 movzx   edx, byte ptr [eax]
.text:08048789                 mov     eax, [esp+14h]
.text:0804878D                 add     eax, 0Bh
.text:08048790                 movzx   eax, byte ptr [eax]
.text:08048793                 cmp     dl, al          ; xor_mypass[10] = xor_mypass[11]
.text:08048795                 jnz     short PH41L
.text:08048797                 mov     eax, [esp+14h]
.text:0804879B                 add     eax, 0Bh
.text:0804879E                 movzx   edx, byte ptr [eax]
.text:080487A1                 mov     eax, [esp+14h]
.text:080487A5                 add     eax, 0Ch
.text:080487A8                 movzx   eax, byte ptr [eax]
.text:080487AB                 cmp     dl, al          ; xor_mypass[11] = xor_mypass[12]
.text:080487AD                 jnz     short PH41L
.text:080487AF                 mov     eax, [esp+14h]
.text:080487B3                 add     eax, 0Ch
.text:080487B6                 movzx   edx, byte ptr [eax]
.text:080487B9                 mov     eax, [esp+14h]
.text:080487BD                 add     eax, 0Dh
.text:080487C0                 movzx   eax, byte ptr [eax]
.text:080487C3                 cmp     dl, al          ; xor_mypass[12] = xor_mypass[13]
.text:080487C5                 jnz     short PH41L
.text:080487C7                 mov     eax, [esp+14h]
.text:080487CB                 add     eax, 0Eh
.text:080487CE                 movzx   eax, byte ptr [eax]
.text:080487D1                 cmp     al, 76h         ; xor_mypass[14] = 0x76
.text:080487D3                 jz      short SUCCESS
.text:080487D5
.text:080487D5 PH41L:
.text:080487D5                 mov     dword ptr [esp], offset a0xph41l ; "0xPh41L"
.text:080487DC                 call    _printf
.text:080487E1                 mov     dword ptr [esp], 7 ; status
.text:080487E8                 call    _exit
.text:080487ED ; ---------------------------------------------------------------------------
.text:080487ED
.text:080487ED SUCCESS:
.text:080487ED                 mov     dword ptr [esp], offset aW3llD03Y0uR50L ; "W3LL d0|\\|3, y0u'r 50 L337 |\\|0W..."
.text:080487F4                 call    _printf
.text:080487F9                 mov     eax, [esp+14h]
.text:080487FD                 mov     [esp], eax      ; ptr
.text:08048800                 call    _free
.text:08048805                 leave
.text:08048806                 retn
.text:08048806 sub_804857C     endp

It ensures the following conditions are met (xor_mypass designates the user input after the previous XOR transformation) :

xor_mypass[2] = xor_mypass[4] = xor_mypass[5] = xor_mypass[6] = xor_mypass[8] = xor_mypass[9] = xor_mypass[10] = xor_mypass[11] = xor_mypass[12] = xor_mypass[13]
xor_mypass[14] = 0x76

Sum up and solution

Sum up

Here is a sum up of the conditions:

Test Condition
test 1
mypass[0] + mypass[1] + ... + mypass[n] + 0xA = 1337
test 2
mypass[1] = '1' (0x31)
mypass[3] = '3' (0x33)
mypass[7] = '7' (0x37)
test 3
mypass[0] = mypass[2]
test 4
xor_mypass[2] = xor_mypass[4] = xor_mypass[5] = xor_mypass[6] = xor_mypass[8] = xor_mypass[9] = xor_mypass[10] = xor_mypass[11] = xor_mypass[12] = xor_mypass[13]
xor_mypass[14] = 0x76

Regarding the last test, we know that bit #14 should be equal to 0x76 after the double XOR transformation. As a consequence, it shoud be equal to 0x76 ^ 0x24 = 0x52 ('R') before the transformation.

With all that in mind, here is how the user input should look like:

┌─────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ bit │  00  │  01  │  02  │  03  │  04  │  05  │  06  │  07  │  08  │  09  │  10  │  11  │  12  │  13  │  14  │  ... │   n  │
├─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ hex │ 0x31 │   *  │   *  │ 0x33 │   *  │   *  │   *  │ 0x37 │   *  │   *  │   *  │   *  │   *  │   *  │ 0x52 │  ... │  ... │   =>   SUM = 1337 - 0xA
├─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ ord │  1   │   *  │   *  │  3   │   *  │   *  │   *  │  7   │   *  │   *  │   *  │   *  │   *  │   *  │  R   │  ... │  ... │
└─────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

If the user input is 15 characters long, let's guess the unknown character (*) as follows:

>>> (1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52) / 11
99
>>> (1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52) % 11
1

99 is in the range of the printable characters but as there is a remainder to the division, we need another unknown character to the user input and it should be in the range of the printable characters ([0x21-0x7E]). Let's start by guessing bit #15 to 0x21:

>>> (1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52 - 0x21) / 11
96
>>> (1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52 - 0x21) % 11
1

96 is in the range of the printable characters but there is a remainder to the division, which could not fit for an additional character.

Let's try with 0x22:

>>> (1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52 - 0x22) / 11
96
>>> hex((1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52 - 0x22) / 11)
'0x60'
>>> (1337 - 0xA - 0x31 - 0x33 - 0x37 - 0x52 - 0x22) % 11
0

This time, it's perfect because the division has no remainder. Hence, here are the values we have found:

┌─────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ bit │  00  │  01  │  02  │  03  │  04  │  05  │  06  │  07  │  08  │  09  │  10  │  11  │  12  │  13  │  14  │  15  │
├─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ hex │ 0x31 │ 0x60 │ 0x60 │ 0x33 │ 0x60 │ 0x60 │ 0x60 │ 0x37 │ 0x60 │ 0x60 │ 0x60 │ 0x60 │ 0x60 │ 0x60 │ 0x52 │ 0x22 │   =>   SUM = 1337 - 0xA
├─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ ord │  1   │   `  │   `  │  3   │   `  │   `  │   `  │  7   │   `  │   `  │   `  │   `  │   `  │   `  │  R   │   "  │
└─────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

Solution

$ ./1337-patched 
Ready to become 1337?
`1`3```7``````R"
W3LL d0|\|3, y0u'r 50 L337 |\|0W...

Comments

blog comments powered by Disqus

Keywords: grehack-2013 assembly x86 reverse-engineering crackme