Les fonctions de hachage, c’est quoi ?

Point de calembour aujourd’hui, je suis pas inspiré. Juste, les fonctions de hachage, ça envoie du steak quand même, mais c’est surtout bien utile en cryptographie.

On continue donc sur notre lancée : hier vous avez pu voir un exemple d’algorithme de (dé)chiffrement (Merkle-Hellman), et aujourd’hui on continue notre série par un (dernier ?) article dans lequel je vais tenter de vous expliquer en quoi consistent les fonctions de hachage cryptographiques.

Forcément, on va encore devoir faire un peu de maths. Moins qu’hier, mais quand même. De toute façon, la cryptographie, ça repose quand même sur un bon socle mathématique, donc dur d’y couper. Attaquons doucement…

 

Principes, vocabulaire…

Si vous avez lu la série d’articles sur la sécurisation de ses communications électroniques, vous savez vaguement à quoi sert une fonction de hachage, mais comme c’est pas forcément le cas (et que c’est pas long), on va y revenir.

Donc, une fonction de hachage, c’est de façon très simplifiée une fonction mathématique qui, en fonction de ce qu’on lui donne à manger en entrée, va vous sortir une chaîne de longueur fixée à l’avance : c’est ce qu’on appelle l’empreinte (ou le condensé, ou encore la somme de contrôle), une suite de caractères assez courte (tout est relatif hein) représentant le texte qu’il condense. Ces empreintes sont beaucoup utilisées pour la signature électronique, et doivent être rapides à calculer afin de rendre rapide l’identification des données.

Vous comprenez du coup que pour que la sortie fasse 160 bits, avec une entrée de (par exemple) 512 bits, il faut que la fonction de hachage intègre une fonction de compression. Concrètement, le bloc que vous entrez est découpé en morceau de taille définie, et la fonction de compression est appliquée à chacun de ces blocs.

 

Les fonctions de hachage répondent malgré tout à un certain nombre de contraintes. On peut citer :

  • la résistance aux collisions : une collision, c’est le fait que deux textes différents donnent la même empreinte, et vous comprenez bien que c’est dans la liste des choses à éviter… 😉
  • la résistance à la préimage : calculer une empreinte via une fonction de hachage, ça doit être facile, on est d’accord. Par contre, partir de l’empreinte pour remonter au texte original, ça, c’est à éviter. On stocke parfois des empreintes de mots de passe plutôt que les mots de passe eux-mêmes, justement parce qu’en cas de piratage, il est compliqué de faire la manipulation inverse !
  • la résistance à la seconde préimage : connaissant une chaîne d’entrée et l’empreinte correspondante, il doit être compliqué de trouver une deuxième chaîne d’entrée qui donne la même empreinte (une sorte de « mix » entre les deux premiers critères, si on veut). Attention, si la résistance aux collisions implique nécessairement une résistance à la seconde préimage, cela ne touche pas à la « première » préimage.

 

Cryptanalyse des fonctions de hachage

La cryptanalyse, pour rappel, c’est le fait d’essayer de « casser » un algorithme de (dé)chiffrement ou une fonction de hachage. Dans le cas qui nous intéresse (les fonctions de hachage — suivez un peu :mrgreen: ), on considère que si on trouve une collision, alors la fonction est cryptanalysée.

Mathématiquement, une fonction de hachage admet une infinité de collisions. Pour autant, concrètement, il est quasi-impossible d’en trouver pour certaines d’entre elles.

 

« Une infinité de collisions ». Là vous avez peut-être tiqué. Ça fait beaucoup, hein, et vous pensez même que c’est un peu trop. C’est votre intuition qui biaise tout, en fait. Et pour vous expliquer ça, je vais prendre un paradoxe très proche de notre cas parce qu’il se base sur la recherche de collisions. Un modèle des plus connus et intéressants, dont vous avez probablement déjà entendu parler : le paradoxe des anniversaires, exprimé par Richard von Mises (que je connais bien de par mes études, pour ses lois utilisées en résistance des matériaux, mécanique des fluides, tout ça…).

On ne va pas refaire toute la partie sur les probabilités, c’est ni le but de cet article, ni le lieu pour ça. Je vais juste rappeler le paradoxe et les résultats. Prenez une classe de primaire, par exemple (ou votre service au travail, ou les gens dans un bar, bref, ce que vous voulez). Quelle est la probabilité pour que deux des personnes du groupe fêtent leur anniversaire le même jour (on ne tient pas compte de l’année, juste jour/mois) ?

