Faiblesse cryptographique dans les algorithmes MD5 et SHA-1

La conférence "Crypto 2004" qui s'est tenue en août 2004 a été l'occasion pour une équipe de chercheurs chinois d'annoncer qu'ils avaient découvert des cas de collision dans l'algorithme MD5 (ainsi que d'autres algorithmes de "hashage" plus exotiques : MD4, HAVAL-128 et RIPEMD). Cette nouvelle a fait sensation car, bien que théoriquement possible, aucun cas de collision réel n'avait été trouvé jusque là. Elle n'est cependant pas très grave pour la communauté sécurité car le cas de collision identifié ne correspond pas au cadre d'utilisation de MD5 dans la sécurité (car on suspecte depuis longtemps que des collisions seront trouvées avec MD5).

Au cours de la même session, un chercheur français (du service "crypto" de la DCSSI) a annoncé qu'il avait découvert un cas de collision dans l'algorithme SHA-0 (un algorithme obsolète, mais très proche de SHA-1), et deux chercheurs israéliens ont annoncé qu'ils avaient découvert des cas de collision dans une version affaiblie de SHA-1. Ces deux annonces font penser que la communauté des crypto-analystes pourrait être sur le point de mettre en évidence des collisions dans l'algorithme SHA-1 lui-même (et non dans des versions affaiblies), ce qui serait un problème majeur pour la communauté sécurité. SHA-1 est en effet réputé pour être très sûr. Ce problème montre que de nouveaux algorithmes, plus résistants que SHA-1 doivent être mis au point. Des travaux sont déjà démarrés dans ce sens (par exemple "Tiger" et "AES-CBC").

Plus de détail sur les algorithmes de calcul d'empreinte et les collisions

Pour mieux comprendre la portée exacte de la découverte de ces "collisions", il nous faut examiner plus en détail le principe des algorithmes de calcul d'empreinte (appelés communément "hashage" ou "calcul de hash").

Les algorithmes de calcul d'empreinte, tels que MD5 ou SHA-1, permettent de calculer une valeur (un nombre) représentative du contenu d'un fichier (ou plus généralement "d'un message"). Si le contenu du fichier change, la valeur calculée (l'empreinte) change. Les algorithmes de calcul d'empreinte sont couramment utilisés en sécurité informatique pour : la vérification d'intégrité des données, le stockage des mots de passe, et la signature électronique.

Ces algorithmes ont la propriété de ne pas être réversibles, ainsi la connaissance de l'empreinte ne permet pas retrouver la valeur d'origine.

La qualité d'un algorithme de calcul d'empreinte s'évalue suivant 3 critères. Nous donnerons ces critères en anglais car c'est leur dénomination usuelle :

• "Collision resistance",
• "Preimage resistance",
• "Second preimage resistance".

Un algorithme est "collision resistant" s'il est difficile de trouver 2 messages distincts "A" et "B" produisant une même empreinte "H". Dans ce cas, il n'y a aucune contrainte sur les valeurs de "A", "B" et "H" : n'importe quel triplet "(A,B,H)" est accepté. Ce type de faiblesse permet à un escroc de monter une arnaque : Il vous promet une belle valeur "A", mais vous donne en définitive une valeur "B" (moins belle) et vous ne pouvez pas protester car "A" et "B" ont la même empreinte. Il s'agit donc d'une forme d'attaque contre la signature électronique.

Un algorithme est "preimage resistant" s'il est difficile de trouver un message "B" produisant la même empreinte "H" que le message "A", en connaissant "H", mais sans connaître "A". Ce type de faiblesse correspond typiquement à l'attaque de mots de passe stockés sous forme d'empreinte : "A" est le mot de passe secret, et "B" sera le mot de passe trouvé par "crackage" de l'empreinte "H".

Un algorithme est "second preimage resistant" s'il est difficile de trouver un message "B" produisant la même empreinte "H" que le message "A", en connaissant "H" et "A". Ce type de faiblesse correspond typiquement à l'attaque de l'intégrité des données : quelqu'un produit un message "B", dérivé de "A" et qui produira la même empreinte que "A".

Les cas de collision dont nous parlons dans cet article sont des cas d'atteinte à la "collision resistance", c'est-à-dire le cas le plus "facile" de collision (dans la mesure où il n'y a pas de contrainte sur "A", "B" et "H"). C'est donc la "collision resistance" de "MD5" et de "SHA-1" qui est impactée par ces annonces.

Dans le cas des collisions "MD5" on pourra noter enfin :

• Qu'aucune information sur la méthode pour découvrir les valeurs adéquates de "A" et "B" n'a été donnée par les chercheurs chinois.
• Un challenge d'attaque en "brute-force" de MD5 avait été lancé en début 2004. Ce challenge se retrouve donc caduque (après 170 jours de calcul intensif et collaboratif) étant donné l'annonce chinoise.

Pour plus d'information

• Article sur les annonces faites lors de "crypto 2004" : http://blog.commerce.net/archives/2004/08/md5_dead_sha1_o.html
• Explication illustrée des types de "resistance" d'un algorithme d'empreinte : http://www.unixwiz.net/archives/2004/08/tech_tip_an_ill.html
• Challenge pour attaquer MD5 en "brute force" : http://www.md5crk.com/