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

pages

Français

Documents

2007

Écrit par
Charles Bouillaguet

Publié par
profil-mupheg-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Documents

2007

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-mupheg-2012

Publié le

01 septembre 2007

Nombre de lectures

Langue

Français

Poids de l'ouvrage

1 Mo

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

Voir

Publié par

profil-mupheg-2012

Publié le

01 septembre 2007

Nombre de lectures

Langue

Français

Poids de l'ouvrage

1 Mo

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 inﬁnie . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . . .

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éﬁnition 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 suﬃt 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ériﬁcation de mots de passe, vériﬁcation de l’intégrité d’un ﬁchier ou d’un message (MAC), construction de schémas de chiﬀrement 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 ﬁxé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 eﬃcace, 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, ﬁxé par la spéciﬁcation 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 diﬃcile 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 diﬃcile de trou-ver un messageMproduisant ce haché (tel queH(M) =y).

résistance auxsecondes pré-imagesÉtant donné un messageM, il est diﬃcile 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 ﬁchier 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, inoﬀensive, et prétendre qu’elle n’a jamais signé que le message in-oﬀensif, et pas le chèque. Elle peut également, dans une certaine mesure, forger de fausses signatures : si elle réussit à faire signer le message inoﬀensif à 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 diﬀérentes choisies. En 1996, Hans

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. Enﬁn, 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 certiﬁcats X.509 pour deux identités diﬀé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 ﬁxes 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. Enﬁn, 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éﬁxe imposé par le challenger, trouver un suﬃxe qui atteigne le haché sur lequel l’attaquant s’était engagé (Chosen Target Forced Preﬁx Preimage).

1.3 Conséquences des progrès de la cryptanalyse Toutes ces attaques montrent, sous des éclairages diﬀé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éciﬁquement à 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 eﬀet, les at-taques en seconde pré-images ont un eﬀet 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 conﬁance à 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.

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 inﬁnies 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 ﬁnalement 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 suﬃsamment 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 ﬁgure 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. Enﬁn, cela donne également une idée plus ﬁne 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 ﬁgurer ma tentative d’obtenir, via la technique de

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. Enﬁn, 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éﬁnis 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 ﬁni 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éﬁnie parN=A∩B. Lemme 1. EA∩B=np∙q Démonstration.première étape du raisonnement consiste à montrer queLa EN=XPω∈A∩B ω∈Ω On remarque qu’on peut écrireA∩Bcomme l’union disjointe de ses éléments : A∩B=[(A∩B)∩ {ω} ω∈Ω Il en découle donc (du fait que l’union est disjointe) : A∩B=X(A∩B)∩ {ω} ω∈Ω 8

Voir