Nuit Du Hack CTF 2015 – Prime Crackme

Intro

Recently I played the Nuit Du Hack CTF and one the challenges I had a look at was the “Prime Crackme” from the reversing category. The challenge is still available at http://quals.nuitduhack.com/challenges/view/3

The goal of the challenge is to create a valid serial or keygen and its description and name already hints that it could be related to prime values so let’s have a look.

 

Analyzing the crackme

The crackme is a 32 bits Linux ELF binary without its symbols stripped thus making it easier to analyze the code.

h4x@kali:~/nuitduhack$ file crackme
crackme: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.26, BuildID[sha1]=0x17916e0f7c4f5d911ba1bb2229286410a29d39ed, not stripped

I loaded the crackme into IDA and used Hex-Rays decompiler plugin to decompile the code to C and renamed the variable names to something which makes more sense.

 

Main function

int __cdecl main(int argc, const char **serial, const char **envp)
{
    int result; // eax@6
    signed int prt1_bit; // esi@7
    int prt2_bit; // esi@7
    int prt3_bit; // esi@7
    int prt4_bit; // esi@7
    int prt5_bit; // esi@7
    char prt6[5]; // [sp+0h] [bp-4Eh]@7
    char prt5[5]; // [sp+5h] [bp-49h]@7
    char prt4[5]; // [sp+Ah] [bp-44h]@7
    char prt3[5]; // [sp+Fh] [bp-3Fh]@7
    char prt2[5]; // [sp+14h] [bp-3Ah]@7
    char prt1[5]; // [sp+19h] [bp-35h]@7
    int prt6_int; // [sp+1Eh] [bp-30h]@7
    int prt5_int; // [sp+22h] [bp-2Ch]@7
    int prt4_int; // [sp+26h] [bp-28h]@7
    int prt3_int; // [sp+2Ah] [bp-24h]@7
    int prt2_int; // [sp+2Eh] [bp-20h]@7
    int prt1_int; // [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(serial[1]) == 29 )
    {
        if ( strchr(serial[1], '0') )
        {
            puts("Invalid char");
            result = 1;
        }
        else
        {
            memset(prt1, 0, 5u);
            memset(prt2, 0, 5u);
            memset(prt3, 0, 5u);
            memset(prt4, 0, 5u);
            memset(prt5, 0, 5u);
            memset(prt6, 0, 5u);
            strncpy(prt1, serial[1], 4u);
            strncpy(prt2, serial[1] + 5, 4u);
            strncpy(prt3, serial[1] + 10, 4u);
            strncpy(prt4, serial[1] + 15, 4u);
            strncpy(prt5, serial[1] + 20, 4u);
            strncpy(prt6, serial[1] + 25, 4u);
            prt1_int = strtol(prt1, 0, 16);
            prt2_int = strtol(prt2, 0, 16);
            prt3_int = strtol(prt3, 0, 16);
            prt4_int = strtol(prt4, 0, 16);
            prt5_int = strtol(prt5, 0, 16);
            prt6_int = strtol(prt6, 0, 16);
            prt1_bit = c1(prt1_int);
            prt2_bit = c1(prt2_int) & prt1_bit;
            prt3_bit = c1(prt3_int) & prt2_bit;
            prt4_bit = c1(prt4_int) & prt3_bit;
            prt5_bit = c1(prt5_int) & prt4_bit;
            result = prt5_bit & c1(prt6_int);
            if ( result )
            {
                result = c1((prt4_int + prt3_int + prt2_int + prt1_int + prt5_int) % prt6_int);
                if ( result )
                {
                    puts("Well done !!!");
                    result = printf("%s is good serial\n", serial[1]);
                }
            }
        }
    }
    else
    {
        puts("Wrong format");
        result = 1;
    }
    return result;
}

First our input serial length is checked(line 29) and has to be 29 characters next it checks if our serial contains any ‘0’ characters(line 31), if such character is found a “Wrong char” message is shown and the crackme exits. Next it zero’s the local variables prt1, prt2, prt3, prt4, prt5, prt6 using ‘memset'(line 38..43) and then copies parts from our input serial into those variables(line 44..49) with ‘strncpy’ each copied part is 4 characters. Based on the pointer adjustment +5, +10, … at line 45,46,… we can see that every 5th character of our input serial is ignored.

Based on this we can construct the following possible serial format 1234-1234-1234-1234-1234-1234

If we continue looking at the code we can see that the copied parts are converted into long integers using ‘strtol'(line 50..55) and stored in prt1_int, prt2_int, prt3_int, prt4_int, prt5_int, prt6_int, the base value of 16 indicates it converts from a hex string into an integer.

Next we can see it call’s ‘c1’ with our serial parts(line 56..61), let’s have a closer look at the ‘c1’ function to see what it does..

