Fonctions de hachage : les empreintes cryptographiques

tbowan

28 Novembre 2019

Vérifier l'intégrité d'une donnée est une tâche complexe. Si, en plus, vous êtes en présence d'attaquants intelligents, elle devient carrément cryptographique. Dans cet article, on vous explique le pourquoi du comment.

Après avoir abordé tranquillement les fonctions de hachage à travers les les sommes de contrôle, nous pouvons maintenant passer aux choses sérieuses et, disons le franchement, cryptographiques.

Précédemment, nous voulions détecter les erreurs accidentelles ; interférence électro-magnétique, erreur de saisie et autres rayons cosmiques. Cette fois, on va aller plus loin pour détecter les erreurs volontaires ; tentative de modification du contenu par des indésirables. La question est donc la suivante :

Comment garantir qu’une donnée est conforme à l’original ?

La différence est de taille car cette fois, nous ne jouons plus simplement contre la deuxième loi de la thermodynamique mais contre des hackers, des vrais, qui utilisent leur intelligence pour pourrir la vie des cryptographes et les histoires d’amour.

Illustration de Jasper Nance, CC-By-NC-SA

Illustration de Jasper Nance, CC-By-NC-SA

Alors, sous vos yeux ébaubis, levons le voile sur ces fonctions et démystifions ce hachage cryptographique

Divulgâchage : c’est en fait plus simple puisqu’il y a moins d’équations (et plus aucun polynôme), et à la fois plus compliqué car cette fois, on va torturer et mélanger des blocs de données pour qu’il n’en reste qu’un, et tellement secoué qu’il ne saura plus d’où il vient.

Contraintes

Après avoir augmenté les enjeux, nous allons donc devoir augmenter les contraintes pour que des fonctions candidates puissent prétendre au titre de hachage cryptographique. Il ne s’agit donc plus de maximiser le nombre d’erreurs découvertes mais de les interdire. Formellement, ça se traduit par les trois contraintes suivantes : le calcul de l’empreinte doit être irréversible, infalsifiable et résistant aux collisions.

Irréversible

Les fonctions de hachage étant utilisée presque partout, on s’attend à ce qu’elles soient facile à calculer. Une fois qu’on a une donnée, en calculer la somme de contrôle ou une empreinte cryptographique ne devrait pas être plus long que de la lire.

Ce qu’on ne veut pas, par contre, c’est pouvoir construire une donnée facilement lorsqu’on dispose de son empreinte.

Les cryptographes, qui sont mathématiciens, donc pointilleux sur le vocabulaire et les notations, parlent ici de résistance à la pré-image. Pour comprendre pourquoi, il faut se rappeler qu’on parle de fonctions, f(x)→y, où y est l’image de x par la fonction f. Réciproquement, x est la préimage de y.

Cette contrainte prend tout son sens lorsqu’on se sert des fonctions de hachage pour protéger la confidentialité des données (et non simplement détecter les erreurs). Dans de nombreux cas, vous voudrez contrôler qu’un tiers vous envoie bien deux fois la même donnée, mais vous aimeriez ne pas avoir besoin de stocker la dite donnée pour éviter qu’elle ne soit accessible à des yeux indiscrets. En voici deux exemples :

  1. Les mots de passes de vos utilisateurs (cf. R22 du guide de l’ANSSI pour la sécurisation des sites web). Lorsqu’ils se connectent, vous voulez vérifier qu’ils vous envoient le même mot de passe que lors de l’inscription,
  2. Les numéros de cartes bancaires (cf. condition 2.3 de la norme PA-DSS). Lorsqu’un client souhaite vérifier une transaction qu’il a effectué avec votre application.

Dans ces deux cas d’utilisation, plutôt que de stocker la donnée en clair, vous stockez son empreinte cryptographique. Chaque fois que l’utilisateur doit vous montrer qu’il connaît la donnée secrète, il vous l’envoie, vous calculez l’empreinte et la chercher dans votre base. Ainsi, si la base venait à être compromise, l’attaquant se retrouverait alors avec des empreintes qu’il ne pourrait pas décoder.

Pour être complet, il est également nécessaire d’ajouter un sel (cf. R23 du précédent guide) pour éviter certaines formes d’attaques particulières. Je vous en parlerai une autre fois 😉.

Infalsifiable

Précédemment, on partait du principe que l’attaquant ne dispose que de l’empreinte et n’avait pas d’information sur la donnée initiale qu’il cherchait à récupérer.

