Birthday Attack
L'attaque des anniversaires exploite le paradoxe des anniversaires : après environ 2^(n/2) calculs de hachage, il y a 50 % de chances de trouver une collision dans un hachage de n bits, ce qui dicte la longueur de sortie requise.
Objectif
Fixe la borne inférieure de la longueur de sortie du hachage pour que la recherche de collisions soit infaisable.
Mécanisme
Paradoxe des anniversaires : parmi 23 personnes, il y a 50 % de chances que deux partagent le même anniversaire. Pour un hachage à sortie de n bits, environ 1,177×√(2^n) = 1,177×2^(n/2) entrées aléatoires donnent 50 % de probabilité de collision. Ainsi, un hachage de 128 bits n'est pas sûr face à seulement 2^64 essais.
Cas d’usage
- Choix de la longueur de sortie du hachage
- Niveau de sécurité des signatures numériques
- Évaluation de la durée de vie des certificats
- Enseignement de la cryptographie
Exemples
- entrée
128-bit hashOutputCollision found in 2^64 trialsInsecure
Erreurs courantes
- Assuming an n-bit hash needs 2^n trials to collide
- Collisions take only 2^(n/2); use outputs of at least 256 bits
Termes associés
Collision Resistance
La résistance aux collisions est la propriété d'une fonction de hachage selon laquelle il est infaisable de trouver deux entrées distinctes produisant le même condensé. L'attaque des anniversaires dicte la longueur de sortie requise. GLOSSAIRE
SHA-256
SHA-256 est le membre de la famille SHA-2 à sortie de 256 bits, très utilisé dans TLS, les blockchains et les applications cryptographiques, sans attaque pratique connue. GLOSSAIRE
MD5
MD5 est une fonction de hachage cryptographique de 128 bits conçue par Ronald Rivest ; prouvée non sûre par des attaques par collision, elle ne sert plus aujourd'hui qu'à des usages sans exigence de sécurité comme les sommes de contrôle. GLOSSAIRE