Retrouvez cet article dans : Misc 18

Lors de l'été 2004, le petit monde de la cryptologie a connu une poussée d'adrénaline qui risque de laisser quelques traces dans son histoire. Le principal point de départ de toute cette excitation est en fait un court article (seulement 4 pages) signé par quatre chercheurs chinois, Xiaoyun Wang, Dengguo Feng, Xuejia Lai et Hongbo Yu, déposé sur l'archive électronique de l'IACR (http://eprint.iacr.org) le 16 août 2004, soit durant la conférence CRYPTO'04 (ces résultats ayant été présentés un jour plus tard lors de la " rump session " qui est une suite d'exposés informels, sérieux ou non, dont les cryptologues sont friands; une vidéo des présentations est d'ailleurs disponible sous [1]). Le contenu de ce papier était pour le moins sommaire : il présentait deux paires de collisions pour MD5, deux paires pour HAVAL-128, deux paires pour MD4, ainsi que deux paires pour RIPEMD, sans expliquer en détail comment ces collisions avaient été obtenues (et au moyen d'attaques à la complexité très basse), ces quatre algorithmes étant des fonctions de hachage cryptographiques. Toujours lors de CRYPTO'04, un article (faisant lui partie du programme " officiel " de la conférence) de Eli Biham et de son étudiant Rafi Chen décrivait une version améliorée de l'attaque d'Antoine Joux et Florent Chabaud (présentée lors de CRYPTO'98) contre SHA-0, l'ancêtre de SHA-1, ne parvenant cependant pas à casser la version complète de l'algorithme. Finalement, toujours lors de la même conférence (à nouveau pendant la " rump session "), Antoine Joux présentait l'exemple d'une collision contre SHA-0, dans sa version complète, cette fois, bouclant la boucle (voir le courrier électronique d'annonce donné en annexe, qui donne quelques détails sur la machine utilisée pour générer cette collision) ! Enfin, durant la mise sous presse de cet article, un coup de tonnerre a de nouveau ébranlé le ciel de la crypto : des cryptologues connus, dont Bruce Schneier et Adi Shamir, ont annoncé avoir reçu par courrier électronique un article signé par Xiaoyun Wang, Yiqun Lisa Yin et Hongbo Yu, soit une partie des acteurs de l'été 2004, annonçant une attaque par collisions (possédant une complexité théorique de 269 opérations) sur SHA-1 (voir l'annonce parue le 15 février 2005 sur le weblog de Bruce Schneier [8]). L'article n'étant pas (encore) publié officiellement, une certaine prudence est de rigueur, mais on peut raisonnablement s'attendre à ce qu'elle soit validée par la communauté des cryptologues, comme cela a été fait pour les résultats sur MD5, qui seront présentés lors d'Eurocrypt'05, qui aura lieu en mai au Danemark. Cette succession de nouveaux résultats étant pour le moins inhabituelle, voire carrément extraordinaire (qui plus est dans le domaine des fonctions de hachage), nous nous proposons donc de faire le point dans cet article sur les fonctions de hachage cryptographiques, dans un premier temps, et sur ces attaques et leur impact dans la vie pratique dans un second temps.

Propriétés d'une fonction de hachage

 Fig. 1- Fonction de hachage x → h(x)

 Au sens large du terme, une fonction de hachage h est une fonction mathématique qui possède au minimum les deux propriétés suivantes : h fait correspondre à une entrée x de taille arbitraire une sortie h(x) de taille fixe notée y (voir Figure 1) ; deuxièmement, le calcul de h(x) devrait être rapide pour n'importe quelle entrée x. Une fonction de hachage cryptographique, en plus des deux propriétés mentionnées plus haut, doit vérifier les trois conditions suivantes :

• Résistance à la première préimage : il doit être impossible pour un adversaire de trouver une entrée x telle que h(x) = y pour un y fixé à l'avance.
• Résistance à la seconde préimage : étant donné une entrée x fixée à l'avance et son haché y = h(x), il doit être impossible pour un adversaire de trouver une seconde entrée x' telle que h(x') = y avec x ≠ x'.
• Résistance aux collisions : il doit être impossible pour un adversaire de trouver deux valeurs arbitraires x ≠ x' telles que h(x) = h(x').

Par le terme " impossible ", on définit implicitement la puissance de calcul dont dispose un adversaire (et l'on admet donc qu'elle est bornée). Les fonctions cryptographiques de hachage sont largement utilisées en conjonction avec les algorithmes de signatures numériques, notamment. Par exemple, pour signer un message x de grande taille (disons plusieurs MB), il est nettement moins coûteux de signer son haché h(x) (qui fait typiquement 128 ou 160 bits de long) que le message x en entier. Si Alice n'utilise pas une fonction de hachage résistante à la seconde préimage, son adversaire Eve peut tenter de trouver un message x' tel que h(x) = h(x') et prétendre qu'Alice a signé x' (plutôt que x). Si, de plus, Eve est capable de choisir le message x qu'Alice va signer, il lui suffira de trouver une collision arbitraire h(x) = h(x') et de lui faire signer un des deux messages, ce qui motive la propriété de résistance aux collisions. On notera au passage que la résistance aux collisions implique la résistance à la seconde préimage, mais que l'inverse n'est pas vrai.

Attaques génériques

Il existe toute une série d'attaques génériques applicables contre n'importe quelle fonction de hachage. Nous nous proposons ici de les présenter brièvement. Pour une fonction de hachage possédant une taille de haché de ℓ bits, et si l'on considère cette fonction comme une boîte noire (c'est-à-dire qu'on n'exploite pas de propriété propre aux mécanismes internes de cette fonction), on peut monter trivialement une attaque contre la première préimage en essayant simplement des valeurs d'entrée x de manière aléatoire et en testant si le haché correspondant est égal à la valeur y visée. Le même principe s'applique également à la recherche d'une seconde préimage. En moyenne, on aura besoin de 2ℓ essais avant de trouver une solution; de plus, cette attaque ne requiert pas de mémoire. En pratique, une taille de haché égale à 128 ou 160 bits rend cette attaque prohibitive.

Attaques de type " paradoxe des anniversaires "

Si l'on cherche à casser la propriété de résistance aux collisions et que l'on ne connaît pas de faiblesse interne à la fonction visée, on va typiquement exploiter le bien-connu " paradoxe des anniversaires " : dans une assemblée de 23 personnes, la probabilité que deux personnes possèdent une date d'anniversaire identique est supérieure à 50% (elle est de plus de 99% pour une assemblée de 60 personnes), ce qui, dans un premier abord, contredit notre intuition (d'où le terme " paradoxe "). De manière équivalente, on peut considérer un terrain de football divisé en 365 rectangles de superficie égale et un footballeur qui est capable de shooter des ballons de telle manière qu'ils arrivent de manière uniformément distribuée dans chacun des 365 rectangles (en d'autres termes, pour chaque tir, les rectangles possèdent la même chance de recevoir le ballon). Le paradoxe des anniversaires version footbalistique indiquerait donc qu'après 60 ballons, on est quasiment certain de trouver un rectangle comportant au moins deux ballons (c'est-à-dire, une collision). La recherche de collisions pour une fonction de hachage obéit aux mêmes lois mathématiques, si ce n'est avec un ordre de grandeur différent pour les paramètres en jeu : en générant aléatoirement un grand nombre de messages, et en se " souvenant " d'une manière ou d'une autre des hachés correspondants, on rencontrera avec une bonne probabilité une collision après approximativement 2 essais. La complexité est donc une fonction de la moitié de la taille du haché. Ainsi, il est possible de casser génériquement une fonction retournant une valeur de 128 bits à l'aide d'un calcul de l'ordre de 264 opérations (280 pour une taille de haché de 160 bits). Un lecteur attentif aura probablement remarqué qu'au premier abord, une attaque de type paradoxe des anniversaires semble exiger une mémoire de taille 2, en plus du même nombre d'opérations de hachage. En réalité, il est possible d'implémenter une variante de l'attaque n'exigeant qu'un nombre très petit et constant de mémoire. Un petit exemple de programme en C qui trouve des pseudo-collisions de n bits pour SHA-1, c'est-à-dire des collisions sur les n bits les plus significatifs est disponible sous [9] ; il exploite l'algorithme ρ de Pollard qui permet de trouver un cycle dans une marche aléatoire. Ce programme doit être linké avec l'implémentation de SHA-1 de Brian Gladman disponible sous [2], et il a été écrit pour être exécuté sur une architecture Intel 32 bits. Il fonctionne de la manière suivante : on utilise pour cela deux marches aléatoires exécutées en parallèle et initialisées avec la même valeur x0 = x0', l'une étant mise à jour par xi = SHA-1(xi-1) tandis que l'autre est mise à jour selon xi' = SHA-1(SHA-1(xi-1')). Ainsi, la seconde marche fonctionne à " double vitesse " (voir Figure 2 ci-dessous).

