Introduction au Hachage

Le hachage est le processus de conversion d'une valeur donnée en une autre valeur. Une fonction de hachage est utilisée pour générer la nouvelle valeur selon un algorithme mathématique. Le résultat d'une fonction de hachage est connu sous le nom de valeur de hachage ou simplement, un hache.

Les bonnes fonctions de hachage utilise généralement un algorithme de hachage unidirectionnel, ou en d'autres termes, le hachage ne peut pas être reconverti dans la valeur d'origine.

Applications

L'une des principales utilisations du hachage est de comparer deux fichiers pour l'égalité. Sans ouvrir deux fichiers de documents pour les comparer mot à mot, les valeurs de hachage calculées de ces fichiers permettront au propriétaire de savoir immédiatement s'ils sont différents.

Le hachage est également utilisé pour vérifier l'intégrité d'un fichier après son transfert d'un endroit à un autre, par exemple dans un programme de sauvegarde de fichiers. Pour s'assurer que le fichier transféré n'est pas corrompu, un utilisateur peut comparer la valeur de hachage des deux fichiers. S'ils sont identiques, le fichier transféré est une copie identique.

Le hachage est également utilisé dans le chiffrement des données. Les mots de passe peuvent être stockés sous la forme de leurs hachages de sorte que même si une base de données est violée, les mots de passe en clair ne sont pas accessibles. MD5, SHA-1 et SHA-2 sont des hachages cryptographiques populaires cependant il existe aujourd'hui des algorithmes plus sures.

Le hachage est aussi souvent utilisé pour implémenter des tables de hachage. Une table de hachage stocke des paires clé/valeur sous la forme d'une liste où n'importe quel élément est accessible à l'aide de son index.

Table de Hachage

Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée.

Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.

Il s'agit d'un tableau ne comportant pas d'ordre (contrairement à un tableau ordinaire). On accède à chaque valeur du tableau par sa clé, qui transformée par une fonction de hachage en une valeur de hachage (un nombre) indexe les éléments de la table.

Un annuaire représenté comme une table de hachage. La fonction de hachage transforme les clés (en bleu) en valeurs de hachage (en rose) indexant les éléments de la table (alvéoles) composés de paires clé–valeur (en vert).

Collisions

Gardez à l'esprit que deux clés peuvent générer le même hachage. Ce phénomène est connu sous le nom de collision. Il existe plusieurs façons de gérer les collisions.

Pour diminuer les risques de collisions, il faut donc premièrement choisir avec soin sa fonction de hachage. Ensuite, un mécanisme de résolution des collisions sera à implémenter si nécessaire.

Une fonction de hachage primaire qui mappe les noms sur des nombres entiers de 0 à 15. Il y a une collision entre les clés "John Smith" et "Sandra Dee".

Types de hachage

Il existe de nombreux types d'algorithmes de hachage tels que RipeMD, Tiger, xxhash et bien d'autres, mais les types de hachage les plus couramment utilisés pour les contrôles d'intégrité des fichiers sont MD5, SHA-2 et CRC32.

MD5 - Une fonction de hachage MD5 encode une chaîne d'informations et l'encode dans une empreinte digitale de 128 bits. MD5 est souvent utilisé comme somme de contrôle pour vérifier l'intégrité des données. Cependant, en raison de son âge, MD5 est également connu pour souffrir de nombreuses vulnérabilités de collision de hachage, mais il reste l'un des algorithmes les plus utilisés au monde.

SHA-2 – SHA-2, développé par la National Security Agency (NSA), est une fonction de hachage cryptographique. SHA-2 inclut des modifications importantes par rapport à son prédécesseur, SHA-1. La famille SHA-2 se compose de six fonctions de hachage avec des résumés (valeurs de hachage) de 224, 256, 384 ou 512 bits : SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA -512/256.

CRC32 - Un contrôle de redondance cyclique (CRC) est un code de détection d'erreur souvent utilisé pour détecter les modifications accidentelles des données. L'encodage de la même chaîne de données à l'aide de CRC32 entraînera toujours la même sortie de hachage, ainsi CRC32 est parfois utilisé comme algorithme de hachage pour les vérifications d'intégrité de fichier. De nos jours, CRC32 est rarement utilisé en dehors des fichiers Zip et des serveurs FTP.

Une fonction de hachage cryptographique (spécifiquement, SHA-1) en action. Notez que même de petits changements dans la donnée d'entrée (ici dans le mot over) changent radicalement le résultat de sortie par un phénomène appelé effet avalanche.