Vous allez me dire, avec une classe de 25 bambins agités, en sachant qu’on a 365 jours dans l’année, y’a peu de chances. À l’intuition, vous allez l’estimer à moins de 50%, cette probabilité. Eh ben… c’est faux. Il se trouve qu’à partir de 23 personnes composant le groupe, la probabilité que deux membres fêtent leur anniversaire le même jour est de 50%. Et sachez aussi que pour un groupe de 58 personnes ou plus, la probabilité grimpe à 99% et plus ! C’est un paradoxe : ça va à l’encontre de l’intuition, et pourtant, c’est prouvé mathématiquement.

Tout ça pour vous dire : trouver des collisions, en théorie, ça se fait bien. D’où la nécessité d’utiliser des empreintes suffisamment longues (au moins 128 bits, voire même 160 bits : ça demanderait au moins 264 hachages pour trouver une collision, et ça commence à faire).

 

 

Plusieurs types de fonctions de hachage ?

Pourquoi faire simple quand on peut faire compliqué ? 😉

On distingue généralement 2 catégories de fonctions de hachage : avec, ou sans clé.

  • sans clé : ce sont les Modification Detection Code (MDC, code de détection de modifications), et elles sont utilisées pour s’assurer de l’intégrité d’un message. On calcule l’empreinte avant envoi (ce résultat est appelé « digest » ou « MDC-Value » ), puis après envoi, et si ça colle, le message n’a pas été modifié. Vous avez probablement croisé ce mécanisme en téléchargeant des fichiers sur le Web : de plus en plus souvent, on croise des fichiers associés à leur empreinte, vous permettant de vérifier que le fichier en question n’a pas été altéré au cours de son transfert. C’est essentiel si le fichier est important (une mise à jour d’Android par exemple, qui si elle était altérée pourrait empêcher votre smartphone de démarrer…) !
Un exemple : l'empreinte MD5 de l'original est donnée !
Un exemple : l’empreinte MD5 de l’original est donnée !
  • avec clé : ce sont les Message Authentication Code (MAC, code d’authentification des messages), qui ont donc une clé comme paramètre additionnel. La clé permet comme souvent de garantir la provenance du message, en plus de l’intégrité (but premier du hachage, ne l’oublions pas).

 

Des exemples !

SHA-1

Développé à partir de SHA-0 par la NSA (eh oui) en 1995, il est capable de traiter des messages de 264 bits maximum, en les découpant en blocs de 512 bits pour générer une empreinte de 160 bits. L’attaque des anniversaires donne une collision en 280 hachages, ce qui est suffisant. Manque de pot, en 2005, des chercheurs ont mis au point une méthode capable de trouver une collision à partir de 269 empreintes, améliorée ensuite pour ne nécessiter que 263 opérations. Il est encore largement utilisé.

 

MD5

Mis au point par Ronal Rivest en 1991, Message Digest 5 est une évolution de MD4 développée pour combler les failles de ce dernier. MD5 découpe les messages en blocs de 512 bits et calcule une empreinte de 128 bits. L’attaque générique des anniversaires donne une collision en 264 opérations, mais une faille « grave » (on pouvait créer des collisions à la demande 😀 ) a été découverte en 1996. MD5 a été « cassé » en 224 opérations et n’est plus considéré comme sûr, bien qu’utilisé pour vérifier l’intégrité de téléchargements. On notera l’existence de Rainbow Tables (tables arc-en-ciel), permettant de remonter d’une empreinte à la chaîne originale (dommage s’il s’agit d’un mot de passe) en quelques secondes. Une contre-mesure efficace est le salage (on y reviendra plus loin).

 

SHA-2 (SHA-256 / SHA-384 / SHA-512)

SHA-2 est, comme SHA-1, développé par la NSA, pour boucher les failles de la génération précédente de fonctions. Une particularité est que cette famille de fonctions de hachage va donner des empreintes de taille différentes, correspondant (le monde est bien fait) au suffixe de la fonction utilisée : SHA-256 va donner une somme de contrôle de 256 bits, SHA-512 fournira lui 512 bits, et ainsi de suite. 😉

SHA-256 découpe le message en blocs de 512 bits, et SHA-384 / SHA-512 en blocs de 1024 bits. Ces fonctions n’ont pas été cassées pour le moment, même si c’est théoriquement possible (force brute par l’attaque des anniversaires : il faut 2m/2 opérations, où m représente le suffixe de la fonction — pour SHA-256, il faut donc 2128 opérations, c’est conséquent 😉 ). Elles sont donc considérées comme sûres, pour le moment.

 

Saler avant de hacher ?!

