Recherche sur les quasi-collisions d'empreintes cryptographiques de l'algorithme de hachage SHA-1

INSCRIPTION

Télécharger Boinc (tutorial)

URL du projet : http://boinc.iaik.tugraz.at/sha1_coll_search

Système d'exploitation : Linux, Windows

• Projet de l'Université de Technologie de Graz en Autriche, Institute for Applied Information Processing and Communications (IAIK)
• Traduction d'un article de Heise Security

Qu'est ce qu'une fonction de hachage

Les fonctions de hachage sont une des bases les plus importantes de la cryptographie. Elles acceptent des données d'entrée de longueur arbitraire et rendent une valeur "hachée" (aussi appelée un condensat ou une empreinte) de longueur fixe.

Fondamentalement, une fonction de hachage cryptographique doit posséder 2 propriétés :

1) sens unique :
En partant d'une empreinte, il ne doit pas être possible de retrouver les données d'entrée qui correspondent à cette empreinte.

2) résistance à la collision (injectivité pour les matheux) :
Il ne doit pas être possible de trouver 2 entrées qui donnent la même empreinte via cette fonction de hachage

Qu'est ce que le SHA-1 ?

La fonction de hachage SHA-1 (cf. wikipedia ) est une des bases les plus importantes de la cryptographie actuelle. SHA-1 a été conçu par la NSA et présenté comme un standard par le NIST en 1995. Surfer sur le web, administrer des serveurs via ssh, ou stocker et comparer des mots de passe sont quelques exemples où SHA-1 est utilisé et auquel beaucoup d'entre nous lui faisons confiance au quotidien.

Illustration d'une fonction de compression SHA-1

Illustration d'une étape de transformation en SHA-1

Que s'est-il passé par le passé ?

Presque tout les prédécesseurs du SHA-1 ont été cassé, c'est à dire que des collisions ont été trouvées :

Types d'attaques pour la recherche de collisions

A partir du moment où l'entrée fournie à une fonction de hachage peut devenir plus grande que sa sortie, les collisions entre les entrées sont inévitables. Pour une fonction de hachage fournissant une sortie de taille n bits, une attaque par le paradoxe des anniversaires demande environ 2 ^n/2 opérations de hachage pour trouver une paire de message entrant en collision. Une attaque dédiée, d'un autre côté, essaye d'exploiter le fonctionnement interne de la fonction de hachage. Le projet SHA-1-Collision Search Graz utilise cette méthode.

M éthode dédiée pour SHA-1

Actuellement personne n'a encore vu de collision pour SHA-1. Des nouvelles méthodes dédiées de recherche de collision sont en développement. Ici nous illustrons rapidement comment cette méthode marche.

1. Une différence de message appropriée est sélectionnée.

2. Une séquence de différences (aussi appelée chemin, trainée, caractéristique ou caractéristique différentielle) est déterminée par l'utilisation d'une fonction de compression (les points rouges sur la figure suivante).

3. La probabilité qu'une telle séquence de différences arrive réellement est très très faible en premier lieu. L'étape suivante est d'utiliser des méthodes cryptographiques pour fixer des parties du message d'entrée (16 mots = 512 bits) à des valeurs particulières qui augmentent cette probabilité.
4. La meilleure méthode connue implique de diviser cette tâche en 2 parties et ainsi de doubler les degrés de liberté utilisables. La prochaine figure illustre cette approche en 2 blocs.

5. La tâche gourmande en ressource processeur consiste à tourner "intelligemment et efficacement" à travers l'espace de recherche restant. C'est cette partie qui est distribuée par le projet.
6. Nous avons développé de nouvelles méthodes de cryptoanalyses qui sont déjà suffisamment avancées pour éviter les simples goulets d'étranglement dans la recherche de collision. Il en résulte que l'optimisation du temps de recherche est un problème d'optimisation multi-dimensionnel :

Au cour du projet, nous espérons obtenir plus de données ce qui permettra une optimisation additionnelle.