Sécurité et preuves de sécurité des fonctions de hachage
80 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Sécurité et preuves de sécurité des fonctions de hachage

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
80 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Master

  • mémoire


Sécurité et preuves de sécurité des fonctions de hachage Charles Bouillaguet, sous la direction de Pierre-Alain Fouque Département d'Informatique de l'ENS de Paris, Crypto Team 12 septembre 2007 Table des matières 1 Introduction 3 1.1 Motivation pour l'étude des fonctions de hachage . . . . . . . 3 1.2 Résultats récents de cryptanalyse . . . . . . . . . . . . . . . . 4 1.2.1 Les attaques contre les fonctions de compression . . . 4 1.2.2 Les attaques contre le mode opératoire lui-même . . . 5 1.3 Conséquences des progrès de la cryptanalyse . . . . . . . . . . 5 1.4 Sujet et résultats obtenus . . . . . . . . . . . . . . . . . . . . 6 2 Préliminaires 8 2.1 Paradoxe des anniversaires, collisions et complexité . . . . . . 8 2.2 Critères de sécurité . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 La construction de Merkle-Damgård . . . . . . . . . . . . . . 11 2.4 Construire des fonctions de compressions à partir d'un block cipher . . . . . . . . . . . . . . . . . . . . . . .

  • collision

  • recherche de collisions parallèle

  • rééquilibrage de diamants

  • mdd-cp

  • résultats récents de cryptanalyse

  • diamant déséquilibré

  • nouvelle attaque

  • sécurité de la construction


Sujets

Informations

Publié par
Publié le 01 septembre 2007
Nombre de lectures 43
Langue Français
Poids de l'ouvrage 1 Mo

Extrait

