Cracking "The XOR Algorithm II"

[supersnail]

Bonjour,

Ce tutoriel a pour but de montrer en quelque sorte la "démarche" de résolution d'un keygenme assez simple mais loin d'être trivial (trouvé sur http://www.crackmes.de/, très bon site où vous pouvez trouver des crackmes/keygenme en tous genres et de tous les niveaux).

Ce tuto se découpe en 3 parties: tout d'abord le premier contact avec le keygenme, puis l'analyse de l'algorithme en lui-même, pour terminer sur l'élaboration d'un keygen.
Comme vous pouvez le constater, ce tuto repose plus sur des morceaux de code commentés que sur de réelles explications. Il est du coup recommandé d'avoir quelques bases en assembleur (ou de profiter de ce tuto pour vous perfectionner en assembleur ) pour la compréhension de ce tuto (prendre des notes à côté n'est pas une mauvaise idée non plus ).

Bref vous pouvez trouver le crackme ici.

I - Premier contact avec le keygenme

Il est désormais temps d'avoir notre premier contact avec notre keygenme, pour cela on va l'ouvrir avec notre désassembleur préféré (pour ma part ce sera IDA Pro), qui nous donne un point d'entrée ressemblant à peu près à ceci:

Code ASM :

public start
start proc near
push    0               ; lpModuleName
call    GetModuleHandleA
mov     hInstance, eax
push    0               ; dwInitParam
push    offset DialogFunc ; lpDialogFunc
push    0               ; hWndParent
push    65h             ; lpTemplateName
push    hInstance       ; hInstance
call    DialogBoxParamA
push    eax             ; uExitCode
call    ExitProcess
start endp

On constate alors que notre programme crée un dialog à partir d'une ressource (que je vous invite à regarder à l'aide de "Resource Hacker"), dont la WndProc (la fonction qui traite les évènements, pour ceux qui n'ont jamais fait de dev sous Windows) a été nommée très logiquement "DialogFunc" par IDA. Allons donc jeter un oeil à cette fonction (que je ne posterai pas ici en entier, vu qu'il est assez "conséquent"). Notre crackme ayant besoin de récupérer la valeur notre mot de passe, on doit s'attendre à trouver un "GetDlgItemText" quelque part, et c'est le cas:

Code ASM :

.text:004010F2                 push    80h             ; cchMax
.text:004010F7                 push    offset String   ; String est une var globale contenant le serial
.text:004010FC                 push    3E9h            ; nIDDlgItem
.text:00401101                 push    [ebp+hDlg]      ; hDlg
.text:00401104                 call    GetDlgItemTextA
.text:00401109                 call    sub_40106E ; fonction mystérieuse
.text:0040110E                 xor     eax, eax
.text:00401110                 xor     ebx, ebx
.text:00401112                 xor     ecx, ecx
.text:00401114                 xor     edx, edx
.text:00401116                 lea     esi, aWeGoAboutOurDa ; "We go about our daily lives understandi"...
.text:0040111C                 lea     edi, unk_4030F1
loc_401122: ; boucle de comparaison
.text:00401122                 mov     al, [esi] ; esi est un pointeur vers la str aWeGoAboutOurDa
.text:00401124                 mov     cl, [edi] ; edi est un pointeur vers unk_4030F1
.text:00401126                 cmp     al, cl ; comparaison des caractères des 2 chaînes
.text:00401128                 jnz     short loc_40114F ; on saute vers un call à ExitProcess en cas de fail
.text:0040112A                 inc     esi ; on passe au char suivant de la str
.text:0040112B                 inc     edi ; on passe au char suivant du "unk"
.text:0040112C                 inc     edx
.text:0040112D                 cmp     edx, 0F0h
.text:00401133                 jz      short loc_401137 ; on jmp vers le "good boy" si on arrive à la fin
.text:00401135                 jmp     short loc_401122

