Reverse-engineering LGC
Généralités
L'algorithme classique de génération de nombres pseudo-aléatoires est de la forme :
X(n+1)=(aX(n)+C) mod M
C'est un formule très simple : un "générateur congruentiel linéaire" ou "Linear Congruential Generator" (LGC) en anglais.
Il va de soit, qu'a la vue de la formule, il existe un moyen de retrouver les paramètres à partir des données.
Ce que je propose : Remplacons les vilaines tables de t4c par leur formules respectives ont y gagnera en taille de code et en clarté (quoi que ca soit discutable)
Méthode 1 (BruteForce)
Méthode 2 (Mathématique)
Tout d'abord voyons comment faire pour une suite simple et courte que j'ai concocté pour l'occasion:
225022651 2758271555 3694341235 2360776595 1568339 3917311699
//on va considerer que le seed est stocké sur 32 bits ce qui nous donne M = 2147483647
(en cours)
Méthode 3 (Reversing)
La recherche du code: Le decryptage des ELNG à surement un minimum de verification d'erreurs voyons ce qu'on peut trouver au niveau des chaines
j'ai tapé "language" pour ma recherche : 'An unkown language file error occured on line %u.'
mmm fabuleux
et un peu plus bas 'Loading language file %s .'
Parfait ! voyons le code qui y fait référence en remontant en haut de la fonction je tombe sur :
0043BDDB call esi ; fopen 0043BDDD mov edi, eax 0043BDDF add esp, 8 0043BDE2 test edi, edi 0043BDE4 mov [ebp+var_28], edi 0043BDE7 jnz short loc_43BE27 0043BDE9 mov ecx, dword ptr [ebp+arg_0] 0043BDEC push ecx ; char 0043BDED push offset aCouldNotLoadLa ; "Could not load language file %s."
l'ouverture étant ici , le décryptage ne devrait pas être loin... on suit le saut qui génère l'erreur ou non et on descend de quelques lignes :
0043BE48 push edi 0043BE49 lea ecx, [ebp+var_40] 0043BE4C mov byte ptr [ebp+var_4], 4 0043BE50 mov [ebp+var_D], 0 0043BE54 call sub_43B640 0043BE59 lea ecx, [ebp+var_40] 0043BE5C call sub_43B670 0043BE61 cmp al, 0FFh 0043BE63 mov ebx, ds:isalpha
Partiellement gagné le premier call fait en effet un appel à une fonction qui fixe le seed à 0x2d9d
Le deuxieme quand à lui lit un caractère grace a fgetc et decrypte l'octet recupéré grace à une table et un bête xor
0043B6A3 movsx eax, byte_507E58[edx] 0043B6AA movsx edx, bl 0043B6AD xor eax, edx
Les références croisées nous amenerons directement au remplissage de la table:
0043B600 loc_43B600: 0043B612 push 0FFh 0043B617 push 0 0043B619 mov ecx, offset unk_50D81C 0043B61E call ??RRandom@@QAEHHH@Z ; Random::operator()(int,int) 0043B623 mov byte_507E58[esi], al 0043B629 inc esi 0043B62A cmp esi, 1E8Fh 0043B630 jl short loc_43B612
La fonction random prend 2 arguments , bien evidement ici la valeur min et max voyant les chiffres, en suivant les appels on se retrouve au coeur du générateur:
0045517C mov eax, dword_50A7DC 00455181 mov ecx, ?Seed@Random@@0_KA ; unsigned __int64 Random::Seed 00455187 push 0 00455189 push 2B3DD441h 0045518E push eax 0045518F push ecx 00455190 call __allmul 00455195 add eax, 1 00455198 adc edx, 0 0045519B cmp esi, edi 0045519D mov ebx, eax 0045519F mov ?Seed@Random@@0_KA, ebx ; unsigned __int64 Random::Seed 004551A5 mov dword_50A7DC, edx
l'algorithme est donc ici seed=seed*0x2b3dd441+1; (les opérations sont en 64 bits)
mais ce n'est pas la valeur renvoyée par la fonction:
004551C6 mov edx, dword_50A7DC 004551CC mov ecx, 16 004551D1 mov eax, ebx 004551D3 call unknown_libname_253 ; Microsoft VisualC 2-8/net runtime
ici un appel non reconnu à une fonction de librairie qui effectue un bit shift à droite de 16 bit sur l'entier de poids faible de l'int64 donc : ((seed & 0xFFFFFFFF)>>16)
ce à quoi je rajoute :
(result%((max+1)-min))+min
(calculé avec __aullrem)
La fonction résultante simplifiée :
__int64 Seed;
unsigned char Random(void)
{
Seed=Seed*0x2b3dd441+1;
return ((Seed & 0xFFFFFFFF)>>16)%0x100;
};
Découvrir les paramètres du générateur d'après les valeurs de sortie etait ici plus ou moins voué a l'échec du fait de la destruction des octets de poids faible.
--Chaotikmind