Fonctions de hachage

Des objets de toutes tailles tombent dans un entonnoir et en ressortent en bas sous forme de carreaux identiques et de même taille.

Comment un site web sait-il que ton mot de passe est correct, sans connaître ton mot de passe ? Comment ton téléphone remarque-t-il qu'un fichier téléchargé a été abîmé en route ? Les deux fois avec la même astuce : une empreinte digitale des données. Petite, toujours de la même taille, et unique pour ce qu'on y a mis.

Les mots dont tu as besoin

Hash (ou fonction de hachage): Une machine à calculer à qui tu donnes quelque chose — un mot, une photo, tout un livre — et qui en fait toujours une suite de caractères de la même longueur. La même entrée donne toujours la même sortie. Changer quelque chose, ne serait-ce qu'une seule lettre, donne une sortie complètement différente.
Bit: Le plus petit morceau d'information : un 0 ou un 1. Huit bits font un octet. Si quelque chose fait « 256 bits », ce sont 256 zéros et uns à la suite.
SHA-256: Le nom de la fonction de hachage la plus utilisée aujourd'hui. Le 256 est le nombre de bits dans la sortie : toujours exactement 256, que tu entres une seule lettre ou un film entier. En hexadécimal, cela fait 64 caractères.
Algorithme: Une recette fixe d'étapes de calcul. SHA-256, SHA-1 et MD5 sont trois recettes différentes avec le même but.
Hexadécimal: Tu le connais du chapitre 1 : écrire des octets avec les chiffres 0–9 et les lettres a–f, deux caractères par octet. Chaque caractère hexa vaut donc quatre bits. C'est ainsi qu'un hash est affiché ci-dessous — et il ne sert à rien d'autre.

Trois règles auxquelles un hash se tient

Règle	Ce que ça signifie
Sens unique	À partir du hash, tu ne peux pas recalculer l'entrée. Pas « difficile », pas « avec un ordinateur rapide, oui » — il n'existe aucun chemin retour. Comme tu ne récupères plus la vache à partir d'un steak haché.
Pas de collisions	Deux entrées différentes ne doivent pas obtenir le même hash. En théorie, c'est possible (il existe une infinité de textes et seulement 2²⁵⁶ hashes), mais personne ne réussit à en trouver.
Effet d'avalanche	Une lettre de différence, et environ la moitié de tous les bits de la sortie basculent. Il ne reste rien qui ressemble au hash précédent.

Essaie toi-même

Tout se passe dans ton navigateur. Rien n'est envoyé au serveur.

Clique sur Crée l'empreinte. Tu vois quatre hashes de la même phrase, avec quatre recettes différentes. Remarque la longueur de chacun.
Change une lettre dans la phrase et clique à nouveau. Compare. Reconnais-tu encore quelque chose ?
Clique sur Montrer l'effet d'avalanche : la démo change elle-même un caractère et compte combien de bits basculent.
Colle un texte très long — les paroles d'une chanson, une dissertation. Le hash garde la même longueur.

Texte

Ce que tu vois exactement là

Ces rangées de caractères ne sont pas du base64. Elles ne contiennent que 0–9 et a–f, et ça, c'est de l'hexadécimal : deux caractères par octet, quatre bits par caractère. Fais le calcul — 64 caractères × 4 = 256 bits, exactement ce qui est écrit derrière SHA-256. Pour SHA-1, tu comptes 40 caractères, donc 160 bits.

Pourquoi de l'hexadécimal ici et du base64 au chapitre 1 ? Parce qu'ici il s'agit de regarder. L'hexadécimal est plus long mais tu peux encore le suivre : chaque caractère vaut exactement quatre bits, et tu peux mettre deux hashs côte à côte et les comparer lettre par lettre. Le base64 est plus court et donc plus pratique à envoyer, mais la frontière entre deux octets y tombe au milieu d'un caractère. Les mêmes octets, une autre façon de les écrire — exactement le propos du chapitre précédent.

