Bien utiliser les fonctions de hachage

Une fonction de hachage peut se comparer à un chiffrement, à l'exception près que le résultat obtenu ne peut pas se déchiffrer (en théorie).

Résultat unique

Une bonne fonction de hachage produit un résultat unique à partir d'un bloc de bits, appelé hash, condensat, somme de contrôle, empreinte ou parfois signature. Par exemple, la somme de contrôle MD5 du mot "Bonjour" est ebc58ab2cb4848d04ec23d83f7ddf985 (le résultat est représenté en hexadécimal), et cela sera toujours vrai. Cela peut sembler déroutant, mais certains algorithmes cryptographiques produisent un résultat différent, alors que les données d'entrée ne diffèrent pas. Prenons un exemple avec la fonction crypt() de PHP :

Comportement chaotique

Un bon algorithme de hachage doit normalement produire un résultat radicalement différent pour chaque chaîne, et ce même si très peu de bits diffèrent. Un exemple :

sha1("Bonjour") : f30ecbf5b1cb85c631fdec0b39678550973cfcbc
sha1("Bonjour !") : 245469f3c41b3222441056b6bc6e789710ef2bfb

Comme vous le voyez, les résultats diffèrent beaucoup. C'est parce que les algorithmes de hachage sont conçus pour être chaotiques. Une toute petite modification dans les bits d'entrée, et cela se traduit par d'importantes modifications du résultat final (grâce à l'effet avalanche).


Comme je l'ai déjà dit, un hash ne doit pas pouvoir se déchiffrer. Par exemple, si je vous donne c7b30cf2f79bd81c7ed59f1cc603d4760e32fb5b, vous ne pouvez pas deviner de quelle chaîne ce hash a été produit. Ce comportement est donc très pratique, car il empêche la cryptanalyse classique qui se base sur la fréquence d'apparition des lettres, et d'autres subtilités. Le seul moyen de retrouver les bits d'entrée est d'employer la méthode de la force brute (tester toutes les possibilités une par une et comparer).

Un algorithme de hachage est considéré comme chaotique si, pour un seul bit changé en entrée, il y a plus d'une chance sur deux que chaque bit de sortie soit modifié.

Les collisions

Vous avez tout à fait raison. Une bonne fonction de hachage doit également résister aux collisions : ce phénomène se produit quand le même hash est obtenu avec deux chaînes de bits différents en entrée.

Les collisions sont assez problématiques : en effet, le but premier d'une fonction de hachage, c'est à dire d'obtenir une empreinte unique en fonction d'une entrée, est perdu ! C'est dommage

Imaginions que vous vouliez télécharger des données (une image ISO de FreeBSD par exemple). Comme vous ne voulez pas gâcher vos CDs, vous vérifiez que l'image téléchargée n'est pas corrompue. Vous calculez donc la somme de contrôle MD5. Par chance, cela correspond à ce qu'il y a d'indiqué sur le site officiel. Vous tentez d'utiliser votre CD-rom fraîchement gravé, cependant ça ne fonctionne pas. Pourquoi ?



Pour remplacer l'algorithme MD5, il existe SHA-1, SHA-256 ou encore Whirlpool. Cependant, sur Internet, MD5 est encore prédominant

Maintenant que vous savez parfaitement ce qu'est une fonction de hachage, on va pouvoir attaquer la partie amusante : les utilisations

Stocker des données sans les afficher en clair

C'est l'utilisation typique des fonctions de hachage. Pour expliquer, on va prendre un exemple : vous avez un site Internet. Cependant, vous êtes soucieux de la sécurité des mots de passe de vos membres, donc vous stockez dans votre base de donnée la somme de contrôle du mot de passe. Cela permet de stocker le mot de passe, sans pour autant l'afficher en clair. Grâce à la propriété d'impossibilité du déchiffrement théorique des fonctions de hachage, personne ne peut retrouver le mot de passe original ! Lorsque le membre tape son mot de passe, il suffit juste de hacher de la même manière ce qu'il a tapé, et de comparer avec la vraie somme de contrôle. Comme les fonctions de hachage produisent un résultat unique pour la même entrée, les sommes de contrôle correspondront si le bon mot de passe a été tapé.