Sécurité et preuves de sécurité des fonctions de hachage Charles Bouillaguet, sous la direction de Pierre-Alain Fouque Département d’Informatique de l’ENS de Paris, Crypto Team 12 septembre 2007
Table des matières 1 Introduction 1.1 Motivation pour l’étude des fonctions de hachage . . . . . . . 1.2 Résultats récents de cryptanalyse . . . . . . . . . . . . . . . . 1.2.1 Les attaques contre les fonctions de compression . . . 1.2.2 Les attaques contre le mode opératoire lui-même . . . 1.3 Conséquences des progrès de la cryptanalyse . . . . . . . . . . 1.4 Sujet et résultats obtenus . . . . . . . . . . . . . . . . . . . . 2 Préliminaires 2.1 Paradoxe des anniversaires, collisions et complexité . . . . . . 2.2 Critères de sécurité . . . . . . . . . . . . . . . . . . . . . . . . 2.3 La construction de Merkle-Damgård . . . . . . . . . . . . . . 2.4 Construire des fonctions de compressions à partir d’un block cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Rôle du strengthening de Merkle-Damgård . . . . . . . . . . 2.6 Attaques en seconde pré-image déjà connues . . . . . . . . . . 2.6.1 Cadre général des attaques génériques en seconde pré-image . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Attaque des longs messages . . . . . . . . . . . . . . . 2.6.3 Attaque de Dean [1] . . . . . . . . . . . . . . . . . . . 2.6.4 Attaque de Kelsey et Schneier [2] . . . . . . . . . . . . 2.7 Un peu de langages formels . . . . . . . . . . . . . . . . . . . 2.7.1 Mots, séquences et carrés . . . . . . . . . . . . . . . . 2.7.2 Séquences sans carrés et morphisme . . . . . . . . . . 2.7.3 Mesure de la complexité d’une séquence infinie . . . . 2.8 Proposition de Rivest et variantes . . . . . . . . . . . . . . . . 2.8.1 Logique du hachage itéré avec dithering . . . . . . . . 2.8.2 Keränen-MDD . . . . . . . . . . . . . . . . . . . . . . 2.8.3 MDD-CP . . . . . . . . . . . . . . . . . . . . . . . . .
1
3 3 4 4 5 5 6 8 8 11 11 12 12 14 14 15 15 18 21 21 21 23 23 23 25 25
3 Une nouvelle attaque générique en seconde pré image 26 3.1 Construction de la structure en diamant . . . . . . . . . . . . 26 3.1.1 Définition de la structure . . . . . . . . . . . . . . . . 26 3.1.2 Algorithme de construction . . . . . . . . . . . . . . . 28 3.2 Application à la construction de messages expandables . . . . 30 3.3 Adaptation de l’attaque au cas de Merkle-Damgård avec Di-thering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.4 Application de l’attaque aux propositions de Rivest . . . . . . 34 3.4.1 Cryptanalyse de Keränen-MDD . . . . . . . . . . . . . 34 3.4.2 Cryptanalyse de MDD-CP . . . . . . . . . . . . . . . . 36 4 Peut-on réparer la proposition de Rivest ? 38 4.1 Variante sans dilution : Eager-MDD . . . . . . . . . . . . . . 38 4.2 Variante avec une autre séquence de base . . . . . . . . . . . 39 4.3 Il suffit de savoir compter... . . . . . . . . . . . . . . . . . . . 41 4.4 ...Ou de savoir jouer aux dés . . . . . . . . . . . . . . . . . . . 42 5 Application de l’attaque au schéma de Shoup pour une UOWHF 46 5.1 Généralités sur les UOWHF . . . . . . . . . . . . . . . . . . . 46 5.2 Description de la construction . . . . . . . . . . . . . . . . . . 47 5.3 cryptanalyse de la UOWHF de Shoup . . . . . . . . . . . . . 48 5.3.1 Fonctions de hachage itérées avec fonctions de com-pression multiples . . . . . . . . . . . . . . . . . . . . . 48 5.3.2 Complexité de la séquence de dithering . . . . . . . . . 48 5.3.3 Comparaison avec la preuve de sécurité de Shoup . . . 50 5.3.4 Target Collision Resistance et secondes pré-images . . 51 5.3.5 (ajout du 12/9/07) Résultats sur l’optimalité de la construction . . . . . . . . . . . . . . . . . . . . . . . . 51 6 Résistance aux attaques en seconde pré-image dans le mo-dèle de l’oracle aléatoire 52 6.1 Résistance du schéma de Merkle-Damgård . . . . . . . . . . 52 6.2 Résistance de HAIFA . . . . . . . . . . . . . . . . . . . . . . . 54 6.3 Comment réparer Merkle-Damgård ? . . . . . . . . . . . . . . 55 6.4 (ajout du 12/9/07) Résistance prouvée aux secondes pré-images 56 7 Conclusion 58 A Tentative d’obtenir un compromis temps-mémoire pour la construction de la structure en diamant 59 A.1 Compromis temps-mémoire . . . . . . . . . . . . . . . . . . . 59 A.2 Recherche de collisions parallèle et compromis temps-mémoire 60 A.3 Application à la construction du diamant - première tentative 62 A.4 Utilité d’un diamant déséquilibré . . . . . . . . . . . . . . . . 63 2
A.5 Rééquilibrage de diamants . . . . . . . . . . . . . . . . . . . . 65 A.6 Troisième tentative —L <+. . . . . . . . . . . . . . . . . 69
1 Introduction 1.1 Motivation pour l’étude des fonctions de hachage Les fonctions de hachage sont des primitives omniprésentes en cryptogra-phie, et leurs applications sont innombrables : signature (“Hash-and-sign”), vérification de mots de passe, vérification de l’intégrité d’un fichier ou d’un message (MAC), construction de schémas de chiffrement asymétriques IND-CCA, etc. etc. En fait, dans bon nombre de ces applications, les fonctions de hachage sont utilisées pour simuler des oracles aléatoires, c’est-à-dire, dans ce contexte, des fonctions prenant en entrée une chaîne de bits de taille arbitraire, et pro-duisant une chaîne de bits aléatoire de taille fixée. Plusieurs fonctions (ou familles de fonctions) de hachage usuelles ont été standardisées (MD5 [3] et SHA-1 [4]). Ce sont toutes des fonctions de hachage itérées, reposant sur le paradigme que Merkle [5] et Damgård [6] ont présenté indépendamment à CRYPTO’90. L’idée, simple et efficace, consiste à itérer une fonction de compression sur les blocs de message successifs. La sécurité de la construction itérée repose alors sur la sécurité de la fonction de compression.
Fig.1:Fonction de hachage itérée.Fest la fonction de compression. Le messageMest coupé en blocsM=x1, . . . , xr.IVest un vecteur d’initiali-sation, fixé par la spécification de la fonction de hachage. La sécurité des applications susmentionnées repose largement sur plu-sieurs propriétés (supposées) des fonctions de hachage : résistance auxcollisionsIl est difficile de trouver deux messagesMet M0qui produisent le même haché, i.e. tels queH(M) =H(M0). résistante auxpré-imagesÉtant donné un hachéy, il est difficile de trou-ver un messageMproduisant ce haché (tel queH(M) =y).
3
résistance auxsecondes pré-imagesÉtant donné un messageM, il est difficile de trouver un autre messageM0qui collisionne avecMque H(M) =H(M0). Ces trois problèmes n’ont pas la même complexité. Calculer des collisions est plus simple que calculer des secondes pré-images, car une seconde pré-image est en particulier une collision (alors que l’inverse n’est pas vrai). De même calculer une seconde pré-image est plus simple que calculer une pré-image : si l’on sait calculer les pré-images, on peut calculer des secondes pré-images, alors que l’inverse n’est pas vrai. Prenons quelques exemples. Si Alice accède à l’ordinateur de Bob pendant qu’il a le dos tourné, elle peut éventuellement lire le fichier qui contient le haché de son mot de passe de connection. Si elle peut calculer une pré-image, alors elle obtiendra un mot de passe (pas nécessairement le même), qui lui permettra de se connecter au compte de Bob n’importe quand. Considérons maintenant un système de signature où, pour signer un mes-sage, on calcule son haché, et où on signe en fait le haché. Supposons qu’Alice soit capable de calculer des collisions. Alors, elle peut générer une collision, et les deux messages auront la même signature. Alice peut très bien signer le premier et ensuite prétendre qu’elle a seulement signé le second. L’inconvé-nient, c’est qu’Alice n’a pas forcément beaucoup de contrôle sur le contenu des deux messages en question. Supposons maintenant qu’Alice soit capable de calculer des secondes pré-images pour la fonction de hachage utilisée. Là, Alice est dans une situation bien plus avantageuse. Elle peut, par exemple, répudier à volonté ses propres signatures : si elle signe un gros chèque, elle peut calculer une seconde pré-image, inoffensive, et prétendre qu’elle n’a jamais signé que le message in-offensif, et pas le chèque. Elle peut également, dans une certaine mesure, forger de fausses signatures : si elle réussit à faire signer le message inoffensif à son pire ennemi (Bob), elle peut ensuite exhiber le gros chèque... portant la signature numérique de Bob. 1.2 Résultats récents de cryptanalyse Cependant, relativement récemment, de nombreux résultats ont conduit la communauté à questionner la sécurité de certaines des fonctions de ha-chage standardisées et largement déployées, ainsi qu’à remettre en question le fait qu’elles puissent simuler des oracles aléatoires dans les implémentations de schéma qui en nécessitent. 1.2.1 Les attaques contre les fonctions de compression En 1993, Bert den Boer et Antoon Bosselaers [7] ont présenté une collision d’une forme particulière sur la fonction de compression de MD5 : un même bloc de message collisionne pour deux IV différentes choisies. En 1996, Hans
4
Dobbertin [8] exhiba deux blocs de messages qui collisionnent pour un IV choisi. Lors de la Rump session de CRYPTO’04 [9], Xiaoyun Wang et al. ont annoncé une nouvelle méthode pour obtenir des collisions pour les fonctions MD4 et MD5. Par la suite, les articles correspondants [10, 11, 12] ont été publiés. D’un autre côté, Biham, Chen, Joux et al. [13] ont obtenu une collision complète pour SHA0 en 2005. Par la suite, la technique a été améliorée par Wang [14]. Ces résultats ont ensuite été étendus à SHA-1 [15]. Aucune collision complète pour SHA-1 n’a été obtenue pour l’instant, bien que de nombreux résultats aillent dans ce sens. Enfin, Klima [16] a mis au point en 2006 un programme qui trouve des collisions pour MD5, à IV arbitraire, en quelques secondes. Ces résultats ne sont pas sans conséquences : Lenstra et al. ont réussi à construire deux certificats X.509 pour deux identités différentes qui colli-sionnent [17, 18] 1.2.2 Les attaques contre le mode opératoire lui-même Le mode opératoire lui-même, qui consiste à itérer une fonction de com-pression, peut être attaqué, ce qui donne lieux à des attaquesgénériques, indépendantes de la fonction de compression. En 1999, dans sa thèse de doctorat, Dean [1] a présenté une attaque en seconde pré-image contre les fonctions de hachage basées sur le schéma de Merkle-Damgård et dont la fonction de compression desquelles possède des points fixes qu’il est facile de trouver. C’est le cas entre autres de toutes les fonctions de hachage dont la fonction de compression est construite selon le schéma de Davies-Meyer [19], en particulier de MD4, MD5, SHA-1, etc. Son attaque a ensuite été étendue en 2005 par Kelsey et Schneier [2]. Pour une complexité à peine supérieure, ils obtiennent des secondes pré-images pour n’importe quelle fonction de hachage basée sur le schéma de Merkle-Damgård . Entre temps, en 2004, Joux [20] a présenté une attaque en multi-collisions contre les fonctions de hachage de type Merkle-Damgård . Pour le prix dek collisions entre deux messages, il est possible de construire2kmessages qui collisionnent. Enfin, en 2006, Kelsey et Kohno [21] ont présenté une nouvelle attaque, qu’ils appellent avec malice l’attaque de Nostradamus. Elle consiste, pour l’adversaire, à choisir un haché, puis étant donné un préfixe imposé par le challenger, trouver un suffixe qui atteigne le haché sur lequel l’attaquant s’était engagé (Chosen Target Forced Prefix Preimage).
5
1.3 Conséquences des progrès de la cryptanalyse Toutes ces attaques montrent, sous des éclairages différents, que les fonc-tions de hachage actuellement déployées sont loin de se comporter comme des oracles aléatoires. L’accélération des progrès de la cryptanalyse autour des années 2004 et 2005 a conduit le NIST à organiser deux workshops, en octobre 2005 et en août 2006, pour discuter des implications des attaques récentes ainsi que pour mieux comprendre la construction de fonctions de hachage et les nouvelles attaques. Plusieurs nouvelles fonctions de compression ont été proposées lors de ces workshops, ainsi que plusieurs modes opératoires. D’un côté, certaines propositions (EMD [22] et OMD [23]), ont été conçues avec comme objectif d’obtenir des preuves de certaines propriétés d’indistin-guabilité face à un oracle aléatoire, et ignorent le fait que l’attaque de [2] s’applique à elles. D’un autre côté, deux de ces nouveaux modes, HAIFA [24] et le “dithered hashing” de Rivest [25] répondent spécifiquement à la préoccupation d’em-pêcher l’attaque en seconde pré-image [2], et les attaques du même type. Il faut cependant bien préciser que ce n’est pas une attaquepratique, puis-qu’elle requiert une quantité de calcul inaccessible aujourd’hui. Elle illustre cependant la faiblesse théorique de la construction de Merkle-Damgård . Cependant, elle présente un certain intérêt théorique. En effet, les at-taques en seconde pré-images ont un effet important sur les systèmes de signature électronique. Dans le cas de MD5, l’attaque de [2] permet d’obtenir une seconde pré-image en environ274évaluations de la fonction de compression. Bien que ceci soit hors de portée aujourd’hui, combien de temps faut-il encore faire confiance à une signature électronique basée sur MD5 ? Toujours est-il qu’il y a aujourd’hui au moins deux modes opératoires qui ont été conçus dans le but de résister à cette attaque. Ils ne disposent cependant d’aucune preuve de sécurité qui garantirait leur résistance face aux attaques en seconde pré-imageen général. Finalement, le NIST a décidé récemment de lancer une compétition pour renouveler les fonctions de hachages standardisées, et pour mettre en place l’AHS (Advanced Hash Standard), de la même manière que l’AES (Advanced Encryption Standard) avait été mis en place. 1.4 Sujet et résultats obtenus Le but de mon stage était donc d’étudier la sécurité de ces nouveaux modes opératoires, en particulier du point de vue de la résistance aux at-taques en seconde pré-image.
6
Le premier objectif consistait à essayer d’obtenir une attaque sur la pro-position qui paraissait la plus faible, à savoir celle de Rivest. J’ai donc étudié la “proposition concrète” de Rivest, ainsi que certaines variantes que lui ou moi avons envisagé. J’ai obtenu une nouvelle attaque en seconde pré-image qui fonctionne contre presque toutes ces variantes. Elle a une complexité légèrement supérieure à celle de [2], et repose principalement sur des idées de l’attaque de Nostradamus [21]. C’est l’objet de la section 3 et le principal résultat (en terme d’importance) du stage. Un des paramètres essentiels de la construction de Rivest est la “séquence de dithering”, qu’il choisit en fonction de critères d’apériodicité. L’attaque que j’obtiens démontre que ce n’est pas le seul critère à prendre en compte, et que, en particulier, la complexité, ou, inversement, le degré de régularité des séquences en question joue un grand rôle. J’ai donc un peu cherché si, en utilisant d’autres séquence de dithering, la proposition de Rivest devenait plus sûre. Pour cela, j’ai été amené à étudier un peu la complexité de certaines suites infinies plus ou moins connues. En particulier, j’ai obtenu, avec l’aide de Steven Gay, une preuve d’un joli résul-tat concernant certain type de séquences très régulières... avant de découvrir qu’il était connu depuis 35 ans ! J’ai finalement obtenu deux variantes de la proposition de Rivest ré-sistantes à mon attaque. L’une d’entre elles est tout simplement HAIFA, l’autre consiste à utiliser une séquence de dithering pseudo-aléatoire. Ces deux constructions sont dans la section 4. Un peu plus tard, je me suis rendu compte que l’attaque que j’avais trou-vée était suffisamment générique pour être appliquée à des constructions qui sortent du cadre de Merkle-Damgård . Elle peut s’appliquer à une Universal One Way Hash Function construite par Shoup [26]. Il présente une preuve de sécurité, donc on ne peut pas dire que je casse sa construction. Cependant, je démontre que sa réduction est “tight”, et je présente la seule attaque connue contre sa construction. Ceci figure section 5. Finalement, avec l’aide de Sebastien Zimmer, j’ai pu obtenir une preuve de sécurité relativement générale qui donne une borne inférieure au coût des attaques génériques en seconde pré-image sur une assez large classe d’ex-tensions du schéma de Merkle-Damgård (en gros, toutes les variations qui font intervenir, d’une manière ou d’une autre, un compteur de ronde). Cela démontre d’une part que l’attaque de [2] sur les fonctions de type Merkle-Damgård classique est optimale, parmi les attaques génériques. D’autre part, cela démontre aussi que HAIFA est résistant aux attaques génériques en seconde pré-image. Enfin, cela donne également une idée plus fine de la taille de l’état interne nécessaire pour se prémunir contre les attaques en seconde pré-image dans le cas de Merkle-Damgård . Il a été suggéré [27] de le doubler ; en fait, une telle augmentation n’est pas nécessaire. Tout ceci est détaillé section 6. En annexe, je fais figurer ma tentative d’obtenir, via la technique de
7
recherche de collisions de van Oorschot et Wiener, [28] un compromis temps-mémoire avantageux pour la construction de la “structure en diamant” de l’attaque de Nostradamus de [21] (c’est en fait une grosse multicollision qui a la forme d’un arbre binaire complet). Cette tentative s’est soldée par un échec, qui est décrit dans l’annexe A. Enfin, les travaux de ce stage vont faire l’objet d’une (tentative de) pu-blication très prochainement. 2 Préliminaires Dans cette section, je présente les résultats et les notions nécessaires pour accéder aux résultats que j’ai obtenus. Je présente tout d’abord des généralités sur les fonctions de hachage, et je décris l’état de l’art des attaques génériques en seconde pré-image. Je définis ensuite un peu de vocabulaire dont j’ai besoin pour présenter les fonctions de hachage que j’ai étudiées. Je décris la proposition de Rivest, que je nomme MDD (Merkle-Damgård avec Dithering), et une de ses variantes. 2.1 Paradoxe des anniversaires, collisions et complexité Vu que dans tout mon stage on a considéré les fonctions de compressions comme des fonctions aléatoires, la brique intellectuelle de base de la plupart des raisonnements présentés ici est le paradoxe des anniversaires. Une des formulations à la fois les plus simples et les plus utiles en est la suivante. SoitΩun ensemble fini de cardinaln.AetBsont des variables aléa-toires indépendantes et distribuées uniformément parmi l’ensemble des sous-ensembles deΩde tailles respectivementpetq.Nest une variable aléatoire définie parN=AB. Lemme 1. EAB=npq Démonstration.première étape du raisonnement consiste à montrer queLa EN=XPωABωΩ On remarque qu’on peut écrireABcomme l’union disjointe de ses éléments : AB=[(AB)∩ {ω} ωΩ Il en découle donc (du fait que l’union est disjointe) : AB=X(AB)∩ {ω}ωΩ 8
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents