Outils de développement · Calculateur de hachage SHA
L'effet d'avalanche : pourquoi un personnage modifié réécrit un hachage SHA
· Comment ça marche
sha-256 cryptographie sécurité validation
Changez une lettre et environ la moitié des bits de sortie s'inversent. Cet article explique la propriété d'avalanche, pourquoi elle est essentielle pour la détection d'altération et comment les cartouches de SHA-2 y parviennent.
S'attendre à ce que le hachage change un peu : l'intuition que la plupart des gens apportent et pourquoi la conception le brise délibérément
La plupart des gens s'attendent à ce que des intrants similaires produisent des résultats similaires. Changez un caractère dans un fichier et le résumé devrait changer légèrement. Au lieu de cela, les hachages cryptographiques sont conçus pour faire le contraire : une modification d’un seul bit dans l’entrée devrait inverser environ la moitié des bits de sortie, de manière imprévisible. Cette propriété s’appelle l’effet d’avalanche et elle est délibérée. La conception répond à un objectif spécifique : la détection d’effraction.
L'effet d'avalanche est la raison pour laquelle « presque correspondant » n'est pas un concept dans le monde du hachage. Un hachage correspond exactement, ou non. Il n’y a pas de « assez proche ». Cette propriété rend le hachage utile pour les contrôles d’intégrité et l’adressage du contenu, et rend les algorithmes de hachage faibles inutilisables à des fins de sécurité.
Avalanche signifie une large diffusion de sortie ; cet article ne fait aucune affirmation de probabilité exacte sans source
Formellement, l'effet d'avalanche signifie que pour deux entrées qui diffèrent d'un seul bit, les résumés de sortie doivent différer d'environ 50% de leurs bits. Pour SHA-256 (256 bits de sortie), la modification d'un bit d'entrée devrait inverser environ 128 bits de sortie. L'effet n'est pas exact ; c'est une propriété statistique. Mais c’est fort : en pratique, chaque bit de l’entrée est soigneusement mélangé à chaque bit de la sortie.
Pourquoi environ la moitié ? Parce qu'une sortie véritablement aléatoire différerait d'une autre sortie aléatoire exactement par la moitié de ses bits en moyenne (par le principe du casier et les statistiques de base). Une bonne fonction de hachage se rapproche du caractère aléatoire ; il produit un résultat qui ne semble avoir aucun modèle perceptible. La moitié des bits retournés en moyenne est la marque du hasard. Si un hachage ne retournait que 10 % des bits, un attaquant pourrait trouver des modèles et les exploiter.
Pourquoi la détection de falsification en a besoin : de petites modifications apportées à un document ne doivent pas produire un hachage presque identique qu'un rapide coup d'œil accepterait
La détection de sabotage repose sur une avalanche. Si vous téléchargez un fichier et calculez son SHA-256, le résumé attendu est ba7816... (à titre d'exemple). Un attaquant modifie le fichier en changeant un octet. Le nouveau résumé passe de ba7816... à quelque chose comme 3d4e92... (complètement différent). Lorsque vous vérifiez le fichier par rapport au résumé attendu, la discordance est immédiate et totale. Il n’y a pas de place pour une mauvaise interprétation : le fichier a été falsifié.
Sans avalanche, un attaquant pourrait modifier un octet et le résumé pourrait ne se déplacer que légèrement, vers ba7817... (un chiffre hexadécimal différent). Une comparaison informelle pourrait ne pas faire la différence. Un attaquant pourrait même rechercher des entrées produisant un résumé commençant par ba78, affirmant que le fichier est authentique. Avalanche rend cela d'un coût prohibitif : trouver ne serait-ce que deux entrées dont les résumés commencent par les mêmes quatre chiffres hexadécimaux nécessite plus de travail que ce que la conception permet.
Comment les tours propagent le changement - rotations, ajouts et fonctions non linéaires exerçant l'influence d'un bit sur tout l'état
Les tours dans SHA-256 (et les tours dans SHA-512) sont conçus pour diffuser les changements. Chaque tour mélange les données à l'aide de fonctions non linéaires (choisir, majorité) et de rotations. Une modification d'un seul bit dans l'entrée entre dans le calendrier des messages et se propage à travers les tours. Les rotations déplacent les positions des bits. Les fonctions non linéaires masquent l'influence du bit : la modification d'un bit de contrôle lors d'une opération de sélection peut inverser n'importe lequel des bits de sortie, en fonction des données sélectionnées.
Les constantes de hachage initiales, les constantes de planification des messages, les montants de rotation et le nombre de tours ont tous été choisis pour maximiser l'effet d'avalanche. Ces chiffres ne sont pas arbitraires ; ils proviennent de la spécification SHA-2 et ont été largement cryptanalysés. Toute modification des constantes ou du nombre de tours produirait un algorithme différent (probablement plus faible).
Exemple pratique : hacher deux entrées qui diffèrent d'un caractère et comparer les résumés petit à petit
Tester les avalanches est simple. Hachez l'entrée abc et notez le résumé. Hachez ensuite abc suivi d'un espace, ou remplacez un caractère par autre chose : abd. Comparez les sorties hexadécimales. Pour SHA-256, environ la moitié des chiffres hexadécimaux 64 seront différents. Comptez-les. Le vecteur de test de la publication ToolAcre : abc produit ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. Une chaîne vide produit e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. Ces résumés n’ont aucun chiffre hexadécimal en commun.
Essayez ceci sur la calculatrice ToolAcre avec n'importe quelle entrée. Hachez une phrase. Changez ensuite une lettre et hachez à nouveau. Comptez les différents chiffres hexadécimaux. Vous constaterez qu'environ la moitié (32 sur 64, dans la plupart des cas) diffèrent. C'est l'effet d'avalanche en action. C’est une propriété de la conception de l’algorithme et non une coïncidence.
Avalanche ne fournit pas de recherche de similarité ni ne quantifie à lui seul la résistance aux collisions
Avalanche ne crée pas de recherche de similarité ni de correspondance approximative. Si vous avez un résumé ba7816... et que vous souhaitez trouver un résumé similaire, vous n'avez pas de raccourci. Vous devez deviner ou forcer les entrées des candidats, hacher chacune d'elles et vérifier une correspondance exacte. L'effet d'avalanche rend chaque supposition également susceptible de produire un résultat similaire ou complètement différent. Certains algorithmes de hachage (appelés hachage sensible à la localité) sont conçus pour préserver la similarité ; ils sont utiles pour la détection et le regroupement de quasi-doublons, mais ce ne sont pas des hachages cryptographiques.
Avalanche ne protège pas non plus contre une recherche de collision déterminée. Un cryptanalyste peut toujours rechercher deux entrées différentes qui produisent le même résumé, mais l’espace de recherche est énorme. La recherche déterminée de collisions est une question différente de la diffusion visuelle. Cet article ne cite pas de chiffre lié à l’anniversaire ni de chronologie matérielle car il n’en a pas dérivé ici. La limite défendable est que les avalanches à elles seules ne prouvent ni ne quantifient la résistance aux collisions.
À retenir : pas de quasi-accidents - essayez l'expérience sur un caractère dans le calculateur de hachage ToolAcre SHA et observez l'ensemble du changement du résumé
Le calculateur de hachage ToolAcre SHA exécute les algorithmes SHA via l'implémentation Web Crypto du navigateur. Vous pouvez l'utiliser pour vérifier les avalanches par vous-même. Chaque élément de précision de l'algorithme est intégré au résultat, et l'implémentation de Web Crypto est auditée et maintenue par le fournisseur du navigateur. Vous voyez le véritable algorithme exécuté sur des entrées réelles. La propriété contre-intuitive selon laquelle un changement de caractère réécrit l’intégralité du résumé n’est pas un défaut ; c'est la fonctionnalité qui fait fonctionner le hachage.
Lorsque vous utilisez un hachage pour vérifier l'intégrité, vous comptez sur une avalanche. Lorsque vous l'utilisez pour l'adressage de contenu (comme les résumés d'images de conteneurs), vous dépendez de la propriété selon laquelle de minuscules changements produisent des résumés très différents. Lorsque vous l'utilisez dans une signature numérique (où la signature est calculée sur un hachage du message), l'effet d'avalanche garantit que la falsification du message produit un changement détectable. La propriété est le fondement de la sécurité basée sur le hachage.