Vérifier l'intégrité d'un fichier

Comme on l'a déjà vu plus haut, il peut être utile de vérifier qu'un fichier téléchargé correspond bien à un fichier d'origine (ou n'importe quel autre fichier, d'ailleurs). En général, un téléchargement corrompu ne diffère que du vrai téléchargement que par quelques bits. Un exemple :



Notre fichier corrompu ne diffère pas beaucoup, cependant, il y a de forte chances que le fichier ne se comporte pas comme prévu. Si c'est un fichier texte, pas de grand problème : deux ou trois caractères seront affectés (voir plus). Si c'est une archive en revanche, impossible de la décompresser !

On se sert donc ici principalement de l'effet chaotique des fonctions de hachage pour détecter toute modification (même moindre) entre les deux fichiers. Étant donné que des modifications mineures des bits d'entrée produisent une sortie très différente, on peut facilement déterminer si le fichier est corrompu ou non.

Générer des nombres pseudo-aléatoires

Eh oui ! De par leur comportement chaotique, les fonctions de hachage sont d'excellents générateurs de nombres aléatoires. Il suffit juste de calculer la somme de contrôle de bits arbitraires (généralement fournis par un autre générateur de nombre pseudo-aléatoires) afin d'obtenir une valeur pseudo-aléatoire.



En théorie, il est impossible pour un ordinateur de calculer des nombres "vraiment" aléatoires. Le vrai hasard ne peut pas exister : un ordinateur ne fait que calculer des nombres, après tout. Aucun hasard là dedans. Pour obtenir un nombre pseudo-aléatoire, on doit donc appliquer un algorithme très chaotique (tiens donc, ça ne vous rappelle pas quelque chose ? ) sur des valeurs qui changent fréquemment : cette entropie est apportée par les temps d'accès aux disques, les mouvements de votre souris, les touches pressées sur votre clavier, l'activité du réseau, ...

Faisons un petit test : on calcule la somme de contrôle d'une chaîne avec différents algorithmes de hachage un très grand nombre de fois, et on compare la fréquence d'apparition des nombres (de 0 à F, nous sommes en hexadécimal).

Fonction de hachage : md5, 320000 caractères, 10000 itérations

0 : trouvé 20035 fois (6.26 %)
1 : trouvé 20026 fois (6.26 %)
2 : trouvé 19665 fois (6.15 %)
3 : trouvé 19996 fois (6.25 %)
4 : trouvé 20156 fois (6.3 %)
5 : trouvé 19744 fois (6.17 %)
6 : trouvé 20181 fois (6.31 %)
7 : trouvé 19898 fois (6.22 %)
8 : trouvé 19998 fois (6.25 %)
9 : trouvé 19994 fois (6.25 %)
a : trouvé 20202 fois (6.31 %)
b : trouvé 19929 fois (6.23 %)
c : trouvé 19950 fois (6.23 %)
d : trouvé 19847 fois (6.2 %)
e : trouvé 20284 fois (6.34 %)
f : trouvé 20095 fois (6.28 %)

Fonction de hachage : sha1, 400000 caractères, 10000 itérations

Fonction de hachage : sha512, 1280000 caractères, 10000 itérations

0 : trouvé 80406 fois (6.28 %)
1 : trouvé 80311 fois (6.27 %)
2 : trouvé 79880 fois (6.24 %)
3 : trouvé 80208 fois (6.27 %)
4 : trouvé 79253 fois (6.19 %)
5 : trouvé 80108 fois (6.26 %)
6 : trouvé 80213 fois (6.27 %)
7 : trouvé 79754 fois (6.23 %)
8 : trouvé 80400 fois (6.28 %)
9 : trouvé 79777 fois (6.23 %)
a : trouvé 79778 fois (6.23 %)
b : trouvé 80251 fois (6.27 %)
c : trouvé 80202 fois (6.27 %)
d : trouvé 79657 fois (6.22 %)
e : trouvé 79926 fois (6.24 %)
f : trouvé 79876 fois (6.24 %)

Fonction PHP : rand(), 320000 itérations

