Vers la fin de SHA-1 : Google et le CWI Institute provoquent une collision

, Partager

Créé en 1995, le SHA-1 pour Secure Hash Algorithm-1, a été la cible de nombreuses tentatives d’attaques aussi bien de la part de la communauté académique que de la communauté industrielle. Les premières faiblesses de cet algorithme ont été exposées dès 2005 entraînant sa dépréciation officielle par les administrations au cours de l’année 2011. En partenariat avec le CWI Institute d’Amsterdam, Google Research a démontré en pratique que SHA-1 pouvait créer des collisions, assurant de fait la dépréciation complète de cette fonction. Cependant, cet algorithme de hachage est encore massivement utilisé dans différents contextes tels que la signature électronique de fichiers ou encore le stockage de mots de passe.

Secure Hash Algorithm-1

En 1995, la National Security Agency crée le SHA-1 pour pallier les défauts et le manque de robustesse de la première itération de cet algorithme, le SHA-0. La fonction est alors modifiée et publiée par le National Institute of Standards and Technology [1]. Le résultat de cette fonction est un « hash » ou « condensat » de 160 bits. Elle est basée sur la construction de Merkle-Damgård [2], et son fonctionnement peut se décomposer en deux phases : prétraitement et calcul du condensat.

La diversité des applications de cette fonction de hachage et sa facilité de mise en œuvre l’ont menée à être considérée comme le couteau suisse de la protection de données. Ainsi, SHA-1 est utilisé depuis sa création pour le hachage de données sensibles, la signature de fichiers, la signature de certificats dans le web, ou encore pour le hachage des mots de passe d’utilisateurs. Cependant, cette fonction ne peut servir à chiffrer des messages plus longs que 264 bits.

Fonctionnement standard de SHA-1

La fonction de hachage SHA-1 génère une signature à partir d’une information passée en entrée. Un changement dans l’information entraînant le calcul d’une nouvelle signature très différente de la précédente :

À noter que cette fonction de hachage peut également être utilisée pour calculer la signature de fichiers.

Faiblesses de la fonction

Les faiblesses de SHA-0 puis de SHA-1 concernant la possibilité de « collision » des condensats générés ont été mises en avant par de nombreux travaux dès 2005. Une telle collision apparaît lorsque deux messages différents en entrée de la fonction produisent un condensat identique. L’un des premiers à avoir objecté la robustesse de cette fonction est Bruce Schneier, qui théorise en 2005 le risque de collision de SHA-1 [3]. La sphère académique montre aussi qu’il est possible de créer des algorithmes pour trouver des collisions cryptographiques [4]. La critique principale issue de la cryptanalyse de SHA-1 réside dans la longueur du condensat de 160 bits produit par la fonction. De fait, chaque message (d’au plus 264 bits) est alors rapporté à un condensat de 160 bits, signifiant qu’il existe un très grand nombre de messages dont le condensat est identique ce qui implique que la robustesse de SHA-1 ne repose que sur le très grand nombre de condensats possibles.

Rôle des architectures hautes performances

La cryptanalyse de SHA-1 montre donc qu’il est possible de trouver deux messages différents ayant le même condensat. Au milieu des années 2000, sa robustesse, bien que critiquée, n’était que peu menacée par les attaques. En effet, les ressources de calcul nécessaires à une telle attaque étaient encore trop peu présentes et pas ou peu accessibles au grand public, donc de fait peu probables.

Aujourd’hui les architectures hautes performances sont plus répandues et accessibles via des plateformes qu’Amazon et OVH peuvent fournir, ou encore que des entreprises privées, notamment du Web, peuvent construire et utiliser.

Preuves de collision et conséquences

Le 23 février 2017, Google et le CWI Institue d’Amsterdam ont annoncé qu’ils avaient provoqué une collision de condensats calculés par SHA-1. En pratique, cela signifie qu’ils ont créé deux documents différents, visuellement et dans leurs contenus, qui partagent le même condensat. Or, pour garantir un niveau de sécurité satisfaisant, de telles collisions ne doivent jamais se produire.

En pratique, une collision se produit lorsque deux informations distinctes sont « hachées » à la même signature :

