vendredi 28 mai 2010

BratAlarm's Just a little crackme

It's been some time since I updated my blog but today I got bored and reversed a very little crackme.
It is the BratAlarm "Just a little crackme" that I'm going to talk about.
It was a bit interesting in the sense that you need to have basic mathematics knowledge.

Basic maths knowledge

Complex numbers are used throughout the whole keygenme to generate the serial.

Complex number basic operations used are the following :
multiplication : (a, b) * (c, d) = (a*c - b*d, b*c + a*d) = (a + i*b) * (c + i*d)
addition : (a, b) + (c, d) = (a + c, b + d) = (a + i*b) + (c + i*d)

Where is the serial checking and generation located?
First of all, this keygenme wasn't packed nor obfuscated in any sort so it was pretty simple to find out
where the interesting parts are :
- API analysis : DialogBoxParamA
- Strings

Using these twos clues, we can extract the fact that everything happens in DialogFunc() and that it is using complex numbers.

How is the serial generated then?

First we need to know what's the serial pattern.
From the following disassembly :
.text:00401129                 mov     serial_part1_real, eax
.text:0040112E                 add     edi, 9
.text:00401131                 mov     byte ptr [edi+8], 0
.text:00401135                 push    edi
.text:00401136                 call    str2num
.text:0040113B                 mov     serial_part1_imaginary, eax
.text:00401140                 add     edi, 9
.text:00401143                 mov     byte ptr [edi+8], 0
.text:00401147                 push    edi
.text:00401148                 call    str2num
.text:0040114D                 mov     serial_part2_real, eax
.text:00401152                 add     edi, 9
.text:00401155                 mov     byte ptr [edi+8], 0
.text:00401159                 push    edi
.text:0040115A                 call    str2num
.text:0040115F                 mov     serial_part2_imaginary, eax

We can safely say that the serial is of some form like that :
AAAAAAAA-BBBBBBBB-CCCCCCCC-DDDDDDDD

The serial is generated in many parts :
* Get username
* Generate serial
- Do a checksum of the string and use it to generate a real and imaginary part, you get Za
- Use some magic to generate a value for a second complex number, you get Zb
- Then we must resolve some equation to get the serial

These are the functions needed to create the serial :
- strsum() : a checksum using all the characters in a string
- str2num() : Convert hexdigit in ASCII to the number form
- gen_magic() : Generate some value using a magic number and the string

The checksum function :
.text:004010B5 strsum:                                 ; CODE XREF: DialogFunc+91
.text:004010B5                 mov     dl, [esi]
.text:004010B7                 add     eax, edx
.text:004010B9                 inc     esi
.text:004010BA                 test    edx, edx
.text:004010BC                 jnz     short strsum


The generation of first number C1 :
.text:004010BE                 mov     ComplexNumber1_real, eax ; Re(C1)
.text:004010C3                 dec     eax
.text:004010C4                 imul    eax, 3
.text:004010C7                 mov     ComplexNumber1_imaginary, eax ; Im(C1)

Magic happens!
.text:004010D8 gen_magic2:                             ; CODE XREF: DialogFunc+B7 j
.text:004010D8                 mov     dl, [esi]
.text:004010DA                 xor     eax, edx
.text:004010DC                 rol     eax, 5
.text:004010DF                 inc     esi
.text:004010E0                 test    edx, edx
.text:004010E2                 jnz     short gen_magic2

Generation of C2 :
.text:004010E4                 xor     edx, edx
.text:004010E6                 mov     ecx, 7A69h
.text:004010EB                 div     ecx
.text:004010ED                 mov     ComplexNumber2_real, edx ; Re(C2)
.text:004010F3                 and     eax, 0FFFh
.text:004010F8                 mov     ComplexNumber2_imaginary, eax ; Im(C2)

str2num()
.text:004012C5 str2num         proc near               ; CODE XREF: DialogFunc+F9 p
.text:004012C5                                         ; DialogFunc+10B p ...
.text:004012C5
.text:004012C5 arg_0           = dword ptr  8
.text:004012C5
.text:004012C5                 push    ebp
.text:004012C6                 mov     ebp, esp
.text:004012C8                 pusha
.text:004012C9                 xor     eax, eax
.text:004012CB                 xor     edx, edx
.text:004012CD                 mov     ecx, 8
.text:004012D2                 mov     esi, [ebp+arg_0]
.text:004012D5
.text:004012D5 loc_4012D5:                             ; CODE XREF: str2num+28 j
.text:004012D5                 mov     dl, [esi]
.text:004012D7                 test    dl, dl
.text:004012D9                 jz      short loc_4012EF
.text:004012DB                 sub     dl, 30h ; '0'
.text:004012DE                 cmp     dl, 0Ah
.text:004012E1                 jb      short loc_4012E6
.text:004012E3                 sub     dl, 7           ; hex digit part
.text:004012E6
.text:004012E6 loc_4012E6:                             ; CODE XREF: str2num+1C j
.text:004012E6                 shl     eax, 4
.text:004012E9                 or      eax, edx
.text:004012EB                 inc     esi
.text:004012EC                 dec     ecx
.text:004012ED                 jnz     short loc_4012D5
.text:004012EF
.text:004012EF loc_4012EF:                             ; CODE XREF: str2num+14 j
.text:004012EF                 mov     [ebp+arg_0], eax
.text:004012F2                 popa
.text:004012F3                 mov     eax, [ebp+arg_0]
.text:004012F6                 leave
.text:004012F7                 retn    4
.text:004012F7 str2num         endp