Vous l’avez sûrement pressenti quand j’ai parlé des rainbow tables pour MD5 : plus ça va, et plus on trouve de tables de hachages qui répertorient les couples empreinte/chaîne d’origine. Or, il existe un moyen de se protéger de ce genre de méthodes : le salage.

Le concept est simple : vous définissez une chaîne de caractères, vous l’ajoutez au bout de la chaîne à hacher, et pouf l’empreinte change. Si le sel reste bien secret, ça devient compliqué de retrouver le mot de passe !

En gros, on choisit un sel : c10b6144 . Mettons que je veuille la somme MD5 correspondant à « Linux ». Sous Linux, j’ai juste à ouvrir mon terminal et à entrer echo -n Linux | md5sum . Je recommence en salant la chaîne « Linux », ce qui donne « Linuxc10b6144 ». Résultat :

  • Linux –> edc9f0a5a5d57797bf68e37364743831
  • Linuxc10b6144 –> 41b4e43196cc88dfd9aa06d762ba597e

Voilà, les chaînes n’ont rien à voir, mais les empreintes conservent la même longueur, comme je le précisais plus haut. Un petit tour sur MD5 Online pour voir, il retrouve bien Linux à partir du condensé, mais pour l’autre, il renonce. C’est pas forcément le meilleur des exemples, mais ça montre l’utilité de saler. Surtout, retenez que si une empreinte salée était « remontée », ça ne donne pas le mot de passe pour autant, du moins pas directement. Là on a juste concaténé le sel et la chaîne, mais libre à chacun de faire d’autres opérations avec son sel 😉

 

Notez aussi que dans certains cas… le sel change régulièrement, rendant la récupération des données originales encore plus difficiles. Ça a ses avantages et ses inconvénients, le principal étant que plus le schéma est complexe, plus ça demande de temps de calcul, et ça, ça coûte cher.

 

End of Transmission

Voilà voilà, on va s’arrêter là pour aujourd’hui. L’air de rien, cet article et le précédent représentent quelques heures de travail, et j’espère sincèrement qu’ils vous auront permis d’aborder sereinement ces notions parfois complexes. Maintenant, vous pouvez vous targuer de savoir (à peu près) comment fonctionne un cryptosystème « under the hood » ! Si vous fermez cet onglet avec une vague idée de comment les messages passent à la moulinette, avec quels mécanismes et quelles contraintes, c’est que j’ai atteint mon objectif.

N’hésitez pas à me soumettre vos questions et pistes d’amélioration, si quelque chose manque, n’est pas clair…

 

Évidemment (et là je m’adresse aux spécialistes), je ne peux pas être exhaustif, tant d’un point de vue technique (j’ai des connaissances incomplètes, j’essaie de partager ce que je sais, mais je ne peux pas tout vulgariser non plus, et je peux aussi me tromper 😉 ) que du point de vue des exemples (je cite certains algorithmes et fonctions, mais ce ne sont pas les seuls, tous les lister/décrire relèverait de la folie pure et ferait fuir le chaland). J’ai pour ces raisons passé sous silence les mécanismes interne de signature électronique, l’élaboration des fonctions de hachage, la vérification de signature… Je voulais initialement faire un exemple de signature/vérification avec RSA, ElGamal et/ou DSA, mais c’est vraiment pas simple à expliquer sans notions assez poussées de mathématiques, que je ne suis pas sûr que tout le monde possède.

Cependant, si vous y tenez vraiment, je peux tout à fait les expliquer 😉

4 réflexions sur “ Les fonctions de hachage, c’est quoi ? ”

  • 11 mars 2014 à 14 h 16 min
    Permalink

    Salut,

    bravo pour l’article, c’est très didactique. Effrayé un instant de tomber sur Von Mises qui m’avais torturé en meca flu 😉

    aller, je m’en vais chercher le rss !

    Réponse
    • 12 mars 2014 à 17 h 17 min
      Permalink

      Hey,

      merci du retour, ça fait toujours plaisir 🙂
      Je confirme, von Mises pique un peu (ok, beaucoup) parfois, mais là il n’y a pas besoin de se prendre la tête !

      Dans l’coup, tout t’a paru clair dans ce que j’ai essayé d’expliquer ?

      Réponse
  • 13 mars 2014 à 11 h 48 min
    Permalink

    Oui, c’était très clair. J’ai particulièrement apprécié l’explication sur le salage. L’information est bien sûr disponible sur le net, mais très souvent je recherche seulement à me faire une idée globale du fonctionnement, ce en quoi ton article tombait à pic (je lisais l’article sur K9 mail avant, qui semble très bien référencé). Peut-etre un prochain article sur les monnaies électroniques ?

    Réponse

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *