Plan du site  
pixel
pixel

Articles - Étudiants SUPINFO

C’est quoi le hachage ?

Par Loïc GUERRIER Publié le 31/10/2016 à 06:25:41 Noter cet article:
(0 votes)
Avis favorable du comité de lecture

Introduction

On retrouve les fonctions de hachage dans de nombreuses applications et vous les utilisez tous les jours sans forcément le savoir. Je vais introduire ces notions de hachage par un exemple concret d’utilisation. Et nous verrons ensuite quelques exemples d’applications où le hachage est utilisé. Dans la plupart des cas, les mots de passe sont enregistrés mais personne ne peut les lire. Et en lisant, la phrase qui précède vous vous dites « Mais si les mots de passe sont illisibles, alors comment fait l’ordinateur pour savoir si j’ai saisi le bon mot de passe ? ». Eh bien, c’est ce que je propose que nous regardions ensemble.

Le mauvais exemple :

J’ai bien commencé le paragraphe du dessus par « Dans la plupart des cas … » car ce n’est pas toujours le cas. Oui, parfois, les mots de passe sont enregistrés en clair et sont facilement lisibles par toute personne qui accède au fichier contenant les mots de passe : heureusement c’est de moins en moins le cas ! ( D’ailleurs sur certains sites ou dans certaines entreprises, si vous oubliez votre mot de passe, on peut vous le donner : ce n’est pas très chouette car ça prouve qu’on peut le lire ! ) Et si on représente ça par un schéma, voila ce que cela donne :

Les mots de passe des utilisateurs circulent et sont stockés en clair, il est facile d’accéder au fichier pour lire les mots de passe : c’est très mauvais pour la sécurité.

Utilisation d’une fonction de hachage

Et si nous utilisions une fonction de hachage ? Cette fonction va prendre le texte du mot de passe et le « mouliner » pour obtenir une signature (cette signature est aussi appelée « empreinte »). L’ordinateur ne va pas envoyer le mot de passe au serveur, mais une signature du mot de passe. Le serveur ne va enregistrer le mot de passe mais enregistrera cette signature. Lorsque l’utilisateur se connectera, le serveur ne va pas vérifier si le mot de passe est identique, mais il va vérifier que la signature du mot de passe saisi est bien la même que la signature du mot de passe enregistré. Voyons ce que cela donne avec le même schéma qu’au dessus mais avec utilisation d’une fonction de hachage :

Définition des fonctions de hachage.

Voici la définition d’une fonction de hachage telle que je pourrais la résumer : Une fonction de hachage est une fonction qui va calculer une empreinte (ou signature) unique à partir des données fournies. Une fonction de hachage doit respecter les règles et propriétés suivantes :

Propriétés des fonctions de hachage :

  • La longueur de la signature doit être toujours la même (quelque soit la longueur des données en entrée. Nous verrons plus loin quelles sont les longueurs des empreintes suivants les fonctions de hachage.)

  • Il n’est pas possible de trouver les données originales à partir des empreintes : Les fonctions de hachage ne fonctionnent que dans un seul sens.

  • Il ne doit pas être possible de prédire une signature. (Il n’est pas possible d’essayer d’imaginer ce que pourrait être la signature en examinant les données)

  • Et enfin, évidemment pour des données différentes : les signatures doivent être différentes.

Signature, empreinte ?

A quoi ça sert le hachage ?

Ce qui est intéressant dans le hachage, ce n’est pas les données elles-mêmes mais leurs signatures. Puisque chaque donnée à sa propre signature, on peut se dire que si les signatures sont identiques alors les données sont identiques. Et à l’inverse, si les signatures sont différentes alors les données sont forcément différentes. Donc le hachage est utilisé pour comparer les données (en comparant les signatures).

Quelques utilisations concrètes des fonctions de hachage.

La liste ci-dessous est loin d’être exhaustive, car il existe bien d’autres utilisations des fonctions de hachage, mais ceux-ci sont faciles à comprendre :

  • Comparaison des mots de passe. Nous l’avons vu sur le schéma du dessus. Attention : Ce schéma n’est pas complet, car idéalement, lors l’enregistrement des mots de passes doit utiliser en plus une chaîne complémentaire appelée « sel » : mais ce n’est pas l’objet de cet article.

  • Vérification des données téléchargées. Par exemple, dans certains cas, lorsque vous téléchargez un fichier sur Internet la signature du fichier original est disponible (soit dans un fichier à part, soit directement affichée sur le site). Pour être sûr que le fichier a été correctement téléchargé, il vous suffit de vérifier que la signature du fichier téléchargé est bien identique à celle fournie.

  • La signature électronique (ou signature numérique) des documents. Les documents envoyés sont passés dans une fonction de hachage, et l’empreinte est envoyée chiffrée en même temps que les documents. Il suffit au destinataire de déchiffrer l’empreinte reçue et vérifier que celle-ci correspond bien au calcul de l’empreinte des données reçues.

  • Pour l’utilisation de tables de hachage, utilisées en développement des logiciels.

  • Pour le stockage des données : si la signature d’un fichier est présente, alors on peut dire que le fichier est présent : il n’est pas nécessaire de l’enregistrer à nouveau. Cela peut être intéressant car si le fichier est très gros, il faudra beaucoup moins de temps pour calculer sa signature que de l’enregistrer à nouveau.

C’est quoi les collisions ?

Oui, à la lecture des définitions du dessus, une question ou remarque doit vous forcément vous venir à l’esprit : Que se passe-t-il lorsque des données produisent la même empreinte ? C’est ce qu’on appelle une collision. Dans la plupart des cas, ce n’est pas bien grave car il ne s’agit que de contrôles : on contrôle que l’empreinte des données reçues est la même que l’empreinte des données envoyées. Cela peut être un peu plus gênant, pour les mots de passe car deux mots de passe différents produisant la même empreinte permettront de s’identifier ! (c’est une des raisons pour laquelle on ajoute du « sel » au mot de passe, mais ce n’est pas la seule raison). C’est carrément très gênant pour les tables de hachage ou pour les stockages de données. C’est pourquoi, il est conseillé d’utiliser des fonctions de hachage avec de faibles taux de collisions.

Quelques fonctions de hachage célèbres

MD5

L'algorithme MD5, pour Message Digest 5, est une fonction de hachage cryptographique qui permet d'obtenir l'empreinte numérique d'un fichier (on parle souvent de message). Il a été inventé par Ronald Rivest en 1991. L'utilisation de cette fonction de hachage dans les signatures numériques peut conduire à de multiples scénarios d'attaque et n'est plus considérée comme un composant fiable de l'infrastructure à clés publiques. Cependant dans le calcul de la « signature » d'un fichier il reste plutôt fiable, même si l'on ne peut pas assurer qu'il y a unicité entre l'empreinte calculée et le fichier ou message sourceCette fonction renvoie une empreinte de 128 bits. À ses débuts, la fonction MD5 était considérée comme sûre, mais au cours du temps, des failles ont été découvertes dans son fonctionnement et durant l'été 2004, il a été cassé par des chercheurs chinois, Xiaoyun Wang, Dengguo Feng, Xuejia Lai (co-inventeur du célèbre algorithme de chiffrement IDEA) et Hongbo Yu. Leur attaque a permis de découvrir une collision complète (deux messages différents qui produisent la même empreinte) sans passer par une méthode de type recherche exhaustive2,5. Sur un système parallélisé, les calculs n'ont pris que quelques heures. Le MD5 n'est donc plus considéré comme sûr, mais l'algorithme développé par ces trois chercheurs concerne des collisions quelconques et ne permet pas de réaliser une collision sur une empreinte spécifique, c'est-à-dire réaliser un deuxième message, à partir de l'empreinte d'un premier message, qui produirait la même empreinte. Un projet de calcul distribué lancé en mars 2004, MD5CRK (en), visait à découvrir une collision complète mais a été subitement arrêté après la découverte de l'équipe chinoise. La sécurité du MD5 n'étant plus garantie selon sa définition cryptographique, les spécialistes recommandent d'utiliser des fonctions de hachage plus récentes comme le SHA-256. On sait maintenant générer des collisions MD5 en moins d'une minute lorsque les deux blocs en collisions sont « libres ». On peut aussi générer une infinité de collisions avec un texte T à partir de deux messages M1 et M2 de même longueur qui sont en collision. Il suffit de concaténer M1 et M2 avec T, tel que T1 = M1 + T et T2 = M2 + T, afin d'obtenir une collision complète entre T1 et T2. On ne peut toutefois pas générer une signature particulière et la falsification de documents reste un exercice difficile. Dès 2006, il est par exemple possible de créer des pages HTML aux contenus très différents et ayant pourtant le même MD5. La présence de métacodes de « bourrage » placés en commentaires, visibles seulement dans la source de la page web, trahit toutefois les pages modifiées pour usurper le MD5 d'une autre. La supercherie peut donc être levée si on examine les sources de la page en question. En 2008, le logiciel BarWF utilise les ressources des instructions SSE2 et des processeurs massivement parallèles d'une carte graphique (CUDA) pour casser du MD5 en force brute à la vitesse annoncée de 350 millions de clés par seconde.

