SHA-1

SHA-1 (Secure Hash Algorithm, prononcé /ʃa.œ̃/) 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 (20 octets), habituellement représenté par un nombre hexadécimal de 40 caractères.

Un tour de la fonction de compression de SHA-1 :
A, B, C, D, E sont des mots de 32 bits ;
<<<_n désigne une rotation des bits par décalage de n bits vers la gauche ;
F est une fonction (non linéaire sur le corps F₂ des booléens) qui dépend du numéro de tour t ;
⊞ est l'addition modulo 2³² (l'addition des entiers machines non signés de 32 bits), qui est non linéaire sur F₂ ;
K_t est une constante (32 bits) qui dépend du numéro de tour t ;
W_t est un mot de 32 bits qui dépend du numéro de tour t ; il est obtenu par une procédure d'expansion à partir du bloc de donnée (512 bits) dont le traitement est en cours.

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 n'était pas suffisamment sûr pour continuer à l'utiliser. 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 cesseraient d'accepter les certificats SHA-1 au plus tard en 2017.

Origine

La fonction de hachage SHA-1 succède à SHA-0 qui a été rapidement mise de côté par le NIST pour des raisons de sécurité insuffisante. SHA-0 était légitimement soupçonné de contenir des failles qui permettraient d'aboutir rapidement à des collisions (deux documents différents qui génèrent le même condensat). Face à la controverse soulevée par le fonctionnement de SHA-0 et certains constats que l'on attribue à la NSA, SHA-0 a été modifiée peu après sa sortie (1993) pour devenir SHA-1 (1995). Une collision complète sur SHA-0 a été effectivement découverte par Antoine Joux et al. en août 2004.

Abandon de SHA-1

En 2005, la cryptanalyste Xiaoyun Wang et ses co-auteurs Yiqun Lisa Yin et Hongbo Yu annoncent une attaque théorique pour la recherche de collisions pour SHA-1 qui est nettement plus efficace que l'attaque des anniversaires (l'attaque générique de référence). L'attaque complète sera publiée à Crypto 2015. Le NIST pour sa part recommande de passer à SHA-2 ou SHA-3 quand c'est possible. Depuis 2013, Microsoft a déclaré l’obsolescence de SHA-1 et en 2014. L'ANSSI déconseille son utilisation dans la seconde version de son Référentiel Général de Sécurité (RGS) d'application au 1^er juillet 2014. Enfin, Google annonce que ses versions de Chrome n'accepteront plus, de façon graduelle, SHA-1 jusqu'à refuser les certificats l'utilisant qui expirent après le 1^er janvier 2017.

En février 2017 Google et le Centrum voor Wiskunde en Informatica annoncent une attaque effective et la première collision pour SHA-1.

Exemples

Voici la signature obtenue sur une phrase (codée en utf8) : SHA1("Wikipédia, l'encyclopédie libre et gratuite") = 6153A6FA0E4880D9B8D0BE4720F78E895265D0A9.

En modifiant un caractère, la signature change radicalement : SHA1("Wikipédia, l'encyclopédie libre et gratuitE") = 11F453355B28E1158D4E516A2D3EDF96B3450406.

Le SHA-1 est un excellent générateur de nombres pseudo-aléatoires (comme beaucoup de fonctions de hachage) et il passe avec succès tous les tests statistiques.

Caractéristiques

En résumé les caractéristiques de SHA-1 sont les suivantes :

