Birthday Bound
La borne d'anniversaire est le plancher de complexité d'attaque fixé par le paradoxe des anniversaires : trouver une collision dans un ensemble de N éléments nécessite environ sqrt(N) échantillons.
Objectif
Elle fixe le plafond de sécurité des fonctions de hachage et des modes de chiffrement par blocs : un hachage de n bits n'offre que 2^(n/2) de résistance aux collisions, et les modes CBC/CTR d'un bloc de n bits se répètent après 2^(n/2) blocs.
Mécanisme
Selon le paradoxe des anniversaires, l'échantillonnage aléatoire dans un ensemble de N éléments répète avec une forte probabilité après environ sqrt(N) tirages. Ainsi, une collision sur un hachage de n bits demande 2^(n/2) opérations, et SHA-256 offre 128 bits de résistance aux collisions.
Cas d’usage
- Évaluation de la force de sécurité des fonctions de hachage
- Plafonds du nombre de blocs pour les modes de chiffrement par blocs
- Choix des longueurs de hachage de signature