Now going to check the serial generation part.
It is done in two routines :

* First routine
.text:004011F1 gen_serial_part1 proc near              ; CODE XREF: DialogFunc+15C
.text:004011F1
.text:004011F1 ComplexResult2  = byte ptr -10h
.text:004011F1 ComplexResult1  = byte ptr -8
.text:004011F1 ComplexResult   = dword ptr  8
.text:004011F1 ComplexNumber   = dword ptr  0Ch
.text:004011F1
.text:004011F1                 push    ebp
.text:004011F2                 mov     ebp, esp
.text:004011F4                 add     esp, 0FFFFFFF0h
.text:004011F7                 pusha
.text:004011F8                 mov     edi, [ebp+ComplexResult]
.text:004011FB                 mov     esi, [ebp+ComplexNumber]
.text:004011FE                 lea     ebx, [ebp+ComplexResult1]
.text:00401201                 lea     ecx, [ebp+ComplexResult2]
.text:00401204                 push    esi
.text:00401205                 push    esi
.text:00401206                 push    ebx
.text:00401207                 call    complex_multiply
.text:0040120C                 push    offset serial_part1_real
.text:00401211                 push    esi
.text:00401212                 push    ecx
.text:00401213                 call    complex_multiply
.text:00401218                 push    ecx
.text:00401219                 push    ebx
.text:0040121A                 push    edi
.text:0040121B                 call    complex_add
.text:00401220                 push    offset serial_part2_real
.text:00401225                 push    edi
.text:00401226                 push    edi
.text:00401227                 call    complex_add
.text:0040122C                 popa
.text:0040122D                 leave
.text:0040122E                 retn    8
.text:0040122E gen_serial_part1 endp

So we have this :
Za = SP2 + C3 * SP1 + C3 * C3

* Second routine
.text:00401231 gen_serial_part2 proc near              ; CODE XREF: DialogFunc+16B
.text:00401231
.text:00401231 ComplexResult2  = byte ptr -10h
.text:00401231 ComplexResult1  = byte ptr -8
.text:00401231 ComplexResult   = dword ptr  8
.text:00401231 ComplexNumber   = dword ptr  0Ch
.text:00401231
.text:00401231                 push    ebp
.text:00401232                 mov     ebp, esp
.text:00401234                 add     esp, 0FFFFFFF0h
.text:00401237                 pusha
.text:00401238                 mov     edi, [ebp+ComplexResult]
.text:0040123B                 mov     esi, [ebp+ComplexNumber]
.text:0040123E                 lea     ebx, [ebp+ComplexResult1]
.text:00401241                 lea     ecx, [ebp+ComplexResult2]
.text:00401244                 push    offset ComplexNumber1_real
.text:00401249                 push    esi
.text:0040124A                 push    ebx
.text:0040124B                 call    complex_add
.text:00401250                 push    offset ComplexNumber2_real
.text:00401255                 push    esi
.text:00401256                 push    ecx
.text:00401257                 call    complex_add
.text:0040125C                 push    ecx
.text:0040125D                 push    ebx
.text:0040125E                 push    edi
.text:0040125F                 call    complex_multiply
.text:00401264                 popa
.text:00401265                 leave
.text:00401266                 retn    8
.text:00401266 gen_serial_part2 endp

We obtain this :
Zb = (C1 + C3)*(C2 + C3)

Next the serial is checked as followed :
Za = Zb
SP2 + C3 * SP1 + C3 * C3 = (C1 + C3)*(C2 + C3)
SP2 + C3 * SP1 + C3 * C3 = C1 * C2 + C1 * C3 + C3 * C2 + C3 * C3
SP2 + C3 * SP1 + C3 * C3 = C1 * C2 + C3 * (C1 + C2) + C3 * C3
SP2 + C3 * SP1 = C1 * C2 + C3 * (C1 + C2)

Using identification, we can see that :
SP1 = C1 + C2
SP2 = C1 * C2

Here is the C source for the keygen :
#include <stdlib.h>
#include <stdio.h>

struct complex_t {
    // real part
    int real;
    // imaginary part
    int i;
};

// complex number multiplication
struct complex_t* complex_multiply (struct complex_t **result,
                                    struct complex_t *complex1,
                                    struct complex_t *complex2)
{
    // check pointer validity
    if (!result || !complex1 || !complex2)
        return NULL;