0 : trouvé 19851 fois (6.2 %)
1 : trouvé 19870 fois (6.21 %)
2 : trouvé 19878 fois (6.21 %)
3 : trouvé 19928 fois (6.23 %)
4 : trouvé 19936 fois (6.23 %)
5 : trouvé 19941 fois (6.23 %)
6 : trouvé 19948 fois (6.23 %)
7 : trouvé 19960 fois (6.24 %)
8 : trouvé 19997 fois (6.25 %)
9 : trouvé 20006 fois (6.25 %)
a : trouvé 20008 fois (6.25 %)
b : trouvé 20052 fois (6.27 %)
c : trouvé 20052 fois (6.27 %)
d : trouvé 20054 fois (6.27 %)
e : trouvé 20229 fois (6.32 %)
f : trouvé 20290 fois (6.34 %)

Que peut-on en dire ? Que les algorithmes de hachage passent tous le test statistique haut la main !

Le résultat donné par la fonction rand() de PHP est surprenant : les pourcentages sont croissants. C'est bien la preuve que les nombres générés ne sont pas réellement aléatoires.

Pour conclure, l'utilité des fonctions de hachage est très diverse et mérite beaucoup d'attention.

Maintenant, place à la pratique

Nous allons hasher correctement des mots de passe d'utilisateurs (sur un site web, un serveur, ...).

Intuitivement ou bête recopiage pompé d'un cours, vous aurez sans doute pensé à hasher simplement le mot de passe avec MD5. Cette méthode n'est pas mauvaise mais je vous la déconseille. En effet, plusieurs problèmes se posent :

• Comme je vous l'ai dit, retrouver ce qui se cache derrière un MD5 est très facile en interrogeant des serveurs contenant des mots et leur MD5 associé. Ceci sera sans doute vrai dans le futur pour les autres fonctions de hachage comme SHA-1, ...
• Si deux utilisateurs ont le même mot de passe, l'empreinte stockée sera identique et c'est un gros problème pour la sécurité...

Il y a plusieurs solutions qui permettent de renforcer la sécurité que nous proposent ces fonctions. Une première consiste à utiliser du sel, c'est à dire une chaîne auxiliaire qu'on mélangera au mot de passe (en concaténant par exemple). Ce sel doit différer pour chaque utilisateur, sinon l'effet est perdu. On peut par exemple prendre le nom d'utilisateur, ou une valeur aléatoire stockée au hasard. On peut aussi combiner les fonctions de hachage : voici des exemples.



Grâce à ces deux méthodes, on peut voir que la sécurité est au rendez-vous : Anna et Steve ont le même mot de passe, cependant le hash est différent. De plus, même si on essaie de retrouver le mot de passe par force brute, on ne peut pas car il est impossible de distinguer le sel du mot de passe (cela est surtout vrai lorsque le mélange entre le sel et le mot de passe est plus complexe qu'une simple concaténation, et encore plus quand le sel est très long).

Cette méthode n'excuse cependant en aucun cas Anna et Steve pour leur choix de mot de passe. Un bon mot de passe sera toujours mieux qu'un mauvais.

Les fonctions de hachage ne sont qu'une toute petite partie du monde de la cryptographie. Si ce tutoriel vous a intéressé, vous serez probablement interessé dans :

• Le chiffrement symétrique
• Le chiffrement asymétrique

Il existe des algorithmes de chiffrement dérivés de fonctions de hachage, par exemple SHACAL (qui dérive de SHA-1).

Voici divers liens :

• Article "Somme de contrôle" sur Wikipédia
• Article "Algorithme de hachage" sur Wikipédia
• Articles "SHA-1", "MD5", et "Whirlpool" sur Wikipédia
• Articles "Chiffrement Symétrique", "Chiffrement Asymétrique" sur Wikipédia
• Cet excellent tutoriel expliquant l'algorithme de chiffrement asymétrique RSA

(Note : les liens mènent vers les articles anglais, car ils sont plus complets.)

En fin de compte, que choisir ?

C'est une question de choix. MD5 est à bannir, sauf si la sécurité n'est vraiment pas une priorité (ni une nécessité).

Il est préférable de se tourner vers des algorithmes récents. SHA-1 est actuellement sûr, cependant il risque de ne plus l'être à long terme. Je vous conseille donc d'utiliser par exemple SHA-512 ou bien Whirlpool.