Cette fois, on refuse qu’il puisse modifier une donnée sans que ça en change l’empreinte.

Les cryptographes parlent ici de résistance à la seconde pré-image. Connaissant une donnée x1, pouvons nous trouver en trouver une deuxième x2 telle que f(x1)=f(x2).

Le cas d’usage est alors différent, la fonction de hachage est alors utilisée pour garantir l’intégrité, la donnée pouvant être publique. Par contre, pour que ça marche, il faut que l’empreinte soit transmise de manière sécurisée... Le cas le plus habituel étant l’empreinte des images ISO de dvd d’installation de logiciels.

Mais si l’attaquant intercepte la donnée ET son empreinte, il peut modifier les deux.

C’est pour cette raison que la fonction de hachage est souvent utilisée conjointement à d’autres algorithmes cryptographiques d’authentification pour garantir l’identité de la personne ayant calculé l’empreinte (on parle alors d’authenticité du message) et on retrouve ces méthodes bien plus souvant :

Résistance aux collisions

Les contraintes précédentes, même si elles sont suffisantes la plupart du temps, sont généralement complétée de la troisième contrainte suivante :

Il est impossible de trouver deux données différentes ayant la même empreinte.

Cette propriété est principalement utilisée pour prouver théoriquement la sécurité de certains protocoles. Dans la pratique, on la retrouve surtout dans les preuves de travail consistant à trouver des données ayant une empreinte similaire mais aussi dans la sécurité de systèmes de stockages utilisant l’empreinte comme adresse (on y reviendra).

Impossibilité ? Pour éviter toute méprise sur le sens de ce termes, il faut l’entendre, lorsqu’on parle de cryptographie comme «  impossible avec des ressources matérielles existantes ».

On pourra toujours générer des données aléatoirement, jusqu’à en trouver deux qui ont la même empreinte. Ça arrivera forcément puisque l’ensemble de donnée possible est bien plus grand par rapport au nombre d’empreinte possibles). Par contre, trouver cette collision prendra tellement de temps que ça n’est pas réaliste, et donc pas utile.

Algorithmes

Contrairement aux sommes de contrôles qui sont relativement faciles à comprendre dans les détails, les fonctions de hachage cryptographiques le sont carrément moins. Même si ces fonctions sont courtes et ne contiennent que des opérations de base, elles les enchaînent et les couplent à des constantes qu’on dirait issues aléatoirement d’une classe de CP survoltée juste avant la distribution des cadeaux du Père Noël...

Alors plutôt que de vous parler des entrailles de chacune de ces fonctions, je vais plutôt vous décrire les trois plus courantes : MD5, SHA-1 et SHA-2.

MD5

Il s’agit de la dernière représentante des Message Digest proposés par Ronald Rivest (co-créateur de RSA) en 1991. Elle permet de calculer une empreinte de 128 bits de n’importe quelle donnée et a été normalisée en 1992 dans la RFC 1321.

1991, naissance du World Wide Web, logo historique de Robert Cailliau

1991, naissance du World Wide Web, logo historique de Robert Cailliau

Elle n’est plus sûre. Et ce depuis un bon moment...

Les premiers signes de faiblesses sont publiés en 1993 (deux initialisation donnant les mêmes résultats) puis 1996 (créer des collisions sur la fonction interne mais pas globalement).

Les choses se sont ensuite accélérées puisqu’une attaque distribuée est menée en 2004 (une heure pour une collision), l’année suivante en quelques minutes sur un notebook, ainsi que l‘usurpation de certificats cryptographiques.

Utiliser cette fonction pour détecter des modifications malicieuse ne marche donc clairement plus.

Techniquement, on peut encore l’utiliser comme checksum (et détecter des erreurs accidentelles), mais vu que des alternatives plus sûres existent, je préfère me passer de MD5.

SHA1

Sentant les choses mal tourner pour MD5, la NSA a publié une nouvelle fonction de hachage produisant une empreinte de 160 bits, sobrement nommée Secure Hash Algorithm, dans le standard FIPS 180-1 (édité par le NIST) en 1995.

1995, derniers essais nucléaires français, par Thomas Conté

1995, derniers essais nucléaires français, par Thomas Conté

Elle n’est plus sûre non plus. Même si on a longtemps cru le contraire.

Les premiers signent apparaissent dès 2004 avec le calcul effectif de collisions sur SHA-0 (le prédécesseur de SHA-1) et des attaques théoriques sont proposées l’année suivante.

