{"partition": "head_middle", "source_domain": "fr.wikibooks.org", "digest": "sha1:AYXPNWTCZPKP3SUX4Y5T7RSUYJRWQJKN", "path": "/lustre/fsn1/projects/rech/qgz/uzq54wg/processed_redpajama/base_processing/output/fr/2014-15/000_00007.parquet"}
Les fonctions de hachage cryptographiques
Un livre de Wikilivres.
Schéma d'un tour de MD5
On rencontre bien souvent sur les pages de téléchargement des empreintes calculées grâce à des algorithmes comme MD5. Ces « résumés » des fichiers permettent notamment de vérifier la validité et l'intégrité des archives récupérées. Cependant, peu d'utilisateurs connaissent le fonctionnement de ces primitives, les fonctions de hachages, qui sont très répandues. Nous nous intéresserons principalement aux fonctions de hachages dites cryptographiques qui touchent un vaste domaine d'applications. Dès la fin des années 1990, certaines fonctions de hachage populaires ont été analysées puis « cassées ». Cet article examine les enjeux liés à ces algorithmes et leur fonctionnement.
2 Définition
3 Les fonctions de hachage dans les structures de données
4 Vers des fonctions plus robustes
5 Les systèmes de mots de passe
5.1 Stimulation/réponse
6 Le paradoxe des anniversaires
6.1 Application dans le cadre du hachage
7 Fonctionnement de MD5
7.1 Cryptanalyse
8 Présentation de SHA-1
9 Conséquences et autres attaques
Introduction[modifier | modifier le wikicode]
Dans cet article, nous utiliserons tantôt les termes empreinte ou condensé pour désigner le même concept. On rencontre aussi le terme signature (numérique) qui a un sens plus large car il est normalement lié à un utilisateur. Cette appellation est plutôt utilisée dans le cadre de la cryptographie asymétrique (signature d'un document via une clé privée avec par exemple GnuPG) mais sous certaines conditions, ce mot s'applique aussi aux fonctions de hachage.
Les auteurs de logiciels proposent souvent des empreintes sur les pages dédiées aux téléchargements, on rencontre des fichiers portant l'extension md5 ou sha1 qui contiennent de telles séquences. En comparant l'empreinte de la version téléchargée avec l'empreinte disponible sur le site, l'utilisateur peut s'assurer que sa version n'a pas été corrompue (erreurs de transmission, virus, etc.). Ces condensés sont pour la plupart calculés grâce aux outils md5sum ou sha1sum qui font partie des GNU Core-utils (un ensemble de programmes indispensables pour gérer un système GNU/Linux).
Par exemple, sur le site de la distribution Fedora, on peut lire ceci dans la section téléchargement :
FC3-i386-disc1.iso (md5sum : db8c7254beeb4f6b891d1ed3f689b412)
Après avoir téléchargé l'iso, on peut lancer l'utilitaire md5sum sur le fichier et on devrait retrouver exactement cette séquence. Si la suite varie, ne serait-ce qu'à un seul endroit, alors nous avons affaire à un fichier corrompu ou incomplet. Il est en effet extrêmement peu probable d'obtenir la même empreinte avec deux fichiers différents, nous reviendrons sur ce point essentiel plus tard. Nous allons également voir que les fonctions de hachage ne se limitent pas seulement à cette application.
Définition[modifier | modifier le wikicode]
Les programmes comme md5sum ou sha1sum" utilisent ce que l'on appelle une fonction de hachage. Il y a en fait deux catégories principales de fonctions de hachage, celles qui sont cryptographiques et les autres. Les fonctions de hachage cryptographiques doivent satisfaire des contraintes liées à la sécurité. MD5 et SHA-1 sont cryptographiques mais il en existe bien d'autres. Les premières fonctions de hachage en tant que telles datent de la fin des années 1980 (MD2) mais l'idée est plus ancienne et, toute précaution gardée, a germé dès l'apparition des codes correcteurs d'erreurs dans le cadre de la théorie de l'information. En effet, une somme de contrôle comme CRC-32 (code de redondance cyclique) s'apparente à une fonction de hachage puisqu'elle permet de vérifier la validité des données. La principale différence, c'est que la somme de contrôle est utilisée pour corriger une mauvaise transmission sur un canal bruité, « sans intelligence », alors que les fonctions de hachage doivent résister à des attaques mathématiques ciblées et d'autres tentatives malveillantes dotées d'une « intelligence » (ie. lancées sciemment par l'attaquant).
Une fonction de hachage prend en entrée un message de taille quelconque, applique une série de transformations et réduit ces données. On obtient à la sortie une chaîne de caractères, le condensé qui résume en quelque sorte le fichier. Cette sortie a une taille fixe qui varie selon les algorithmes (128 bits pour MD5 et 160 bits pour SHA-1). Vous aurez remarqué que la séquence calculée par md5sum est codée en hexadécimal, ceci dans le but de limiter la longueur de la chaîne et faciliter les comparaisons entre les empreintes. Il serait en effet assez pénible de devoir comparer deux suites binaires de 128 caractères.
Une fonction de hachage cryptographique doit aussi satisfaire d'autres contraintes. La première stipule qu'il doit être très difficile de retrouver ou générer un texte à partir de l'empreinte (on parle alors de fonction à sens unique). Par très difficile, on entend que même avec une armée de machines dédiées à cette tâche, il sera impossible d'effectuer une telle extraction en un temps raisonnable. Au passage, on ne voit que trop fréquemment sur des forums des assertions erronées comme mot de passe crypté avec MD5. Une fonction de hachage toute seule n'est pas une primitive pour chiffrer. Cependant, des variantes comme SHACAL (basée sur SHA-1) permettent de travailler en mode chiffrement et donc d'obtenir un algorithme de chiffrement par bloc, réversible pour autant que l'on connaisse la clé. Il est aussi possible d'employer la fonction de hachage comme générateur de nombres pseudo-aléatoires ayant pour graine la clé, et d'effectuer un ou-exclusif avec le texte à chiffrer. On obtient alors un chiffrement de flux.
Une autre caractéristique d'une fonction de hachage cryptographique concerne le comportement de l'empreinte selon le fichier en entrée. La moindre modification dans ce fichier doit engendrer un condensé totalement différent. En outre, le hachage doit rendre impossible la création d'un fichier qui donne la même empreinte qu'un autre. Cette dernière contrainte est cruciale pour assurer l'intégrité d'un fichier. Si elle n'était pas respectée, on pourrait facilement générer un fichier corrompu mais valide aux yeux de l'utilisateur. Toutefois, cela ne veut pas dire que des collisions n'existent pas. Comme une empreinte a une taille fixe et que celle-ci est inférieure à la taille des messages que l'on peut mettre à l'entrée de la fonction, alors il existe nécessairement au moins deux messages qui génèrent la même empreinte. Pour être plus exact, avec des entrées dont la taille n'est pas limitée, il existe une infinité de collisions. La solidité de la fonction repose en partie sur l'impossibilité de trouver de tels conflits en un temps raisonnable.
Les fonctions de hachage dans les structures de données[modifier | modifier le wikicode]
Table de hachage avec des listes chaînées pour gérer les collisions
Cette résistance aux collisions est aussi recherchée dans les langages de programmation et plus particulièrement dans des structures de données nommées « tables de hachage », « dictionnaires » ou « maps ».
Il s'agit de structures qui peuvent être indexées par des objets ou clés. Un objet se voit attribué un numéro idéalement unique obtenu via une fonction de hachage et cet identifiant permet de retrouver l'objet qui lui est associé dans la table. Par exemple en Java, on peut écrire :
url = table.get("Gentoo")
au lieu d'une indexation classique comme
url = table[10].
La chaîne Gentoo sert de clé pour accéder à l'URL. Bien entendu, il faut éviter que deux objets distincts entrent en collision et accèdent à la même entrée dans la table. Grâce à une fonction de hachage la plus robuste possible sans pénaliser les performances, on évite d