    // check pointer validity
    if (!*result)
        *result = malloc(sizeof(**result));

    // we calculate the real part
    (*result)->real = complex1->real * complex2->real - complex1->i * complex2->i;
    // we calculate the imaginary part
    (*result)->i = complex1->i * complex2->real + complex1->real * complex2->i;

    // result = (a+bi)*(c+di) = (a*c - b*d) + (b*c + a*d)i

    return *result;
}

// complex number addition
struct complex_t* complex_add (struct complex_t **result,
                               struct complex_t *complex1,
                               struct complex_t *complex2)
{
    // check pointer validity
    if (!result || !complex1 || !complex2)
        return NULL;

    // check pointer validity
    if (!*result)
        *result = malloc(sizeof(**result));

    // we calculate the real part
    (*result)->real = complex1->real + complex2->real;
    // we calculate the imaginary part
    (*result)->i = complex1->i + complex2->i;

    // result = (a+bi)+(c+di) = (a+c) + (b+d)i

    return *result;
}

unsigned int strsum (unsigned char *str, size_t len) {
    size_t i;
    int sum;

    // check pointers
    if (!str || !len)
        return -1;

    // sum
    for (i = 0, sum = 0; *str && i < len; i++)
        sum += str[i];

    return sum;
}

unsigned int rol32 (unsigned int val, size_t shift) {
    shift = shift % 32;
    return (val << shift) | (val >> (32 - shift));
}

int gen_magic (unsigned char *str, size_t len) {
    unsigned int magic = 0x12345678;
    unsigned char byte;

    // check pointers
    if (!str || !len)
        return -1;

    // magic happen
    do {
        byte = *str;
        magic ^= byte;
        magic = rol32(magic, 5);
        ++str;
    } while (byte);

    return magic;
}

struct complex_t** keygen (unsigned char *name, size_t len) {
    unsigned int magic;
    struct complex_t c1, c2;
    struct complex_t *s1 = NULL, *s2 = NULL, **serial;

    // compute Za and Zb
    c1.real = strsum(name, len);
    c1.i = (c1.real - 1) * 3;
    magic = gen_magic(name, len);
    c2.real = magic % 0x7a69;
    c2.i = (magic / 0x7a69) & 0xfff;

    // compute serial part 1    
    s1 = complex_add (&s1, &c1, &c2);
    // compute serial part 2
    s2 = complex_multiply (&s2, &c1, &c2);
    
    // show complex numbers
    printf ("(a, b) : (%x, %x)\n", c1.real, c1.i);
    printf ("(c, d) : (%x, %x)\n", c2.real, c2.i);
    // show serial calculations
    printf ("Serial part 1 = (a+c, b+d)\n");
    printf ("Serial part 2 = (a*c - b*d, b*c + a*d)\n");
    // show serial
    printf ("serial : %08X-%08X-%08X-%08X\n", s1->real, s1->i, s2->real, s2->i);
    
    return serial;
}

int main (int argc, char *argv[]) {
    unsigned char *username;

    username = calloc (1, 128);

    // ask username
    printf ("Please input username\n");
    gets(username);
    // show serial
    keygen (username, 128);
    
    return 0;
}

We don't need to reconstruct source code from keygenme but here it is for those who didn't follow :

// keygenme
int keygenme (unsigned char *name, size_t len) {
    unsigned int magic;
    struct complex_t *ctmp1 = NULL, *ctmp2 = NULL;
    struct complex_t c1, c2, c3;
    struct complex_t userserial_part1, userserial_part2;
    struct complex_t *serial_part1 = NULL, *serial_part2 = NULL;

    // part 1
    //
    c1.real = strsum (name, len);
    c1.i = (c1.real - 1) * 3;
    //
    magic = gen_magic(name, len);
    c2.real = magic % 0x7a69;
    c2.i = (magic / 0x7a69) & 0xfff;
    //
    c3.real = 3;
    c3.i = 0x4e1f;
    //
    userserial_part1.real = str2num(name, 8);
    userserial_part1.i = str2num(name + 9, 8);
    userserial_part2.real = str2num(name + 18, 8);
    userserial_part2.i = str2num(name + 27, 8);
    // we generate part 1
    ctmp1 = complex_multiply (&ctmp1, &c3, &c3);
    ctmp2 = complex_multiply (&ctmp2, &c3, &userserial_part1);
    serial_part1 = complex_add (&serial_part1, ctmp1, ctmp2);
    serial_part1 = complex_add (&serial_part1, serial_part1, &userserial_part2);
    // we generate part 2
    complex_add (&ctmp1, &c3, &c1);
    complex_add (&ctmp2, &c3, &c2);
    serial_part2 = complex_multiply (&serial_part2, ctmp2, ctmp1);
    
    return 0;
}

Hope you enjoyed reading this small tutorial.

Happy reversing,

m_101

- link : Just a Little Crackme