hachage

Une définition du Jargon Français.
Aller à : Navigation, rechercher
Reviser.png Cet article est à revoir. Si le cœur vous en dit...


nom masculin  [algorithmie]. En cryptologie c'est le fait d'utiliser une fonction de condensation.

Le terme hachage désigne aussi, parfois, le résultat (une empreinte numérique), toutefois hash est d'ordinaire préféré.

Att.png Une infinité de fonctions de condensation existent, donc tout autant de valeurs du hash d'un message donné. 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 sans avoir à le stocker. 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. L'intérêt est que même si un pirate s'empare de ces "mots de passe hashés" il ne pourra pas en obtenir facilement l'équivalent en clair, donc ne pourra pas se usurper un compte utilisateur puisqu'aucune fonction ne permet, à partir d'un hash, d'obtenir directement la forme en clair. La seule attaque possible consiste à essayer toutes les mots de passe possibles, avec force brutale. 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é sauvé lors de la création du mot de passe.

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 la base de listes, afin d'éviter de la comparer à chacune des autres.

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 déjà en base.

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