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.

Une fonction de hachage cryptographique est une fonction de hachage qui, à une donnée de taille arbitraire, associe une image de taille fixe, et dont une propriété essentielle est qu'elle est pratiquement impossible à inverser, c'est-à-dire que si l'image d'une donnée par la fonction se calcule très efficacement, le calcul inverse d'une donnée d'entrée ayant pour image une certaine valeur se révèle impossible sur le plan pratique. Pour cette raison, on dit d'une telle fonction qu'elle est à sens unique.

En raison de leur ubiquité, ces fonctions à sens unique ont été appelées les chevaux de trait de la cryptographie moderne. La donnée d'entrée de ces fonctions est souvent appelée message ; la valeur de sortie est souvent appelée valeur de hachage , empreinte numérique, empreinte, ou encore haché (en anglais, message digest ou digest, hash).

Une fonction de hachage cryptographique idéale possède les quatre propriétés suivantes :

• la valeur de hachage d'un message se calcule « très rapidement » ;
• il est, de fait, impossible, une valeur de hachage étant donnée, de construire un message ayant cette valeur de hachage ;
• il est, de fait, impossible de modifier un message sans changer sa valeur de hachage ;
• il est, de fait, impossible de trouver deux messages différents ayant la même valeur de hachage.

Les fonctions de hachage cryptographiques ont de nombreuses applications en sécurité informatique, notamment dans les signatures numériques, les codes d'authentification de message et les autres formes d'authentification.

Les fonctions Secure Hash Algorithm du NIST sont des exemples de fonctions de hachage cryptographiques.

Propriétés

La plupart des fonctions de hachage cryptographiques sont conçues pour prendre une suite de bits de longueur quelconque en entrée (éventuellement la longueur est bornée, mais la borne est très élevée), et produire une valeur de hachage de longueur fixe en sortie.

Une fonction de hachage cryptographique doit être capable de résister à tous les types connus d'attaque cryptanalitique. Au minimum, elle doit avoir les propriétés suivantes :

résistance à la préimage (en anglais, preimage resistance ) : pour toute valeur de hachage h, il devrait être difficile de trouver un message m tel que h = hash (m) ; cette notion est liée à la notion de fonction à sens unique ; les fonctions qui n'ont pas cette propriété sont vulnérables aux attaques de préimage (en anglais, preimage attack (en) ;

résistance à la seconde préimage (en anglais, second preimage resistance ) : pour toute entrée m1, il devrait être difficile de trouver une entrée différente m2 telle que hash(m1) = hash(m2) ; les fonctions qui n'ont pas cette propriété sont vulnérables aux attaques de seconde préimage (en anglais, second-preimage attacks) ;

résistance aux collisions : il doit être difficile de trouver deux messages différents m1 et m2 tels que hachage (m1) = hachage (m2) ; une telle paire de messages est appelée une collision de hachage cryptographique ; pour obtenir cette propriété, il faut une valeur de hachage au moins deux fois plus longue que celle requise pour obtenir la résistance à la préimage ; si la clé n'est pas assez longue, une collision peut être trouvée par une attaque des anniversaires.

Ces propriétés impliquent qu'un adversaire malveillant ne peut pas remplacer ou modifier les données d'entrée sans changer son empreinte numérique. Ainsi, si deux chaînes ont la même empreinte numérique, on peut être très confiant qu'ils sont identiques.

Une fonction qui possède ces trois propriétés peut tout de même avoir des propriétés indésirables. Actuellement, des fonctions populaires de hachage cryptographique sont vulnérables à des attaques qui allongent la longueur du message : en effet, si hash(m) et la longueur de m sont connus, en choisissant un m' approprié, un attaquant peut calculer hachage(m||m') [où || désigne la concaténation]. Cette particularité peut être utilisée pour briser des algorithmes d'authentification fondés sur des fonctions de hachage. La code Keyed-Hash Message Authentication (HMAC) permet de corriger cette faiblesse.

On pourrait augmenter la sécurité des fonctions de hachage cryptographiques en exigeant des propriétés additionnelles pour ces fonctions. Par exemple,

il est impossible de trouver deux messages ayant des empreintes numériques semblables;

il est impossible de déduire quelque information que ce soit d'un message à partir de son empreinte numérique.

Les algorithmes de somme de contrôle (checksum), comme CRC32 et d'autres contrôles de redondance cyclique, sont conçus pour répondre à des exigences beaucoup plus faibles et sont généralement inadéquats comme fonctions de hachage cryptographique. Par exemple, un CRC a été utilisé pour vérifier l'intégrité des messages dans la norme de cryptage WEP, mais une attaque qui exploitait la linéarité de la somme de contrôle a été rapidement découverte.