SHA1

SHA-1 (Secure Hash Algorithm) est une fonction de hachage cryptographique conçue par la National Security Agency des États-Unis (NSA), et publiée par le gouvernement des États-Unis comme un standard fédéral de traitement de l'information (Federal Information Processing Standard du National Institute of Standards and Technology (NIST)). Elle produit un résultat (appelé « hash » ou condensat) de 160 bits. SHA-1 n'est plus considéré comme sûr contre des adversaires disposant de moyens importants. En 2005, des cryptanalystes ont découvert des attaques sur SHA-1, suggérant que l'algorithme pourrait ne plus être suffisamment sûr pour continuer à l'utiliser dans le futur. Depuis 2010, de nombreuses organisations ont recommandé son remplacement par SHA-2 ou SHA-3. Microsoft, Google et Mozilla ont annoncé que leurs navigateurs respectifs n'accepteraient plus les certificats SHA-1 au plus tard en 2017. Le SHA-1 prend un message d'un maximum de 264 bits en entrée. Son fonctionnement est similaire à celui du MD4 ou MD5 de Ronald Rivest. Quatre fonctions booléennes sont définies, elles prennent 3 mots de 32 bits en entrée et calculent un mot de 32 bits. Une fonction spécifique de rotation est également disponible, elle permet de déplacer les bits vers la gauche (le mouvement est circulaire et les bits reviennent à droite). Une de ces rotations n'était pas présente dans le SHA-0, elle permet de casser certaines caractéristiques linéaires dans la structure. Cela permet d'éviter une attaque sur les bits neutres décrite par Eli Biham, technique reprise pour calculer la collision complète sur SHA-0 (Antoine Joux et al.). Le SHA-1 commence par ajouter à la fin du message un bit à 1 suivi d'une série de bits à 0, puis la longueur du message initial (en bits) codée sur 64 bits. La série de 0 a une longueur telle que la séquence ainsi prolongée a une longueur multiple de 512 bits. L'algorithme travaille ensuite successivement sur des blocs de 512 bits. Pour chaque bloc l'algorithme calcule 80 tours (ou rondes, « rounds » en anglais) successifs et applique une série de transformations sur l'entrée. La première étape consiste à calculer 80 valeurs sur 32 bits. Les 16 premières valeurs sont obtenues directement à partir du bloc « message » en entrée. Les 64 autres sont calculées successivement. Le SHA-1 les obtient grâce à une rotation (absente dans SHA-0) qui est appliquée sur le résultat d'un XOR, il utilise pour cela 4 mots obtenus dans les itérations précédentes. On définit ensuite cinq variables qui sont initialisées avec des constantes (spécifiées par le standard), le SHA-1 utilise encore 4 autres constantes dans ses calculs. Si un bloc de 512 bits a déjà été calculé auparavant, les variables sont initialisées avec les valeurs obtenues à la fin du calcul sur le bloc précédent. Il s'ensuit 80 tours qui alternent des rotations, des additions entre les variables et les constantes. Selon le numéro du tour, le SHA-1 utilise une des quatre fonctions booléennes. L'une de ces fonctions est appliquée sur 3 des 5 variables disponibles. Les variables sont mises à jour pour le tour suivant grâce à des permutations et une rotation. En résumé, le SHA-1 change sa méthode de calcul tous les 20 tours et utilise les sorties des tours précédents. À la fin des 80 tours, on additionne le résultat avec le vecteur initial. Lorsque tous les blocs ont été traités, les cinq variables concaténées (5 × 32 = 160 bits) représentent la signature.

SHA2