On aperçoit ici un appel à une fonction mystérieuse juste après l'appel à GetDlgItemTextA, suivi d'une routine de comparaison entre la chaîne "aWeGoAbout" et le unk_4030F1. Cette fonction mystérieuse doit donc faire des rites sataniques sur aWeGoAbout ou sur le "unk" pour éviter que la comparaison échoue tout le temps.
Il est donc grand temps pour nous d'aller plonger dans cette fonction mystérieuse.

II - Voyage en terre inconnue

Une fois arrivé en 0040106E, on peut observer quelque chose similaire à ceci:

Code ASM :

 sub_40106E      proc near               ; CODE XREF: DialogFunc+2Cp
.text:0040106E                 push    ebp
.text:0040106F                 mov     ebp, esp
.text:00401071                 sub     esp, 10h
.text:00401074                 xor     ebx, ebx
.text:00401076                 xor     ecx, ecx
.text:00401078                 xor     edx, edx
.text:0040107A                 cmp     eax, 20h ; comparaison de la longueur du serial à 32
.text:0040107D                 jnz     short loc_4010B0 ; exit si le serial fait pas 32 caractères
.text:0040107F                 lea     edi, aWeGoAboutOurDa ; " on fout aWeGo dans edi
.text:00401085                 call    sub_401014 ; fonction mystérieuse 1
.text:0040108A                 mov     ebx, edx
.text:0040108C                 call    sub_401000 ; fonction mystérieuse 2
loc_401091:
.text:00401091                 lea     esi, String ; on fout le serial entré dans esi
.text:00401097                 cmp     byte ptr [edi], 0
.text:0040109A                 jz      short loc_4010B0 ; si on est à la fin de la str, GTFO
.text:0040109C                 add     esi, edx ; début de l'algo "mystérieux"
.text:0040109E                 mov     al, [esi]
.text:004010A0                 xor     [edi], al
.text:004010A2                 add     [edi], dl
.text:004010A4                 add     bl, [edi]
.text:004010A6                 add     bl, dl
.text:004010A8                 call    sub_401000 ; fonction mystérieuse 2
.text:004010AD                 inc     edi
.text:004010AE                 jmp     short loc_401091 ; on revient au début de la boucle
loc_4010B0:
.text:004010B0                 add     esp, 10h
.text:004010B3                 pop     ebp
.text:004010B4                 retn
.text:004010B4 sub_40106E      endp

Il nous reste maintenant à savoir quel rôle jouent la "fonction mystérieuse 1" et la "fonction mystérieuse 2" pour comprendre l'algo mis en oeuvre.

Examinons donc la "fonction mystérieuse 1":

Code ASM :

 sub_401014      proc near               ; CODE XREF: sub_40102D+12p
.text:00401014                                         ; sub_40106E+17p
.text:00401014                 xor     edx, edx
.text:00401016                 lea     esi, String ; charge le mdp rentré par l'utilisateur
.text:0040101C                 mov     ecx, 20h ; on place 32 dans le compteur
.text:00401021
.text:00401021 loc_401021:                             ; CODE XREF: sub_401014+14j
.text:00401021                 add     dl, [esi] ; on ajoute à dl le code ASCII du mdp
.text:00401023                 inc     esi ; on décale d'un caractère
.text:00401024                 dec     ecx ; on décrémente le compteur
.text:00401025                 cmp     ecx, 0
.text:00401028                 jg      short loc_401021
.text:0040102A                 xor     esi, esi
.text:0040102C                 retn
.text:0040102C sub_401014      endp

On observe ici une routine qui fait la somme des codes ASCII des caractères du mot de passe entré par l'utilisateur, le tout tronqué à 1 octet (la taille du registre dl).
Avant de pouvoir examiner la routine principale, il faut d'abord savoir ce que fait la "fonction mystérieuse 2", dont le code est posté ci-dessous:

Code ASM :

sub_401000 proc near
push    ecx
mov     eax, ebx
mov     ebx, 20h
mov     ecx, edx
xor     edx, edx
div     ebx
xor     ebx, ebx
xor     ecx, ecx
pop     ecx
retn
sub_401000 endp

