Fonction de hashage

Fonction de hashage

Fonction de hachage

On nomme fonction de hachage une fonction particulière qui, à partir d'une donnée fournie en entrée, calcule une empreinte servant à identifier rapidement, bien qu'incomplètement, la donnée initiale. Les fonctions de hachage sont utilisées en informatique et en cryptographie.

Exemple de fonction de hachage appliquée sur 3 entrées distinctes.

Sommaire

Terminologie

Le résultat d'une fonction de hachage peut être appelé selon le contexte somme de contrôle, empreinte, résumé de message, condensé, condensat ou encore empreinte cryptographique lorsque l'on utilise une fonction de hachage cryptographique. On l'appelait autrefois aussi signature, mais cette terminologie est moins utilisée afin d'éviter une confusion avec son sens juridique : le hachage est en effet aussi employé pour les signatures numériques.

Utilité

Les fonctions de hachage servent à rendre plus rapide l'identification des données : calculer l'empreinte d'une donnée ne doit coûter qu'un temps négligeable. 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.

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 8 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.

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 clé 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, l'identité n'est pas encore prouvée ; mais la comparaison octet par octet n'aura plus à se faire que sur le sous-ensemble bien plus restreint de fichiers qui ont la même empreinte.

Selon l'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) entraine une perturbation importante de l'empreinte correspondante, rendant une recherche inverse par approximations successives impossible : on parle d'effet avalanche.

Considérations mathématiques

Une fonction de hachage aura typiquement un ensemble de définition infini, par exemple les chaînes de caractères, de tailles arbitraires, et un ensemble d'arrivée fini, fixé d'avance, comme par exemple une séquence de bits de taille fixe.

Une fonction de hachage est dite parfaite pour un ensemble S si elle est une injection de S dans N. Elle est dite minimale si elle est parfaite de S dans [ 0, |S| - 1 ]. Enfin, une fonction de hachage h peut préserver l'ordre, c’est-à-dire que x \le y \Leftrightarrow h(x) \le h(y).

Un exemple classique de fonction de hachage est la fonction modulo n : Si on dispose d'un grand nombre de données, à ordonner dans un tableau de n cases, on pourra ranger l'élément numéro i dans la case n°(i modulo n). Ainsi, pour aller chercher notre donnée, nous n'avons plus besoin de parcourir tous les élèments jusqu'à trouver l'élèment n°i : Il suffit de parcourir les élèments contenus dans la case n°(i modulo n). Si les données initiales étaient réparties uniformément, le temps de recherche en moyenne est divisé par n.

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é de 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 \scriptstyle 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.

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 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).

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[1].

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[2] 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.

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ésentants de fortes similitudes.

Salage

Le salage (salting en anglais) d'une fonction de hachage permet de renforcer la sécurité de cette fonction. En effet, des crackers malins peuvent construire des tables de hachage correspondant à des valeurs (par exemple, des mots de passe) souvent utilisées, ce qui leur permet de cracker les résultats de hachage et de récupérer les informations qui doivent rester secrètes.

Le salage permet d'éviter ce genre de pratique, il consiste à ajouter une chaîne de caractères à l'information avant le hachage. Par exemple, dans le cas du hachage d'un mot de passe, on peut concaténer l'identifiant (login) au mot de passe, puis y concaténer une chaîne de caractères avant le hachage. On obtient ainsi une fonction de hachage salé beaucoup plus difficile à cracker. Pour avoir un salage ultime ou incracable, (sauf bien sur avec l'attaque par force brute consistant à tester toutes les valeurs possibles - cette méthode prend tellement de temps avec un bon mot de passe que l'on ne peut plus qualifier cela de crackage), on doit ajouter une chaîne aléatoire au mot de passe avant d'appliquer la fonction de hachage, par exemple, on concatène l'identifiant et le mot de passe, on hache le tout avec du SHA-1, on concatène le résultat à l'identifiant et au mot de passe non hachés et on hache le tout avec du MD5.

Le salage est particulièrement efficace pour lutter contre les attaques faites avec des tables arc-en-ciel qui sont des tables de haches précalculés permettant de retrouver un mot de passe haché dans des délai très courts. Le simple ajout d'un sel au hache rend l'utilisation de ces tables caduque.

Utilisations

Les fonctions de hachages sont couramment utilisées par les logiciels informatiques, leur fonction peut varier suivant les cas.

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 :

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.

Somme de contrôle