Degré de difficulté

Dans la pratique de la cryptographie, difficile signifie généralement au-delà de la portée de tout adversaire, et cela aussi longtemps que la sécurité du système est jugée importante. La signification du terme est dépendante de la valeur de l'information à protéger, puisque l'effort qu'un agent malveillant peut mettre à la tâche est généralement proportionnel à son espérance de gain. L'évaluation de la puissance de traitement d'un adversaire doit aussi tenir compte de la période de temps durant laquelle l'information doit être protégée. En effet, comme les connaissances cryptographiques et la puissance de traitement des ordinateurs augmentent rapidement, il faut tenir compte de ce fait pour estimer les capacités d'un adversaire dans 10 ou 20 ans. Toutefois, étant donné que l'effort nécessaire pour briser un message augmente très rapidement avec la longueur de la valeur de hachage, même une augmentation par un facteur de mille de la puissance de traitement peut être neutralisée par l'addition d'une dizaine de bits à la valeur de hachage.

Dans certaines analyses théoriques, difficile a le sens mathématique spécifique suivant pas résoluble dans un temps polynomial asymptotique. Cette définition de difficile est importante dans l'étude des fonctions de hachage cryptographiques prouvablement sécurisées, mais n'est généralement pas un gage de sécurité dans la pratique. Par exemple, un algorithme de temps exponentiel peut parfois être résoluble assez rapidement pour permettre une attaque. À l'inverse, un algorithme de temps polynomial (par exemple, celui qui nécessite n étapes pour une clé de n chiffres) peut être trop lent pour une implantation pratique.

Illustration

Voici un exemple d'utilisation d'un hachage cryptographique :

Alice propose un problème difficile de mathématiques à Bob, prétend qu'elle l'a résolu et défie Bob de le résoudre ;

Bob veut bien essayer, mais il veut s'assurer qu'Alice ne bluffe pas ;

pour prouver sa bonne foi, Alice écrit sa solution, calcule la valeur de hachage de sa solution et donne à Bob la valeur de hachage (tout en gardant sa solution secrète) ;

lorsque Bob arrive avec sa solution quelques jours plus tard, Alice peut prouver qu'elle connaissait la solution avant la communication de Bob en révélant sa solution à Bob ;

Bob peut vérifier que la solution d'Alice a été écrite avant la communication de sa solution en calculant la valeur de hachage de la solution d'Alice et en comparant cette valeur avec la valeur fournie par Alice.

Le scénario précédent est un exemple d'une mise en gage simple. Dans la pratique, Alice et Bob seraient souvent des programmes informatiques et le secret serait quelque chose de moins facilement usurpée qu'une solution de puzzle.

Applications

Vérification de l'intégrité des fichiers ou des messages

