GreHack-2013/150-1337
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:
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 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
Keywords: grehack-2013 assembly x86 reverse-engineering crackme