Attaque des anniversaires

Comme exemple du paradoxe des anniversaires, il est possible de considérer le scénario suivant.

« Un enseignant ayant une classe de 30 élèves demande à ses élèves de lui donner leurs dates d’anniversaires, afin de déterminer s'il y a deux élèves qui fêtent leurs anniversaires le même jour — cela correspond à la collision de hash. »

Intuitivement, la probabilité que cela arrive paraît faible. Si l’enseignant prenait un jour spécifique, par exemple le 14 août, alors la probabilité qu’au moins un élève soit né ce jour spécifique est ${\displaystyle 1-(364/365)^{30}}$, soit environ 7,9 %[note 1].

Par contre, la probabilité qu’au moins un élève ait la même date d’anniversaire que n’importe lequel des autres élèves est environ égale à 70 %, soit : ${\displaystyle 1-365!/((365-n)!\cdot 365^{n})}$ avec ${\displaystyle n=30}$[2].

Soit une fonction ${\displaystyle f,}$ le but de l’attaque est de trouver deux antécédents différents ${\displaystyle x_{1},}$ ${\displaystyle x_{2}}$ tels que ${\displaystyle f(x_{1})=f(x_{2}).}$ Une telle paire ${\displaystyle x_{1},}$ ${\displaystyle x_{2}}$ est appelée une collision. La méthode utilisée pour trouver une collision est simplement de comparer l’image de ${\displaystyle f}$ pour différents antécédents qui peuvent être choisis de façon aléatoire ou pseudo-aléatoire jusqu'à ce que le même résultat soit trouvé plus d’une fois. Grâce au paradoxe des anniversaires, cette méthode peut être très efficace. Plus précisément, si une fonction ${\displaystyle f(x)}$ définie sur ${\displaystyle H}$ permet d’obtenir des images différentes avec la même probabilité et que ${\displaystyle H}$ est un ensemble suffisamment grand, alors on peut espérer obtenir une paire d'antécédents différents ${\displaystyle x_{1}}$ et ${\displaystyle x_{2}}$ pour lesquelles ${\displaystyle f(x_{1})=f(x_{2})}$ après avoir calculé l’image de la fonction pour seulement ${\displaystyle 1.25{\sqrt {|H|}}}$ différents antécédents en moyenne.

Considérons l’expérience suivante. Dans un ensemble de cardinal ${\displaystyle H,}$ on choisit ${\displaystyle n}$ valeurs au hasard en autorisant les répétitions. Soit ${\displaystyle p(n;H)}$ la probabilité que durant cette expérience au moins une valeur soit choisie plus d’une fois. Cette probabilité est à peu près égale à ${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}.\,}$ Soit ${\displaystyle n(p;H)}$ le plus petit nombre de valeurs qu’on doit choisir, alors la probabilité de trouver une collision est au moins ${\displaystyle p.}$ En inversant cette expression, on trouve l’approximation suivante ${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}},}$ et en attribuant une valeur égale à 0,5 à la probabilité de collision, on trouve ${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}.\,}$ Soit ${\displaystyle Q(H)}$ le nombre prévu de valeurs à choisir avant de trouver la première collision. Ce nombre est environ égal à ${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}.}$

Par exemple, si un hash de 64 bits est utilisé, il y a à peu près 1,8 × 10¹⁹ différentes images. Si elles sont aussi probables à obtenir, ce qui est le meilleur des cas pour l’attaquant, alors il faudra « seulement » 5,1 × 10⁹, soit environ 5 milliards d’essais pour générer une collision en utilisant la force brute. Cette valeur est appelée limite de l’anniversaire[note 2]) et pour ${\displaystyle n}$ en binaire, cette valeur peut être calculée comme ${\displaystyle 2^{n/2}}$[3].

Le tableau ci-dessus montre le nombre de hashs ${\displaystyle n(p)}$ qu’il faut pour obtenir telle ou telle probabilité de succès, en considérant que toutes les valeurs de hachage ont la même probabilité. À titre de comparaison,le taux d'erreur non corrigeable d’un disque dur classique est 10^-18 à 10^-15[4]. En théorie, les hashs MD5 ou les UUIDs, sont de 128 bits, et devraient rester dans cette fourchette jusqu’à environ 820 milliards de documents, même si ses images possibles sont beaucoup plus nombreuses.

