Le paradoxe des anniversaires et les collisions

Combien d'essais faut-il pour trouver une collision sur une empreinte de n bits ? L'intuition dit 2^n. L'intuition se trompe, et l'écart change tout le dimensionnement de la cryptographie.

Le paradoxe des anniversaires

Posez la question : dans un groupe de personnes, combien faut-il en réunir pour avoir plus d'une chance sur deux que deux d'entre elles partagent le même jour d'anniversaire ?

Il y a 365 jours. On pourrait croire qu'il faut environ 183 personnes. La réponse réelle est 23. C'est le paradoxe des anniversaires : il n'est pas paradoxal, juste contre-intuitif.

La raison : on ne cherche pas une personne née un jour fixé, on cherche n'importe quelle paire qui coïncide. Or le nombre de paires dans un groupe de k personnes est k(k-1)/2, qui grandit comme le carré de k. Avec 23 personnes, cela fait déjà 253 paires.

Chercher une préimage      : "qui est né le 14 mars ?"   -> ~365 essais
Chercher une collision     : "deux personnes coïncident" -> ~23 essais
       (même écart entre 2^n et 2^(n/2) sur une empreinte)

Application au hachage

Une empreinte de n bits a 2^n valeurs possibles. Transposons :

• Trouver une préimage ou une seconde préimage (cible fixée) coûte environ 2^n essais.
• Trouver une collision (n'importe quelle paire) ne coûte que ~2^(n/2) essais, par le paradoxe des anniversaires.

C'est un résultat majeur : la résistance aux collisions d'une fonction de hachage est au plus de n/2 bits, quelle que soit sa qualité. Ce n'est pas un défaut d'implémentation, c'est une borne mathématique inévitable.

Le tableau du dimensionnement

Le niveau de sécurité contre les collisions est la moitié de la taille de l'empreinte :

Taille d'empreinte	Sécurité préimage	Sécurité collision
128 bits (MD5)	2^128	2^64 (cassable)
160 bits (SHA-1)	2^160	2^80 (cassable)
256 bits (SHA-256)	2^256	2^128 (sûr)
512 bits (SHA-512)	2^512	2^256 (sûr)

La conséquence pratique

Pour viser 128 bits de sécurité contre les collisions — le standard actuel — il faut une empreinte de 256 bits. C'est exactement pourquoi SHA-256 est le minimum recommandé aujourd'hui : ses 256 bits offrent 128 bits de résistance aux collisions.

À l'inverse, les 64 bits de résistance de MD5 sont largement à la portée d'un attaquant moderne : 2^64 opérations sont réalisables.

En résumé

Le paradoxe des anniversaires fait qu'une collision sur n bits ne coûte que ~2^(n/2) essais, et non 2^n. La résistance aux collisions vaut donc la moitié de la taille de l'empreinte. Pour 128 bits de sécurité, il faut 256 bits d'empreinte : c'est la raison d'être de SHA-256.