Article détaillé : Somme de contrôle.

Table de hachage

Article détaillé : Table de hachage.

Notes et références

  1. ↑ (en)Ondrej Mikle Practical Attacks on Digital Signatures Using MD5 Message Digest
  2. ↑ 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)

Voir aussi

Articles connexes

Wiktprintable without text.svg

Voir « hash » sur le Wiktionnaire.

Lien externe


Fonctions de hachage cryptographiques
Modifier
Algorithmes : AR | Boognish | FFT-hash | HAS-160 | Haval | MD2 | MD4 | MD5 | MD6 | N-hash | PANAMA | RIPEMD | RIPEMD-128 | RIPEMD-160 | RIPEMD-256 | SHA-0 | SHA-1 | SHA-224 | SHA-256 | SHA-384 | SHA-512 | Snefru | StepRightUp | Tiger | VSH | Whirlpool
Cryptanalyse : Paradoxe des anniversaires | Linéaire / Différentielle  | Attaque par force brute | Effet avalanche | Pseudo-collision

Architecture : Remplissage | Fonction de compression | Construction de Merkle-Damgard | Construction de Miyaguchi-Preneel | Construction de Matyas-Meyer-Oseas | Construction de Davies-Meyer


Crypto key.png Générateurs de nombres pseudo-aléatoires
Modifier
Rapides : Générateur congruentiel linéaire, Mersenne Twister, RANDU
Cryptographiques : Blum Blum Shub, Fortuna, ISAAC, Yarrow
Briques : Congruence sur les entiers, Fonction de hachage, Registre à décalage
Voir aussi le portail de la cryptologie
  • Portail de la cryptologie Portail de la cryptologie
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Fonction de hachage ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction de hashage de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Hashage — Fonction de hachage On nomme fonction de hachage une fonction particulière qui, à partir d une donnée fournie en entrée, calcule une empreinte servant à identifier rapidement, bien qu incomplètement, la donnée initiale. Les fonctions de hachage… …   Wikipédia en Français

  • Table de hashage — Table de hachage En informatique, une table de hachage est une structure de données qui permet une association clé élément, c est à dire une implémentation du type abstrait table de symboles. On accède à chaque élément de la table via sa clé. Il… …   Wikipédia en Français

  • Partition (base de données) — Pour les articles homonymes, voir Partition. Dans une base de données, une partition est une division logique d une table stockée en plusieurs parties indépendantes. Le partitionnement de tables est généralement effectué pour améliorer la gestion …   Wikipédia en Français

  • Adler-32 — est une fonction de hashage inventée par Mark Adler et dérivée de la fonction de Fletcher. Sommaire 1 Caractéristiques 2 Algorithme[2] 2.1 Optimisation …   Wikipédia en Français

  • Authentification HTTP — HTTP Authentification L identification (ou authentification) HTTP (spécifiée par [RFC 2617]) permet de s identifier auprès d un serveur HTTP en lui montrant que l on connaît le nom d un utilisateur et son mot de passe, afin d accéder aux… …   Wikipédia en Français

  • HTTP Authentification — L identification (ou authentification) HTTP (spécifiée par [RFC 2617]) permet de s identifier auprès d un serveur HTTP en lui montrant que l on connaît le nom d un utilisateur et son mot de passe, afin d accéder aux ressources à accès restreint… …   Wikipédia en Français

  • APR1 — Usage APR 1 est une fonction de hashage utilisé par les serveurs Apache pour chiffrer les mots de passe .htaccess. Il se sert de MD5 comme base. Le résultat est structuré comme suit : $apr1$ SALT $ HASH Le sel fait 8 caractères et le hash 22 …   Wikipédia en Français

  • Hash consing — Partage maximale En informatique, le partage maximale, ou hash consing est une technique utilisée pour économiser de la mémoire, ou plus rarement du temps de calcul. Il s agit, lorsqu une structure de données est créé, de vérifier si une… …   Wikipédia en Français

  • Partage maximale — En informatique, le partage maximale, ou hash consing est une technique utilisée pour économiser de la mémoire, ou plus rarement du temps de calcul. Il s agit, lorsqu une structure de données est créé, de vérifier si une structure de donnée égale …   Wikipédia en Français

  • Signature numérique — Pour les articles homonymes, voir Signature (homonymie). La signature numérique (parfois appelée signature électronique) est un mécanisme permettant de garantir l intégrité d un document électronique et d en authentifier l auteur, par analogie… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”