Pourquoi cette longueur compte

256 bits, ça veut dire 2²⁵⁶ résultats possibles. C'est un nombre à 78 chiffres. À titre de comparaison : le nombre d'atomes dans l'univers est un nombre à environ 80 chiffres. Chaque texte possible obtient une place dans un espace aussi grand que l'univers — la probabilité que deux textes différents atterrissent par hasard au même endroit est pratiquement nulle.

La leçon que tu ne peux pas voir

Regarde dans la démo la ligne avec SHA-1. Elle a l'air exactement aussi aléatoire que SHA-256, seulement plus courte : 160 bits au lieu de 256, donc 40 caractères hexa au lieu de 64. Pourtant, SHA-1 est cassé : en 2017, des chercheurs de Google et du CWI à Amsterdam ont montré deux fichiers PDF différents avec exactement le même hash SHA-1. La règle « pas de collisions » était brisée. MD5 avait disparu bien avant.

À la sortie, tu ne remarques rien de tout ça. Qu'une fonction de hachage soit bonne ou non ne dépend pas de son apparence aléatoire, mais du fait que des mathématiciens y aient trouvé un point faible ou non. C'est pourquoi tu utilises aujourd'hui SHA-256 et pas quelque chose qui « a l'air tout aussi bien ».

Peut-on « décrypter » un hash ? Non. Rien n'est chiffré, il n'y a rien à déchiffrer. Pourtant, il existe des sites qui prétendent pouvoir le faire — et parfois ils y arrivent vraiment. Comment c'est possible, et pourquoi c'est important pour tes mots de passe, c'est le chapitre suivant.

Voici les maths : le paradoxe des anniversaires

Lance un dé. Combien de fois dois-tu lancer pour obtenir un six ? Six fois en moyenne. Mais combien de fois dois-tu lancer pour voir n'importe quel nombre une deuxième fois ? Après quatre lancers, cette probabilité atteint déjà 72 %. C'est bien plus rapide — et c'est le même phénomène que dans une classe : avec 23 élèves, la probabilité que deux soient nés le même jour dépasse 50 %. Alors qu'il y a 365 jours.

L'astuce est dans ce que tu cherches. Tu ne cherches pas quelqu'un né le jour de ton anniversaire — pour ça il te faut plus de 250 personnes. Tu cherches n'importe quels deux. Avec 23 élèves tu peux former 253 duos différents, et chaque duo est une chance de doublon. Voilà pourquoi « doublon » arrive bien plus vite que ton intuition ne le dit.

Possibilités	Un doublon est probable après
6 (un dé)	4 lancers
365 (anniversaires)	23 élèves
1 000 000	environ 1 200 essais
2²⁵⁶ (SHA-256)	environ 2¹²⁸ essais

Tu vois le motif ? C'est à chaque fois environ la racine carrée du nombre de possibilités. Avec un million de possibilités tu as déjà un doublon après un bon millier d'essais — pas après un demi-million.

Et maintenant le hash. Un hash est l'« anniversaire » d'un texte : chaque texte en reçoit un, parmi 2²⁵⁶ possibles. Une collision — deux textes avec le même hash — c'est donc simplement deux élèves nés le même jour. Et le tableau dit combien de textes tu dois essayer pour que ça arrive probablement : pas 2²⁵⁶, mais 2¹²⁸. Un hash n'est qu'à moitié aussi solide que sa longueur le laisse croire.

C'est la raison pour laquelle 256 est la norme et non 128. Un hash de 128 bits donne une collision après 2⁶⁴ essais — et tous les ordinateurs qui font tourner Bitcoin aujourd'hui calculent ce nombre de hashs ensemble en moins d'une seconde. Avec 256 bits il en reste 128, et ça, personne ne l'atteint. Ceci est du calcul des probabilités : un petit calcul sur des dés détermine la longueur que doit avoir chaque hash au monde.