Outils de développement · Calculateur de hachage SHA
Merkle-Damgård expliqué : la construction derrière SHA-1 et SHA-2
· Contexte
sha-256 cryptographie API du navigateur
Une fonction de compression de taille fixe ne peut pas hacher seule une entrée arbitraire. Merkle – Damgård l'enchaîne bloc par bloc ; cet article explique la construction, son idée de preuve et les faiblesses qu'elle comporte.
Entrée arbitraire, sortie fixe : le problème que chaque fonction de hachage doit résoudre en premier
Une fonction de hachage doit mapper une entrée arbitraire à une sortie fixe. Un message de trois octets et un message de trois mégaoctets doivent tous deux produire exactement 256 bits de sortie pour SHA-256. Le hachage doit être déterministe, donc la même entrée produit toujours la même sortie. La sortie doit paraître aléatoire ; changer un seul bit de l’entrée devrait changer environ la moitié des bits de sortie.
Ce sont des exigences contradictoires à première vue, car un seul algorithme rapide ne peut pas gérer des messages de longueur arbitraire et produire une sortie uniforme de largeur fixe. La construction Merkle – Damgård résout ce problème en utilisant une fonction de compression de taille fixe à plusieurs reprises, envoyant la sortie de chaque application dans l'entrée de la suivante. Cette construction est utilisée par SHA-1 et l'ensemble de SHA-2 (SHA-256, SHA-384 et SHA-512).
La fonction de compression — un mélangeur de taille fixe qui prend un état et un bloc et renvoie un nouvel état
Une fonction de compression est la primitive cryptographique de base qui alimente un hachage Merkle-Damgård. Il prend un état de taille fixe, généralement 256 bits pour SHA-256 ou 512 bits pour SHA-512, et un bloc d'entrée de taille fixe, généralement 512 bits pour SHA-256 ou 1024 bits pour SHA-512. La fonction de compression les mélange à l'aide d'opérations au niveau du bit, de rotations et de recherches de table, produisant un nouvel état de même taille. Cette fonction doit être résistante aux collisions : trouver deux paires différentes (état, bloc) qui produisent la même sortie doit être difficile.
La fonction de compression elle-même n'est pas une fonction de hachage complète : elle ne gère pas la longueur d'entrée arbitraire, et elle ne gère même pas la première entrée, qui n'a pas d'état précédent. Au lieu de cela, il s’agit de l’élément de base autour duquel une construction plus vaste est construite. La fonction de compression est la seule opération cryptographique qui s'exécute de manière répétée ; tout le reste est une comptabilité qui relie cette fonction à un hachage complet.
Chaînage et vecteur d'initialisation - comment les blocs s'alimentent les uns dans les autres à partir d'un état de départ fixe
Le vecteur d'initialisation est l'état de départ fixe, choisi avec soin pour éviter les symétries ou les faiblesses. Pour SHA-256, le IV est constitué de huit mots de 32 bits dérivés des parties fractionnaires des racines carrées des huit premiers nombres premiers. Ces valeurs sont arbitraires mais déterministes, donc chaque implémentation produit le même résultat. Le premier bloc de message est mélangé au IV à l'aide de la fonction de compression, produisant un nouvel état. Le deuxième bloc de message est mélangé à cet état, produisant un autre nouvel état, et ainsi de suite dans chaque bloc du message.
Ce chaînage est la partie cruciale : la sortie d'un bloc dépend de tous les blocs précédents, donc changer n'importe quel bit d'un bloc précédent modifie tous les blocs suivants. Au moment où le bloc final est traité, l'état contient des informations sur chaque bit de l'entrée. Le rembourrage est l’astuce qui rend cette construction solide. Un message n’est pas toujours divisé uniformément en blocs. La construction Merkle – Damgård utilise le renforcement MD : ajoutez un seul bit au message, puis ajoutez des zéros jusqu'à ce qu'il reste presque un bloc complet, puis ajoutez la longueur du message d'origine.
Remplissage avec la longueur du message - pourquoi le renforcement MD est ce qui rend la construction solide
L'argument de sécurité de Merkle-Damgård dit que si la fonction de compression est résistante aux collisions, alors l'ensemble du hachage est résistant aux collisions. La preuve est une réduction : si vous pouviez trouver une collision dans le hachage, vous pourriez extraire une collision dans la fonction de compression, ce qui contredit l'hypothèse selon laquelle la fonction de compression est difficile à entrer en collision. L’intuition est que toute collision dans le hachage doit finalement produire une collision dans l’un des appels de fonction de compression, car l’état est complètement reporté.
Des faiblesses à Merkle–Damgård ont été découvertes au fil du temps, même si la construction de base est solide. L'extension de longueur en est un : un attaquant qui voit le résumé d'un message peut étendre le message et calculer un résumé valide pour le message plus long sans rien connaître de l'entrée. Les attaques de seconde pré-image en sont une autre : étant donné un message, trouver un message différent avec le même hachage est plus facile qu'il ne devrait l'être pour certains types de messages. Ces faiblesses ont motivé la conception de SHA-3, qui utilise une approche différente appelée construction en éponge.
Le remplissage de codage de longueur sépare les messages complétés ; une preuve de sécurité complète est une preuve extérieure au référentiel
La fonction de compression pour SHA-256 prend un état 256 bits (huit mots 32 bits) et un bloc 512 bits. L'opération utilise 64 tours, chacun mélangeant l'état avec une constante et un mot du bloc. Le mixage utilise des opérations au niveau du bit : XOR, AND, NOT. Il utilise des rotations et des décalages qui déplacent les bits sans changer les bits définis. Il utilise des recherches de table qui fournissent un mélange non linéaire que XOR seul ne peut pas réaliser.
SHA-512 utilise la même construction que SHA-256 mais avec des opérations 64 bits au lieu d'opérations 32 bits. L'état est de 512 bits (huit mots de 64 bits) et la taille du bloc est de 1024 bits. La fonction de compression comporte 80 tours au lieu de 64, et les constantes et les recherches dans les tables sont différentes. Pour SHA-384, l'état et la fonction de compression sont les mêmes que pour SHA-512, mais seuls les premiers 384 bits de l'état final sont émis. Les derniers 128 bits sont ignorés. Cette troncature est la raison pour laquelle SHA-384 résiste à l'extension de longueur.
L'extension de longueur est la limite de construction vérifiée ; les allégations de multicollision et de motivation SHA-3 sont omises
La sécurité d'un hachage Merkle – Damgård dépend de plusieurs propriétés détenues. La fonction de compression doit être résistante aux collisions, il est donc impossible de l’attaquer directement. Le schéma de remplissage doit garantir que différents messages produisent différentes formes remplies, de sorte que chaque collision dans le hachage doit impliquer une collision de fonction de compression. La taille du bloc et la taille de l’état doivent être suffisamment grandes pour que la force brute soit impossible. Un État plus large élargit l'espace de recherche générique, mais cet article ne joint pas de nombre d'opérations ou de date de faisabilité sans une dérivation en ligne et une source examinée.
Si un attaquant découvre une faiblesse dans la fonction de compression, ou si les ordinateurs quantiques deviennent pratiques et peuvent rechercher un espace non structuré en un temps sqrt(2^n) au lieu de 2^n, alors les marges de sécurité s'érodent. La faiblesse qui a motivé SHA-3 n'était pas une rupture de la fonction de compression, mais le problème d'extension de longueur et d'autres vulnérabilités structurelles. Une construction en éponge évite ces problèmes en ne publiant jamais son état interne complet.
Ce que cela ne couvre pas : les fonctions rondes spécifiques de SHA-256, couvertes dans un article séparé
La façon dont la construction Merkle – Damgård gère chaque taille d'entrée est la conséquence pratique de sa conception. Divisez le message en blocs de 512 bits, complétez le dernier bloc, traitez chaque bloc via la fonction de compression en séquence et affichez l'état final. Pour une entrée d'un octet, le remplissage produit un bloc 512 bits (un octet de message, un bit de remplissage, 447 bits de zéros et 64 bits pour la longueur). Le nombre de compressions est le nombre de blocs 512 bits, qui est proportionnel à la longueur du message.
Chaque résumé produit par le calculateur de hachage ToolAcre SHA provient de cette construction. Le résumé 64-caractère SHA-256 est l'état final 256 bits imprimé en hexadécimal. Le résumé 128-caractère SHA-512 est l'état final 512 bits imprimé en hexadécimal. Le résumé 96-caractère SHA-384 est le premier 384 bits de l'état final 512-bit. Le remplissage en coulisse garantit que chaque message possible produit exactement le bon nombre de blocs et la bonne largeur de résumé. Il s'agit de la construction Merkle – Damgård standard exécutée dans le navigateur.
À retenir : le même squelette derrière quatre algorithmes – chaque résumé produit par le calculateur de hachage ToolAcre SHA provient de cette construction
Comprendre la construction est utile pour savoir pourquoi les résumés ont toujours la même largeur et pourquoi la modification d'un bit de l'entrée modifie l'ensemble du résumé. La propriété de chaînage signifie que chaque bit de l’entrée affecte chaque bit de la sortie via une série d’opérations de mixage. Une modification d'un bit au début du message se propagera à toutes les compressions ultérieures, de sorte que le résumé final est complètement différent. Cette propriété est appelée effet d’avalanche et est la signature d’une fonction de hachage sonore.
La construction Merkle – Damgård est utilisée depuis des décennies et constitue la base des fonctions de hachage les plus largement déployées. SHA-1 et SHA-2 sont construits sur cette construction, et de nombreux systèmes déployés s'appuient sur leurs sorties. La construction est établie plutôt qu’expérimentale, mais cette histoire ne rend pas chaque utilisation sûre ; l’extension de longueur est une limite documentée. Comprendre cette construction aide les développeurs à comprendre pourquoi certaines propriétés de sécurité sont valables et pourquoi certains vecteurs d'attaque existent.