signed int __cdecl c1(int a1)
{
    signed int result; // eax@2
    int codelen; // [sp+0h] [bp-138h]@3
    int iv[2]; // [sp+4h] [bp-134h]@1
    char v4[140]; // [sp+Ch] [bp-12Ch]@1
    char v5[140]; // [sp+98h] [bp-A0h]@1
    int (__cdecl *func)(int); // [sp+124h] [bp-14h]@3
    int keylen; // [sp+128h] [bp-10h]@1
    int key; // [sp+12Ch] [bp-Ch]@1

    iv[0] = 0x3039;
    iv[1] = 0xD431;
    key = (int)"azertyuiopazerty";
    keylen = 16;
    if ( aes_init("azertyuiopazerty", 16, iv, v5, v4) )
    {
        result = -1;
    }
    else
    {
        codelen = 96;
        func = (int (__cdecl *)(int))aes_decrypt(v4, buf_0, &codelen);
        EVP_CIPHER_CTX_cleanup(v5);
        EVP_CIPHER_CTX_cleanup(v4);
        result = func(a1) != 0;
    }
    return result;
}

When we look at the code we can see it uses AES with a hardcoded key and IV(line 12..14). Looking further at the code we can see the AES is used to decrypt the data in ‘buf_0’ and the returned pointer from the call to ‘aes_decrypt’ being cast into a function(line 23) ‘func’. At line 26 the ‘func’ function is called and our serial part is being passed as its argument. I figured out that this hidden code might hold some interesting info on the algorithm so I decided to dump the decrypted code using GDB and patched the code back into the crackme and decompiled the function.

BOOL __cdecl buf_0(signed int a1)
{
    signed int v2; // [sp+8h] [bp-8h]@1
    signed int i; // [sp+Ch] [bp-4h]@1

    v2 = 0;
    for ( i = 1; ; ++i )
    {
        if ( i <= a1 )
        {
            if ( a1 % i )
                continue;
            ++v2;
            if ( v2 <= 2 )
                continue;
        }
        break;
    }
    return v2 == 2;
}

I quickly identified the code as a basic prime validation algorithm, it takes our input serial integer and checks if the value is a prime value, if so it returns 1 else 0
So knowing this we can continue looking at the ‘main’ function code…

At line 56..61 it takes our serial parts 1 .. 6 and checks if every part is a prime and bitwise AND’s the results with the previous prime check result. The check at line 62 check’s if result is 1 this would be the case if all our serial parts were valid prime values. If continue looking at the code we can see another check(line 65) based on prime check above it(line 64)

This last prime check sums the serial parts 1 .. 5 and then does a modulo serial part 6, the remainder of this should also be a valid prime value

((prt1+prt2+prt3+prt4+prt5) % prt6) == prime

 

let’s get cracking!

I decided to write a dirty python keygen which first searches all prime values less than 65535  with no zero’s in it and then uses this list of prime values to bruteforce a valid combination. Searching the valid prime values takes some time to complete, optional you could collect them just once and store them in a separate file and include that into the keygen. The argument passed  to the keygen is the amount of serials to generate.

#!/usr/bin/env python
import sys

def isprime(v):
    v2 = 0
    i = 0
    while True:
        i += 1
        if i <= v:
            if v % i:
                continue
            v2 += 1
            if v2 <= 2:
                continue
        break
    return v2 == 2

def isnullsafe(v):
    return not ((v & 0x000f == 0) or (v & 0x00f0 == 0) or (v & 0x0f00 == 0) or (v & 0xf000 == 0))

# create a list with prime values
def safeprimes():
    primes = []
    for i in range(4369, 65535): # 0x1111 .. 0xFFFF
        if isnullsafe( i ):
            if isprime( i ):
                primes.append( i )
    return primes

def main(serials):
    print 'Collecting safeprimes'
    primes = safeprimes()
    pcount = len(primes)
    print 'Searching serial(s)'
    found = 0
    for i in range(pcount - 5):
        primesum  = primes[i]
        primesum += primes[i + 1]
        primesum += primes[i + 2]
        primesum += primes[i + 3]
        primesum += primes[i + 4]
        for prime in primes:
            if isprime( primesum % prime ):
                # print serial
                print "%04X-%04X-%04X-%04X-%04X-%04X" % (
                    primes[i],
                    primes[i + 1],
                    primes[i + 2],
                    primes[i + 3],
                    primes[i + 4],
                    prime)
                found += 1
                if found == serials:
                    return
    return

if __name__ == '__main__':
    try:
        main(int(sys.argv[1]))
    except KeyboardInterrupt:
        print 'Closed by user'

Testing the keygen

h4x@kali:~/nuitduhack$ ./crackme.py 1
Collecting safeprimes
Searching serial(s)
1115-1127-112D-1139-1145-116F
h4x@kali:~/nuitduhack$ ./crackme 1115-1127-112D-1139-1145-116F
Well done !!!
1115-1127-112D-1139-1145-116F is good serial

 

GAME OVER

 

Advertisements