Attaque des anniversaires

Une attaque des anniversaires ou attaque par le paradoxe des anniversaires est un type d’attaque en cryptanalyse qui exploite des notions mathématiques équivalentes à celles qu’utilise le paradoxe des anniversaires en théorie des probabilités. Cette attaque peut être utilisée pour modifier les communications entre deux personnes ou plus. L’attaque est possible grâce à la probabilité plus élevée de collisions avec des tentatives d’attaques aléatoires et un niveau fixe de permutations, comme dans le principe des tiroirs.

Comprendre le problème

Article détaillé : Paradoxe 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 $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 : $1-365!/((365-n)!\cdot 365^{n})$ avec $n=30$ ^[1].

En mathématiques

Soit une fonction $f,$ le but de l’attaque est de trouver deux antécédents différents $x_{1},$ $x_{2}$ tels que $f(x_{1})=f(x_{2}).$ Une telle paire $x_{1},$ $x_{2}$ est appelée une collision. La méthode utilisée pour trouver une collision est simplement de comparer l’image de $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 $f(x)$ définie sur $H$ permet d’obtenir des images différentes avec la même probabilité et que $H$ est un ensemble suffisamment grand, alors on peut espérer obtenir une paire d'antécédents différents $x_{1}$ et $x_{2}$ pour lesquelles $f(x_{1})=f(x_{2})$ après avoir calculé l’image de la fonction pour seulement $1.25{\sqrt {|H|}}$ différents antécédents en moyenne.

Considérons l’expérience suivante. Dans un ensemble de cardinal $H,$ on choisit $n$ valeurs au hasard en autorisant les répétitions. Soit $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 à $p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}.\,$ Soit $n(p;H)$ le plus petit nombre de valeurs qu’on doit choisir, alors la probabilité de trouver une collision est au moins $p.$ En inversant cette expression, on trouve l’approximation suivante $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 $n(0.5;H)\approx 1.1774{\sqrt {H}}.\,$ Soit $Q(H)$ le nombre prévu de valeurs à choisir avant de trouver la première collision. Ce nombre est environ égal à $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 $n$ en binaire, cette valeur peut être calculée comme $2^{n/2}$ ^[2].

Des exemples pour des hashs de tailles différentes avec 2 chiffres significatifs.
Nombre de bits du hash	Images possibles (H)	Probabilité de collision désirée (p)
		10⁻¹⁸	10⁻¹⁵	10⁻¹²	10⁻⁹	10⁻⁶	0,1 %	1 %	25 %	50 %	75 %
16	65 536	<2	<2	<2	<2	<2	11	36	190	300	430
32	4,3 × 10⁹	<2	<2	<2	3	93	2 900	9 300	50 000	77 000	110 000
64	1,8 × 10¹⁹	6	190	6 100	190 000	6 100 000	1,9 × 10⁸	6,1 × 10⁸	3,3 × 10⁹	5,1 × 10⁹	7,2 × 10⁹
128	3,4 × 10³⁸	2,6 × 10¹⁰	8,2 × 10¹¹	2,6 × 10¹³	8,2 × 10¹⁴	2,6 × 10¹⁶	8,3 × 10¹⁷	2,6 × 10¹⁸	1,4 × 10¹⁹	2,2 × 10¹⁹	3,1 × 10¹⁹
256	1,2 × 10⁷⁷	4,8 × 10²⁹	1,5 × 10³¹	4,8 × 10³²	1,5 × 10³⁴	4,8 × 10³⁵	1,5 × 10³⁷	4,8 × 10³⁷	2,6 × 10³⁸	4,0 × 10³⁸	5,7 × 10³⁸
384	3,9 × 10¹¹⁵	8,9 × 10⁴⁸	2,8 × 10⁵⁰	8,9 × 10⁵¹	2,8 × 10⁵³	8,9 × 10⁵⁴	2,8 × 10⁵⁶	8,9 × 10⁵⁶	4,8 × 10⁵⁷	7,4 × 10⁵⁷	1,0 × 10⁵⁸
512	1,3 × 10¹⁵⁴	1,6 × 10⁶⁸	5,2 × 10⁶⁹	1,6 × 10⁷¹	5,2 × 10⁷²	1,6 × 10⁷⁴	5,2 × 10⁷⁵	1,6 × 10⁷⁶	8,8 × 10⁷⁶	1,4 × 10⁷⁷	1,9 × 10⁷⁷

Le tableau ci-dessus montre le nombre de hashs $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^[3]. 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 $\ln {\frac {1}{1-p}}$ dans l’équation pour $n(p;H)$ n’est pas calculée avec précision pour les petites valeurs de $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.

Exemple de code source

Voici une fonction en Python qui peut générer le tableau ci-dessus avec plus de précision :

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

