Hashclash

Détails

Trouver la nature de la vulnérabilité de l'algorithme de hachage MD5

Projet terminé

 

Le projet s'est terminé avec la publication des résultats sur les vulnérabilités de l'algorithme MD5 : Résultats

La prochaine étape du projet pourrait être d'étudier la fonction de hachage cryptographique SHA-1

 

Projet dans le domaine de la sécurité informatique
Le but est de trouver la nature de la vulnérabilité de l'algorithme MD5 (Message Digest 5 est une fonction de hachage cryptographique encore très populaire, mais qui n'est plus considéré comme un algorithme sûr) qui pour la petite histoire a été mise en évidence par un groupe d'informaticien chinois : Xiaoyun Wang, Dengguo Feng, Xuejia Lai et Hongbo Yu
Projet hollandais tout comme Leiden. C'est la thèse d'un étudiant en master à l'université d'Eindhoven.
Ce projet Boinc existe depuis le 24 novembre 2005

Le projet annonce que pour trouver la solution à leur problème il leur faudrait , avec un pentium IV 3Ghz , calculer pendant 800 jours 24h/24 et 7 jours sur 7.
Et donc ils espèrent réduire cette durée grâce à BOINC.
Ensuite ils prévoient dejà de travailler sur la fonction de hachage cryptographique SHA-1 réputée plus sure que MD5.

 

Quelques explications supplémentaires sur Hashclash

traduction de cette page

MD5

MD5 est une fonction de hachage qui permet d'obtenir pour chaque message une empreinte numérique (en l'occurrence une séquence de 128 bits ), ceci est appelé un "hash" . Le but étant de rendre le plus difficile possible la survenance des 2 événements suivants

  • trouver une collision : deux messages avec les mêmes "hash"
  • trouver une pré-image : pour un "hash" donné, trouver un message qui trace le chemin de ce "hash"

En raison de ses propriétés, MD5 est employé généralement pour les buts suivants :

  • Vérification de l'intégrité : pour vérifier qu'un dossier n'a pas été modifié ou a bien été transmis correctement
  • Signature Digital : un message est signé grâce à l'empreinte numérique (le hash)

MD5 a été conçu par Ron Rivest en 1991. Il casse chaque message en 512 blocs de bits, et les traite séparement de manière itérative en employant la fonction md5compress.

  • iv0 est une valeur fixe dans MD5
  • iv1 = md5compress (iv0, block1)
  • iv2 = md5compress (iv1, block2)
  • ….

Le hash d'un message est la valeur "iv" calculée en utilisant le dernier bloc.

Collisions MD5

MD5 a été cassé en août 2004 par une équipe de recherche chinoise se composant de Xiaoyun Wang, Dengguo Feng, Xuejia Lai et de Hongbo Yu. Ils ont montré comment créer une collision de deux messages avec les mêmes hash. Cependant ces messages ont une structure particulière :

  • Les premiers blocs sont égaux, par exemple block1,…, block41. Par conséquent les deux messages ont la même valeur pour iv1,…, iv41.
  • Deux blocs sont générés complètement aléatoiretement : block42 et block43. Ils dépendent de la valeur spécifique dans iv41. Les messages diffèrent dans ces deux blocs, toutefois ces blocs sont tels que tous les deux ont la même valeur iv43.
  • Les derniers blocs sont également égaux, donc toutes valeurs d'iv43 jusqu'à la dernière valeur d'iv, le "hash", sont égales.

Leur attaque crée des collisions qui ne sont pas facilement utilisables pour des fins néfastes. Dans la réalité ces deux blocs se heurtants, qui sont totalement aléatoire, sont utilisés pour seulement quelques cas pratiques. Il y a deux exemples où celà est utilisé :

  • Dans les certificats numériques : les blocs aléatoires sont mis à l'intérieur d'une clef rendue publique. Toutefois ces certificats ont toujours les même Nom, Adresse, etc., ainsi vous ne pouvez pas duper n'importe qui avec celà.
  • Dans les documents numériques : les blocs aléatoires sont mis à l'intérieur "d' une construction "if-then-else". Dans cette construction chaque dossier contient les deux documents, toutefois en utilisant le "if-then-else" l'un ou l'autre du premier ou du deuxième document est accessible

La première attaque a été faite au bout d'une durée d'environ une heure grâce à la grappe de serveurs IBM p690. Des rapports postérieurs prouvent que des attaques avec un Pentium4 1.7Ghz peuvent être faites en approximativement 4 heures. Actuellement Marc a mis au point une substantielle accélération de la vitesse d'une telle attaque. Un rapport est en préparation.

 

Projet HashClash

En employant les techniques de l'attaque menée par Xiaoyun Wangs, nous essayons de trouver les collisions qui sont "les plus flexibles". Plus concrètement, nous permettrons aux premiers blocs des deux messages d'être choisis aléatoirement. Cette attaque est une recherche qui a dejà commencé, toutefois il est déjà clair qu'elle exige une puissance informatique à grande échelle. Par conséquent le projet HashClash a été lancé. Actuellement vous pouvez rejoindre HashClash pour nous aider dans la première phase de cette recherche, appelée "MD5 Birthdaying". Elle consiste à trouver un bloc avec des propriétés très spécifiques, ceci nous aidera dans les phases postérieures. Constatant que le bloc sur un Pentium4 simple 3Ghz prendrait approximativement 800 jours avec un PC fonctionnant 24 heures sur 24 et 7 jour sur 7. Nous espérons trouver ce bloc beaucoup plus rapidement, en combinant les puissances informatiques de beaucoup plus de PC.

Ce projet est seulement prévu dans le domaine de la recherche cryptographique . Nous avons l'intention de clarifier la nature des vulnérabilités de l'application MD5 ces failles ont été ouvertes par des collisions initiés par les méthodes de Wangs et de son équipe. Ensuite nous avons également l'intention de travailler sur les collisions de SHA-1

Les membres de l'Alliance Francophone qui ont trouvé des résultats intéressants

1 ère Etape du Projet :

4 membres de l'Alliance Francophone ont trouvé des collisions

Collission 41 pour [AF>France]daniel

Collisions 60 pour [AF>FRANCE>Est>IDF>EDLS] Mephisto94

Collisions 106 pour [AF>FRANCE>PICARDIE]laurent02

Collisions 112 pour [AF>France>IDF>EDLS]nicodu95

 

2 ème Etape du Projet :

Bloc 2 - Elimination de la bitdifference 2 sur 8 :

[AF>France] dref

 

Bloc 5 - Elimination de la bitdifference 5 sur 8 (résultat utilisé) :

[AF>FRANCE>Est>IDF>EDLS] Mephisto94

   

Articles en rapport