Le projet est interrompu du fait de l'absence de progrès. Aucune nouvelle unité ne sera générée dans un futur plus ou moins proche.
 
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

 

Liens du projet
L'Alliance Francophone
Statistiques

 

 

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 :

  • Le cryptographe allemand Hans Dobbertin a trouvé une paire de messages en collision pour MD4 en 1996.
  • En 2004, un groupe de chercheurs chinois (Professeur Wang et al.) a trouvé les premières collisions pour le MD5 et le RIPEMD.
  • Indépendamment, et peu de temps après, un groupe français (Antoine Joux et al.) a rapporté une collision pour le SHA-0 (appellé aussi SHA), le prédécesseur direct de SHA-1.

Jusqu'à aujourd'hui, personne n'a pu démontrer de collision pour le SHA-1 puisqu'il est beaucoup plus résistant à ces types d'attaques. Néanmoins, les chercheurs définissent des variantes où ils réduisent le nombre d'itération. La variante s'approchant le plus du SHA-1 réél dont on a obtenu une paire de messages de collision, est un SHA-1 réduit à 70 itérations sur 80. Notez toutefois que la charge de travail augmente habituellement de façon exponentiel avec le nombre d'itérations. Cela implique qu'une fonction de hachage dont une attaque sur une variante avec moitié moins d'itérations ne signifie pas que la fonction de hachage est à moitié cassée.

 

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.