• taille du message : 2⁶⁴ bits maximum
• taille des blocs : 512 bits (le message en entrée est découpé en blocs de 512 bits)
• taille des mots : 32 bits (SHA-1 est construite à partir d'opérations sur des mots de 32 bits)
• taille du condensé : 160 bits
• niveau de sécurité : collision en 2⁶³ opérations.

L’attaque des anniversaires, qui est l'attaque générique sur les fonctions de hachage cryptographique pour trouver une collision, permet de trouver (théoriquement) celle-ci en 2⁸⁰ opérations, ce qui est donc la sécurité attendue pour une telle fonction de hachage. Mais dans le cas de SHA-1, il existe une attaque (théorique) en 2⁶⁹ opérations connue depuis 2005. C'est attaque a été améliorée en une attaque en 2⁶³ opérations, et une collision a effectivement été découverte en 2017.

Attaques

Une attaque brute basée sur le paradoxe des anniversaires permet de trouver une collision complète sur une clé SHA-1 complète (sur 160 bits) avec un nombre d'opérations de l'ordre de $2^{80}$.

En 2005, Rijmen et Oswald ont publié une attaque sur une version simplifiée du SHA-1 (53 tours), leur attaque permet de trouver une collision avec moins de $2^{80}$ opérations.

En février 2005, Bruce Schneier a fait état d'une attaque sur la version complète du SHA-1 par l'équipe chinoise de Wang, Yin et Yu. Leur méthode permet de trouver :

• une collision dans le SHA-1 complet de 128 bits avec $2^{69}$ opérations au lieu de $2^{80}$ par l’attaque des anniversaires
• une collision dans le SHA-0 complet avec seulement $2^{39}$ opérations
• une collision dans une version simplifiée du SHA-1 (58 tours) avec $2^{33}$ opérations

La description de l'attaque a été publiée en juin 2005.

Le 17 août 2005, une amélioration de l'attaque a été annoncée par Wang et al. à la conférence CRYPTO 2005, la complexité passe ainsi de 2⁶⁹ à 2⁶³, soit une division par 64 de la complexité originale.

Lors de l'Eurocrypt 2009 (avril), une amélioration de l'attaque aurait permis de réduire à nouveau sa complexité jusqu'à atteindre $2^{52}$. Toutefois, ces résultats furent démentis et l'article fut retiré à la suite de la découverte d'une erreur dans l'évaluation de cette complexité.

Une équipe composée de chercheurs de chez Google et du CWI (Centrum Wiskunde et Informatica) ont annoncé le 23 février 2017 qu'ils avaient réussi à obtenir une collision entre deux documents.

Une équipe composée de chercheurs universitaires (Gaëtan Leurent de l'Inria en France et son collègue Thomas Peyrin de l'Université de Nanyang à Singapour) a annoncé en début avril 2019 avoir mis au point une attaque sur la version complète de SHA-1 (80 tours) permettant d'obtenir pour n'importe quelle valeur de hachage une collision sur des préfixes choisis en un nombre d'opérations situé entre $2^{66.9}$ et $2^{69.4}$, ce qui réduit le coût d'obtention de collisions à moins de 150 000 $, à la portée d'une organisation de moyenne taille (ou de bandes organisées) et plus seulement de grandes organisations ou de gouvernements, basée sur une analyse différentielle multi-bloc (et non un bloc unique avec les tentatives précédentes), ce qui permet d'en améliorer l'efficacité en réduisant l'espace de recherche de façon incrémentielle. En décembre 2019, ces mêmes chercheurs ont annoncé avoir amélioré leur attaque et pouvoir obtenir une collision en $2^{63.7}$ opérations, pour un coût de 45k$. Les investigations continuent pour déterminer le coût minimum de ce type d'attaque qui pourrait en pratique s'avérer même inférieur (des attaques similaires sont démontrées également sur d'autres algorithmes de hachage similaires, y compris MD5 qui était déjà connu pour être cassé mais qui le devient encore plus facilement). Toutefois l'attaque annoncée ne concerne pas encore les empreintes de messages (ou signatures) HMAC basées sur SHA-1.

Description

La fonction de hachage SHA-1 est une fonction de hachage itérative, c'est-à-dire qu'elle itère sur le message en entrée découpé en blocs successifs de même taille une fonction, dite fonction de compression pour produire un condensé, ou haché, ou empreinte de taille fixe. Plus précisément elle repose sur la construction de Merkle-Damgård, c'est-à-dire que l'entrée est complétée par un procédé dur de bourrage pour que sa longueur soit un multiple de la taille du bloc, le dernier bloc contenant une représentation binaire de la taille de l'entrée initiale, ce qui permet de réduire la résistance aux collisions de la fonction de hachage à celle de la fonction de compression. Son fonctionnement est similaire à celui des fonctions MD4 et MD5 de Ronald Rivest.

Dans le cas de SHA-1 on a :

• taille de bloc : 512 bits ;
• taille du haché : 160 bits ;
• fonction de compression :{0,1}^160+512 → {0,1}¹⁶⁰ ;
• taille maximale de l'entrée : 2⁶⁴ bits.

Cette dernière limitation (théorique) vient du fait que la longueur de l'entrée, ajoutée dans le dernier bloc, est stockée sur 64 bits.

La fonction de compression est construite à partir d'opérations sur des mots de 32 bits, qui représentent des entiers non-signés inférieurs à 2³². Ces opérations sont :

• les opérations bit à bit usuelles :
  • le ET bit à bit ;
  • le OU bit à bit ;
  • le OU exclusif bit à bit ;
  • le NON bit à bit ;
• l'addition entière modulo 2³², c'est-à-dire l'addition informatique usuelle sur des entiers non-signés de 32 bits ;
• un décalage circulaire de s bits vers la gauche (0 ≤ s < 32).

Ces opérations s'implémentent de façon extrêmement efficace, mais combinées de façon adéquate, elles permettent d'obtenir une sortie qui parait avoir les qualités recherchées pour une fonction de hachage (en particulier résistance à la collision, résistance à la préimage).

Détails

Les spécifications de SHA-1 sont décrites pour la première fois en avril 1995 dans le document officiel du NIST FIPS 180-1 pour un standard de fonction de hachage cryptographique, puis reprises dans les versions successives de ce document jusqu'à la version de 2015 du FIPS-180-4. Elles ne seront pas reprises dans la version suivante. Elles sont largement accessibles sur Internet.

Bourrage

Le bourrage consiste à compléter le message initial M de longueur en bits l< 2⁶⁴, pour obtenir un message M' dont la longueur est un multiple de 512 bits (la taille de bloc). L'injectivité du procédé est une condition nécessaire : on aurait une collision évidente si M ≠ N mais que, après bourrage M' = N'.

Le message complété M' est obtenu en concaténant à la fin du message M un bit à 1 suivi d'une suite de bits à 0 dont la longueur dépend de l, suivie de la représentation binaire de l, codée sur 64 bits, c'est-à-dre que les 64 derniers bits de M' sont réservés à cet usage. La longueur de la suite de bits à 0 est la plus petite pour laquelle la longueur du message complété M' est un multiple de 512.

Fonction de hachage itérative

Le message complété M' est découpé en n blocs de 512 bits consécutifs, soient M⁽¹⁾ , … , M⁽ⁿ⁾. La concaténation est notée ||, on a :

M' = M⁽¹⁾ || … || M⁽ⁿ⁾.

L'algorithme itère une fonction de compression, soit compress : {0,1}¹⁶⁰ × {0,1}⁵¹² → {0,1}¹⁶⁰, et utilise un vecteur d'initialisation IV de 160 bits. Il produit une suite Hⁱ de valeurs de chaînage de 160 bits, la dernière valeur étant le haché.

H⁽⁰⁾ := IV

H⁽ⁱ⁺¹⁾ := compress(H⁽ⁱ⁾, M⁽ⁱ⁺¹⁾), pour 0≤ i < n

SHA-1(M) = H⁽ⁿ⁾.

Le vecteur d'initialisation de 160 bits IV est composé de 5 mots de 32 bits dont les valeurs sont données en hexadécimal (un chiffre hexadécimal représente 4 bits) dans les spécifications.

Fonction de compression

Dans ce qui suit les opérations sur les mots de 32 bits utilisées sont notées :

• ∧ pour le ET bit à bit ;
• ∨ pour le OU bit à bit ;
• ⊕ pour le OU exclusif bit à bit ;
• ¬ pour le NON bit à bit ;
• + pour l'opération sur les mots correspondant à l'addition arithmétique modulo 2³² (l'addition informatique de deux entiers non signés de 32 bits) ;
• x <<< s pour le décalage circulaire de s bits vers la gauche des bits de x, où x est un mot de 32 bits et 0 ≤ s < 32).

En notant << et >> les décalages ordinaires vers la gauche et vers la droite :

• << : décalage binaire à gauche, x << s s'obtient en supprimant les s bits de gauche de x et ajoutant s bits à zéro à droite ;
• >> : décalage binaire à droite, x >> s s'obtient en supprimant les s bits de droite de x et ajoutant s bits à zéro à gauche ;

alors x <<< s = (x << s) ∨ (x >> (32-s)).

La fonction de compression prend en entrée une valeur de chaînage H, analysée en 5 mots de 32 bits, et un bloc de 512 bits B analysé en 16 mots de 32 bits. La première phase est une phase d'expansion : le bloc B est étendu en un tableau W de 80 mots de 32 bits par la précédure suivante :

fonction expand(B){   Le bloc B de 512 bits et vu comme un tableau de 16 mots de 32 bits B[0] … B[15]
  W est un tableau de 80 mots de 32 bits      W[0] … W[79] 
  pour i de 0 à 79 {
    si i < 16
      alors W[i]:= B[i]
      sinon W[i] :=  (W[i – 3] ⊕ W[i – 8] ⊕ W[i – 14] ⊕ W[i – 16]) <<< 1 Ce décalage circulaire vers la
                                                                             gauche de 1 bit est la seule
                                                                             différence avec SHA-0 sur
                                                                             l'ensemble de l'algorithme 
   }
   renvoyer(W)
 } 

fonction compress(H,B) {
  (a0,b0,c,d0,e0) := H             H est analysé comme 5 mots de 32 bits
  (a,b,c,d,e) = (a0,b0,c0,d0,e0) 
  W := expand(B)
  pour t de 0 à 79 {
    temp := (a <<< 5) + f(t, b, c, d) + e + K[t] + W[t] 
    (a, b, c, d, e) := (temp, a, b <<< 30, c, d)
    }
  H := (a+a0, b+b0, c+c0, d+d0, e+e0)
    renvoyer(H)
 }

La fonction f en jeu à chacun des 80 tours est calculée par opérations bit à bit sur ses 3 derniers arguments et prend 3 formes différentes, en fonction du numéro de tour (premier argument) :

  0 ≤ t < 20 : f(t, b, c, d)  = (b ∧ c) ⊕ (¬b ∧ d)  (= (b ∧ c) ∨ (¬b ∧ d) )
 20 ≤ t < 40 : f(t, b, c, d)  = b ⊕ c ⊕ d
 40 ≤ t < 60 : f(t, b, c, d)  = (b ∧ c) ⊕ (b ∧ d) ⊕ (c ∧ d) (= (b ∧ c) ∨ (b ∧ d) ∨ (c ∧ d ))
 60 ≤ t < 80 : f(t, b, c, d)  = b ⊕ c ⊕ d

Les constantes de 32 bits K[t] prennent 4 valeurs différentes suivant le numéro de tour t, elles sont définies dans les spécifications.

Le SHA-1 en mode chiffrement

Les primitives des fonctions de hachage cryptographiques sont assez proches de celles des chiffrements symétriques. SHA-1, a été adaptée par Helena Handschuh et David Naccache pour obtenir un chiffrement par bloc appelé SHACAL.

Notes et références

E.A.Grechnikov,Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics, (http://eprint.iacr.org/2010/413)

Bibliographie

• « Hash functions : Overview », NIST, 9 septembre 2024 (consulté le 26 septembre 2026).
  • (en) « FIPS PUB 180-4 : Secure Hash Standard (SHS) », Federal Information Processing Standards Publication, NIST, août 2015 (DOI 10.6028/NIST.FIPS.180-4, consulté le 27 septembre 2026), version à jour du standard, contient encore une description de SHA-1 (qui sera supprimée dans la prochaine révision entamée en 2023.
  • (en) « FIPS PUB 180-1 : Secure Hash Standard (SHS) », Federal Information Processing Standards Publication, NIST, 17 avril 1995 (DOI 10.6028/NIST.FIPS.180-1, consulté le 27 septembre 2026), première publication de SHA-1 (obsolète comme standard).
• (en) RFC 3174, US Secure Hash Algorithm 1 (SHA1), IETF 2001.
• (en) Jean-Philippe Aumasson, Serious cryptography : A Practical Introduction to Modern Encryption, no starch press, 2018 (ISBN 978-1-59327-826-7)
• (en) Douglas Stinson et Maura Paterson, Cryptography : Theory and Practice, Londres, CRC Press, 2019, 4^e éd., 598 p. (ISBN 9781032476049, lire en ligne).

Voir aussi

Articles connexes

• Secure Hash Algorithm pour les autres fonctions de hachage chryptographiques publiées par le NIST.

Liens externes

• (en) Slides d'Adi Shamir à CRYPTO 2005[PDF].
• (en) SHACAL[PDF], description de SHA-1 en mode chiffrement (SHACAL)
• (fr) Un calculateur de hash en SHA-1

Sources

• Cet article est partiellement ou en totalité issu de l'article intitulé « Spécifications SHA-1 » (voir la liste des auteurs).