Rating:
# 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](challenge/prime.tar.gz), 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:
>```bash
>$ 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:
>```c
>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 = &arg;;
> 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:
>```c
> 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:
>```c
> 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:
>```c
>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:
>```bash
>gdb-peda$ b *0x08048D9C
>gdb-peda$ r
>(.. we see v7 = 0x082234b0 ..)
>gdb-peda$ disas 0x082234b0, 0x8223510
>Dump of assembler code from 0x82234b0 to 0x8223510:
>```
>```asm
>=> 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:
>```c
>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](solution/crackmeprimesolution.py) 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:
>```python
>#!/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:
>```bash
>$ 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
