Le calcul partagé pour cracker SHA-1

Logo du groupe de recherche IAIK Krypto Le projet SHA - 1 Collision Search Graz vient d'être présenté lors de la 27ème conférence CRYPTO 2007 qui s'est tenue du 19 au 23 Août à Santa Barbara en Californie, voici les feuilles du rétroprojecteur qui ont été utilisées pour exposer le projet (à moitié sérieusement).

Plusieurs articles de présentation du projet sont apparus ces derniers jours sur internet, notamment un article sur le site anglais Heise Security dont voici la traduction :

Des chercheurs de l'université des technologies de Graz ont lancé un projet de calcul partagé pour trouver un nouveau type de vulnérabilité dans l'algorithme de hachage SHA-1, utilisé dans de nombreuses applications Internet telles que les connections cryptées et les e-mails. Les algorithmes de hachage du type de SHA-1 exécutent une séquence d'opérations mathématiques sur un bloc de données, par exemple un message, qui produit une valeur de longeur constante ou une "empreinte cryptographique" pour les messages de longeur arbitraire. Même des modifications mineures dans le message originel ont un effet important sur l'empreinte, rendant les changements facilement détectables.

Cependant, des collisions peuvent se produire, c'est-à-dire que l'algorithme produit la même empreinte pour au moins deux messages différents. En présence d'une collision, les messages variables concernés ne peuvent pas être distingués de ceux utilisant l'empreinte, bien qu'en effet la plupart des messages variables ne sont souvent pas très utiles, car ils se composent de données humaines sans signification. Trouver des collisions à l'aide de méthodes simplistes est extrêmement compliqué. Cependant, en 2005, des chercheurs chinois ont démontré que la recherche de collisions peut en principe être optimisé de sorte que le nombre de tentatives puisse passer en-dessous du minimum théorique de 280. Ainsi, il y a un an, une méthode pour contrôler le contenu d'une proportion probablement substantielle de messages manipulés a été rendue publique.

Les cryptographes de l'université des technologies de Graz adoptent une approche légèrement différente : ils ne s'intéressent pas directement aux collisions, mais aux quasi-collisions, c'est à dire lorsque SHA-1 produit des empreintes presque similaires à partir de deux messages différents. Ils pensent que deux quasi-collisions avec les mêmes différences minimales pourraient réellement se compenser, produisant les mêmes résultats qu'une vraie collision.

Pour examiner cette théorie, les chercheurs ont lancé un projet de calcul partagé. Le client Boinc connu pour d'autres projets tels que Seti@Home sera utilisé à Graz. Pour ceux qui souhaiteraient aider à trouver des collisions, il est conseillé de lire le manuel sur le site internet du projet.

Le successeur de SHA-1 est actuellement reconstruit à partir de zéro car les algorithmes prévus à l'origine pour être intégrés dans l'ensemble de la famille SHA-2 sont semblables à SHA-1 et donc vulnérable à ce même type d'attaques.