Les fonctions de hachage expliquées
Quand vous téléchargez un logiciel et vérifiez sa somme de contrôle, vous vous connectez avec un mot de passe, signez un document ou ajoutez un bloc à Bitcoin, une fonction de hachage est à l'œuvre. Elle transforme n'importe quelle quantité de données en une courte empreinte de taille fixe, le condensat, d'une manière impossible à défaire ou à falsifier. L'idée est simple, mais les exigences envers une bonne fonction de hachage sont strictes, et deux des plus utilisées, MD5 et SHA-1, n'y ont pas résisté.
Une empreinte pour les données
Une fonction de hachage prend une entrée de n'importe quelle longueur et renvoie un condensat de longueur fixe : 256 bits pour SHA-256, écrits sous forme de 64 chiffres hexadécimaux. La même entrée donne toujours le même condensat, si bien que le condensat peut représenter les données. Si deux fichiers ont le même condensat SHA-256, vous pouvez être sûr qu'ils sont identiques, et si un bit d'un téléchargement a été endommagé, son condensat ne correspond plus à celui indiqué par l'éditeur. Comme il existe bien plus d'entrées possibles que de condensats, de nombreuses entrées partagent forcément chaque condensat ; une bonne fonction de hachage rend simplement impossible d'en trouver une seule.
Trois promesses
Un hachage cryptographique fait trois promesses. Résistance à la préimage : étant donné un condensat, on ne peut pas trouver d'entrée qui le produise. Résistance à la seconde préimage : étant donné une entrée, on ne peut pas trouver une autre entrée ayant le même condensat. Résistance aux collisions : on ne peut pas trouver deux entrées quelconques ayant le même condensat. Pour une fonction de hachage idéale de n bits, les meilleures attaques consistent à deviner : environ 2ⁿ essais pour une préimage et environ 2ⁿᐟ² pour une collision. On dit qu'une fonction de hachage est cassée lorsque quelqu'un trouve une méthode beaucoup plus rapide que cela.
L'effet avalanche
Changez un bit de l'entrée et chaque bit du condensat devrait s'inverser avec une chance sur deux, indépendamment des autres. Une petite modification du message donne alors un condensat qui semble totalement sans rapport, et le condensat ne trahit rien de la partie de l'entrée qui a changé. SHA-256 y parvient en exécutant 64 tours qui font tourner, additionnent et combinent ses huit mots de 32 bits, de sorte qu'en quelques tours chaque bit d'entrée a influencé chaque mot. Une simple somme des octets, en revanche, change exactement de la quantité dont l'entrée a changé : elle dévoile donc tout.
Au cœur de SHA-256
SHA-256 commence par compléter le message : il ajoute un bit 1, des zéros et la longueur du message, jusqu'à ce que le total soit un multiple de 512 bits. Il traite ensuite le message par tranches de 512 bits. Chaque bloc est étendu en 64 mots, qui sont mélangés dans un état de huit mots de 32 bits, en partant de valeurs fixes tirées des racines carrées des huit premiers nombres premiers. L'état obtenu après le dernier bloc est le condensat. Cette construction en chaîne, qui porte le nom de Ralph Merkle et d'Ivan Damgård, est partagée par MD5, SHA-1 et SHA-512 ; le plus récent SHA-3, normalisé en 2015, utilise une construction différente appelée éponge.
L'attaque des anniversaires
Dans un groupe de 23 personnes, la probabilité que deux d'entre elles aient le même anniversaire dépasse tout juste une chance sur deux, alors que l'année compte 365 jours, car ce qui compte est le nombre de paires, qui croît comme le carré de la taille du groupe. Les collisions d'une fonction de hachage suivent la même règle. Parmi 2ᵏ condensats possibles, on s'attend à une collision après environ √(π/2 · 2ᵏ) entrées aléatoires. Pour 32 bits, cela fait environ 82 000 entrées, trouvées en un instant ; pour 128 bits, c'est environ 2⁶⁴, ce qui est à la portée de gros efforts de calcul. C'est pourquoi les 128 bits de MD5 n'ont jamais été généreux, et pourquoi SHA-256 double la longueur pour offrir une sécurité de 128 bits.
MD5 et SHA-1 : cassés
Ron Rivest a conçu MD5 en 1991, et la NSA a conçu SHA-1, publié en 1995. En 2004, Xiaoyun Wang et ses collègues ont montré comment produire rapidement des collisions MD5, et en 2008 des chercheurs s'en sont servis pour forger un certificat auquel les navigateurs web faisaient confiance. Le logiciel d'espionnage Flame, en 2012, a utilisé une collision MD5 pour se faire passer pour une mise à jour Microsoft. SHA-1 est tombé en 2017, lorsque Google et le CWI Amsterdam ont publié deux fichiers PDF différents ayant le même condensat SHA-1, au prix d'environ 2⁶³ calculs. Les deux conviennent encore pour repérer des erreurs accidentelles, mais pas pour quoi que ce soit qu'un attaquant pourrait viser.
Où l'on utilise les fonctions de hachage
Les signatures numériques signent le condensat d'un document plutôt que le document lui-même. Git nomme chaque fichier et chaque commit par son condensat, et les mineurs de Bitcoin cherchent des en-têtes de bloc dont le double hachage SHA-256 commence par une longue suite de zéros. Les sites web ne devraient jamais stocker les mots de passe, seulement leur condensat ; mais comme les gens choisissent des mots de passe courts, ce hachage doit être lent et salé, avec des méthodes comme bcrypt, scrypt ou Argon2, afin que deviner devienne coûteux. Les sommes de contrôle comme CRC-32, utilisées dans les fichiers ZIP, les images PNG et Ethernet, sont aussi des fonctions de hachage, conçues pour détecter le bruit plutôt que les attaquants.
À vous de jouer
Ouvrez le bac à sable des fonctions de hachage pour hacher votre propre texte avec SHA-256, SHA-512, SHA-1, MD5, CRC-32 et une somme miniature des octets. Appuyez sur Changer un caractère et comptez les bits inversés, utilisez Lancer le test pour soumettre mille modifications d'un bit au test d'avalanche et voir la courbe en cloche autour de la moitié du condensat, et Trouver une collision pour obtenir de vraies collisions sur les 8 à 32 premiers bits d'un condensat et voir l'attaque des anniversaires à l'œuvre.
Questions fréquemment posées
Hacher, est-ce la même chose que chiffrer ?
Non. Le chiffrement est fait pour être défait par quiconque détient la clé ; le hachage n'a pas de clé et ne peut être défait par personne. Le chiffrement garde un message secret, tandis qu'un hachage ne donne qu'une empreinte qui permet de vérifier un message que vous avez déjà.
Combien de temps faudrait-il pour trouver une collision SHA-256 ?
Avec l'attaque des anniversaires, environ 2¹²⁸ hachages, un nombre de 39 chiffres. Même si tous les ordinateurs de la Terre ne faisaient rien d'autre, il faudrait infiniment plus longtemps que l'âge de l'univers. Aucun raccourci n'est connu.
Pourquoi deux hachages du même texte ne diffèrent-ils jamais ?
Une fonction de hachage est déterministe : elle n'a ni hasard ni clé, donc les mêmes octets donnent toujours le même condensat. De petites différences invisibles, comme un espace final, une fin de ligne différente ou une autre forme Unicode d'une lettre accentuée, donnent en revanche un condensat différent.
Qu'est-ce qu'un sel ?
Une valeur aléatoire stockée à côté du condensat d'un mot de passe et mélangée à celui-ci. Deux utilisateurs ayant le même mot de passe obtiennent alors des condensats différents, et un attaquant ne peut pas utiliser une seule table précalculée de mots de passe courants pour tous les comptes.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir le bac à sable des fonctions de hachage