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 :
 

Leave a Reply