hachage

Une définition du Jargon Français.
Aller à : Navigation, rechercher

nom masculin  [algorithmie]  [cryptologie]. Action consistant à calculer, selon une méthode donnée (une fonction mathématique), une valeur caractéristique d'un lot de données (appelée hash), qui en est la signature selon cette méthode.

De nombreuses méthodes de hachage sont couramment utilisées.

Parfois le terme hachage désigne aussi le résultat mais c'est incorrect.

Tout condensat est un hash, mais l'inverse n'est pas vrai car si un hash honore cette contrainte:

déterminisme
un même message produit toujours le même hash

... un condensat honore de surcroît:

sens unique
il est impossible de déterminer le message en ne disposant que de son condensat (anglais : one-way). En d'autres termes on sait calculer facilement le condensat à partir du message, mais pas ce dernier grâce à l'autre,
décorrélation
le condensat du message modifié est très différent de son hash originel (la modification d'un seul bit du message produit un condensat dont en moyenne la moitié des bits seront différents),
unicité
il est impossible d'obtenir le même condensat à partir de deux messages distincts. C'est une certitude lorsque tous les messages possibles sont prédéterminés lors de la conception de la fonction de condensation (tout hash est alors dit parfait), à défaut la taille du condensat est ajustée de sorte qu'il soit en pratique impossible d'obtenir le même condensat à partir de deux messages distincts.

Certaines fonctions de hachage offrent au moins l'une de ces 3 dernières garanties. Celles qui ne garantissent pas le sens unique sont obsolètes.

Att.png Une infinité de fonctions de hachage et de condensation existent, donc pour un message donné tout autant de hashes et de condensats. Certaines font toutefois l'objet d'une norme ou de conventions.

En anglais : hash, fingerprint ou hashing.

Utilité

Mots de passe

C'est par exemple utile pour pouvoir vérifier que quelqu'un détient un mot de passe en évitant de le stocker donc de l'exposer à de l'espionnage. Pour cela lorsqu'un utilisateur définit son mot de passe on le passe à la fonction de condensation choisie, souvent appelée OWF dans ce contexte, et on enregistre ce qu'elle produit.

Pour vérifier un mot de passe saisi par un utilisateur lors du login, on le passe à la OWF et on compare ce qu'elle produit avec ce qui a été stocké lors de la création du mot de passe.

L'intérêt est que même si un pirate s'empare de ces condensats (couramment appelés "hashes de mots de passe") il ne pourra pas en obtenir facilement l'équivalent en clair, donc ne pourra pas usurper un compte utilisateur puisque aucune fonction ne permet, à partir d'un condensat, d'obtenir directement la forme en clair. La seule attaque possible consiste à essayer toutes les mots de passe possibles (force brutale), en calculant le condensat de tout mot de passe possible et en le vérifiant comme décrit ci-devant (s'il correspond le mot de passe créé est utilisable).

Indexation

Cette méthode permet, par exemple, de produire à partir d'une liste d'entiers une valeur plus concise (un hash) qui en est raisonnablement représentative ou caractéristique car les hashes de deux listes aux contenus distincts seront très probablement différents. C'est utile lorsqu'il s'agit de déterminer si une nouvelle liste donnée se trouve ou non déjà dans une base de listes.

Pour cela, au préalable, on calcule puis conserve un hash de type convenu, par exemple le cumul des valeurs de ses éléments (appelé checksum) du contenu de chaque liste placée dans la base, afin de l'employer en guise d'« index ».

Pour déterminer si une liste se trouve déjà en base il suffira dès lors de calculer son hash puis, sachant que la fonction de hachage produit le même hash pour deux listes identiques, de sélectionner, pour comparaison exhaustive, les seules listes présentes en base qui ont le même hash qu'elle. La comparaison est nécessaire car chaque hash correspond à beaucoup de listes possibles, donc des listes aux contenus différents peuvent correspondre au même hash, sauf si l'on emploie un hash parfait. En pratique on préfère une fonction de hachage plus efficace qu'un checksum car causant moins de collisions (sens 3), mais moins coûteux ou contraignant qu'un hachage parfait, donc par exemple MD5 ou l'une des fonctions de la famille SHA.

Exemple

On dispose de 4 listes d'entiers nommées A, B, C et D.

La fonction de hachage retenue est un checksum.

On commence par calculer puis stocker la somme des éléments de chaque liste:

Nom de liste Contenu Hash
A 1, 3, 5 9
B 2, 4, 8 14
C 1, 4, 4 9
D 90, 100, 111 301

A et C, aux contenus distincts, conduisent au même hash. C'est une collision (sens 2). Adopter une autre fonction de hashage pourrait la faire disparaître. Celle qui élève au carré avant d'additionner, par exemple, conduirait à un hash de A égal à 35, et à 33 pour C.

Pour déterminer rapidement si une nouvelle liste abritant "6, 7, 11" se trouve ou non dans la base il suffit de calculer son hash (24) puis de le comparer à ceux des listes en base. Au mieux, ici, quatre comparaisons d'entiers donnent une certitude: le fait qu'aucun ne vaut 24 révèle que cette liste n'est pas dans la base.

Voir aussi table de transposition, table de hashs distribuée et Bloom filter.