Une application importante du hachage cryptographique est la vérification de l'intégrité d'un fichier (ou d'un message). Par exemple, la modification d'un fichier lors d'une transmission (ou toute autre activité) peut être prouvée en comparant la valeur de hachage du fichier avant et après la transmission.

En pratique, la plupart des algorithmes de signature numérique d'un fichier ne vérifient pas que le fichier n'a pas été changé, mais bien que la valeur de hachage du fichier n'a pas changé. Toutefois, à cause des caractéristiques des fonctions de hachage cryptographiques, la vérification de la valeur de hachage est considérée comme la preuve que le fichier lui-même est authentique.

Des valeurs de hachage obtenues par les algorithmes MD5, SHA-1 ou SHA-2 sont parfois affichées avec les fichiers correspondants sur des sites Web ou des forums informatiques pour permettre la vérification de l'intégrité des fichiers. Cette pratique établit une chaîne de confiance pourvu que les valeurs de hachage soient affichées sur un site sécurisé par HTTPS.

Vérification de mot de passe

Une application associée est la vérification de mot de passe (inventé par Roger Needham (en)). Le stockage de tous les mots de passe utilisateur en clair peut entraîner une violation de sécurité massive si le fichier de mots de passe est compromis. Une façon de réduire ce danger est de stocker seulement la valeur de hachage de chaque mot de passe. Pour authentifier un usager, le mot de passe fourni par l'utilisateur est haché et comparé avec la valeur de hachage stockée. Avec cette approche, les mots de passe perdus ne peuvent pas être récupérés s'ils sont oubliés ; ils doivent être remplacés par de nouveaux mots de passe.

Le mot de passe est souvent concaténé avec un sel cryptographique non secret avant que la fonction de hachage soit appliquée. Le sel est stocké avec la valeur de hachage du mot de passe. Parce que les utilisateurs ont différents sels, il est impossible de construire des tables de valeurs de hachage précalculées pour les mots de passe communs. Les fonctions de dérivation de clés, comme PBKDF2, Bcrypt ou Scrypt, typiquement utilisent des appels répétés d'une fonction de hachage cryptographique pour augmenter le temps nécessaire pour effectuer des attaques par force brute sur des valeurs de hachage de mots de passe stockés.

En 2013, une compétition de hachage de mots de passe, intitulée Password Hashing Competition (en) a été annoncée pour choisir un nouvel algorithme standard de hachage de mot de passe. Le 20 juillet 2015, Argon2 a été choisi comme le vainqueur de la compétition. Des mentions de reconnaissance ont aussi été attribuées aux hachages suivants : Catena, Lyra2, Scrypt et Makwa.

Preuve de travail

Une preuve de travail est une mesure économique visant à dissuader les attaques par déni de service et d'autres abus comme le spam en exigeant un travail du demandeur de service. Le travail est habituellement un calcul complexe effectué par un ordinateur. Une caractéristique clé de ces travaux est leur asymétrie : le travail doit être modérément difficile (mais possible) pour le demandeur, mais facile à vérifier pour le fournisseur de service. Un système populaire - utilisé dans le minage de Bitcoins et Hashcash - utilise l'inversion partielle d'une fonction de hachage. Le demandeur doit trouver un message dont la valeur de hachage commence par un certain nombre de bits à zéro. Le travail moyen que l'expéditeur doit effectuer afin de trouver un message valide est exponentiel relativement au nombre de zéros requis au début de la valeur de hachage, alors que le destinataire peut vérifier la validité de la réponse proposée en exécutant une seule fonction de hachage. Ainsi, avec Hashcash, comme un expéditeur doit générer un message dont la valeur de hachage a des zéros dans les 20 premiers bits, il devra en moyenne essayer 2 messages pour trouver un message valide.

Identifiant pour fichier ou données

Une valeur de hachage peut aussi servir comme un moyen d'identifier de manière fiable un fichier ; plusieurs systèmes de gestion de code source, y compris Git, Mercurial et Monotone, utilisent le sha1sum de divers types de contenu (le contenu de fichiers, les arborescences de répertoires, etc.) pour les identifier de manière unique. Les valeurs de hachage sont utilisées pour identifier les fichiers sur les réseaux de partage de fichiers pair-à-pair. Par exemple, dans un lien ed2k, la valeur de hachage d'une variante de MD4 est combinée avec la taille du fichier, fournissant des informations suffisantes pour localiser les sources du fichier, le télécharger et en vérifier le contenu.

L'une des principales applications d'une fonction de hachage est de permettre la consultation rapide d'un élément dans une table de hachage. Étant des fonctions de hachage d'un genre particulier, les fonctions de hachage cryptographiques se prêtent aussi à cette utilisation. Cependant, en comparaison avec les fonctions de hachage standards, les fonctions de hachage cryptographiques sont beaucoup plus coûteuses en calcul. Pour cette raison, elles sont utilisées seulement dans des contextes où il est nécessaire de se protéger contre les risques de falsification (la création de données avec la même valeur de hachage que les données attendues) par des participants potentiellement malveillants.

Génération d'éléments pseudo-aléatoires et dérivation de clés

Les fonctions de hachage cryptographiques peuvent également être utilisées dans la génération de nombres et de suites de bits pseudo-aléatoires, ou pour dériver de nouvelles clés ou de nouveaux mots de passe à partir d'une clé ou d'un mot de passe sécurisé.

一个工作中的密码哈希函数 (特定的, SHA-1)。注意，即使在源输入（在这里的词“over”）的微小变化导致所产生的输出发生急剧变化，通过所谓的雪崩效应。

密码哈希函数（英语：Cryptographic hash function），又译为加密哈希函数、密码散列函数、加密散列函数，是散列函数的一种。它被认为是一种单向函数，要由散列函数输出的结果，回推输入的数据是什么，是非常困难的。这种散列函数的输入数据，通常被称为消息（message），而它的输出结果，经常被称为消息摘要（message digest）或是摘要（digest）。

一个理想的密码哈希函数应该有四个主要的特性：

对于任何一个给定的消息，它都很容易就能运算出哈希数值

由一个已知的哈希数值，去推算出原始的消息，这是不可行的

在不更动哈希数值的前提下，修改消息内容是不可行的

对于两个不同的消息，它不能给与相同的哈希数值

在信息安全中，有许多重要的应用，都使用了密码哈希函数来实作，例如数字签章，消息鉴别码。