Fig. 2 - Deux marches aléatoires exécutées en parallèle.

 

Dès que l'on trouve une collision xq = xq' pour un q quelconque, on sait que la marche rapide a rattrapé la marche lente (elle l'a peut-être déjà fait plusieurs fois, mais sans que l'on ait pu s'en rendre compte). Cela correspond à la partie FIRST STEP dans le code. Dans un second temps, on va déterminer combien de fois la marche rapide a rattrapé la marche lente (partie SECOND STEP), et à l'aide de ce nombre, on peut déterminer (partie THIRD STEP) xq-1 et xq-1' qui hachent sur la même valeur (tronquée). Il est également possible de paralléliser l'opération sur un grand nombre de machines en gérant des " points distingués " de manière centralisée. Ce bout de code permet de trouver deux valeurs collisionnant sur les 73 bits de gauche (sur un total de 160) en moins de trois jours sur une machine rapide. Si l'on tient également compte des bits en commun pas forcément adjacents, on arrive à un total de 118 bits identiques sur 160. Trouver des pseudo-collisions sur une fonction de hachage n'étant pas forcément très utile (à part si l'on considère une construction qui tronquerait le haché à un nombre trop petit de bits), le but de ce petit programme est très modestement d'illustrer une attaque par paradoxe des anniversaires implémentée sans mémoire.

Attaques dédiées

Les résultats de l'été dernier n'ont pas été obtenus via une attaque par paradoxe des anniversaires, bien trop coûteuse en temps de calcul, mais par une attaque " différentielle ". Le principe est relativement simple (mais il reste difficile à mettre en œuvre, et c'est là que " l'art " du cryptanalyste entre en jeu) et a été publié dans le monde académique par Biham et Shamir au tout début des années 1990 dans le cadre de la cryptanalyse différentielle du DES : on part de messages identiques (d'une taille de 2048 bits, dans la collision exhibée sur SHA-0 par Antoine Joux) et l'on cherche des positions de bit telles que si on les inverse dans un des deux messages, la probabilité qu'une collision existe est bien plus grande que prévue. Si l'on étudie de plus près les deux messages donnés dans le courrier électronique, on remarque ainsi que seule une petite partie des données est différente. L'effet de ces différences va s'annuler à l'intérieur de la fonction avec une certaine probabilité, qu'il est possible de calculer, et ensuite, tout le jeu consistera à générer suffisamment de paires de messages obéissant à cette différence, et d'attendre qu'une collision se produise, cette opération étant parallélisable très facilement. Dans l'attaque d'Antoine Joux, cette probabilité est de l'ordre de 2-50, et le nombre de paires de messages à générer est donc de l'ordre de l'inverse de ce (très petit) nombre.

Standards et autres

En plus d'être utilisées en conjonction avec des algorithmes de signature, les fonctions de hachage jouent un rôle central dans bien des domaines de la cryptologie, qu'elle soit théorique ou plus appliquée ; il est donc vital de disposer de fonctions rapides et sûres. En fait, l'immense majorité des fonctions de hachage que l'on rencontre en pratique font partie de deux familles : SHA-x et MDx. Il existe d'autres propositions dans la littérature (comme RIPEMD-x, TIGER, HAVAL, etc.), mais ces dernières sont soit cassées, soit elles n'ont pas été suffisamment cryptanalysées (voire pas du tout) et il est donc difficile de leur faire confiance pour un usage sérieux en pratique. En ce qui concerne le statut des fonctions de hachage, dont nous ne discutons pas dans cet article, le lecteur pourra se référer à la synthèse de Paulo Barreto [3], qui vaut le coup d'œil !

La famille MDx

La famille MDx (pour Message Digest version x) est issue des travaux de Ron Rivest (le " R " de RSA). Une première version de cette fonction, MD2, design propriétaire dans un premier temps, a seulement été publiée en 1992 ; même si on peut la considérer comme étant cassée, on la rencontre encore dans certains standards pour des raisons d'interopérabilité, principalement. Une seconde version, MD4 a été publiée, quant à elle, en 1990. Elle a également été cassée, et il n'est plus recommandé de l'utiliser en pratique. La version la plus courante, toujours largement déployée en pratique, est MD5, publiée en 1992. MD5 prend en entrée un message de taille arbitraire et retourne un haché possédant une taille de 128 bits. Grossièrement, voici son fonctionnement (on se référera à [4] pour plus de détails) : dans un premier temps, on tronçonne le message en blocs de 512 bits, le dernier bloc étant éventuellement complété à l'aide d'un bourrage, si besoin est, et la taille du message, codée sous la forme d'un entier de 64 bits, formant la fin du dernier bloc. MD5 est une fonction de hachage itérée, ce qui signifie qu'elle fait usage d'une fonction de compression prenant l'état courant, de 128 bits, ainsi qu'un bloc de 512 bits de données comme entrées, et retournant un nouvel état de 128 bits qui fera office d'entrée lors de l'itération suivante, le premier état étant une constante indépendante du message. Finalement, une transformation simple termine le processus. La fonction de compression est construite à partir d'opérations sur des entiers de 32-bit qui rendent MD5 très efficace sur les microprocesseurs modernes. Cryptographiquement parlant, MD5 est désormais considéré comme étant cassé, puisque des collisions ont été exhibées ; il est ainsi fortement recommandé d'éviter son utilisation dans le cadre d'une application critique dans le futur. Cependant, il faut noter que le glas ne sonnera définitivement pour MD5 que dès le moment où une attaque pratique par seconde préimage sera proposée, ce qui laisse un certain temps à disposition (néanmoins compté) pour organiser la transition. En résumé, il n'est désormais plus recommandé d'utiliser les membres de la famille MDx (soit MD2, MD4 et MD5) dans le cadre d'applications exigeant un haut niveau de sécurité.

La famille SHA-x

La famille SHA-x possède une propriété rare : c'est un design de la NSA rendu public et devenu un standard américain (ainsi que, de facto, mondial). Une première version, baptisée à l'origine SHA, et renommée SHA-0 par la suite pour la distinguer des autres, a été remplacée par une version améliorée, nommée SHA-1, ces deux fonctions produisant un haché de taille 160 bits. Il apparaît que la cause de ce remplacement était un problème de sécurité, dont les détails n'ont cependant pas été divulgués. Cependant, trois années plus tard, deux chercheurs français, Antoine Joux et Florent Chabaud ont exhibé [5] une attaque différentielle permettant théoriquement de trouver des collisions en 261 opérations (au lieu de 280 en utilisant le paradoxe des anniversaires). Une des conclusions de leur article était que le passage de SHA-0 à SHA-1 a strictement amélioré la sécurité de la fonction (du moins vis-à-vis de leur attaque). De là à conclure que le problème soulevé par la NSA était identique, il n'y a qu'un pas à faire (de manière prudente, cependant...). Plus tard, avec l'avènement de l'AES (nouveau standard pour le chiffrement symétrique), de nouvelles fonctions, SHA-256, SHA-384 et SHA-512 ont été publiées par le NIST (organe de standardisation américain). Ces fonctions possèdent des tailles de haché respectives de 256, 384 et 512 bits pouvant être utilisées de manière naturelle avec des clefs AES de taille 128, 192 et 256 bits. Le design des fonctions SHA-x peut être interprété comme étant une généralisation (à l'esprit relativement conservateur) de celui des fonctions de la famille MDx, et finalement, il n'y a pas de différence fondamentale entre ces deux familles. Le lecteur intéressé trouvera la description complète de ces fonctions dans les deux standards [6]. Le statut actuel des membres de la famille SHA-x est le suivant : on peut considérer que SHA-0 est, au même titre que MD5, désormais cassé, étant donné qu'il est possible de générer des collisions en pratique. Cela ne pose pas de problèmes majeurs, car cette fonction n'a pas vraiment été déployée en pratique. SHA-1, pour l'instant, est considéré comme possédant une sécurité fortement ébranlée par l'annonce du 15 février 2005. Entre l'été 2004 et le mois de février 2005, le consensus général à ce sujet était que les attaques contre SHA-0, ne semblaient pas applicables à SHA-1, Biham ayant lui-même déclaré publiquement qu'il ne voyait pas de danger à court terme pour SHA-1. Les événements auront finalement eu raison de sa prédiction. Quant aux nouveaux membres de la famille, SHA-256, SHA-384 et SHA-512, ils semblent être hors de portée des cryptanalystes (pour l'instant). Il faut cependant savoir que ces designs sont très récents, et qu'il n'existe, pour l'instant, quasiment pas de littérature à leur sujet...

Les événements récents et leurs conséquences

Les événements de ces derniers mois n'ont laissé personne indifférent, et ils me suggèrent ainsi plusieurs réflexions que le lecteur de MISC ne manquera pas de confronter à sa propre opinion. Premièrement, il est indéniable que l'étude, qu'elle soit constructive ou plus cryptanalytique, des fonctions cryptographiques de hachage était largement délaissée par la communauté académique les dix ou quinze dernières années, alors que, paradoxalement, les fonctions de hachage sont une des primitives cryptographiques les plus largement répandues dans la vie réelle. Cet état de fait se laisse facilement vérifier en calculant la proportion de papiers publiés lors de conférences ayant les fonctions de hachage comme sujet, et en comparant cette proportion aux autres sujets d'intérêt actuels en cryptographie. Il est aussi difficile d'expliquer cette situation que de prédire pourquoi un chercheur donné préférera travailler sur tel ou tel sujet, les affinités personnelles de chacun entrant en jeu de manière subjective. Cependant, une des leçons à en retirer est qu'il faut toujours se méfier de l'eau qui dort, et surtout, que rien n'est jamais acquis définitivement en cryptographie. Dans tous les cas, les résultats récents ont réveillé de manière brutale la communauté scientifique, et les fonctions de hachage redeviennent un sujet intéressant pour de nombreux chercheurs, ce qui, en soi, n'est pas une mauvaise chose ! Deuxièmement, il faut noter que la casse de MD5 n'arrive pas comme une surprise complète. Des travaux antérieurs de den Boer et de Bossalaers [7] ont démontré que la fonction de compression de MD5 n'est pas exempte de collisions. À l'époque, la portée de ces résultats était peu claire : certains les avaient commentés comme étant sans importance quant à leur impact sur la sécurité de MD5, d'autres avaient laissé entendre qu'il valait mieux considérer MD5 comme une fonction désormais " suspecte " et qu'il était raisonnable de songer à la remplacer par une alternative plus sûre dans les applications critiques. Les événements de l'été dernier laissent supposer que l'opinion des " paranoïaques " était la bonne : d'une faille sur la fonction de compression seule, aux conséquences apparemment théoriques, on est passé à des collisions sur la fonction complète. Comme indiqué plus haut, l'impact réel de ces collisions n'est pas (encore) dévastateur. Cependant, il est à parier que l'état de l'art n'en restera pas là, et qu'à terme, une attaque par seconde préimage verra très probablement le jour dans le futur. Tout le travail du devin consiste ainsi à savoir quand... Finalement, il est bon de se souvenir que les membres de la famille SHA-x ont de nombreux points en commun avec le design des fonctions MDx (le point de départ du design de SHA-1 étant MD4). Sans vouloir présumer de la sécurité des fonctions qui tiennent encore debout, une fois de plus, ce manque de diversité laisse pour le moins perplexe : par exemple, dans le monde de la clé publique, de nombreuses alternatives à RSA, standard incontournable, ont été proposées et étudiées, même si aucune ne s'est vraiment imposée pour l'instant. En cas de casse majeure de RSA, on ne se retrouvera ainsi pas (complètement) pris au dépourvu, étant donné que de nombreux algorithmes dont la sécurité est basée sur des problèmes difficiles différents de l'extraction de racines modulaires (comme pour RSA) sont à disposition des cryptologues. Il apparaît ainsi qu'un besoin urgent en matière de designs alternatifs se fait ressentir dans le domaine des fonctions cryptographiques de hachage.

En conclusion...

Même si les attaques présentées contre MD5 et SHA-1 n'ont pas un impact catastrophique sur les applications (étant donné qu'il s'agit de collisions, et non pas d'attaques contre la seconde préimage), force est de constater qu'aujourd'hui, une seule famille de fonctions cryptographiques de hachage en laquelle on puisse encore avoir un semblant de confiance reste à disposition de l'ingénieur-cryptologue, et parmi les membres de cette famille, trois fonctions ( SHA-256, SHA-384 et SHA-512) peuvent réellement se targuer de posséder une " histoire cryptanalytique " encore vierge ; cependant, faute d'avoir été cryptanalysés de manière sérieuse sur une période de temps conséquente, ces membres récents exigent indéniablement encore un peu de recul. Cette situation, quoique pas dramatique, reste pour le moins très inconfortable, et le besoin de nouveaux designs commence à se faire extrêmement pressant !

 

Courrier électronique

Références

• [1] http://www.hcrypto.com
• [2] http://fp.gladman.plus.com
• [3] http://planeta.terra.com.br/informatica/paulobarreto/hflounge.html
• [4] R. Rivest, The MD5 message-digest algorithm, RFC 1321.
• [5] F. Chabaud, A. Joux, Differential Collisions in SHA-0, Proceedings of CRYPTO'98, Springer-Verlag.
• [6] http://csrc.nist.gov/CryptoToolkit/tkhash.html
• [7] B. den Boer, A. Bossalaers, Collisions for the compression function of MD5, Proceedings of EUROCRYPT'93, Springer-Verlag.
• [8] http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
• [9] http://crypto.junod.info/pseudo_coll_sha1.c

 Retrouvez cet article dans : Misc 18