Pour mettre en œuvre cette attaque de SHA-1, Google a tiré profit de son expertise technique et de son infrastructure cloud. Ces ressources ont permis de réaliser l’un des plus gros calculs à avoir été effectué par des machines. La méthode employée repose sur la génération d’un préfixe pdf spécialement construit pour générer deux documents aux contenus différents mais aux condensats identiques. Leur technique, nommée « SHAttered », a nécessité plus de neuf quintillions de calculs par SHA-1 (environ 1030 calculs). Cette quantité d’opérations prendrait environ 6500 ans de calculs à un ordinateur pour la première phase de calcul et environ 110 ans pour une carte graphique performante pour la seconde phase du calcul, ou encore un an pour 110 cartes graphiques qui seraient utilisées pour répartir le calcul. Malgré le nombre important de calculs nécessaires, SHAttered est environ cent mille fois plus rapide que la force brute qui représente quelques 12 millions d’années de calculs par une carte graphique pour la seconde phase, ou encore un an s’ils sont répartis sur 12 millions de cartes graphiques.

Les conséquences de cette démonstration pratique vont au-delà du tour de force que représente la mise en œuvre d’une méthode permettant de démontrer les défauts et les faiblesses d’une méthode de hachage. La plus évidente étant la possibilité pour un hacker bien financé de produire une collision et ainsi de pénétrer un système dont l’authentification est basée sur SHA-1. En effet, une multitude d’applications utilisent SHA-1 pour la sécurisation de mots de passe de comptes utilisateurs, la signature de fichiers, la protection de données sensibles et la signature de certificats pour le Web notamment. D’autres systèmes utilisent SHA-1 dans leur fonctionnement, à l’instar de git et svn pour la gestion de versions de code source. Leurs fonctionnements sont basés sur la différence de signature SHA-1 entre les fichiers de deux versions différentes. Ces systèmes sont très utilisés pour gérer le développement applicatif d’un très grand nombre de projets, tels que le code source du système d’exploitation linux, et sont aux cœurs de deux des plateformes en ligne les plus utilisées par la communauté open-source : github.com et bitbucket.org.

Les systèmes concernés par l’attaque sont ceux qui reposent sur SHA-1 pour la signature de contenus. Nous pouvons notamment citer :

  • Les certificats numériques et leurs signatures
  • Les signatures PGP et GPG des emails
  • Les signatures de codes sources d’applications
  • Les mises à jour de logiciels
  • Les sommes de contrôle d’images disques
  • Les systèmes de sauvegarde et d’archivage
  • Les systèmes d’authentification (ou de déduplication)
  • git
  • svn
  • Les systèmes de contrôles de version de code source
  • Les mots de passes utilisateurs hachés par cette fonction
  • Les clefs d’API de certains services web

Recommandations

Les acteurs du Web, Mozilla et Google, ont réagi en considérant que les sites Web dont les certificats sont signés par SHA-1 ne sont plus considérés comme sécurisés dans les dernières mises à jour de leurs navigateurs (Chrome et Firefox). D’autres moteurs web attendent leur mise à jour. Concernant git, son créateur Linus Torvalds (créateur de Linux également) a annoncé sur son blog que la migration vers d’autres standards plus robustes comme SHA-2, SHA-3 et SHA-256 étaient en cours d’étude.


Rédacteur
- Marc-Emmanuel Perrin, Attaché adjoint pour la Science et la Technologie, San Francisco, deputy-sf@ambascience-usa.org

Notes

[1Standard FIPS-180-1, NIST 1995

[2Itération à partir d’une fonction de compression dont l’entrée a une taille fixe à laquelle on ajoute sa longueur en fin de message - phase aussi connue sous le nom de renforcement.

[3B. Schneier. Cryptanalisis of SHA-1. 2011

[4J. Yajima, T. Iwasaki, Y. Naito, Y. Sasaki, T. Shimoyama, N. Kunihiro, and K. Ohta.
A strict evaluation method on the number of conditions for the sha-1 collision search.
In Proceedings of the 2008 ACM symposium on Information, computer and communications security