Si le code est sauvegardé dans un fichier nommé anniversaire.py, il peut être lancé dans un terminal comme dans l’exemple suivant :

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

Approximation rapide

Une bonne règle générale qui peut être utilisée pour calculer mentalement est la relation $p(n)\approx {n^{2} \over 2m},$ qui peut aussi s’écrire $n\approx {\sqrt {2m\times p(n)}}$ . Elle fonctionne bien pour les probabilités inférieures ou égales à 0,5.

Ce schéma d'approximation est particulièrement facile à utiliser lorsque l’on travaille avec des exposants. Par exemple, supposons que l’on génère des hashs de 32 bits ( $m=2^{32}$ ) et que l’on veuille que la probabilité de collision soit au maximum de un sur un million ( $p\approx 2^{-20}$ ). Pour calculer le nombre de hash qu’il est possible d’avoir au maximum pour ce risque de collision, on fait $n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5$ ce qui est proche de la réponse exacte qui est 93.

Vulnérabilité pour les signatures numériques

Les signatures numériques peuvent être vulnérables à une attaque des anniversaires. Un message $m$ est normalement signé par le premier calcul $f(m)$ , où $f$ est une fonction de hachage cryptographique et ensuite utiliser une clé secrète pour signer $f(m)$ . Supposons que Mallory veuille escroquer Bob en signant un contrat frauduleux. Mallory prépare un contrat juste — $m$ — et un autre, frauduleux — $m'$ . Ensuite, elle trouve un certain nombre de formulations où $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 $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 $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, $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 $n$ est le nombre de paires. Le nombre de tables de hachage que Mallory génère réellement est $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.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Birthday attack » (voir la liste des auteurs).

Notes

↑ Pour simplifier on ignore les années bissextiles.
↑ Voir majorant ou minorant

Références

↑ (en) « Math Forum: Ask Dr. Math FAQ : The Birthday Problem », sur mathforum.org (consulté le 7 août 2015).
↑ (en) Jacques Patarin et Audrey Montreuil, « Benes and Butterfly schemes revisited » [PDF] [ps], sur eprint.iarc.org, Université de Versailles, 2005 (consulté le 15 mars 2007).
↑ (en) « Empirical Measurements of Disk Failure Rates and Error Rates », sur https://arxiv.org (consulté le 8 août 2015).

Annexes

Bibliographie

[Bellare et Kohno 2004] (en) Mihir Bellare et Tadayoshi Kohno, « Hash Function Balance and Its Impact on Birthday Attacks », Advances in Cryptology — EUROCRYPT 2004, lecture Notes in Computer Science, vol. 3027,‎ 2004, p. 401–418 (ISBN 978-3-540-21935-4, ISSN 0302-9743, DOI 10.1007/978-3-540-24676-3_24, lire en ligne [PDF]).
[Schneier 1996] (en) Bruce Schneier, Applied Cryptography : protocols, algorithms, and source code in C , New York, Wiley, 1996, 2^e éd., 758 p.

Articles connexes

Liens externes

(en) « Birthday Attack », FAQ de X5 Networks Crypto.

Portail de la cryptologie

[1] Pour simplifier on ignore les années bissextiles.

[3] Voir majorant ou minorant

[2] (en) « Math Forum: Ask Dr. Math FAQ : The Birthday Problem », sur mathforum.org (consulté le 7 août 2015).

[4] (en) Jacques Patarin et Audrey Montreuil, « Benes and Butterfly schemes revisited » [PDF] [ps], sur eprint.iarc.org, Université de Versailles, 2005 (consulté le 15 mars 2007).

[5] (en) « Empirical Measurements of Disk Failure Rates and Error Rates », sur https://arxiv.org (consulté le 8 août 2015).

[note 1]

[1]

[note 2]

[2]

[3]

v · m Fonctions de hachage cryptographiques
Algorithmes	APR1 AR Boognish FFT-hash HAS-160 Haval MD2 MD4 MD5 MD6 N-hash PANAMA RadioGatún RIPEMD RIPEMD-128 RIPEMD-160 RIPEMD-256 Scrypt SHA-0 SHA-1 SHA-2 SHA-224 SHA-256 SHA-384 SHA-512 SHA-3 Snefru StepRightUp Streebog Tiger VSH Whirlpool
Cryptanalyse	Attaque des anniversaires Paradoxe des anniversaires Linéaire Différentielle Attaque par force brute Effet avalanche Pseudo-collision Attaque de collisions Attaque de préimage Attaque par extension de longueur
Architecture	Remplissage Fonction de compression Construction de Merkle-Damgård Construction de Miyaguchi-Preneel Construction de Matyas-Meyer-Oseas Construction de Davies-Meyer Construction de l'éponge