On remarque que cette fonction place la valeur de ebx dans eax, qui sera divisé par ebx, qui vaut 32. Le quotient de la division se trouve dans eax, tandis que le reste se situe dans edx (cf la doc Intel).
Grâce à ces précieuses informations, on peut déduire de la fonction principale (sub_40106E) le processus de génération, dont le début est:
- Somme des codes ASCII du serial entré par l'utilisateur (on invoque "fonction mystérieuse 1")
- Modulo 32 de cette somme (on invoque "fonction mystérieuse 2" et on récupère edx)
Il faut maintenant comprendre la boucle principale de l'algo:

Code ASM :

loc_401091:
.text:00401091                 lea     esi, String ; on fout le serial entré dans esi
.text:00401097                 cmp     byte ptr [edi], 0
.text:0040109A                 jz      short loc_4010B0 ; si on est à la fin de la str, GTFO
.text:0040109C                 add     esi, edx ; on décale le mdp de la somme modulo 32
.text:0040109E                 mov     al, [esi] ; on récupère le code du caractère entré par l'user
.text:004010A0                 xor     [edi], al ;on xor aWeGo avec ce code
.text:004010A2                 add     [edi], dl ;on ajoute la somme modulo 32 à aWeGo
.text:004010A4                 add     bl, [edi]
.text:004010A6                 add     bl, dl ; on ajoute le caractère calculé à la somme modulo 32
.text:004010A8                 call    sub_401000 ; on refait un algo modulo 32
.text:004010AD                 inc     edi ; on décale aWeGo d'un caractère
.text:004010AE                 jmp     short loc_401091 ; on revient au début de la boucle

En une sorte de pseudo-C, notre algo donnerait quelque chose du genre:

Code C :


x = sumUserPassword() % 32; // fonction mystérieuse 1
int i;
for(i=0; str[i] !=0; i++) {
   aWeGoAboutOurDa[i] = (aWeGoAboutOurDa[i] ^ userPassword[x]) + x;
   x = (userPassword[x] + x) % 32
}

Cela transforme donc notre chaîne aWeGoAboutOurDa, qui va ensuite être comparée au unk qu'on a vu précédemment, et nous renvoyer le "good boy" si ces deux zones mémoires ont le même contenu.

III - Let's keygen it !

On remarque assez vite que l'algorithme qui "chiffre" aWeGoAboutOurDa dépend d'un paramètre lié à l'entrée de l'utilisateur, que nous ne connaissons évidemment pas. Cependant (et heureusement pour nous), ce paramètre ne peut avoir que 32 valeurs possibles (merci le modulo !), ce qui nous autorise à bruteforcer légèrement pour trouver la (ou les) bonnes clés. De plus, ce paramètre étant égal à la somme des codes des caractères du serial, il faut vérifier que le serial trouvé vérifie ce critère.

Ainsi, l'algo sera (toujours en "pseudo-C"):

Code C :


