Résistance aux collisions
La résistance aux collisions est une propriété des fonctions de hachage cryptographiques : une fonction de hachage cryptographique H est résistante aux collisions s’il est difficile de trouver deux entrées qui donnent la même valeur de hachage ; c’est-à-dire deux entrées A et B de telles que : , et A ≠ B[1].
Une fonction de hachage avec plus d’entrées que de sorties doit nécessairement générer des collisions[1]. Considérons une fonction de hachage telle que SHA-256 qui produit une sortie de 256 bits à partir d’une entrée d’une longueur arbitraire. Comme la fonction doit générer une des 2256 sorties pour chaque membre d’un ensemble beaucoup plus vaste d’entrées, le principe des tiroirs garantit que certaines entrées auront la même valeur de hachage. La résistance aux collisions ne signifie pas qu’il n'y a pas de collisions, mais seulement que les collisions sont difficiles à trouver[2].
Le paradoxe des anniversaires illustre la limite supérieure de la résistance aux collisions : si une fonction de hachage produit N bits de sortie, un attaquant qui teste 2N/2 (ou ) opérations de hachage sur des entrées aléatoires est susceptible de trouver deux sorties identiques. S’il existe une méthode plus facile que cette attaque par force brute pour trouver deux sorties identiques, la fonction de hachage est considérée comme inadéquate pour servir de fonction de hachage cryptographique[3].
Les fonctions de hachage cryptographiques sont généralement conçues pour être résistantes aux collisions. Cependant, de nombreuses fonctions de hachage que l'on croyait résistantes aux collisions ont été cassées. Par exemple, on connaît maintenant des techniques plus efficaces que la force brute pour trouver des collisions pour les fonctions de hachage MD5 et SHA-1[4],[5]. D'un autre côté, il existe des preuves mathématiques que, pour certaines fonctions de hachage, la recherche de collisions est au moins aussi difficile que certains problèmes mathématiques difficiles comme la factorisation ou le logarithme discret[6]. On dit que ces fonctions ont été prouvées sûres[3].
Utilisation
modifierLa résistance aux collisions est souhaitable dans plusieurs situations :
- dans certains systèmes de signature numérique, une autorité atteste l'authenticité d'un document en publiant une signature à clé publique sur une valeur de hachage du document ; s'il est possible de produire deux documents avec la même valeur de hachage, un attaquant pourrait obtenir d'une autorité une attestation d'authenticité sur un document, et ensuite prétendre que l'autorité a attesté l'authenticité d'un autre document ;
- dans certaines preuves de travail, les utilisateurs fournissent des collisions de hachage comme preuve qu'ils ont effectué une quantité significative de calculs ; s'il existe un moyen plus facile de trouver des collisions que la force brute, les utilisateurs peuvent trouver des collisions sans effectuer une quantité significative de calculs ;
- dans certains systèmes de fichiers distribués, les parties comparent les valeurs de hachage des fichiers afin de s'assurer qu'ils ont la même version d'un fichier ; un attaquant qui pourrait produire deux fichiers avec la même valeur de hachage pourrait tromper les utilisateurs en leur faisant croire qu'ils ont la même version d'un fichier quand, en fait, ils ont des fichiers différents.
Notes et références
modifier- Goldwasser et Bellare 2008, p. 136.
- Goldwasser et Bellare 2008, p. 143.
- Pass, R. "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme". Course on Cryptography, Cornell University, 2009.
- Xiaoyun Wang and Hongbo Yu, « How to Break MD5 and Other Hash Functions » (consulté le )
- Xiaoyun Wang, Yiquin Lisa Yin, Hongobo Yu, « Finding Collisions in the Full SHA-1 ».
- Galbraith 2012.
Annexes
modifierBibliographie
modifier- (en) Shafi Goldwasser et Mihir Bellare, « Lecture Notes on Cryptography » [PDF], (consulté le ).
- [Galbraith 2012] (en) Steven Galbraith, Mathematics of Public Key Cryptography, Cambridge university press, (lire en ligne [PDF]), « 3.5 Number-theoretic hash functions »