Attaque des anniversaires

Modèle:Voir homonymes 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. L'objet de l'attaque consiste à comparer entre elles les méthodes de chiffrement de plusieurs sources jusqu'à ce que deux d'entre elles correspondent. 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

Paradoxe des anniversaires

Modèle:Article détaillé Comme exemple du paradoxe des anniversaires, il est possible de considérer le scénario suivant.

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

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$.

Utilisation du paradoxe

Modèle:... Contrairement à d'autres attaques, celle-ci n'exploite pas une vulnérabilité du système mais seulement le fait que les valeurs de hachage ne soient pas très nombreuses. L'objectif est de trouver des collisions dans les hachages cryptographiques, par comparaison des valeurs de hachages entre un grand nombre d'ensemble de données. Par exemple en exploitant un grand nombre de signatures numériques, l'attaque des anniversaires peut statistiquement par la force brute découvrir au moins Modèle:Nobr utilisant le même cryptage. Le criminel peut alors créer de faux certificats qui semblent authentiques.

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 à Modèle:Retrait 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 Modèle:Retrait et en attribuant une valeur égale à 0,5 à la probabilité de collision, on trouve Modèle:Retrait Soit $Q(H)$ le nombre prévu de valeurs à choisir avant de trouver la première collision. Ce nombre est environ égal à Modèle:Retrait

Par exemple, si un hash de Modèle:Nobr est utilisé, il y a à peu près Modèle:Nombre images. Si elles sont aussi probables à obtenir, ce qui est le meilleur des cas pour l’attaquant, alors il faudra « seulement » Modèle:Unité, soit environ Modèle:Nobr d’essais pour générer une collision en utilisant la force brute. Cette valeur est appelée limite de l’anniversaire) et pour $n$ en binaire, cette valeur peut être calculée comme $2^{n/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	Modèle:Unité	<2	<2	<2	<2	<2	11	36	190	300	430
32	Modèle:Unité	<2	<2	<2	3	93	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité
64	Modèle:Unité	6	190	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité
128	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité
256	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité
384	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité
512	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité	Modèle:Unité

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 Modèle:Abréviation discrète 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 Modèle:Code à cause de la Modèle:Lien. Quand Modèle:Code est disponible par exemple, l’expression équivalente Modèle:Code 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é Modèle:Code, 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 Modèle:Retrait qui peut aussi s’écrire Modèle:Retrait 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 Modèle:Nobr ($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 Modèle:Retrait 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^{\prime }$. 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 synonymesModèle: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^{\prime }$. 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^{\prime })$. 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.

Annexes

Bibliographie

• Modèle:Article.
• Modèle:Ouvrage

Articles connexes

• Attaque de collisions
• Modèle:Lien

Liens externes

• Modèle:En « Modèle:Langue », FAQ de Modèle:Langue.