FunJp : Page créée avec « == 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 "... »

2017-04-23T19:41:35Z

Page créée avec « == 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 "... »

Nouvelle page

== 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

Reverse-engineering LGC - Historique des versions

FunJp : Page créée avec « == 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 "... »

FunJp : Page créée avec « == 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 "... »