« Les fonctions de hachage cryptographiques » : différence entre les versions
Contenu supprimé Contenu ajouté
Ligne 82 :
Maintenant, si nous voulons trouver une collision quelconque, nous pouvons appliquer le paradoxe des anniversaires. Il en ressort que pour trouver une collision sur SHA-1 avec un taux de réussite de 50%, nous avons besoin d'au moins 2<sup>80</sup> messages au contenu aléatoire (<math>\sqrt{2^{160}}</math>). Avec 2<sup>81</sup> messages, nous aurons de forte chance de trouver une collision. Le gain est énorme par rapport aux 2<sup>160</sup> du départ mais un facteur comme 2<sup>80</sup> reste difficilement accessible même pour une grosse organisation (il faudrait compter quelques années).
Mis à part le manque de puissance de calcul, un problème de taille survient. Comment stocker les 2<sup>80</sup> empreintes pour la comparaison ? À raison de 160 bits par empreinte, cela représente environ 200 millions de milliards de GB, soit 25 millions de milliard de Go. Il existe toutefois des techniques plus sophistiquées qui évitent le stockage des empreintes. La ''résistance aux collisions'' d'une fonction de hachage est donc bornée par le paradoxe des anniversaires mais rien ne dit qu'il n'existe pas un meilleur moyen pour trouver ces collisions en profitant des faiblesses de l'algorithme.
À titre de comparaison, MD5 a un espace plus réduit car son empreinte ne fait ''que'' 128 bits, soit une attaque avec 2<sup>64</sup> messages. À l'instar des concours de factorisation, ''MD5Crk'' visait à trouver une collision sur MD5 en faisant appel aux ordinateurs des particuliers. L'algorithme employé était le [[:w:Algorithme rho de Pollard|rho de Pollard]], initialement utilisé pour résoudre un autre problème cryptographique : le [[:w:logarithme discret|logarithme discret]]. Le principe est d'attribuer une empreinte distincte à chaque ordinateur, le programme hache cette empreinte et recommence sur le résultat qu'il vient d'obtenir. Avec suffisamment de temps devant soi, on est assuré de trouver une collision. Précisons avant tout qu'une fonction de hachage est nécessairement cyclique : comme le nombre d'états possibles est limité alors effectuer plus d'itérations que d'états possibles va obligatoirement nous amener à rencontrer un état déjà connu. Ceci explique le nom attribué à cette méthode puisque la forme du chemin parcouru ressemble à la lettre grec ''rho''. Un algorithme de Pollard s'exécutant sur une unique machine doit détecter quand il entre dans un cycle. À ce moment, on sait qu'une collision s'est produite mais pas forcément son emplacement exact. L'algorithme permet de la retrouver ainsi que la paire de messages concernés.
| |||