char serial[32];
for(x=0;x<32;i++) {
  int offset = x;
  while(aWeGoAboutOurDa[i] != 0) {
    serial[x] = (aWeGoAboutOurDa[i] ^ (unk_4030F1[i] -x);
    x = (unk_4030F1[x] + x) % 32
  }
  if (sumUserPassword(serial) == offset)
     printf("%s", serial);
}

Finalement, l'implémentation de notre keygen (en C) donne quelque chose comme:

Code C :

#include <stdio.h>

char *to_encode = "We go about our daily lives understanding almost nothing of the world."
                  " Few of us spend much time wondering why nature is the way it"
                  " is; where the cosmos came from;... why we remember the past and"
  " not the future; and why there is a universe.";


char encoded[] = {0x87, 0x2B, 0x73, 0x5A, 0x30, 0x20, 0x5F, 0x5F, 0x27, 0x39, 0x1E, 0x73, 0x2E, 0x64, 0x5D, 0x72, 0x29, 0x68, 0x76, 0x67, 0x19, 0x23, 0x42, 0x3C, 0x1E, 0x5C, 0x3D, 0x6D, 0x48, 0x78, 0x37, 0x37, 0x5B, 0x37, 0x47, 0x32, 0x52, 0x3A, 0x76, 0x69, 0x65, 0x64, 0x20, 0x2D, 0x54, 0x48, 0x3D, 0x39, 0x60, 0x2E, 0x52, 0x34, 0x3B, 0x6A, 0x71, 0x29, 0x8D, 0x2D, 0x5A, 0x6D, 0x47, 0x2B, 0x41, 0x6D, 0x4A, 0x38, 0x24, 0x6D, 0x29, 0x66, 0x72, 0x07, 0x5E, 0x6B, 0x20, 0x5D, 0x57, 0x24, 0x1B, 0x45, 0x68, 0x71, 0x60, 0x55, 0x37, 0x55, 0x70, 0x6E, 0x3A, 0x4C, 0x4F, 0x64, 0x35, 0x29, 0x33, 0x49, 0x73, 0x6A, 0x5D, 0x5F, 0x37, 0x37, 0x5B, 0x1D, 0x6F, 0x57, 0x60, 0x35, 0x61, 0x19, 0x23, 0x44, 0x31, 0x39, 0x33, 0x3B, 0x5C, 0x70, 0x6A, 0x5C, 0x60, 0x34, 0x3B, 0x5E, 0x14, 0x36, 0x60, 0x68, 0x76, 0x60, 0x65, 0x31, 0x2B, 0x23, 0x24, 0x64, 0x36, 0x59, 0x2B, 0x25, 0x23, 0x77, 0x65, 0x2E, 0x59, 0x7E, 0x4C, 0x25, 0x6A, 0x33, 0x43, 0x6A, 0x76, 0x5A, 0x62, 0x64, 0x54, 0x10, 0x69, 0x5B, 0x23, 0x2B, 0x7D, 0x6F, 0x1B, 0x84, 0x72, 0x38, 0x28, 0x46, 0x17, 0x28, 0x59, 0x7E, 0x5B, 0x3B, 0x6E, 0x2A, 0x41, 0x4B, 0x2E, 0x56, 0x09, 0x46, 0x61, 0x49, 0x73, 0x67, 0x58, 0x67, 0x47, 0x73, 0x58, 0x3C, 0x4D, 0x23, 0x44, 0x27, 0x38, 0x19, 0x6B, 0x77, 0x2B, 0x73, 0x59, 0x38, 0x2A, 0x65, 0x65, 0x50, 0x70, 0x8D, 0x1F, 0x34, 0x51, 0x0D, 0x5E, 0x6B, 0x5A, 0x73, 0x39, 0x28, 0x2A, 0x40, 0x49, 0x73, 0x50, 0x24, 0x09, 0x33, 0x71, 0x4E, 0x22, 0x2F, 0x69, 0x64, 0x25, 0x31, 0x6C, 0x62};

char password[50];

int main()
{
  int x=0, i=0, j=0;
  char s;
 
  // We try to bruteforce the key
  for(i=0; i<32; i++)
    {
      printf("[+] Bruteforcing with initial x = %d\n", i);
      x = i;
      memset(password, 0, 50); // clear the password
      while(to_encode[j] != 0)
    {
      s = encoded[j] - x;
      s = s ^ to_encode[j];
      password[x] = s;
      x = (x + encoded[j]) % 32;
      j++;
    }
      if(checkPassword(i))
    printf("Potential password for x=%d: %s\n",i, password);
      j = 0;
    }
  return 0;
}

int checkPassword(int x)
{
  int i;
  int acc = 0;
  for(i=0; password[i] != 0; i++)
    {
      acc = (acc + password[i]) & 0xff;
    }
  return ((acc % 32) == x);
}
 

, et on obtient avec ce code le serial "A(U*SYGF(GH9(*5y9][@%}+)78y3htxa" (en enlevant les guillemets bien sûr).
Bien sûr, si quelqu'un a une solution plus propre pour keygen, je suis preneur

[Horgh]

Nice post, c'est toujours sympa à lire

[supersnail]

Merci beaucoup

[ark]

Pas mal, tes explications sont clair, c'est cool