Fonction de hachage

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Une fonction de hash (anglicisme) ou fonction de hachage est une fonction qui associe à un grand ensemble de données un ensemble beaucoup plus petit (de l'ordre de quelques centaines de bits) qui est caractéristique de l'ensemble de départ . Cette propriété fait qu'elles sont très utilisées en informatique, en particulier pour accéder rapidement à des données grâce aux Tables de hachage (ou hash tables en anglais). En effet, une fonction de hachage permet d'associer à une chaîne de caractères un entier particulier. Ainsi, si nous connaissons l'empreinte des chaînes de caractères stockées, nous pouvons rapidement vérifier si une chaîne se trouve ou non dans cette table (en O(1) si la fonction de hachage est suffisamment bonne). Les fonctions de hachage sont aussi extrêmement utiles en cryptographie.

Sommaire

1 Terminologie
2 Propriétés mathématiques
3 Tables de hachage et structures de données
4 Fonction de hachage cryptographique
5 Fonction de hachage perceptuelle
6 Utilisation
- 6.1 Traduction de brochures techniques
- 6.2 Contrôle d'accès
7 Voir aussi
8 Bibliographie

[modifier] Terminologie

Le terme fonction de hachage évite l'emploi de l'anglicisme hash. Le résultat de cette fonction est par ailleurs aussi appelé somme de contrôle, empreinte, résumé de message, condensé ou encore empreinte cryptographique lorsque l'on utilise une fonction de hachage cryptographique.

[modifier] Propriétés mathématiques

Plus précisément, pour une fonction de hachage H, il faut que : H(x) ≠ H(y) implique x ≠ y et H(x) = H(y) implique probablement x = y. Si l'ensemble dans lequel est tiré x est plus grand que l'ensemble des valeurs prises par H, cette dernière propriété est difficile à évaluer. En fait, la probabilité dépend grandement du domaine d'application de cette fonction de hachage. Pour les fonctions de hachage cryptographiques, utilisées pour stocker les mots de passe ou assurer l'authenticité des données, cette propriété s'écrit : pour tout x dont on connaît le hachage H(x), alors il est très difficile de calculer un y tel que H(x) = H(y).

[modifier] Tables de hachage et structures de données

Les fonctions de hachage ne sont pas nécessairement destinées à de la cryptographie. On les utilise fréquemment dans des structures de données : les tables de hachage. Le principe est d'attribuer à chaque « case » de la table, un index obtenu via le hachage d'une « clé » qui est souvent une chaîne de caractères. En fournissant la clé et en la hachant à nouveau, on peut aller lire l'élément correspondant. Toutefois, des collisions existent car les fonctions de hachage utilisées ne sont pas très robustes. De plus, la taille des tables étant limitée, l'espace ainsi disponible est fortement limité. Des techniques destinées à lever ces conflits sont nécessaires. On utilise en particulier 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 devra alors parcourir la liste chaînée jusqu'à trouver 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).

[modifier] Fonction de hachage cryptographique

Une fonction de hachage cryptographique est utilisée entre autres pour la signature électronique, et rend également possible 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é et de sa signature, 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 » que ce soit au niveau algorithmique ou matériel. 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 ((en) Practical Attacks on Digital Signatures Using MD5 Message Digest).

[modifier] 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^[1] 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 signatures, il est possible de savoir si deux échantillons correspondent à la même séquence sonore.

Il est à noter que ces techniques, alliées au tatouage numérique, sont principalement destinées à lutter contre le piratage, la contrefaçon et toutes les autres infractions liées au copyright. Elles sont également intéressantes pour gérer des bases de données et trouver rapidement des échantillons présentants de fortes similitudes.

[modifier] Utilisation

[modifier] Traduction de brochures techniques

Imaginons traduire d'anglais en français un ouvrage, par exemple Perl version 5. Quand arrivera sa suite Perl version 6, on sait d'ores et déjà que sans doute 60% ou plus des phrases de l'ancienne version seront présentes - éventuellement placées ailleurs - dans la nouvelle. On procède donc de la façon suivante :

Chaque traducteur traduit sur le réseau, phrase par phrase (dans leur contexte) le livre Perl 5.
La signature (hash) de chaque phrase anglaise d'origine est calculée.
On stocke dans une base de données (voire un simple fichier à accès direct) l'information phrase anglaise + phrase française, indexée par cette signature qui sert donc de clé.
La signature de chaque phrase à traduire est calculée et, si la phrase correspondante existe dans la base de données, la traduction existante proposée en préremplissage au traducteur.

Ce procédé fait déjà gagner du temps lors de la première traduction (Perl 5). Il en fera gagner encore plus avec la suivante sur un livre comprenant beaucoup de phrases dont beaucoup ont été déjà traduites (Perl 6).

[modifier] 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 demandé. 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 (compromis des deux précédentes)

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 SHA2 (256, 384 ou 512 bits au choix) est d'ores et déjà prêt s'il faut abandonner aussi le SHA-1.

[modifier] Voir aussi

[modifier] Bibliographie

↑ Robust Audio Hashing for Content Identification (2001) Jaap Haitsma, Ton Kalker and Job Oostveen, Philips Research, International Workshop on Content-Based Multimedia Indexing (CBMI'01)

Fonctions de hachage cryptographiques

Modifier