Fonction de hachage

Une fonction de hachage est une fonction qui peut être utilisée pour mapper des données de taille arbitraire à des valeurs de taille fixe. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage , codes de hachage , résumés ou simplement hachages . Les valeurs sont généralement utilisées pour indexer une table de taille fixe appelée table de hachage . L'utilisation d'une fonction de hachage pour indexer une table de hachage est appelée hachage ou adressage de stockage dispersé .

Les fonctions de hachage et leurs tables de hachage associées sont utilisées dans les applications de stockage et de récupération de données pour accéder aux données en un temps réduit et presque constant par récupération. Ils nécessitent une quantité d'espace de stockage à peine supérieure à l'espace total requis pour les données ou les enregistrements eux-mêmes. Le hachage est une forme d'accès aux données efficace en termes de calcul et d'espace de stockage qui évite le temps d'accès non constant des listes ordonnées et non ordonnées et des arbres structurés, ainsi que les exigences de stockage souvent exponentielles de l'accès direct aux espaces d'état de clés de grande taille ou de longueur variable.

L'utilisation des fonctions de hachage repose sur les propriétés statistiques de l'interaction entre la clé et la fonction : le comportement dans le pire des cas est intolérablement mauvais avec une probabilité extrêmement faible, et le comportement dans le cas moyen peut être presque optimal (collision minimale ) .

Les fonctions de hachage sont liées (et souvent confondues avec) les sommes de contrôle , les chiffres de contrôle , les empreintes digitales , la compression avec perte , les fonctions de randomisation , les codes de correction d'erreur et les chiffrements . Bien que les concepts se chevauchent dans une certaine mesure, chacun a ses propres utilisations et exigences et est conçu et optimisé différemment. La fonction de hachage diffère de ces concepts principalement en termes d' intégrité des données .

Exemples de hachages de textes par la fonction md5; (a) le texte utilisé est la version libre de Vingt mille lieues sous les mers du projet Gutenberg ; (b) la version modifiée est le même fichier texte, le 10^e caractère de la 1000^e ligne ayant été remplacé par le caractère "*".

Principe général

Exemple pédagogique du principe des fonctions de hachage appliqué à des images: on considère ici une fonction de hachage consistant à convertir une image haute résolution en une empreinte très basse résolution. L'empreinte est beaucoup plus légère en mémoire. Elle perd une grande partie de l'information mais elle reste suffisante pour distinguer rapidement deux images.

Une fonction de hachage est typiquement une fonction qui, pour un ensemble de très grande taille (théoriquement infini) et de nature très diversifiée, va renvoyer des résultats aux spécifications précises (en général des chaînes de caractère de taille limitée ou fixe) optimisées pour des applications particulières. Les chaînes permettent d'établir des relations (égalité, égalité probable, non-égalité, ordre...) entre les objets de départ sans accéder directement à ces derniers, en général soit pour des questions d'optimisation (la taille des objets de départ nuit aux performances), soit pour des questions de confidentialité.

Autrement dit : à 1 fichier (ou à 1 mot) va correspondre une signature unique (le résultat de la fonction de hachage, soit le hash).

En termes très concrets, on peut voir une fonction de hachage (non cryptographique) comme un moyen de replier l'espace de données que l'on suppose potentiellement très grand et très peu rempli pour le faire entrer dans la mémoire de l'ordinateur. En revanche, une fonction de hachage cryptographique est ce que l'on appelle une fonction à sens unique, ce qui veut dire que le calcul de la fonction de hachage est facile et rapide tandis que le calcul de sa fonction inverse est infaisable par calcul et donc non calculable en pratique. Grâce à la valeur de hachage (le hash), on peut discriminer deux objets apparemment proches, ce qui peut être utilisé pour garantir l'intégrité des objets, autrement dit leur non-modification par une erreur ou un acteur malveillant.

Tables de hachages

Article principal : table de hachage

Les fonctions de hachage sont utilisées conjointement avec des tables de hachage pour stocker et récupérer des éléments de données ou des enregistrements de données. La fonction de hachage traduit la clé associée à chaque donnée ou enregistrement en un code de hachage, qui est utilisé pour indexer la table de hachage. Lorsqu'un élément doit être ajouté à la table, le code de hachage peut indexer un emplacement vide (également appelé compartiment), auquel cas l'élément est ajouté à la table à cet endroit. Si le code de hachage indexe un emplacement complet, une sorte de résolution de collision est requise : le nouvel élément peut être omis (non ajouté à la table), ou remplacer l'ancien élément, ou il peut être ajouté à la table à un autre emplacement en une procédure déterminée. Cette procédure dépend de la structure de la table de hachage : Dans le hachage chaîné, chaque emplacement est la tête d'une liste chaînée ou d'une chaîne, et les éléments qui entrent en collision au niveau de l'emplacement sont ajoutés à la chaîne. Les chaînes peuvent être conservées dans un ordre aléatoire et recherchées linéairement, ou dans un ordre sériel, ou sous forme de liste auto-ordonnée par fréquence pour accélérer l'accès. Dans le hachage d'adresse ouvert , la table est sondée à partir de l'emplacement occupé d'une manière spécifiée, généralement par sondage linéaire , sondage quadratique ou double hachage jusqu'à ce qu'un emplacement ouvert soit localisé ou que la table entière soit sondée (débordement). La recherche de l'élément suit la même procédure jusqu'à ce que l'élément soit localisé, qu'un créneau libre soit trouvé ou que le tableau entier ait été recherché (élément absent du tableau).

