Fonctions de hachage cryptographiques

Une fonction de hachage cryptographique compresse une entrée de longueur arbitraire en un condensat court de longueur fixe, de manière unidirectionnelle et résistante aux collisions, servant ainsi de bloc de construction fondamental pour l'intégrité, l'authentification et de nombreux protocoles de niveau supérieur.

Definition

Une fonction de hachage cryptographique est une fonction déterministe qui mappe des entrées de longueur arbitraire vers une sortie de longueur fixe (condensat) de telle sorte qu'il est infaisable de trouver une préimage, une seconde préimage, ou deux entrées distinctes produisant la même sortie.

Scope

Ce sujet aborde les propriétés de sécurité des fonctions de hachage (résistance à la préimage, à la seconde préimage et aux collisions), leurs constructions internes (Merkle-Damgaard, éponge), les familles standardisées SHA-2 et SHA-3, et des applications telles que la vérification d'intégrité, le stockage de mots de passe, l'engagement (commitment) et la preuve de travail (proof-of-work). Il traite des attaques cryptanalytiques, y compris la borne d'anniversaire et les cassures de MD5 et SHA-1. Il exclut les codes d'authentification à clé, qui sont traités sous les codes d'authentification de message, bien que de nombreux MAC soient construits à partir de fonctions de hachage.

Core questions

• Qu'est-ce qui distingue une fonction de hachage cryptographique d'une somme de contrôle ordinaire ou d'une fonction de table de hachage ?
• Pourquoi la résistance à la préimage, à la seconde préimage et aux collisions sont-elles distinctes, et comment sont-elles liées ?
• Pourquoi le paradoxe des anniversaires borne-t-il la résistance aux collisions à la moitié de la longueur du condensat ?
• Comment les constructions Merkle-Damgaard et éponge étendent-elles une compression de taille fixe à une entrée arbitraire ?
• Comment les fonctions de hachage sont-elles utilisées pour s'engager sur des données (commit to data), vérifier l'intégrité et stocker des mots de passe ?

Key concepts

• condensat de message
• résistance à la préimage
• résistance à la seconde préimage
• résistance aux collisions
• attaque des anniversaires
• construction Merkle-Damgaard
• construction éponge (Keccak)
• attaque par extension de longueur
• preuve de travail

Key theories

Résistance aux collisions et borne d'anniversaire

En raison du paradoxe des anniversaires, une attaque générique de recherche de collision sur un hachage de n bits réussit avec environ 2^(n/2) opérations ; la résistance aux collisions nécessite donc des condensats d'environ deux fois le niveau de sécurité souhaité (par exemple, 256 bits pour une sécurité de 128 bits).

Constructions itérées et éponge

Le paradigme Merkle-Damgaard construit un hachage complet en itérant une fonction de compression à entrée fixe sur des blocs de message ; la construction éponge utilisée par SHA-3 (Keccak) absorbe l'entrée et extrait la sortie d'un grand état de permutation, évitant ainsi les faiblesses d'extension de longueur.

Mechanisms

Un hachage Merkle-Damgaard complète le message (padding), le divise en blocs et applique itérativement une fonction de compression qui mélange chaque bloc dans une valeur de chaînage courante, produisant la valeur finale comme condensat. La construction éponge de SHA-3, quant à elle, absorbe les blocs de message en les combinant par XOR dans une partie d'un grand état permuté par la fonction Keccak-f, puis extrait les bits du condensat, ce qui évite la propriété d'extension de longueur inhérente à la construction Merkle-Damgaard simple.

Clinical relevance

Les fonctions de hachage sont omniprésentes : elles vérifient l'intégrité des téléchargements de logiciels, ancrent les signatures numériques (qui signent un hachage, et non le document entier), indexent le contenu dans Git et les réseaux de diffusion de contenu, sécurisent le stockage des mots de passe via des fonctions de dérivation de clé lentes (bcrypt, Argon2), et fournissent la preuve de travail (proof-of-work) et les arbres de Merkle qui sous-tendent les blockchains. La cassure pratique de la résistance aux collisions de MD5 et SHA-1 a contraint à une migration vers SHA-2 sur l'ensemble d'Internet.

Evidence & guidelines

SHA-2 (SHA-256, SHA-512) est spécifié dans FIPS 180-4 et SHA-3 dans FIPS 202 ; les deux sont approuvés par le NIST. MD5 et SHA-1 sont dépréciés pour un usage sécurisé après des attaques par collision démontrées (la collision SHAtattered de SHA-1 en 2017 étant un événement marquant). Pour le stockage des mots de passe, les standards recommandent des fonctions résistantes à la mémoire (memory-hard functions) telles qu'Argon2 plutôt qu'un simple hachage.

History

La famille MD (MD4 et MD5 de Rivest) et les SHA-0/SHA-1 conçus par la NSA ont dominé les années 1990. Les attaques par collision de Xiaoyun Wang (2004-2005) ont cassé MD5 et affaibli SHA-1, ce qui a incité le NIST à lancer le concours ouvert SHA-3 (2007-2012), remporté par la conception éponge Keccak de Bertoni, Daemen, Peeters et Van Assche. SHA-1 a été pratiquement cassé par la collision SHAttered en 2017.

Key figures

• Ralph Merkle
• Ivan Damgaard
• Guido Bertoni
• Joan Daemen
• Xiaoyun Wang

Seminal works

• nist2015sha3
• katz2020
• menezes1996

Frequently asked questions

Pourquoi ne puis-je pas simplement hacher un mot de passe et stocker le condensat ?

Les hachages cryptographiques simples sont rapides, ce qui permet aux attaquants d'essayer des milliards de suppositions par seconde contre une base de données volée. Le stockage des mots de passe utilise plutôt des fonctions délibérément lentes, salées et résistantes à la mémoire (memory-hard functions) (bcrypt, scrypt, Argon2) afin que le forçage brutal de chaque mot de passe soit coûteux.

SHA-256 est-il cassé maintenant que SHA-1 l'est ?

Non. SHA-1 et SHA-256 sont des algorithmes différents ; les attaques par collision sur SHA-1 ne se transfèrent pas à SHA-2. SHA-256 reste intact et est le hachage polyvalent recommandé, aux côtés de SHA-3.