Attaque de préimage

En cryptographie, une attaque de préimage est une attaque sur une fonction de hachage cryptographique qui essaie de trouver un message qui a une valeur spécifique de hachage. Une bonne fonction de hachage cryptographique doit résister à des attaques de préimage.

Il existe deux types d'attaques de préimage :

• l'attaque de préimage : pour une valeur de sortie spécifiée, un attaquant tente de trouver une entrée qui produit cette valeur en sortie, c’est-à-dire, pour un $y$ donné, il tente de trouver un $x$ tel que $h(x)=y$ ;
• l'attaque de seconde préimage : l'attaquant tente de trouver une seconde entrée qui a la même valeur de hachage qu’une entrée spécifiée ; pour un $x$ donné, il tente de trouver une deuxième préimage $x'\neq x$ tel que $h(x)=h(x')$.

Tout comme il existe deux types d'attaques de préimage, il existe deux types de résistance à la préimage :

• la résistance à la préimage : pour pratiquement toutes les valeurs de sortie préspécifiées, il est calculatoirement impossible de trouver une entrée qui produit cette valeur en sortie, c’est-à-dire, pour un $y$ donné, il est difficile de trouver un $x$ tel que $h(x)=y$.
• la résistance à la seconde préimage : il est calculatoirement impossible de trouver une seconde entrée qui a la même valeur de hachage qu’une entrée spécifiée ; soit un $x$ donné, il est difficile de trouver une deuxième préimage $x'\neq x$ tel que $h(x)=h(x')$.

Ces résistances ne doivent pas être confondues avec la résistance à la collision dans laquelle il est calculatoirement impossible de trouver deux entrées distinctes $x$ et $x'$ ayant la même valeur de hachage, c'est-à-dire que $h(x)=h(x')$. La résistance à la collision implique la résistance à la seconde préimage, mais ne garantit pas la résistance à la préimage.

Attaques de préimage actuelles

Par définition, une fonction de hachage cryptographique idéale est telle que le moyen le plus rapide pour calculer une première ou une seconde préimage est par une attaque de force brute. Pour une table de hachage de n bits, cette attaque a une complexité de 2ⁿ, ce qui est considéré comme trop élevé pour être réalisable pour une valeur de hachage typique de n = 128 bits. Si une telle complexité est la meilleure qui peut être espérée par un adversaire, alors la fonction de hachage est considérée comme résistante à la préimage.

Des attaques de préimage plus rapides peuvent être trouvées par la cryptanalyse de certaines fonctions. Ces attaques sont habituellement spécifiques à cette fonction. Certaines attaques importantes de préimage ont déjà été découvertes, mais elles ne sont pas encore pratiques. Dans ce contexte, pratique signifie que l'attaque pourrait être exécutée par un adversaire avec une quantité raisonnable de ressources dans une durée raisonnable de temps. Par exemple, une attaque de préimage qui coûte des milliards de dollars et prend des décennies pour trouver une préimage n'est pas pratique ; par contre, une attaque qui coûterait quelques milliers de dollars et prendrait quelques heures serait très pratique.

Toutes les attaques pratiques ou presque pratiques actuellement connues sur les fonctions MD5 et SHA-1 sont des attaques de collisions. En général, une attaque de collisions est plus facile à monter qu'une attaque de préimage, car elle ne se limite pas par une valeur spécifique (n'importe quelles deux valeurs peuvent être utilisées pour créer une collision). La complexité de l'attaque de collisions est 2^n/2.

Si une attaque de préimage pratique est découverte pour une des fonctions utilisées dans les protocoles Internet, cela affecterait sérieusement la sécurité des informations sur Internet. Cependant, comme les cryptographes connaissent d'autres fonctions de hachage et qu'ils sont continuellement à la recherche de fonctions plus sécuritaires, il est probable qu'ils remplaceront une fonction de hachage affaiblie par une nouvelle fonction plus forte avant qu'elle soit brisée.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Preimage attack » (voir la liste des auteurs).