Utilisations spécialisées

Les fonctions de hachage sont également utilisées pour créer des caches pour les grands ensembles de données stockés sur des supports lents. Un cache est généralement plus simple qu'une table de recherche hachée car toute collision peut être résolue en supprimant ou en réécrivant le plus ancien des deux éléments en collision.

Les fonctions de hachage sont un ingrédient essentiel du filtre Bloom , une structure de données probabiliste efficace en espace qui est utilisée pour tester si un élément est membre d'un ensemble .

Un cas particulier de hachage est connu sous le nom de hachage géométrique ou méthode de la grille . Dans ces applications, l'ensemble de toutes les entrées est une sorte d' espace métrique , et la fonction de hachage peut être interprétée comme une partition de cet espace dans une grille de cellules . La table est souvent un tableau avec deux indices ou plus (appelés fichier de grille , index de grille , grille de compartiment et noms similaires), et la fonction de hachage renvoie un tuple d'index . Ce principe est largement utilisé en infographie , en géométrie computationnelle et dans de nombreuses autres disciplines, pour résoudre de nombreux problèmes de proximité dans le plan ou dans l'espace tridimensionnel , tels que la recherche de paires les plus proches dans un ensemble de points, de formes similaires dans une liste de formes, d'images similaires dans une base de données d'images , etc.

Les tables de hachage sont également utilisées pour implémenter des tableaux associatifs et des ensembles dynamiques .

Propriétés

Uniformité