SHA-2 (Secure Hash Algorithm) est une famille de fonctions de hachage qui ont été conçues par la National Security Agency des États-Unis (NSA), sur le modèle des fonctions SHA-1 et SHA-0, elles-mêmes fortement inspirées de la fonction MD4 de Ron Rivest (qui a donné parallèlement MD5). Telle que décrite par le National Institute of Standards and Technology (NIST), elle comporte les fonctions, SHA-256 et SHA-512 dont les algorithmes sont similaires mais opèrent sur des tailles de mot différentes (32 bits pour SHA-256 et 64 bits pour SHA-512), SHA-224 et SHA-384 qui sont essentiellement des versions des précédentes dont la sortie est tronquée, et plus récemment SHA-512/256 et SHA-512/224 qui sont des versions tronquées de SHA-512. Le dernier suffixe indique le nombre de bits du haché. Les algorithmes de la famille SHA-2, SHA-256, SHA-384 et SHA-512, sont décrits et publiés en compagnie de SHA-1 comme standard du gouvernement fédéral des États-Unis (Federal Information Processing Standard) dans le FIPS 180-2 (Secure Hash Standard)datant de 2002 (une prépublication pour appels à commentaires a été faite en 2001). La fonction SHA-224 est ajoutée un peu plus tard. La dernière version à ce jour, le FIPS 180-4 (Secure Hash Standard) date de mars 2012 et ajoute les fonctions SHA-512/256 et SHA-512/224. En 2005, des problèmes de sécurité de SHA-1 ont été mis en évidence : il existe pour la recherche de collisions une attaque théorique nettement plus rapide que l'attaque générique des anniversaires sur les fonctions de hachage. Bien que l'algorithme de SHA-2 partage des similarités avec celui de SHA-1, ces attaques n'ont actuellement pas pu être étendues à SHA-2. Le NIST a cependant organisé un concours pour sélectionner une nouvelle fonction de hachage, SHA-3. Le concours a débouché fin 2012 sur le choix d'une nouvelle famille de fonctions dont la conception est très différente de SHA-1 et de SHA-2. La nouvelle famille de fonctions est présentée comme un autre choix possible, elle ne remet pas en cause l'utilisation de SHA-2 du moins dans l'immédiat. Comme toutes les fonctions de hachage les fonctions SHA-2 prennent en entrée un message de taille arbitraire, avec une borne (toute théorique) pour celle-ci, et produisent un résultat (appelé « hash », haché, condensat ou encore empreinte…) de taille fixe. La taille du haché est indiquée par le suffixe : 224 bits pour SHA-224, 256 bits pour SHA-256, 384 bits pour SHA-384 et 512 bits pour SHA-512. Les algorithmes de la famille SHA-2 sont très semblables, il y a essentiellement deux fonctions différentes, SHA-256 et SHA-512, les autres étant des variantes de l'une ou l'autre. Les fonctions SHA-256 et SHA-512 ont la même structure mais diffèrent par la taille des mots et des blocs utilisés. Cette structure est assez proche de celle de SHA-1, mais un peu plus complexe et en évite certaines faiblesses connues. Elle se rattache plus généralement à une famille de fonctions de hachage inspirées de MD4 et MD5 de Ron Rivest. On retrouve comme primitives l'addition pour des entiers de taille fixe n soit une addition modulo 2n, opération non linéaire (au sens de l'algèbre linéaire) sur le corps des booléens F2, ainsi que des opérations bit à bit (xor et autres). Comme toutes les fonctions de cette famille (sauf SHA-3, reposant sur une fonction éponge), elles suivent un schéma itératif qui suit la construction de Merkle-Damgård (sans opération de finalisation). La fonction de compression itérée possède deux entrées de taille fixe, la seconde entrée étant de même taille que la sortie de la fonction :

  • une donnée obtenue par découpage du message à traiter, la taille est de 512 bits pour SHA-256 et SHA-224 et de 1024 bits pour SHA-512 et SHA-384,

  • le résultat de la fonction de compression à l'itération précédente (256 bits pour SHA-256 et SHA-224, 512 pour SHA-512 et SHA-384).

Les entrées de la fonction de compression sont découpées

  • en mots de 32 bits pour SHA-256 et SHA-224,

  • en mots de 64 bits pour SHA-512 et SHA-384

La fonction de compression répète les mêmes opérations un nombre de fois déterminé, on parle de tour ou de ronde, 64 tours pour SHA-256, 80 tours pour SHA-512. Chaque tour fait intervenir comme primitives l'addition entière pour des entiers de taille fixe, soit une addition modulo 232 ou modulo 264, des opérations bit à bit : opérations logiques, décalages avec perte d'une partie des bits et décalages circulaires, et des constantes prédéfinies, utilisées également pour l'initialisation. Avant traitement, le message est complété par bourrage de façon que sa longueur soit un multiple de la taille du bloc traité par la fonction de compression. Le bourrage incorpore la longueur (en binaire) du mot à traiter : c'est le renforcement de Merkle-Damgård ((en)Merkle-Damgård strengthening), ce qui permet de réduire la résistance aux collisions de la fonction de hachage à celle de la fonction de compression. Cette longueur est stockée en fin de bourrage sur 64 bits dans le cas de SHA-256 (comme pour SHA-1), sur 128 bits dans le cas de SHA-512, ce qui « limite » la taille des messages à traiter à 264 bits pour SHA-256 (et SHA-224) et à 2128 bits pour SHA-512 (et SHA-384).

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Toeic, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels