ESIGN Tools 1.0

Mon défi Waga invader a récemment été cassé par jB (python powered ) et 0×87k qui en a profité pour faire un magnifique tutorial que je ne peux m’empêcher de publier. L’algorithme du crackme reposait essentiellement sur le schéma de signature ESIGN, qui est presque méconnu. Vous pourrez trouver plus de détails sur cet algorithme dans le célèbre “Handbook of applied cryptography”.

Il m’est venu alors l’idée de coder un petit tool à la sauce “RSATools” mais pour ESIGN, ça ne vous servira sûrement jamais mais ce n’était vraiment pas compliquer à coder, alors j’en ai profité. Qui sait, ça sera peut être utile? En tout cas, le développement de ce petit tool permet de mettre en évidence les faiblesses de ESIGN et m’a permis de comprendre pourquoi, je m’explique :

Rappelons d’abord comment vérifier la validité d’une signature:
- Soit la clef publique (N,K) où N = p*p*q (p et q premiers) et K>=4
- Soit S la signature pour un message M
- On calcule u = S^K mod N
- On hashe le message M : z = h(M) (h = fonction de hachage)
- On accepte la signature si z <= u <= z + ((2/3)*log2(N))

Il y a donc un problème si on utilise un hash d’une taille en bits inférieure à (2/3)*log2(N), à ce moment là n’importe quel message M pourrait correspondre à une signature donnée à cause de l’approximation faite sur u. Il est donc fortement déconseillé (ce serait même une catastrophe) d’utiliser la fonction SHA1 avec un modulus de 520 bits par exemple, il serait plus judicieux dans ce cas d’utiliser un SHA-512.

Et même si vous utilisez une taille de hash proche de la taille en bit du modulus, on peut falsifier la signature en bruteforçant un message m’ dont les premiers bits du hash sont égaux à ceux du hash réalisé sur le message M original.

Pour illustrer :
- Prenons N (129 bits) = 19094C92C1DDAE2E0E1FBAADC0DEF67FB = 7AFA49D6815* 7AFA49D6815* 6C7DF5E7153
- Prenons K = 29A
- Alors le taux d’erreur est 2^((2/3)*log2(N)) = 4000000000000000000000 (en hexa)
- Si on utilise MD5, les hashs ont une taille de 128 bits.
- On peut alors bruteforcer un message m’ dont les premiers bits du hash MD5 seront les mêmes que les premiers 43 bits du hash de M. (43 = 128 - log2(4000000000000000000000)+1)

Si on signe “waga” (md5 = 0c52bcf239340f9642ee665dc7c34370) avec X=4CBEB10DA6C (valeur secrète lors de la génération, cf help dans ESIGN Tools) on obtient la signature 60F0145E06C2C3165FC95B8D28DAD39A qui nous donne u = 0C52BCF23940845B7B50402098D82550, u vérifie alors bien l’approximation.

On peut alors trouver m’ par bruteforce en vérifiant que (u-4000000000000000000000) <= md5(m’) <= U, et ceci sans connaître la clef privée.

Les 128 bits qu’offre en terme de sécurité MD5 est alors réduit à une petite cinquantaine de bits.

Tout ça pour dire que le schéma ESIGN paraît vraiment peu fiable du fait de l’approximation grossière faite pour valider la signature. Peut être est ce pour cela que l’algorithme est peu utilisé?

Si vous trouvez des bugs, n’hésitez pas à me contacter.

Waga Invader solution by 0×87k

ESIGN Tools 1.0 beta test

ESIGN Tools source (C++,miracl lib)

Filed under : Crypto
By admin
On August 29, 2007
At 23:21
Comments : 0
 
 

Tuto pour Pulsar’s JC#1

Voici un tutorial pour le premier crackme de Pulsar destiné au junk code. Le code original est vraiment noyé dans du junk qui forme en tout plus de 4500 instructions assembleur, c’est l’horreur. Heureusement IDA est là pour nous aider .
Au travers de ce crackme, j’ai pu m’initier aux script IDC et je dois dire que c’est vraiment un outil très puissant, peut être un peu lent mais c’est vraiment pour lui trouver un défaut.

Le package contient :
- Un PDF détaillant ma méthode
- Le script IDC qui permet de déjunker entièrement le crackme
- Le code entier du crackme déjunké

Tutorial Pulsar’s JC#1 (PDF + script IDC)

Filed under : Tutorial
By admin
On August 20, 2007
At 22:57
Comments : 3
 
 

Deux nouveaux keygenme

Voilà 2 nouveaux keygenme :

Waga-Invader
A la base, ce petit proggie est un jeu écrit entièrement en C++, un shoot’em’up complètement débile. Pour accèder à un niveau secret, vous devez fournir une clef valide, c’est en fait un crypto keygenme. Il s’agit d’une implantation d’un algorithme de signature peu médiatisé. La routine est extrêmement simple à appréhender et courte, la génération d’une signature valide n’est pas aussi évidente que cela.
Vous devez posséder une carte graphique correctement configurée pour OpenGL.

E-Tour-Dissez-Moi
C’est un tout petit keygen me écrit en C, modélisant un problème célèbre, un peu comme les petits casse-têtes de votre grand-père. La routine est démunie de toutes obfuscations et ne comporte aucune opération mathématique, même pas un ADD et un MUL . Je vous conseille de modéliser le problème sur papier dans un prermier temps.

Waga Invader crypto keygenme (OpenGL)


E-Tour-Dissez-Moi Keygenme

Filed under : Reversing
By admin
On August 15, 2007
At 17:59
Comments : 0