En 2012, un concours pour trouver de nouvelles fonctions est lancé par le NIST qui élu l’algorithme Keccak, renommé SHA-3 (puisque SHA-2 est sorti en 2002). En 2013, Microsoft ne le considère plus sûr et l’ANSSI émet un avis similaire en 2014.

En 2017, une preuve de concept a été menée par Google et l’institut CWI d’Amsterdam qui ont pu créer deux fichiers PDF différent mais avec la même empreinte.

Comme précédemment, il n’est donc plus sage d’utiliser SHA-1 pour des contrôles d’intégrité dans un contexte de sécurité informatique. On continue tout de même de l’utiliser dans certaines applications.

Par exemple, git et mercurial, deux systèmes de gestion de versions, l’utilisent pour identifier les données internes. Dans ce contexte, SHA-1 n’est pas utilisé pour vérifier l’intégrité mais pour identifier un document (ou un objet de manière générale). Un attaquant peut bien sûr créer deux fichiers, le deuxième usurpant le premier, mais il est consensuellement admit qu’il est plus facile d’insérer directement des données malicieuses que s’embêter à générer des collisions.

SHA2

Comme c’est toujours bien d’avoir de l’avance, la NSA avait, dès 2002, normalisé deux nouvelles fonctions de hachage dans sa version suivante de la norme FIPS 180-2 : SHA256 et SHA512 qui, comme leurs noms l’indiquent, génèrent des empreintes de 256 bits et 512 bits.

2002, passage à l’Euro, illustration de martaposemuckel

2002, passage à l’Euro, illustration de martaposemuckel

Elle est considérée comme sûre. Jusqu’à preuve du contraire. On sait, depuis 2003, que les attaques sur SHA-0 et SHA-1 n’ont pas d’impact et comme aucune attaque n’a actuellement été publiée, on se dit que tout va bien.

C’est donc la fonction utilisée la plupart du temps dès qu’il s’agit de vérifier l’intégrité des données (dans les certificats cryptographiques et tout un tas de flux chiffrés comme TLS, SAML, JWT, ...).

Côté régalien

Si vous êtes amenés à devoir choisir une fonction de hachage, ou vérifier que celle en cours dans votre environnement est bonne ou non, je vous suggère de vous référer au RGS, section 2.3 de l’ANSSI qui résume la situation avec trois règles :

  1. Pour une utilisation ne devant pas dépasser 2020, la taille minimale des empreintes générées par une fonction de hachage est de 200 bits.
  2. Pour une utilisation au-delà de 2020, la taille minimale des empreintes générées par une fonction de hachage est de 256 bits.
  3. La meilleure attaque connue permettant de trouver des collisions doit nécessiter de l’ordre de 2h/2 calculs d’empreintes, où h désigne la taille en bits des empreintes.

Et si vous ne voulez pas vous pencher sur les détails des fonctions et dans la littérature pour vérifier la non existence d’attaques en moins de 2h/2 calculs, vous pouvez vous tourner vers le rapport du NIST plus dirigiste en la matière :

SHA-1 ne peut plus être utilisé pour générer des empreintes. Il peut, à la rigueur, être utilisé pour des contrôles d’intégrité mais pour des raisons de rétro-compatibilité.

SHA2 est le nouveau standard, SHA-3 est une alternative.

Et après

Fonctions de hachage : les sommes de contrôle
20 Novembre 2019 Utilisées pour vérifier l'intégrité des données, les fonctions de hachage sont partout. Aujourd'hui, nous vous présentons les sommes de contrôles, les plus faciles d'entre elles.
C'est quoi une PKI ?

19 septemre 2019 À force d'en parler, c'est presque devenu un buzzword vide de sens. Démystifions donc ce concept pour voir ce qu'il apporte et comment s'en servir à propos.

Le Logarithme Discret

7 Juillet 2017 Opération algébrique dont la difficulté est à la base de nombreux algorithmes de cryptographie moderne. On vous présente les concepts nécessaires à sa définition ainsi que ses faiblesses dans certains cas particuliers.

L’Échange de clé Diffie-Hellman

23 Juillet 2017 Un des nombreux classiques de la cryptographie moderne. Il permet à la fois d'établir un secret partagé sans nécessiter de canal de communication privé mais est également pour fournir une confidentialité persistante entre sessions. Comment ça marche ? Comment on l'utilise ? Cet article répond à vos questions.