Attaque des anniversaires

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Anniversaire (homonymie).

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[modifier | modifier le code]

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 , alors la probabilité qu’au moins un élève soit né ce jour spécifique est , soit environ 7,9 %[note 1].

Par contre, la probabilité qu’au moins un élève aie la même date d’anniversaire que n’importe lequel des autres élèves est environ égale à 70 %, soit : avec [1].

En mathématiques[modifier | modifier le code]

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

Considérons l’expérience suivante. Dans un ensemble on choisit valeurs au hasard en autorisant les répétitions. Soit la probabilité que durant cette expérience au moins une valeur choisie plus d’une fois. Cette probabilité est à peu près égale à Soit le plus petit nombre de valeurs qu’on doit choisir, alors la probabilité de trouver une collision est au moins En inversant cette expression, on trouve l’approximation suivante et en attribuant une valeur égale à 0,5 à la probabilité de collision, on trouve Soit le nombre prévu de valeurs à choisir avant de trouver la première collision. Ce nombre est environ égal à

Par exemple, si un hash de 64 bits est utilisé, il y a à peu près 1,8×1019 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×109, 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] (en anglais : birthday bound) et pour en binaire, cette valeur peut être calculée comme [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−18 10−15 10−12 10−9 10−6 0,1 % 1 % 25 % 50 % 75 %
16 65 536 <2 <2 <2 <2 <2 11 36 190 300 430
32 4,3×109 <2 <2 <2 3 93 2 900 9 300 50 000 77 000 110 000
64 1,8×1019 6 190 6 100 190 000 6 100 000 1,9×108 6,1×108 3,3×109 5,1×109 7,2×109
128 3,4×1038 2,6×1010 8,2×1011 2,6×1013 8,2×1014 2,6×1016 8,3×1017 2,6×1018 1,4×1019 2,2×1019 3,1×1019
256 1,2×1077 4,8×1029 1,5×1031 4,8×1032 1,5×1034 4,8×1035 1,5×1037 4,8×1037 2,6×1038 4,0×1038 5,7×1038
384 3,9×10115 8,9×1048 2,8×1050 8,9×1051 2,8×1053 8,9×1054 2,8×1056 8,9×1056 4,8×1057 7,4×1057 1,0×1058
512 1,3×10154 1,6×1068 5,2×1069 1,6×1071 5,2×1072 1,6×1074 5,2×1075 1,6×1076 8,8×1076 1,4×1077 1,9×1077
Le tableau ci-dessus montre le nombre de hashs 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 dans l’équation pour n’est pas calculée avec précision pour les petites valeurs de 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[modifier | modifier le code]

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[modifier | modifier le code]

Une bonne règle générale qui peut être utilisée pour calculer mentalement est la relation qui peut aussi s’écrire . 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 () et que l’on veuille que la probabilité de collision soit au maximum de un sur un million (). Pour calculer le nombre de hash qu’il est possible d’avoir au maximum pour ce risque de collision, on fait ce qui est proche de la réponse exacte qui est 93.

Vulnérabilité pour les signatures numériques[modifier | modifier le code]

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

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 choisi de manière à ce qu’elle soit 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 d’algorithme utilisant une attaque des anniversaires pour le calcul de logarithmes discrets.

Notes et références[modifier | modifier le code]

(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[modifier | modifier le code]

  1. Pour simplifier on ignore les années bissextiles.
  2. Voir limites supérieures et inférieures (en).

Références[modifier | modifier le code]

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

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]