Il est facile de constater que si les images de la fonction sont inégalement réparties, alors une collision peut être trouvée encore plus vite. La notion « de répartition des images » d’une fonction de hachage influe directement sur la résistance de la fonction à des attaques des anniversaires. Cette faiblesse rend vulnérables des hashs populaires tels que MD et SHA.

La sous-expression ${\displaystyle \ln {\frac {1}{1-p}}}$ dans l’équation pour ${\displaystyle n(p;H)}$ n’est pas calculée avec précision pour les petites valeurs de ${\displaystyle p}$ lorsqu’elle est directement traduite dans un langage de programmation par log(1/(1-p))​ à cause de la perte de signification (en). Quand log1p​ est disponible par exemple, l’expression équivalente -log1p(-p)​ devrait être utilisée à la place. Si ce n’est pas le cas, la première colonne du tableau est remplie de zéros, et de nombreux éléments dans la seconde colonne n’ont pas de chiffres significatifs corrects.

def birthday(probability_exponent, bits):
    from math import log1p, sqrt
    probability = 10. ** probability_exponent
    outputs     =  2. ** bits
    return sqrt(2. * outputs * -log1p(-probability))

$ python -i anniversaire.py
>>> birthday(-15, 128)
824963474247.1193
>>> birthday(-6, 32)
92.68192319417072

Les signatures numériques peuvent être vulnérables à une attaque des anniversaires. Un message ${\displaystyle m}$ est normalement signé par le premier calcul ${\displaystyle f(m)}$, où ${\displaystyle f}$ est une fonction de hachage cryptographique et ensuite utiliser une clé secrète pour signer ${\displaystyle f(m)}$. Supposons que Mallory veuille escroquer Bob en signant un contrat frauduleux. Mallory prépare un contrat juste — ${\displaystyle m}$ — et un autre, frauduleux — ${\displaystyle m'}$. Ensuite, elle trouve un certain nombre de formulations où ${\displaystyle m}$ change mais pas le sens du contrat, par exemple une virgule inutile à insérer, une ligne vide, un caractère d'espace à la place de deux, remplacer des mots par des synonymes, etc. En combinant ces changements, elle peut créer un grand nombre de versions différentes de ${\displaystyle m}$ et du nombre qui certifie la totalité du contrat.

De la même manière, Mallory crée aussi un grand nombre de versions différentes du contrat frauduleux ${\displaystyle m'}$. Ensuite, elle applique la fonction de hash sur toutes ces différentes versions jusqu’à trouver deux contrats qui aient la même valeur de hash, ${\displaystyle f(m)=f(m')}$. Elle montre la version du contrat équitable à Bob pour qu’il le signe. Une fois le contrat signé, Mallory prend la signature et y attache le contrat frauduleux. La signature est la « preuve » que Bob a signé le contrat frauduleux.

Les probabilités diffèrent légèrement du problème d'anniversaires original, comme Mallory ne gagne rien en trouvant deux contrats justes ou deux contrats frauduleux avec le même hachage. La stratégie de Mallory est de générer des paires d’un contrat juste et d’un contrat frauduleux. Les équations de problèmes d’anniversaires appliquent quand ${\displaystyle n}$ est le nombre de paires. Le nombre de tables de hachage que Mallory génère réellement est ${\displaystyle 2n}$.

Pour éviter cette attaque, la longueur de ce que génère la fonction de hachage utilisée pour un schéma de signature doit être choisie de manière à être assez grande pour que l’attaque des anniversaires devienne mathématiquement impossible, soit environ deux fois plus de bits que nécessaire pour empêcher une attaque par force brute ordinaire.

L’algorithme rho de Pollard pour les logarithmes est un exemple utilisant une attaque des anniversaires pour le calcul de logarithmes discrets.