Les propriétés attendues

Une fonction de hachage transforme une donnée de taille quelconque en une empreinte de taille fixe. Mais toutes les fonctions qui font cela ne sont pas cryptographiques : ce statut se mérite en satisfaisant des propriétés précises.

Les propriétés de base

Trois propriétés sont attendues de n'importe quelle fonction de hachage utile :

• Déterministe : la même entrée donne toujours la même empreinte. Sans cela, impossible de vérifier quoi que ce soit.
• Sortie de taille fixe : que l'entrée fasse 3 octets ou 3 gigaoctets, l'empreinte a la même longueur (256 bits pour SHA-256).
• Rapide à calculer : hacher un fichier doit prendre un temps négligeable.

"a"                          -> 3f2c8b...      (256 bits)
"Bonjour tout le monde"      -> a91e7d...      (256 bits)
un fichier de 4 Go           -> 0c4f19...      (256 bits)
      entrée quelconque             empreinte de taille fixe

Les trois résistances

C'est ici que le qualificatif cryptographique se joue. Une fonction de hachage cryptographique doit résister à trois types de recherche :

• Résistance à la préimage : étant donné une empreinte h, il est impossible de retrouver un message m tel que H(m) = h. C'est la propriété à sens unique.
• Résistance à la seconde préimage : étant donné un message m1, il est impossible de trouver un autre message m2 différent tel que H(m1) = H(m2).
• Résistance aux collisions : il est impossible de trouver deux messages quelconques m1 et m2 distincts ayant la même empreinte.

La nuance entre les deux dernières est subtile mais capitale : dans la seconde préimage, m1 est imposé ; dans la collision, l'attaquant a le droit de choisir les deux messages. Cette liberté rend la collision plus facile à obtenir, on le verra au chapitre suivant.

Propriété	Ce qui est donné	Ce qu'on cherche	Usage protégé
Préimage	l'empreinte h	un m tel que H(m)=h	mots de passe stockés
Seconde préimage	un message m1	un m2 != m1, même empreinte	intégrité d'un document précis
Collision	rien d'imposé	deux m de même empreinte	signatures, certificats

L'effet d'avalanche

Une bonne fonction de hachage possède l'effet d'avalanche : changer un seul bit de l'entrée doit modifier environ la moitié des bits de sortie, de façon imprévisible.

H("chat")  = 1a3f...0b   (empreinte A)
H("chats") = e7c2...94   (empreinte B, sans rapport visible)

Sans cet effet, des entrées proches donneraient des empreintes proches, et un attaquant pourrait reconstruire l'entrée par approximations successives. L'avalanche garantit qu'aucune information sur l'entrée ne « fuit » dans l'empreinte.

En résumé

Une fonction de hachage cryptographique est déterministe, de sortie fixe et rapide, mais surtout elle résiste à la préimage, à la seconde préimage et aux collisions, tout en présentant un fort effet d'avalanche. Ces résistances ne sont pas équivalentes : la collision, où l'attaquant choisit les deux messages, est la plus exigeante à garantir.