Pour une fonction de hachage idéale à sortie de 256 bits, quelle combinaison donne l'ordre de grandeur du nombre de calculs nécessaires à une attaque par force brute dans deux cas : trouver une entrée qui produit une valeur de hachage donnée (attaque par préimage), et trouver deux entrées différentes quelconques qui produisent la même valeur de hachage (attaque par collision) ?

Réponse : A. Attaque par préimage : environ 2^256 ; attaque par collision : environ 2^128

Une fonction de hachage idéale à sortie de n bits a 2^n valeurs de hachage possibles, et chaque entrée essayée correspond à une valeur donnée avec une probabilité de 1/2^n. Une attaque par préimage demande donc environ 2^n calculs, soit environ 2^256 pour n = 256. Dans une attaque par collision, en revanche, n'importe quelles deux entrées peuvent coïncider : essayer k entrées donne environ k^2/2 paires à comparer. Lorsque k^2/2 approche 2^n, c'est-à-dire lorsque k est de l'ordre de 2^(n/2), une collision devient probable ; pour n = 256, cela fait environ 2^128. C'est la même idée que le paradoxe des anniversaires, selon lequel dans un groupe de 23 personnes, la probabilité que deux d'entre elles aient le même anniversaire dépasse 50 % ; on parle donc d'attaque des anniversaires. Par conséquent, la résistance d'une fonction de hachage aux collisions est estimée à la moitié de sa longueur de sortie, et obtenir une sécurité équivalente à 128 bits exige une sortie de 256 bits.