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

Projet terminé

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