Une bonne fonction de hachage doit mapper les entrées attendues aussi uniformément que possible sur sa plage de sortie. Autrement dit, chaque valeur de hachage dans la plage de sortie doit être générée avec à peu près la même probabilité . La raison de cette dernière exigence est que le coût des méthodes basées sur le hachage augmente fortement à mesure que le nombre de collisions (paires d'entrées mappées sur la même valeur de hachage) augmente. Si certaines valeurs de hachage sont plus susceptibles de se produire que d'autres, une plus grande partie des opérations de recherche devra rechercher dans un plus grand ensemble d'entrées de table en collision.

Notez que ce critère exige uniquement que la valeur soit uniformément distribuée , et non aléatoire en aucun cas. Une bonne fonction de randomisation est (à moins de problèmes d'efficacité de calcul) généralement un bon choix en tant que fonction de hachage, mais l'inverse n'est pas nécessairement vrai.

Les tables de hachage ne contiennent souvent qu'un petit sous-ensemble des entrées valides. Par exemple, une liste de membres d'un club peut ne contenir qu'une centaine de noms de membres, sur le très grand nombre de noms possibles. Dans ces cas, le critère d'uniformité doit être valable pour presque tous les sous-ensembles typiques d'entrées qui peuvent être trouvées dans le tableau, et pas seulement pour l'ensemble global de toutes les entrées possibles.

En d'autres termes, si un ensemble typique de m enregistrements est haché en n emplacements de table, la probabilité qu'un seau reçoive beaucoup plus que m / n enregistrements devrait être extrêmement faible. En particulier, si m est inférieur à n , très peu de compartiments doivent avoir plus d'un ou deux enregistrements. Un petit nombre de collisions est pratiquement inévitable, même si n est beaucoup plus grand que m – voir le problème de l'anniversaire .

Dans des cas particuliers où les clés sont connues à l'avance et que l'ensemble de clés est statique, une fonction de hachage peut être trouvée qui atteint une uniformité absolue (ou sans collision). Une telle fonction de hachage est dite parfaite . Il n'existe aucun moyen algorithmique de construire une telle fonction - la recherche d'une est une fonction factorielle du nombre de clés à mapper par rapport au nombre d'emplacements de table dans lesquels elles sont exploitées. Trouver une fonction de hachage parfaite sur plus d'un très petit ensemble de clés est généralement irréalisable en termes de calcul; la fonction résultante est susceptible d'être plus complexe en termes de calcul qu'une fonction de hachage standard et ne fournit qu'un avantage marginal par rapport à une fonction avec de bonnes propriétés statistiques qui produit un nombre minimum de collisions. Voir la fonction de hachage universelle.

Tests et mesures

Lors du test d'une fonction de hachage, l'uniformité de la distribution des valeurs de hachage peut être évaluée par le test du chi carré . Ce test est une mesure de la qualité de l'ajustement : il s'agit de la distribution réelle des éléments dans les compartiments par rapport à la distribution attendue (ou uniforme) des éléments. La formule est :

où: "n" est le nombre de clés, "m" est le nombre de seaux, "bj" est le nombre d'articles dans le compartiment "j".

Un rapport dans un intervalle de confiance (0,95 - 1,05) indique que la fonction de hachage évaluée a une distribution uniforme attendue.

Les fonctions de hachage peuvent avoir certaines propriétés techniques qui les rendent plus susceptibles d'avoir une distribution uniforme lorsqu'elles sont appliquées. L'un est le critère strict d'avalanche: chaque fois qu'un seul bit d'entrée est complété, chacun des bits de sortie change avec une probabilité de 50 %. La raison de cette propriété est que des sous-ensembles sélectionnés de l'espace de clés peuvent avoir une faible variabilité. Pour que la sortie soit distribuée uniformément, une faible quantité de variabilité, même un bit, doit se traduire par une grande quantité de variabilité (c'est-à-dire une distribution sur l'espace de table) dans la sortie. Chaque bit doit changer avec une probabilité de 50 % car si certains bits hésitent à changer, les clés se regroupent autour de ces valeurs. Si les bits veulent changer trop facilement, le mappage se rapproche d'une fonction XOR fixe d'un seul bit. Des tests standard pour cette propriété ont été décrits dans la littérature.   La pertinence du critère pour une fonction de hachage multiplicative est évaluée ici.

Efficacité

Dans les applications de stockage et de récupération de données, l'utilisation d'une fonction de hachage est un compromis entre le temps de recherche et l'espace de stockage des données. Si le temps de recherche était illimité, une liste linéaire non ordonnée très compacte serait le meilleur moyen ; si l'espace de stockage était illimité, une structure accessible de manière aléatoire et indexable par la valeur-clé serait très grande, très clairsemée, mais très rapide. Une fonction de hachage prend un temps fini pour mapper un espace de clés potentiellement grand à une quantité réalisable d'espace de stockage interrogeable dans un laps de temps limité, quel que soit le nombre de clés. Dans la plupart des applications, la fonction de hachage doit être calculable avec un minimum de latence et accessoirement en un minimum d'instructions.

La complexité de calcul varie en fonction du nombre d'instructions requises et de la latence des instructions individuelles, les plus simples étant les méthodes au niveau du bit (pliage), suivies des méthodes multiplicatives, et les plus complexes (les plus lentes) sont les méthodes basées sur la division.

Étant donné que les collisions devraient être peu fréquentes et entraîner un retard marginal mais qu'elles sont par ailleurs inoffensives, il est généralement préférable de choisir une fonction de hachage plus rapide plutôt qu'une fonction nécessitant plus de calculs mais économisant quelques collisions.

Les implémentations basées sur la division peuvent être particulièrement préoccupantes car la division est microprogrammée sur presque toutes les architectures de puces. La division ( modulo ) par une constante peut être inversée pour devenir une multiplication par l'inverse multiplicatif de la taille du mot de la constante. Cela peut être fait par le programmeur ou par le compilateur. La division peut également être réduite directement en une série de soustractions de décalage et d'ajouts de décalage, bien que la minimisation du nombre de ces opérations requises soit un problème de taille; le nombre d'instructions de montage qui en résultent peut être supérieur à une dizaine, et noyer le pipeline. Si l'architecture comporte des unités fonctionnelles de multiplication matérielle, la multiplication par l'inverse est probablement une meilleure approche.

Nous pouvons autoriser la taille de table n à ne pas être une puissance de 2 et ne pas avoir à effectuer d'opération de reste ou de division, car ces calculs sont parfois coûteux. Par exemple, soit n significativement inférieur à 2 ^b . Considérons une fonction génératrice de nombres pseudo -aléatoires P (clé) uniforme sur l'intervalle [0, 2 ^b  − 1] . Une fonction de hachage uniforme sur l'intervalle [0, n -1] est n P (clé)/2 ^b . On peut remplacer la division par un décalage de bit à droite (éventuellement plus rapide) : nP(touche) >> b .

Si les clés sont hachées à plusieurs reprises et que la fonction de hachage est coûteuse, le temps de calcul peut être économisé en précalculant les codes de hachage et en les stockant avec les clés. La correspondance des codes de hachage signifie presque certainement que les clés sont identiques. Cette technique est utilisée pour la table de transposition dans les programmes de jeu, qui stocke une représentation hachée 64 bits de la position du plateau.

Universalité

Un schéma de hachage universel est un algorithme aléatoire qui sélectionne une fonction de hachage h parmi une famille de telles fonctions, de telle sorte que la probabilité d'une collision de deux clés distinctes soit 1/ m , où m est le nombre de valeurs de hachage distinctes souhaité—indépendamment des deux touches. Le hachage universel garantit (au sens probabiliste) que l'application de la fonction de hachage se comportera aussi bien que si elle utilisait une fonction aléatoire, pour toute distribution des données d'entrée. Cependant, il aura plus de collisions qu'un hachage parfait et peut nécessiter plus d'opérations qu'une fonction de hachage à usage spécial.

Applicabilité

Une fonction de hachage est applicable dans une variété de situations. Une fonction de hachage qui n'autorise que certaines tailles de table, des chaînes jusqu'à une certaine longueur ou qui ne peut pas accepter de graine (c'est-à-dire autoriser le double hachage) n'est pas aussi utile qu'une autre.

Déterminisme

Une procédure de hachage doit être déterministe , ce qui signifie que pour une valeur d'entrée donnée, elle doit toujours générer la même valeur de hachage. En d'autres termes, il doit être fonction des données à hacher, au sens mathématique du terme. Cette exigence exclut les fonctions de hachage qui dépendent de paramètres variables externes, tels que les générateurs de nombres pseudo-aléatoires ou l'heure de la journée. Il exclut également les fonctions qui dépendent de l'adresse mémoire de l'objet haché dans les cas où l'adresse peut changer pendant l'exécution (comme cela peut arriver sur les systèmes qui utilisent certaines méthodes de récupération de place ), bien que parfois le rehachage de l'élément soit possible.

Le déterminisme est dans le cadre de la réutilisation de la fonction. Par exemple, Python ajoute la fonctionnalité selon laquelle les fonctions de hachage utilisent une graine aléatoire qui est générée une fois lorsque le processus Python démarre en plus de l'entrée à hacher.   Le hachage Python ( SipHash ) est toujours une fonction de hachage valide lorsqu'il est utilisé dans une seule exécution. Mais si les valeurs sont persistantes (par exemple, écrites sur le disque), elles ne peuvent plus être traitées comme des valeurs de hachage valides, car lors de la prochaine exécution, la valeur aléatoire peut différer.

Plage définie

Il est souvent souhaitable que la sortie d'une fonction de hachage ait une taille fixe (mais voir ci-dessous). Si, par exemple, la sortie est limitée à des valeurs entières de 32 bits, les valeurs de hachage peuvent être utilisées pour indexer dans un tableau. Un tel hachage est couramment utilisé pour accélérer les recherches de données.   La ​​production d'une sortie de longueur fixe à partir d'une entrée de longueur variable peut être réalisée en divisant les données d'entrée en morceaux de taille spécifique. Les fonctions de hachage utilisées pour les recherches de données utilisent une expression arithmétique qui traite de manière itérative des morceaux de l'entrée (tels que les caractères d'une chaîne) pour produire la valeur de hachage.

Plage de variables

Dans de nombreuses applications, la plage de valeurs de hachage peut être différente pour chaque exécution du programme ou peut changer au cours de la même exécution (par exemple, lorsqu'une table de hachage doit être étendue). Dans ces situations, il faut une fonction de hachage qui prend deux paramètres : les données d'entrée z et le nombre n de valeurs de hachage autorisées.

Une solution courante consiste à calculer une fonction de hachage fixe avec une très grande plage (disons, 0 à 2 ³²  − 1 ), à diviser le résultat par n et à utiliser le reste de la division . Si n est lui-même une puissance de 2 , cela peut être fait par masquage et décalage de bits . Lorsque cette approche est utilisée, la fonction de hachage doit être choisie de manière à ce que le résultat ait une distribution assez uniforme entre 0 et n  - 1 , pour toute valeur de n pouvant survenir dans l'application. Selon la fonction, le reste peut n'être uniforme que pour certaines valeurs de n, par exemple nombres impairs ou premiers .

Plage variable avec un minimum de mouvement (fonction de hachage dynamique)

Lorsque la fonction de hachage est utilisée pour stocker des valeurs dans une table de hachage qui survit à l'exécution du programme et que la table de hachage doit être étendue ou réduite, la table de hachage est appelée table de hachage dynamique.

Une fonction de hachage qui déplacera le nombre minimum d'enregistrements lorsque la table est redimensionnée est souhaitable. Ce qu'il faut, c'est une fonction de hachage H ( z , n )  - où z est la clé hachée et n est le nombre de valeurs de hachage autorisées - telle que H ( z , n  + 1) = H ( z , n ) avec probabilité proche de n /( n  + 1) .

Le hachage linéaire et le stockage en spirale sont des exemples de fonctions de hachage dynamiques qui s'exécutent en temps constant mais relâchent la propriété d'uniformité pour obtenir la propriété de mouvement minimal. Le hachage extensible utilise une fonction de hachage dynamique qui nécessite un espace proportionnel à n pour calculer la fonction de hachage, et il devient une fonction des clés précédentes qui ont été insérées. Plusieurs algorithmes qui préservent la propriété d'uniformité mais nécessitent un temps proportionnel à n pour calculer la valeur de H ( z , n ) ont été inventés.

Une fonction de hachage avec un minimum de mouvement est particulièrement utile dans les tables de hachage distribuées .

Normalisation des données

Dans certaines applications, les données d'entrée peuvent contenir des caractéristiques qui ne sont pas pertinentes à des fins de comparaison. Par exemple, lors de la recherche d'un nom personnel, il peut être souhaitable d'ignorer la distinction entre les majuscules et les minuscules. Pour de telles données, il faut utiliser une fonction de hachage compatible avec le critère d' équivalence des données utilisé : c'est-à-dire que deux entrées considérées comme équivalentes doivent produire la même valeur de hachage. Cela peut être accompli en normalisant l'entrée avant de la hacher, comme en majuscule toutes les lettres.

Hachage des types de données entiers

Il existe plusieurs algorithmes courants pour le hachage des entiers. La méthode donnant la meilleure distribution dépend des données. L'une des méthodes les plus simples et les plus courantes dans la pratique est la méthode de division modulo.

Fonction de hachage d'identité

Si les données à hacher sont suffisamment petites, on peut utiliser les données elles-mêmes (réinterprétées comme un entier) comme valeur hachée. Le coût de calcul de cette fonction de hachage d' identité est effectivement nul. Cette fonction de hachage est parfaite , car elle mappe chaque entrée à une valeur de hachage distincte.

La signification de "suffisamment petit" dépend de la taille du type utilisé comme valeur hachée. Par exemple, en Java , le code de hachage est un entier 32 bits. Ainsi, les objets entiers Integer32 bits et virgule flottante 32 bits Floatpeuvent simplement utiliser directement la valeur ; alors que l'entier Long64 bits et la virgule flottante 64 bits Doublene peuvent pas utiliser cette méthode.

D'autres types de données peuvent également utiliser ce schéma de hachage. Par exemple, lors du mappage de chaînes de caractères entre majuscules et minuscules , on peut utiliser l'encodage binaire de chaque caractère, interprété comme un entier, pour indexer une table qui donne la forme alternative de ce caractère ("A" pour "a", " 8" pour "8", etc.). Si chaque caractère est stocké sur 8 bits (comme en ASCII étendu  ou ISO Latin 1 ), la table n'a que 2 ⁸ = 256 entrées ; dans le cas des caractères Unicode , le tableau aurait 17×2 ¹⁶ =1 114 112 entrées.

La même technique peut être utilisée pour mapper des codes de pays à deux lettres comme "us" ou "za" aux noms de pays (26 ² = 676 entrées de table), des codes postaux à 5 chiffres comme 13083 aux noms de ville (100 000 entrées), etc. Les valeurs de données non valides (telles que le code de pays "xx" ou le code postal 00000) peuvent être laissées non définies dans le tableau ou mappées à une valeur "null" appropriée.

Pliage

Un code de hachage pliant est produit en divisant l'entrée en n sections de m bits, où 2 ^m est la taille de la table, et en utilisant une opération au niveau du bit préservant la parité telle que ADD ou XOR pour combiner les sections, suivies d'un masque ou de décalages vers coupez tous les bits en excès à l'extrémité supérieure ou inférieure. Par exemple, pour une taille de table de 15 bits et une valeur de clé de 0x0123456789ABCDEF, il existe cinq sections composées de 0x4DEF, 0x1357, 0x159E, 0x091A et 0x8. En ajoutant, nous obtenons 0x7AA4, une valeur de 15 bits.

Carrés médians

Un code de hachage à carrés moyens est produit en mettant au carré l'entrée et en extrayant un nombre approprié de chiffres ou de bits du milieu. Par exemple, si l'entrée est 123 456 789 et que la taille de la table de hachage est de 10 000, la mise au carré de la clé produit 15 241 578 750 190 521, de sorte que le code de hachage est pris comme les 4 chiffres du milieu du nombre à 17 chiffres (en ignorant le chiffre supérieur) 8750. produit un code de hachage raisonnable s'il n'y a pas beaucoup de zéros à gauche ou à droite dans la clé. Il s'agit d'une variante du hachage multiplicatif, mais pas aussi bonne car une clé arbitraire n'est pas un bon multiplicateur.

Hachage de division

Une technique standard consiste à utiliser une fonction modulo sur la clé, en sélectionnant un diviseurqui est un nombre premier proche de la taille de la table, donc. La taille de la table est généralement une puissance de 2. Cela donne une distribution de. Cela donne de bons résultats sur un grand nombre de jeux de clés. Un inconvénient important du hachage de division est que la division est microprogrammée sur la plupart des architectures modernes, y compris x86, et peut être 10 fois plus lente que la multiplication. Un deuxième inconvénient est qu'il ne brisera pas les clés en cluster. Par exemple, les clés 123000, 456000, 789000, etc. modulo 1000 correspondent toutes à la même adresse. Cette technique fonctionne bien dans la pratique car de nombreux ensembles de clés sont déjà suffisamment aléatoires et la probabilité qu'un ensemble de clés soit cyclique par un grand nombre premier est faible.

Terminologie

Le résultat d'une fonction de hachage peut être appelé selon le contexte somme de contrôle, empreinte, empreinte numérique, hash, résumé de message, condensé, condensat, signature ou encore empreinte cryptographique lorsque l'on utilise une fonction de hachage cryptographique.

Collision

Est appelé « collision » d'une fonction de hachage, un couple de données distinctes de son ensemble de départ dont les sommes de contrôle sont identiques. Les collisions sont en général considérées comme indésirables mais sont généralement impossibles à éviter du fait de la différence de taille entre les ensembles de départ et d'arrivée de la fonction.

Cette situation est considérée comme rare, voire impossible, en fonction du niveau de qualité de la fonction de hachage. C'est ce qui permet de considérer qu'à un fichier (ou un mot de passe) correspond une signature unique. Et donc qu'une signature donnée ne peut provenir que d'un unique fichier (ou mot de passe) de départ.

Considérations mathématiques

Définitions

Soit une fonction de hachage f d'un ensemble S dans un ensemble N.

La fonction f est dite parfaite pour l'ensemble S si elle est une injection de S dans N.

La fonction f est dite minimale si elle est parfaite et si S et N sont de même cardinal.

Dans le cas où S=N, on dit que f préserve une relation donnée $r_{o}$ de S si

$\forall (x,y)\in S^{2},r_{o}(x,y)\Rightarrow r_{o}(f(x),f(y))$

Conséquences

Une fonction de hachage parfaite ne possède aucune collision.

Lorsque l'ensemble d'arrivée est de cardinal inférieur à l'ensemble de départ, il existe nécessairement des collisions. Le nombre de collisions est alors supérieur ou égal à card(S)–card(N).

Applications en optimisation

Principes généraux

Les fonctions de hachage ont plusieurs objectifs.

1. Elles servent à rendre plus rapide l'identification des données : le calcul d'empreinte d'une donnée représente un temps négligeable au regard d'une comparaison complète (plus longue à réaliser).
2. Elles permettent de stocker un espace virtuel très grand, mais peu rempli, de données dans un espace physique forcément limité où l'accès aux données est direct, comme s'il s'agissait d'un tableau. En ce sens, le hachage s'oppose aux listes chaînées et aux arbres de recherche.

Une fonction de hachage doit par ailleurs éviter autant que possible les collisions (états dans lesquels des données différentes ont une empreinte identique) : dans le cas des tables de hachage, ou de traitements automatisés, les collisions empêchent la différenciation des données ou, au mieux, ralentissent le processus.

Hors cryptographie, les fonctions de hachage ne sont en général pas injectives, car on souhaite conserver des empreintes plus petites que les données traitées – pour des considérations de stockage en mémoire : il faut donc concevoir une fonction de hachage homogène, donnant une empreinte de taille raisonnable tout en minimisant le nombre de collisions. Par exemple on peut associer une empreinte de 16, 32 ou 64 bits à chaque document d'une bibliothèque de plusieurs millions de fichiers. Si deux fichiers ont des empreintes différentes, ils sont à coup sûr différents. Si leurs empreintes sont identiques en revanche, un mécanisme de gestion des collisions doit être activé.

Pour un bon emploi de la fonction de hachage, il est souhaitable qu'un infime changement de la donnée en entrée (inversion d'un seul bit, par exemple) entraîne une perturbation importante de l'empreinte correspondante. S'il s'agit de cryptographie, cela rend une recherche inverse par approximations successives impossible : on parle d'effet avalanche. S'il s'agit de stockage efficace, cela minimisera le risque d'une collision, deux clés de noms proches donneront accès à des endroits éloignés dans la mémoire physique.

Conception d'une fonction de hachage

La conception d'une fonction de hachage est en général heuristique. Pour des cas d'optimisation le concepteur cherchera à trouver un compromis entre la taille des empreintes et le nombre de collisions pour des échantillons de données traités représentatifs de cas d'utilisation réels.

La question du hachage uniforme, ou encore de l'équirépartition de l'ensemble de départ vis-à-vis de la fonction de hachage est un élément essentiel conditionnant l'efficacité de la fonction de hachage : si par exemple, dans une table de hachage de taille 10, nous devons ranger des éléments numérotés de 10 en 10, ou de 20 en 20, il est totalement inopportun d'utiliser la fonction modulo 10, car alors tous les éléments se retrouveraient groupés dans la première case. La difficulté à trouver une bonne fonction de hachage consiste donc à trouver une fonction h qui catégorise notre ensemble de départ S en classes d'équivalence de proportions égales, pour la relation d'équivalence $\scriptstyle {{\mathcal {R}}(x)=\{y\in S\,|\ x=h(y)\}}$. De façon probabiliste, une fonction de hachage uniforme dans l'ensemble d'arrivée $\scriptstyle {\mathcal {E}}$ est une fonction h telle que $\scriptstyle {{\mathcal {8}}i{\mathcal {2E,~P}}(h(x)=i)={\frac {1}{card({\mathcal {E}})}}}$. On parlera dans ce cas d'uniformité de la sortie.

Exemple pédagogique simple

Un exemple courant de fonction de hachage passable est la fonction qui, à un fichier informatique, associe sa taille.

Nous voulons comparer deux fichiers informatiques afin de déterminer s'ils sont identiques (par exemple déterminer si un document a été modifié). La solution évidente consiste à vérifier la correspondance caractère par caractère mais cette méthode peut s'avérer fastidieuse. Une solution souvent plus rapide consiste à comparer la taille des fichiers dans la mémoire (en général disponible immédiatement dans le système d'exploitation, employée ici comme empreinte ou hachage) : si cette taille diffère nous avons obtenu très rapidement la preuve que les deux fichiers étaient différents. A contrario, si les deux tailles de fichiers coïncident, il n'est pas possible de conclure formellement que les deux fichiers sont identiques (cas de la collision). Finalement, reconnaître des fichiers à la taille est rapide, mais avec un taux de collision élevé ce qui rend cette technique peu fiable.

Exemples d'applications typiques

Tables de hachage et structures de données

On utilise fréquemment les fonctions de hachage dans des structures de données : les tables de hachage. Le principe est d'utiliser les empreintes des clés comme indices des éléments de la table. Ces empreintes sont des nombres entiers obtenus en hachant la clé des objets à stocker, souvent une chaîne de caractères. On peut ensuite retrouver l'objet associé à une clé donnée : il suffit de hacher la clé pour obtenir une empreinte et de lire dans le tableau l'élément dont l'indice est cette empreinte. Toutefois, des collisions existent car il existe moins d'empreintes possibles que de valeurs possibles pour la clé. Des techniques destinées à lever ces conflits sont nécessaires, par exemple le principe de chaînage : chaque élément de la table constitue le début d'une liste chaînée. Si deux clés fournissent la même empreinte et donc accèdent au même élément de la table, on doit alors parcourir la liste chaînée pour l'élément qui correspond bien à la clé donnée (la clé est en général stockée avec l'élément dans un nœud de la liste).

On utilise aussi des fonctions de hachage dans le filtre de Bloom, une structure de données probabiliste.

Fonction de hachage perceptuelle

La plupart des fonctions de hachage produisent des empreintes radicalement différentes si l'entrée est légèrement modifiée. Ce phénomène est particulièrement visible avec les fonctions de hachage cryptographiques qui se comportent de manière imprévisible grâce à l'effet avalanche. Toutefois, il existe des fonctions de hachage qui tolèrent une certaine marge d'erreur. Elles sont particulièrement utiles pour hacher des données qui peuvent subir des perturbations comme les sons ou encore les images. Par exemple, un fichier audio original et sa version en MP3 seront totalement différents si la comparaison se fait au niveau binaire. Toutefois, le résultat est plus ou moins identique pour un auditeur. Un système développé par Philips consiste à subdiviser le signal en plusieurs bandes de fréquences et à les hacher séparément. La fonction de hachage est conçue pour ne modifier que quelques bits si le signal change. En calculant la distance de Hamming entre deux empreintes, il est possible de savoir si deux échantillons correspondent à la même séquence sonore.

Ces techniques, alliées au tatouage numérique, sont principalement destinées à lutter contre la contrefaçon. Elles sont également intéressantes pour gérer des bases de données et trouver rapidement des échantillons présentant de fortes similitudes.

Principes généraux

En cryptographie les contraintes sont plus exigeantes et la taille des empreintes est généralement bien plus longue que celle des données initiales ; un mot de passe dépasse rarement une longueur de 15 caractères, mais son empreinte peut atteindre une longueur de plus de 100 caractères. La priorité principale est de protéger l'empreinte contre une attaque par force brute, le temps de calcul de l'empreinte passant au second plan.

Une fonction de hachage cryptographique est utilisée entre autres pour la signature électronique, et rend également possibles des mécanismes d'authentification par mot de passe sans stockage de ce dernier. Elle doit être résistante aux collisions, c’est-à-dire que deux messages distincts doivent avoir très peu de chances de produire la même signature. De par sa nature, tout algorithme de hachage possède des collisions, mais on considère le hachage comme cryptographique si les conditions suivantes sont remplies :

• il est très difficile de trouver le contenu du message à partir de la signature (attaque sur la première préimage) ;
• à partir d'un message donné, de sa signature et du code source de la fonction de hachage, il est très difficile de générer un autre message qui donne la même signature (attaque sur la seconde préimage) ;
• il est très difficile de trouver deux messages aléatoires qui donnent la même signature (résistance aux collisions).

Par très difficile, on entend « techniquement impossible en pratique », par toutes techniques algorithmiques et matérielles, en un temps raisonnable. Le MD5 par exemple n'est plus considéré comme sûr car on a trouvé deux messages qui génèrent la même empreinte. Toutefois, la mise en œuvre de ces techniques n'est pas aisée et dans le cas du MD5, les chercheurs ont trouvé une collision sur deux messages au contenu aléatoire. On peut cependant construire à partir d'une collision des attaques réelles.

Exemples d'applications typiques

Contrôle d'accès

Un mot de passe ne doit pas être stocké en clair sur une machine pour des raisons de sécurité. Seul le résultat du hachage du mot de passe est donc stocké. Pour identifier un utilisateur, l'ordinateur compare l'empreinte du mot de passe d'origine (stocké) avec l'empreinte du mot de passe saisi par l'utilisateur. Toutefois, cette manière de faire n'est pas complètement satisfaisante. Si deux utilisateurs décident d'utiliser le même mot de passe alors le condensé obtenu sera identique. Cette faille est potentiellement utilisable par trois méthodes :

• attaque par dictionnaire ;
• attaque par force brute ;
• attaque par table arc-en-ciel.

Lors d'une attaque par dictionnaire, on pourrait raisonnablement déduire que le mot de passe choisi par les deux utilisateurs est relativement facile à mémoriser.

Pour contrer ce type d'attaque, on ajoute une composante aléatoire lors de la génération initiale de l'empreinte. Cette composante, aussi appelée « sel », est souvent stockée en clair. On peut simplement utiliser l'heure de l'attribution du mot de passe ou un compteur qui varie selon l'utilisateur. Le mot de passe est ensuite mélangé avec le sel, cette étape varie selon le système employé. Une méthode simple est de concaténer le mot de passe avec le sel. Le sel n'étant pas identique pour deux utilisateurs, on obtiendra deux signatures différentes avec le même mot de passe. Cela réduit fortement la marge d'une attaque via un dictionnaire.

Les algorithmes SHA-1 (Secure Hash Algorithm 1 : 160 bits) et MD5 (Message-Digest algorithm 5, 128 bits, plus ancien et moins sûr) sont des fonctions de hachage utilisées fréquemment. Le SHA-2 (SHA-256, SHA-384 ou SHA-512 bits au choix) est d'ores et déjà prêt s'il faut abandonner aussi le SHA-1.

Salage

Le salage (salting en anglais) consiste à ajouter une chaîne de caractères (un nonce) à l'information avant le hachage. Par exemple, dans un cadre cryptographique, au lieu de pratiquer le hachage sur le mot de passe seul, on peut le faire sur le résultat de la concaténation du mot de passe avec une autre chaîne de caractères pseudo-aléatoire, obtenue par un hachage de l'identifiant (login) concaténé avec le mot de passe. Les deux fonctions de hachage (celle qu'on utilise pour générer la chaîne pseudo-aléatoire et celle qu'on applique au résultat) peuvent être différentes (par exemple SHA-1 et MD5).

Cela permet de renforcer la sécurité de cette fonction.

En effet, en l'absence de salage, il est possible de cracker le système à l'aide de tables de hachage correspondant à des valeurs (telles que des mots de passe) souvent utilisées, par exemple les tables arc-en-ciel.

Le simple ajout d'un sel (ou nonce) avant hachage rend l'utilisation de ces tables caduque, et le cassage doit faire appel à des méthodes telles que l'attaque par force brute (cette méthode, consistant à tester toutes les valeurs possibles, prend tellement de temps avec un bon mot de passe que l'on ne peut plus qualifier cela de crackage).

Logiciels de contrôle d'intégrité

Les logiciels de contrôle d'intégrité permettent de vérifier les éventuelles modifications/altérations de fichiers, en vérifiant périodiquement chaque fichier par rapport à une table de référence. La table de référence contient les signatures (hash) de chaque fichier d'origine. Périodiquement le logiciel vient vérifier que la signature de chaque fichier corresponde bien à la signature d'origine contenue dans la table de référence. Bien évidemment, il faut que la table de référence soit stockée de façon « sûre » et donc elle-même non sujette à des modifications ou altérations.

Exemple de logiciel : tripwire.

Notes et références

Stokes, Jon (2002-07-08). "Understanding CPU caching and performance". Ars Technica. Retrieved 2022-02-06.

Annexes

Bibliographie

(en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition], chap. 6 Searching, section 6.4 Hashing

Liens externes

• (fr) Le hachage chez Interstices