Fonction de hachage - Définition

Fonction de hachage cryptographique

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.

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 index des « cases » 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 un objet à partir de sa clé: il suffit de lire dans le tableau la case dont l'index est l'empreinte de cette clé. 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 case de la table constitue le début d'une liste chaînée. Si deux clés fournissent le même condensé et donc accèdent à la même portion 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).

Salage

Le salage (salting en anglais) consiste à ajouter une chaîne de caractères à 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 avant hachage rend l'utilisation de ces tables caduque, et le craquage 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).