David Madore's WebLog: Les fonctions de hachage, c'est génial

Je me sens d'humeur[#] pédagogique : à essayer d'expliquer ce que c'est qu'une fonction de hachage (cryptographique) et pourquoi je trouve que c'est quelque chose d'absolument génial. Le point de départ, ça pourrait être le problème suivant : on a deux personnages (que, conformément à la tradition, on pourrait appeler Alice et Bob[#2]) qui veulent jouer à pile ou face pour désigner un gagnant et un perdant ; l'ennui, c'est qu'Alice et Bob ne sont reliés que par un canal de communication quelconque (par exemple, ils sont en train de se téléphoner, ou ils échangent des emails), ils n'ont pas accès à un tiers impartial, encore moins à une pièce visible des deux — et il ne sert à rien qu'Alice jette de son côté pièce en l'air et dise j'ai gagné si Bob ne peut pas s'assurer qu'elle n'a pas triché ! Pourtant, la grande surprise, c'est qu'il y a bien un moyen de désigner un gagnant et un perdant de façon impartiale avec un simple canal de communication. On peut prendre ça comme un problème de logique : je crois que c'est la catégorie de problèmes (catégorie à laquelle je ne saurais même pas donner un nom — peut-être protocoles cybernétiques) qui me fascine le plus ; et je n'aurais jamais pensé qu'il y avait une solution, jusqu'à ce qu'on me l'explique. C'est pour ça que je trouve que les fonctions de hachage sont quelque chose de merveilleusement ingénieux.

Donc, qu'est-ce que c'est qu'une fonction de hachage ? On va prendre pour illustrer l'exemple de SHA224, qui en est un exemple tout à fait respectable : la fonction SHA224 prend en entrée une chaîne quelconque de caractères[#3] (un document arbitraire), par exemple, MOUTON, et elle renvoie ce qu'on appelle un haché ou une empreinte, qui fait toujours la même taille, et dans le cas de SHA224, comme le nom l'indique (SHA, au fait, veut dire Secure Hash Algorithm), fait 224 bits, c'est-à-dire 224 données pouvant prendre la valeur 0 ou 1 :

MOUTON → SHA224: 01101110 01101111 11011000 10000100 01111100 00101101 11110110 10110010 11111000 00101110 01011001 11010100 11101011 11001010 10010111 10110011 11010001 00101110 10100010 01101110 00101011 11010101 11000110 00010011 01000000 00010111 00010111 01101100

La longueur sera toujours 224, quelle que soit la taille de l'entrée, qu'elle soit d'un caractère (ou même zéro) ou cent milliards. Comme c'est un peu long à écrire en binaire (qu'on mette ou pas des espaces pour aérer), on préfère généralement l'hexadécimal (base 16 : les chiffres vont de 0 à 9 et de a à f, et alors il n'y en a plus que 56),

MOUTON → SHA224: 6e6fd884 7c2df6b2 f82e59d4 ebca97b3 d12ea26e 2bd5c613 4017176c

ou le MIME (base 64) —

MOUTON → SHA224: bm/YhHwt9rL4LlnU68qXs9Euom4r1cYTQBcXbA==

— mais dans tous les cas, c'est la même valeur, sous différentes formes. Mettons qu'on s'en tienne à l'hexadécimal, qui est le plus habituel. Le fait important est que le calcul de la fonction de hachage est universel (tout le monde peut refaire le calcul et trouvera la même valeur) mais tout à fait imprévisible et en apparence aléatoire (il n'y a pas d'autre moyen de connaître le haché que de faire le calcul, et du point de vue de toutes les statistiques qu'on voudra faire, tout se passe comme si chaque bit du haché était tiré au hasard pour chaque chaîne possible) : c'est là que ça devient intéressant. Même le plus petit changement dans l'entrée donne une empreinte complètement différente :

BOUTON → SHA224: 7f1f70cd 41b67802 fb7ae2b9 56f9d859 8efdb14d 83da8daa be3493e1

BOULON → SHA224: 21a45514 44ffdbb4 954173f9 309acea2 a5160d27 f768dc1a 2d1da051

Ce n'est pas directement ce caractère « aléatoire » qui permettra de jouer à pile ou face, mais c'est déjà quelque chose d'intéressant[#4]. D'autre part, il faut se rendre compte que si je connais un haché,

? → SHA224: cbc7de29 e97b427f d952f10f 1fc9701e da21bdb6 7d12e5e9 b118e29b

cela ne donne aucune information utile sur le document qui a été haché, et en particulier, il n'y a pas moyen, a priori[#5], de le retrouver. Pire, n'existe pas de moyen (pratique !) de trouver une chaîne quelconque (pas forcément la même) ayant ce haché. En fait, c'est encore plus fort que ça : il va de soi qu'il doit exister plusieurs entrées différentes qui ont le même haché en sortie (et ce, pour n'importe quelle fonction de hachage donnée), et même un nombre infini, puisque l'ensemble des chaînes est infini alors que celui des hachés est fini (comme leur taille est constante) ; pourtant, si la fonction de hachage est bonne (c'est-à-dire cryptographiquement forte) personne n'est capable de fournir deux documents qui ont la même empreinte (on parle de collisions[#6]).

Là on a un intérêt évident de la fonction de hachage : elle permet de vérifier l'intégrité d'une donnée. Quand je grave un CD, je note sur la pochette le haché (généralement MD5, parce que c'est plus court) des données qu'il contient, ce qui permettra de vérifier qu'il n'y a pas eu de corruption. De même, si Alice et Bob ont un gros fichier chacun de leur côté, et soupçonnent que c'est le même, une façon de s'en assurer, sans transmettre le fichier entier par le canal de communication (ce qui est long), c'est de calculer chacun le haché, et de s'assurer qu'ils ont le même.

Il y a mieux : la fonction de hachage permet de créer des plis scellés. En effet, si je dispose d'un document maintenant, que je ne veux pas rendre public, mais je veux pouvoir prouver, plus tard, que je le possédais dès maintenant, la méthode traditionnelle était de mettre le document sous pli scellé et de le déposer auprès d'une personne de confiance (typiquement, l'Académie des sciences). La méthode cryptographique consiste à simplement calculer le haché de ce document et le publier (il ne donnera aucune information utilisable à qui que ce soit), garder le document lui-même bien au secret (en faisant attention à ne pas le perdre ! car si on y change un seul bit, l'empreinte devient complètement différente) : s'il s'avère qu'on veut plus tard publier le document, chacun pourra alors vérifier que son haché est bien celui qui avait été annoncé, et donc (comme la seule façon de calculer un haché est de disposer du document) que le document était bien connu au moment où le haché a été révélé. D'où l'exacte analogie avec l'enveloppe scellée.

Et voici alors comment on peut jouer à pile ou face : Alice, de son côté, va choisir le nom d'un des deux joueurs (donc soit le sien soit celui de Bob), elle le met dans une enveloppe scellée virtuelle, c'est-à-dire qu'elle en révèle uniquement le haché (bien sûr, il faut qu'elle mette d'autres choses dans le haché, typiquement elle écrirait mon choix est : Alice suivi de donnés aléatoires et dénuées de sens, car si elle mettait le simple nom, Bob pourrait calculer le haché de chacun des noms possibles, il n'y en a que deux donc c'est facile, et savoir quel est le choix d'Alice). Bob note ce haché, et choisit (sans savoir ce qu'il contient) si le joueur dans l'enveloppe est le gagnant ou le perdant, et l'annonce à Alice, qui révèle alors le contenu de l'enveloppe (les données précises qui ont été hachées, et en particulier le nom qu'elle a choisi), que Bob peut vérifier. De cette façon, ni Alice (qui ne sait pas ce que Bob va décider, et qui ne peut pas changer d'avis une fois qu'elle a communiqué le haché) ni Bob (qui ne sait pas ce que le haché contient) ne peut tricher. Dès lors qu'au moins un des deux joueurs veut assurer que le jeu est aléatoire, il tire une pièce et, quoi que fasse l'autre joueur, il aura une chance sur deux de gagner et une chance sur deux de perdre : c'est donc un jeu parfaitement équitable, équivalent à pile-ou-face[#7].

Il y a beaucoup d'autres usages des fonctions de hachage, je ne peux pas tous les mentionner. En voici cependant une autre qui me fascine : imaginez que vous êtes l'administrateur d'un site de jeu en ligne, vous devez stocker des informations sur vos joueurs, disons, leur nom et le nombre de points qu'ils ont gagné à un jeu quelconque (les épreuves dont ils sont sortis victorieux, ou je ne sais quoi d'autre), mais vous ne voulez pas stocker ces informations de votre côté : parce que ces joueurs ne vous rapportent rien, c'est à eux de stocker ces informations à leur sujet (dans un cookie ou dans l'adresse qu'ils noteront, ou peu importe). Mais vous ne voulez pas qu'ils puissent tricher et augmenter leur score ! Comment vérifier qu'ils vous redonnent bien les informations que vous leur avez laissées ? Le plus simple est de leur donner, en plus des informations proprement dites, un haché de ces informations plus d'une partie secrète, commune à tout le monde, et que vous seul connaissez. Ce haché, donc, ne leur permettra pas de retrouver la partie secrète, ni de modifier les informations, mais vous pouvez, vous, vérifier l'intégrité des données qu'ils ont stockées. C'est là le principe de fonctionnement de ce mini-site que j'avais écrit il y a longtemps : la partie intéressante, donc, c'est que le serveur ne stocke aucune donnée sur qui répond à quoi, il n'y a pas de système de comptes ou de mots de passe, et pourtant, il n'est censément pas possible de tricher.

Voilà, je pense que ça résume assez bien pourquoi je trouve que les fonctions de hachage sont une des inventions les plus géniales qui soient, dans le sens « quelque chose d'extrêmement simple, mais qui a des applications incroyables ».

[#] La raison de cette inspiration, c'est que je viens de soumettre une implémentation — qui devrait à terme faire son chemin jusque tous les systèmes GNU/Linux parmi les utilitaires de base — des fonctions de hachage SHA224, SHA256, SHA384 et SHA512. À force de trouver que ça manquait vraiment (surtout maintenat que SHA-1 est (pour ainsi dire) cassé) je me suis décidé à coder la chose moi-même.

[#2] Les cryptographes appellent toujours Alice et Bob les deux parties impliquées dans un protocole cryptographique (il y a des prénoms pour la suite de l'alphabet, bien sûr, s'il y a plus de deux parties). Il faut croire qu'ils n'ont pas énormément d'imagination ! Petit, je me plaignais aussi que Molière donnait les mêmes noms à ses personnages dans toutes ses pièces.

[#3] Les maniaques feront observer que, non, elle prend une chaîne d'octets en entrée, ou même, d'ailleurs, une chaîne de bits, et qu'elle ne précise rien du tout sur l'encodage de caractères. Certes, mais il faut essayer d'être pédagogique, et ce n'est pas forcément le moment d'insister sur la différence entre octets et caractères : disons que les caractères sont encodés en UTF-8.

[#4] Voici un exemple idiot : les normaliens ont besoin, chaque année, de se tirer au hasard un classement de priorité pour la répartition des chambres d'internat (le thurnage) : effectuer un tirage au sort non manipulable, et vérifiable, devant des centaines de personnes et quand il s'agit de tirer des centaines de nom est malcommode. Mais les fonctions de hachage permettent de s'en sortir autrement : on demande à quelques mains innocentes (voire à tous ceux qui veulent venir s'assurer de la neutralité du tirage) de fournir chacun un mot (ce qu'on présente sous la forme d'un cadavre exquis), on les met bout à bout et, pour chaque nom possible d'une personne à classer, on met ce nom à la fin, on calcule le haché (selon une fonction de hachage précisée à l'avance), et on ordonne les gens dans l'ordre du haché. (Par exemple, si les mots du cadavre exquis étaient LA GIRAFE FLOUE REGARDE, une personne nommée Madore serait mieux placée que Dupond parce que le SHA224 de LA GIRAFE FLOUE REGARDE MADORE, qui commence par f45e est plus grand que celui de LA GIRAFE FLOUE REGARDE DUPOND, qui est en 9f72.) Comme le choix des mots est publié (et qu'on a une façon de normaliser les noms), chacun peut s'assurer qu'il a correctement été classé vis-à-vis de n'importe qui d'autre ; et comme un changement quelconque sur un mot modifie complètement le classement, on ne peut pas spéculer sur quel mot apporterait un meilleur classement ou un moins bon. (Bon, ce n'est pas exactement la méthode qu'on a adoptée, elle est un peu moins transparente, mais ça pourrait le devenir dès l'an prochain.)

[#5] Bien sûr, il y a des cas où c'est possible. Par exemple, si je vous dis que le haché en question est celui d'un simple mot français (écrit en majuscules), vous n'avez qu'à parcourir tout le dictionnaire pour retrouver de quel mot il s'agit, et ça prend un temps très faible pour un ordinateur. (Et il se trouvera bien quelqu'un pour me dire quel était mon mot secret, là.) Mais si le haché est celui d'une phrase complète, ou, pire, d'un document de taille conséquente, il n'y a évidemment aucune façon de retrouver le document. (En un sens c'est dommage, parce que ce serait une méthode de compression merveilleuse, si on pouvait !)

[#6] Mais avec le temps et l'amélioration d'une part des méthodes cryptanalytiques et d'autre part de la puissance des ordinateurs, il arrive qu'on y parvienne. Par exemple, la fonction de hachage MD5 (la plus connue), de longueur 128 bits, est maintenant « cassée » car on en connaît des collisions. Car autant fabriquer une fonction de hachage est facile sur le principe (on mélange les données « un peu n'importe comment » jusqu'à produire une sortie essentiellement aléatoire), autant en faire une qui soit efficace, équilibrée et difficile à cryptanalyser, cela est très délicat.

[#7] Il semble qu'on peut même, en théorie, grâce à la cryptographie, jouer aux cartes sur un simple canal de communication : j'avais lu l'algorithme, mais je ne me le rappelle plus précisément. Cependant, il est plus compliqué et n'utilise pas que des fonctions de hachage mais aussi de la cryptographie asymétrique.