Nuit Du Hack CTF 2015: Crackme Prime
Category: Reversing Points: 150 Description:
"I am Optimus Prime, and I send this message to any surviving Autobots taking refuge among the stars. We are here, we are waiting."
Keygen me, I'm the Prime.
Validate your serial here : http://crackmeprime.challs.nuitduhack.com/
Write-up
The challenge consists of reversing a binary in order to write a keygen (or at least find a single valid serial) for it. As usual we start by checking our file:
$ file ./crackme crackme: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=0x92d632c664b683dc98873fe1c785d1e6928e7272, not stripped
A statically linked unstripped 32-bit ELF binary it is. The next thing to do is loading it in IDA Pro and decompiling the main routine and the functions it calls:
int __cdecl main(int argc, const char **argv, const char **envp) { int result; // eax@6 signed int v4; // esi@7 int v5; // esi@7 int v6; // esi@7 int v7; // esi@7 int v8; // esi@7 char v9; // [sp+0h] [bp-4Eh]@7 char v10; // [sp+5h] [bp-49h]@7 char v11; // [sp+Ah] [bp-44h]@7 char v12; // [sp+Fh] [bp-3Fh]@7 char dest; // [sp+14h] [bp-3Ah]@7 char s; // [sp+19h] [bp-35h]@7 int v15; // [sp+1Eh] [bp-30h]@7 int v16; // [sp+22h] [bp-2Ch]@7 int v17; // [sp+26h] [bp-28h]@7 int v18; // [sp+2Ah] [bp-24h]@7 int v19; // [sp+2Eh] [bp-20h]@7 int v20; // [sp+32h] [bp-1Ch]@7 int *v21; // [sp+46h] [bp-8h]@1 v21 = &argc; if ( argc <= 1 ) { puts("please give me serial number"); exit(0); } if ( strlen(argv[1]) == 29 ) { if ( strchr(argv[1], 48) ) { puts("Invalid char"); result = 1; } else { memset(&s, 0, 5u); memset(&dest, 0, 5u); memset(&v12, 0, 5u); memset(&v11, 0, 5u); memset(&v10, 0, 5u); memset(&v9, 0, 5u); strncpy(&s, argv[1], 4u); strncpy(&dest, argv[1] + 5, 4u); strncpy(&v12, argv[1] + 10, 4u); strncpy(&v11, argv[1] + 15, 4u); strncpy(&v10, argv[1] + 20, 4u); strncpy(&v9, argv[1] + 25, 4u); v20 = strtol(&s, 0, 16); v19 = strtol(&dest, 0, 16); v18 = strtol(&v12, 0, 16); v17 = strtol(&v11, 0, 16); v16 = strtol(&v10, 0, 16); v15 = strtol(&v9, 0, 16); v4 = c1(v20); v5 = c1(v19) & v4; v6 = c1(v18) & v5; v7 = c1(v17) & v6; v8 = c1(v16) & v7; result = v8 & c1(v15); if ( result ) { result = c1((v17 + v18 + v19 + v20 + v16) % v15); if ( result ) { puts("Well done !!!"); result = printf("%s is good serial\n", argv[1]); } } } } else { puts("Wrong format"); result = 1; } return result; }
From these lines:
if ( strlen(argv[1]) == 29 ) { if ( strchr(argv[1], 48) ) { puts("Invalid char"); result = 1; }
We know the serial is supposed to be 29 characters long and cannot contain the '0' character. The series of strncpy calls tells us the serial gets seperated into 6 4-digit values which get converted to a long from hex representation. This gives us the following serial format:
XXXX-XXXX-XXXX-XXXX-XXXX-XXXX
Where X is [1-9A-F].
Next we see a series of calls to c1 with the various serial segments as arguments resulting in the following validation check:
v8 = (c1(v16) & (c1(v17) & (c1(v18) & (c1(v19) & c1(v20))))) result = v8 & c1(v15) if ( result ) { result = c1((v17 + v18 + v19 + v20 + v16) % v15); if ( result ) { puts("Well done !!!"); result = printf("%s is good serial\n", argv[1]); } }
Let's look at the c1 function:
signed int __cdecl c1(int a1) { signed int result; // eax@2 int v2; // [sp+0h] [bp-138h]@3 int v3; // [sp+4h] [bp-134h]@1 int v4; // [sp+8h] [bp-130h]@1 char v5; // [sp+Ch] [bp-12Ch]@1 char v6; // [sp+98h] [bp-A0h]@1 int (__cdecl *v7)(int); // [sp+124h] [bp-14h]@3 int v8; // [sp+128h] [bp-10h]@1 int v9; // [sp+12Ch] [bp-Ch]@1 v3 = 12345; v4 = 54321; v9 = (int)"azertyuiopazerty"; v8 = 16; if ( aes_init("azertyuiopazerty", 16, &v3, &v6, &v5) ) { result = -1; } else { v2 = 96; v7 = (int (__cdecl *)(int))aes_decrypt(&v5, &buf_0, &v2); EVP_CIPHER_CTX_cleanup(&v6); EVP_CIPHER_CTX_cleanup(&v5); result = v7(a1) != 0; } return result; }
The function decrypts a static buffer using openssl_AES with the key "azertyuiopazerty" and salt 12345 and subsequently calls that 'hidden' function over a1 and returns the result. Let's put a breakpoint after the buffer gets decrypted:
gdb-peda$ b *0x08048D9C gdb-peda$ r (.. we see v7 = 0x082234b0 ..) gdb-peda$ disas 0x082234b0, 0x8223510 Dump of assembler code from 0x82234b0 to 0x8223510:=> 0x082234b0: push ebp 0x082234b1: mov ebp,esp 0x082234b3: sub esp,0x10 0x082234b6: mov DWORD PTR [ebp-0x8],0x0 0x082234bd: mov DWORD PTR [ebp-0x4],0x1 0x082234c4: jmp 0x82234e3 0x082234c6: mov eax,DWORD PTR [ebp+0x8] 0x082234c9: cdq 0x082234ca: idiv DWORD PTR [ebp-0x4] 0x082234cd: mov eax,edx 0x082234cf: test eax,eax 0x082234d1: jne 0x82234df 0x082234d3: add DWORD PTR [ebp-0x8],0x1 0x082234d7: cmp DWORD PTR [ebp-0x8],0x2 0x082234db: jle 0x82234df 0x082234dd: jmp 0x82234eb 0x082234df: add DWORD PTR [ebp-0x4],0x1 0x082234e3: mov eax,DWORD PTR [ebp-0x4] 0x082234e6: cmp eax,DWORD PTR [ebp+0x8] 0x082234e9: jle 0x82234c6 0x082234eb: cmp DWORD PTR [ebp-0x8],0x2 0x082234ef: jne 0x82234f8 0x082234f1: mov eax,0x1 0x082234f6: jmp 0x82234fd 0x082234f8: mov eax,0x0 0x082234fd: leave 0x082234fe: ret
Manually translating this disassembly listing to pseudo-code yields:
function v7(a1) { var1 = 0 var2 = 1 while(var2 <= a1) { if(a1 % var2 == 0) { var1++ if(var1 > 2) break; } var2++ } if(var1 != 2) { return 0; } else { return 1; } }
Which is effectively a prime-number check that returns 1 if a1 is prime and 0 if it isn't. This means that we now know our serial should look as follows:
X0-X1-X2-X3-X4-X5
Where every Xi is a 4-digit prime number (in hex representation) without containing zeros and in addition (sum(A1..A5) % A6) is prime too. We wrote a little keygen to generate valid serials. It works by finding a valid prime and using it for all but 1 of the first 5 fields and for the last field. In this fashion we only have to bruteforce one of the first 5 fields so that its addition to the sum of the others will leave a remainder (modulo the found prime) that is itself prime:
#!/usr/bin/python # # Nuit Du Hack CTF 2015 # Crackme Prime (REVERSING/150) Solution # # @a: Smoke Leet Everyday # @u: https://github.com/smokeleeteveryday # from pyprimes import * def isValidSerial(v16, v17, v18, v19, v20, v15): v8 = (isprime(v16) and (isprime(v17) and (isprime(v18) and (isprime(v19) and isprime(v20))))) and isprime(v15) return isprime((v17 + v18 + v19 + v20 + v16) % v15) def keygen(startPoint): primeiterator = primes_above(startPoint) p = next(primeiterator) # Generate valid prime while('0' in hex(p)[2:]): p = next(primeiterator) # Use as first v17,v18,v19,v20,v15 only bruteforce v16 A = [p]*6 while not(isValidSerial(A[0], A[1], A[2], A[3], A[4], A[5])): A[0] = next(primeiterator) while('0' in hex(A[0])[2:]): A[0] = next(primeiterator) return "-".join(hex(A[i])[2:] for i in range(6)) print keygen(0x2AD0)
Which gives us the following result:
$ python crackmeprimesolution.py 55d9-2add-2add-2add-2add-2add $ ./crackme 55d9-2add-2add-2add-2add-2add Well done !!! 55d9-2add-2add-2add-2add-2add is good serial
Submitting the serial to the online validator gives us the flag:
Congratulation! The flag is : WowThatWasEasyAES