Calculateur de probabilité de collision de hachage
Données
| Taille du hachage | 128 |
|---|---|
| Nombre d'éléments | 1 000 000 |
Calculateur de probabilité de collision de hachage
Estimez la probabilité d'une collision de hachage par effet anniversaire parmi un ensemble de valeurs hachées, et déterminez le nombre d'éléments nécessaires pour atteindre 50 % de chance de collision pour une taille de hachage donnée.
Données
Paramètres de hachage
Résultats
Saisissez une valeur pour afficher les résultats.
Probabilité de collision
Probabilité de collision de hachage
Une fonction de hachage associe une entrée de longueur arbitraire à une sortie de longueur fixe appelée condensat. Idéalement, aucune paire d'entrées distinctes ne devrait produire le même condensat — propriété dite de résistance aux collisions. En pratique, l'espace de sortie étant fini, les collisions existent nécessairement ; la question est de savoir combien d'entrées doivent être hachées avant qu'une collision soit probable. Ce calculateur quantifie cette probabilité à l'aide de l'approximation des anniversaires, nommée d'après le paradoxe des anniversaires.
Le paradoxe des anniversaires
Dans un groupe de 23 personnes tirées uniformément au hasard parmi une année de 365 jours, la probabilité que deux d'entre elles partagent le même anniversaire dépasse déjà 50 %. Cette probabilité est bien plus élevée que l'intuition ne le suggère, car elle porte sur toute paire au sein du groupe, et non sur une correspondance avec une date cible précise. La même asymétrie régit les collisions de hachage : trouver deux entrées ayant le même hachage (une collision) est bien plus facile que de trouver une entrée qui produit un hachage cible donné (une préimage).
Formule
Pour une fonction de hachage dont la sortie est de bits, l'espace de recherche contient valeurs également probables. Étant donné éléments hachés aléatoirement, la probabilité exacte de collision est le complément de la probabilité que les sorties soient toutes distinctes :
p=1−k=0∏n−1(1−2bk)Pour un grand et un modéré, l'approximation des anniversaires donne une forme simplifiée :
p≈1−e−n2/(2⋅2b)En résolvant pour le nombre d'éléments à partir duquel la probabilité atteint 50 % :
n50%=2⋅2b⋅ln2Exemple de calcul
Pour un hachage de 32 bits (tel que CRC32 utilisé dans les sommes de contrôle) :
n50%=2×232×ln2=2×4294967296×0,6931≈5954124768≈77163Avec seulement 77 163 fichiers dans un dépôt, la probabilité que deux d'entre eux partagent le même CRC32 est d'environ 50 %. Vérification avec la formule d'approximation :
p=1−e−771632/(2×232)≈1−e−0,693≈0,50C'est pourquoi le CRC32 est inadapté comme identifiant unique dans des grandes collections, même s'il constitue un excellent code de détection d'erreurs sur de petits flux de données.
Conséquences en matière de sécurité
La borne des anniversaires établit qu'une fonction de hachage de bits n'offre que bits de résistance aux collisions. Un attaquant a besoin d'environ évaluations pour trouver une collision — et non . C'est pourquoi les fonctions de hachage cryptographiques sont conçues avec des sorties plus larges que le niveau de sécurité visé :
| Fonction de hachage | Sortie | Résistance aux collisions |
|---|---|---|
| MD5 | 128 bits | ~ (compromise en pratique) |
| SHA-1 | 160 bits | ~ (compromise en pratique) |
| SHA-256 | 256 bits | ~ (standard actuel) |
| SHA-3-512 | 512 bits | ~ (haute sécurité) |
MD5 et SHA-1 sont qualifiées de « compromises » non seulement en raison de la borne des anniversaires, mais parce que des chercheurs ont mis en évidence des faiblesses algorithmiques permettant de trouver des collisions bien plus rapidement que opérations. Des collisions MD5 peuvent être calculées sur du matériel grand public en quelques minutes grâce à des techniques publiées.
Pour une analyse connexe des espaces de recherche de mots de passe, voir Calculateur d'entropie de mot de passe.
Questions fréquentes (FAQ)
Qu'est-ce que le paradoxe des anniversaires en cryptographie ?
Le paradoxe des anniversaires est le résultat contre-intuitif selon lequel dans un groupe de seulement 23 personnes, la probabilité que deux d'entre elles aient le même anniversaire dépasse déjà 50 %, bien qu'il existe 365 anniversaires possibles.
Le même raisonnement s'applique aux fonctions de hachage : un attaquant n'a besoin que d'environ √(2^b) = 2^(b/2) éléments hachés pour atteindre 50 % de probabilité de trouver deux entrées avec la même sortie. C'est l'attaque par anniversaire. Pour un hachage de 128 bits comme MD5, ce seuil est d'environ 2^64 ≈ 1,8 × 10¹⁹ éléments — bien moins que les 2^128 combinaisons qu'exigerait une attaque par préimage.
Pourquoi une attaque par anniversaire ne nécessite-t-elle que la moitié des bits pour réussir ?
Une attaque par préimage doit trouver une valeur de hachage précise et doit donc parcourir l'espace complet de 2^b possibilités. Une attaque par anniversaire n'a besoin que de deux entrées quelconques qui entrent en collision ; par la borne des anniversaires, la probabilité de trouver une telle paire dépasse 50 % après environ 2^(b/2) échantillons.
C'est pourquoi les fonctions de hachage cryptographiques sont conçues avec deux fois plus de bits de sortie que le niveau de sécurité visé : un hachage de 256 bits offre une résistance aux collisions de 128 bits.
Pourquoi MD5 et SHA-1 sont-ils considérés comme non sécurisés ?
MD5 (128 bits) et SHA-1 (160 bits) ont été compromis par des attaques de collision pratiques — non pas seulement des attaques probabilistes par anniversaire, mais des faiblesses algorithmiques permettant de trouver des collisions bien plus efficacement que la borne des anniversaires ne le prédit. En 2004, des chercheurs ont démontré des collisions MD5 ; en 2017, le projet SHAttered de Google a produit la première collision SHA-1 connue publiquement.
Ces fonctions restent sûres pour des usages non cryptographiques tels que les sommes de contrôle et l'adressage de contenu, mais ne doivent pas être utilisées lorsque la résistance aux collisions est requise, comme pour les signatures numériques ou les autorités de certification.
Quelle est la différence entre une collision et une préimage ?
Une collision consiste à trouver deux entrées distinctes x et y telles que hachage(x) = hachage(y). Une préimage consiste à trouver une entrée x dont le hachage correspond à une valeur cible h précise — plus difficile car on ne peut pas choisir librement les deux entrées. Une seconde préimage consiste à trouver une entrée y différente ayant le même hachage qu'un x connu.
Ces propriétés sont listées par ordre croissant de difficulté : la résistance aux collisions est la propriété la plus faible, et la résistance aux secondes préimages est la plus forte. Les fonctions de hachage utilisées dans les signatures numériques doivent résister aux attaques par seconde préimage ; celles utilisées dans les tables de hachage ou les filtres de Bloom n'ont besoin que d'une résistance aux collisions faible.