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 renvoie 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 renvoie 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 a 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 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 sera pour une autre fois.

Une autre utilisation qui n’avait pas été prévue par les cryptographes est le stockage des mots de passe. 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.

13 commentaires sur « Il était une fois un gnome et les Fonctions de Hachage… »

  • Coquille :
    > C’est sûr que ça va arriver mais si il a une suffisamment de dés, une centaine par exemple

    Ne serait pas plutôt :
    > C’est sûr que ça va arriver mais si il a une suffisamment grande quantité de dés, une centaine par exemple

  • “Comme notre gnome à pleins de dés” ► “Comme notre gnome a pleins de dés” (verbe)
    “C’est sûr que ça va arriver mais si il a une suffisamment de dés, une centaine par exemple” ► “C’est sûr que ça va arriver mais si il a suffisamment de dés, une centaine par exemple” (il y a un “une” en trop je crois)

  • “Parce que les mots sont importants”, je rapelle que “retourner” est un anglicisme, on dit “renvoyer” en bon français…

    • Bonjour Aveheuzed,

      Réponse hyper tardive, mais corrigé.
      Effectivement, c’est un anglicisme certainement dû aux “return x;” dans pas mal de langage informatique.

  • “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.”
    C’est surtout : “nous serons bien embêté(e)s.”
    L’écriture dite inclusive n’est, à ce jour, pas reconnue. Par ailleurs le point indique la fin d’une phrase : c’est un élément structurant dans toute phrase. Cela vaut dans de nombreuses langues indo-européennes qui ne changeront pas cet usage parce que quelques Françaises et Français veulent faire parler d’eux.
    Enfin la langue française est déjà suffisamment complexe et, malheureusement aussi, très détériorée par les médias qui ne font aucun effort.
    Par ailleurs, je rappelle le message correctif (pas encore pris en compte) de Seb35, je cite :
    ce serra → ce sera

    Toutes mes excuses pour ce commentaire un peu long, mais il me semble très bien s’ajouter au slogan de ce site. Les mots, comme l’orthographe et la grammaire sont importants.
    Un grand merci pour votre site très intéressant et qui remet quelques pendules à l’heure.

    • Bonjour Gax3,

      Réponse hyper tardive, je suis désolé.

      – Pour l’écriture inclusive, je ne rentrerai pas dans le débat, je ne pense pas que ce soit le lieu. C’est un choix de rédaction de l’auteure que je soutiens.
      – La faute sur “serra” a enfin été corrigée.

      Merci de votre soutien 🙂

      Edit: Pseudo mal copié-collé lors de la première réponse :/

  • Je suis désolé, mais ça a beau être de la vulgarisation, cela ne doit pas induire en erreur. Or non seulement ton analogie du gnome qui jette ses dés AU HASARD s’oppose au prinicpe du hachage : de mêmes opérations qui donnent toujours le même résultat ; MAIS SURTOUT, tu contredis l’intérêt premier de cette méthode : en indiquant que le gnome “renvoie la clé si il a déjà vu le fichier”. OR, les mêmes calculs sont effectués, et surtout, ON NE STOCKE PAS LE FICHIER.

    • Cet article n’a pas vocation à expliquer en détail le fonctionnement (mathématique et algorithmique) d’une fonction de hachage, mais d’expliquer aux néophytes un comportement en utilisant une analogie. J’ai par ailleurs essayé de mettre en place des étiquettes sur les billets de ce blog pour catégoriser le niveau requis de lecture.
      Le billet commence par “Imaginez une grande boite noire […]”… On ne peut pas faire plus clair. Je ne pense pas que les lecteurs s’imaginaient communiquer avec des gnomes en utilisant des fonctions de hachage…

      Si vous souhaitez plus de détails mathématiques et/ou algorithmiques, je vous conseille le livre “Cryptographie : Théorie et pratique” de Douglas Stinton aux éditions Vuibert (ISBN : 2711748006).
      PS: je n’ai pas de part chez eux, mais j’ai apprécié ce livre. 🙂

Laisser un commentaire

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

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.