Fonctions de Hachage

Aujourd'hui alors que je lisais le document d'un collègue parlant de la nouvelle attaque permettant de faire un rogue CA à partir de la vulnérabilité du MD5, je réalise que j'ai de nombreuses lacunes sur les fonctions de hachage. Ce billet permet donc de faire une petite introduction sur ces fonctions.

Une fonction de hachage qu'est ce que c'est ? C'est une fonction qui prend en entrée une donnée et qui calcule son empreinte, un petit peu comme l'empreinte digitale d'un doigt. Cette empreinte est une suite d'information caractéristique de la donnée initiale.

Les fonctions de hachage sont à sens unique, ce qui veut dire qu'à partir de l'empreinte, il est impossible de revenir aux données initiales. En d'autres termes, si x représente les données et f() une fonction de hachage, alors il n'existe pas de fonction f-¹() permettant à partir de f(x) de revenir x.

Ceci est assez simple à comprendre. Supposons que notre fonction f() ait comme sortie une empreinte de 128 bits (donc 2¹²⁸ empreintes différentes). Si on calcule f(x) pour x allant de 0 à 2¹²⁸ (donc 2¹²⁸+1 valeurs différentes), il y aura au minimum deux f(x) identiques pour deux x différents.

L'autre particularité importante de la fonction de hachage et qu'il est très difficile de trouver une valeur y qui a comme caractéristique que f(y) = f(x) pour x différent de y. Dans le cas idéal, il faudrait brute forcer la valeur de y (c'est à dire tester en moyenne 2¹²⁸/2=2¹²⁷ possibilités) pour trouver un f(y) = f(x) pour un x donné. Le "pour un x donné" est très important car si x n'est pas fixé, d'après le paradoxe des anniversaires, trouver n'importe quel couple x,y tel que f(x) = f(y) ne revient à faire "que" 2⁶⁴ opérations (racine carré de 2¹²⁸).

Ok tout ça c'est bien beau mais à quoi servent ces fonctions ? Ces fonctions sont très utilisées en informatique et particulièrement en sécurité. Les algorithmes MD5, SHA... sont des fonctions de hachages.
On trouve souvent le résultat de ces fonctions à coté de fichier que l'on veut télécharger par exemple. Ce résultat permet de s'assurer que le fichier en notre possession est bien conforme. Il suffit de calculer le md5 du fichier que l'on possède. Si les md5 sont les mêmes, on a bien la même version (et on ne possède pas a priori une version vérolée, excepté bien entendu si le pirate a pu modifier le site web et le md5 affiché).
Une autre utilité est par exemple l'utilisation pour stocker des mots de passe. On ne stocke plus le mot de passe, mais le hash du mot de passe. De cette façon si un pirate s'empare du fichier (ou accède à la base de données), il ne s'empare plus du mot de passe, mais seulement de son hash (et comme il est impossible de remonter aux données initiales...). La vérification de ce dernier se faisant du coup en comparant le hash de la chaîne fournie avec la valeur stockée.
Enfin un autre exemple d'utilité est la signature numérique. Quand quelqu'un vous envoie un fichier, il calcule l'empreinte de ce fichier et chiffre cette dernière avec sa clef privé. A la réception, il ne vous reste plus qu'à déchiffrer la signature grâce à la clef publique de l'émetteur et à la comparer avec l'empreinte du fichier. Si c'est la même, alors vous êtes sûrs que le fichier envoyé n'a pas été modifié par une tierce personne, car seul l'émetteur a pu chiffrer l'empreinte (seul détenteur de la clef privé).

Maintenant que se passe-t'il quand la fonction de hachage n'est pas idéale ? On ne peut bien entendu toujours pas remonter aux données pour les raisons évoquées précédemment, mais par contre la difficulté pour trouver un y tel que f(y) = f(x) peut être réduite. C'est ce qui s'est produit pour le md5, puis plus tard pour SHA-1 qui réduit la complexité pour trouver une collision de 2⁸⁰ itérations (car le SHA-1 produit une sortie de 160 bits) à 2⁶⁹ en Février 2005, puis de nouvelles recherches ont prouvé qu'il était encore possible de faire mieux.

Jusqu'à présent les failles découvertes permettaient de simplifier le calcul pour trouver un couple x,y tel que f(x) = f(y). Chose intéressante bien entendu, mais beaucoup moins que trouver un y tel que f(y) = f(x) pour un x donné. Cela reste un premier pas vers le cassage total de l'algorithme.

Aujourd'hui les recherches en cryptanalyse sur le MD5 montrent qu'il est possible de trouver un y tel que f(y) = f(x) avec seulement une partie de x fixée. Alors vous allez dire que ca casse pas trois pattes à un canard quand il s'agit du mot de passe. Dans ce cas là c'est vrai qu'une bonne atttaque par dictionnaire (ou par rainbow tables) sera toujours plus intéressante, mais dans certains cas cela peut avoir des conséquences beaucoup plus génantes.