Le paradoxe des anniversaires en informatique
Combien faut-il de personnes dans une pièce pour que deux d’entre elles aient une chance sur deux de partager leur anniversaire ? Seulement 23, bien moins que les 365 jours de l’année. La même surprise vaut pour les empreintes de hachage, les identifiants aléatoires et les sommes de contrôle : les collisions apparaissent bien avant que l’espace des valeurs possibles soit rempli. C’est la borne des anniversaires.
La formule
Avec b bits, il existe 2^b valeurs possibles. Pour n éléments aléatoires, le nombre attendu de paires en collision vaut n(n − 1) ÷ 2^(b+1), et la probabilité d’au moins une collision est environ :
p ≈ 1 − e^(−n² ÷ 2^(b+1))
Le nombre d’éléments qui donne 50 % de risque vaut environ 1,1774 × 2^(b/2) : la racine carrée de l’espace, et non l’espace lui-même.
Exemple
Un milliard d’identifiants aléatoires de 64 bits : n² ÷ 2^65 ≈ 0,0271, donc p ≈ 2,7 %. Les 50 % sont atteints vers 5,06 milliards d’éléments, et rester sous un risque sur un million limite à environ 6 millions d’éléments.
| Bits | 50 % de collision après | Risque d’un sur un million après |
|---|---|---|
| 32 | 77 000 | 93 |
| 64 | 5,1 milliards | 6,1 millions |
| 128 (l’UUID v4 en a 122) | 2,2 × 10¹⁹ | 2,6 × 10¹⁶ |
| 256 | 4 × 10³⁸ | 4,8 × 10³⁵ |
Conclusions pratiques
- Les hachages de 32 bits (CRC-32, identifiants courts) entrent vite en collision : ne les utilisez jamais comme clés uniques.
- Des identifiants aléatoires de 64 bits conviennent pour des millions de lignes, pas pour des milliards.
- Un UUID v4 compte 122 bits aléatoires : il en faudrait environ 2,7 milliards de milliards pour une chance sur deux.
- Tronquer un SHA-256 à 8 caractères hexadécimaux ne laisse que 32 bits.
Collisions accidentelles et collisions provoquées
Ces chiffres supposent des valeurs aléatoires. Un attaquant qui cherche une collision a lui aussi besoin d’environ 2^(b/2) essais : c’est pourquoi l’ANSSI recommande des fonctions de hachage d’au moins 256 bits pour une sécurité de 128 bits. Les algorithmes cassés comme MD5 et SHA-1 permettent des collisions bien plus vite que la borne des anniversaires.