Il était une fois un gnome et les Fonctions de Hachage…

Pour avoir une bonne idée de ce qu’est une fonction de hachage il suffit d’imagination.

  • Imaginez une grande boite noire, c’est notre fonction de hachage. Dans cette boite habite un gnome avec un grand livre, un énorme dictionnaire, et de nombreux dés.
  • N’importe qui peut mettre des messages dans la boîte, ça peut être des images, des films, des logiciels, des textes, n’importe quoi.
  • Pour chaque nouveau message que le gnome n’a jamais vu, il lance tous ses dés est génère une nouvelle série de chiffres. Il écrit dans son dictionnaire que pour l’entrée (le « mot » d’un dictionnaire classique) correspondant au message, on a le haché (la « définition ») correspondant à la série de chiffres qu’il a obtenue. Finalement il retourne cette série à la personne qui a fournie le fichier.
  • S’il a déjà vu ce fichier, à l’entrée correspondant au message dans son dictionnaire, il aura déjà une empreinte d’inscrite. Il la retourne donc simplement.

Une fonction de hachage cryptographique a trois propriétés :

  1.   Il doit être très difficile de recalculer le contenu d’un message qu’on a jamais vu à partir de son empreinte, c’est ce qu’on appelle « la résistance à la pré-image ».
    Dans notre histoire de gnome, notre boite noire est bien résistante à la pré-image parce que comme le gnome lance les dés au hasard, le seul moyen de retrouver le message correspondant à l’empreinte est de le retrouver dans le dictionnaire. Mais lorsqu’on cherche dans un dictionnaire, on ne cherche que dans un sens : du mot vers sa définition. Dans l’autre sens, il faut avoir de la chance (on tombe directement à la bonne page) ou lire pleins de définitions avant de tomber sur la bonne. C’est bien difficile.
  2. À partir d’un message donné, de son empreinte et de comment fonctionne la boîte noire (son algorithme, son code source), il doit être très difficile de générer un nouveau message qui donne la même empreinte, c’est ce qu’on appelle «la résistance à la seconde préimage ».
    Pour notre boîte à gnome, connaître l’algorithme c’est connaître l’existence du gnome, des dés et du dictionnaire, et savoir comment le gnome fait pour tirer ses empreintes aux dés. Si on a un message et une empreinte, pour que notre gnome retire aux dés la même empreinte pour le nouveau message qu’on lui donne, il va falloir soit truquer ses dés soit le corrompre. S’il est difficile voir impossible de faire l’un et l’autre, notre fonction de hachage « boîte à gnome » est bien résistante à la seconde pré-image.
  3. Enfin, il doit être très difficile de trouver deux messages qui donnent la même empreinte, c’est ce qu’on appelle «la résistance aux collisions ».
    Pour nous, ça voudrait dire que quelque soit la façon, on arrive à trouver deux messages qui ont la même définition, la même empreinte. Comme notre gnome à pleins de dés, il faut qu’il tombe exactement sur le même jet deux fois. C’est sûr que ça va arriver mais si il a une suffisamment de dés, une centaine par exemple, c’est un peu comme jouer à l’euromillion : on peut gagner mais c’est très rare, très difficile. Notre boite à gnome est donc bien résistante aux collisions.

Une fonction de hachage qui a ces trois propriétés est ce qu’on appelle une « fonction de hachage cryptographiquement sûre ». Aujourd’hui, dans le monde, tout le monde utilise les mêmes fonctions publiquement accessibles : SHA 256 ou SHA3.[1]

Comme tout le monde utilise les même fonction, tout le monde aura la même empreinte pour le même fichier. C’est comme si tout le monde utilisait la même boîte noire avec le même gnome et surtout le même dictionnaire.

Mais à quoi ça sert exactement ?

L’utilité première de ces fonctions est d’assurer l’intégrité d’un fichier en permettant de vérifier qu’il n’a pas été modifié depuis le calcul de l’empreinte. Par exemple, si j’ai pleins de fichiers sur mon ordinateur, je peux calculer une empreinte pour détecter si ils ont été modifiés (l’empreinte ne correspond plus) ou non (l’empreinte correspond toujours).

Quand on télécharge un fichier sur un site internet, on nous donne parfois son empreinte. Comme les fonctions de hachage sont publiques, on peut recalculer l’empreinte du fichier et vérifier que c’est bien le même.
Comme il est difficile de faire des collisions, on peut être assuré que si l’empreinte est bonne on a bien le fichier qui y correspond. Ceci a pour limite la confiance qu’on a dans l’empreinte affichée sur le site. Si une personne malveillante a remplacé le fichier par un virus en prenant soin de recalculer l’empreinte et de la modifier sur le site, nous seront bien embêté.e.s. Pour surmonter ce problème, les cryptographes ont inventé les signatures numériques mais ce serra pour une autre fois.

Une autre utilisation qui n’avait pas été prévue par les cryptographes est le stockage des mots de passes. C’est pourtant aujourd’hui une des principales utilisations par les informaticiens de ces fonctions (en trichant un peu). Mais c’est l’histoire suivante. Donc à la prochaine avec les fonctions de hachage à clé ou sel. 🙂

Cryptie

[1] Vous verrez aussi MD5 et SHA1 mais on a découvert qu’elles n’étaient pas sûres (elles ne sont pas résistantes aux collisions par exemple), donc il faut éviter de les utiliser.

5 thoughts on “Il était une fois un gnome et les Fonctions de Hachage…

Laisser un commentaire

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