SHA-1

• a, b, c, d, e = variables de travail (en l'occurrence des mots de w bits), utilisées dans le calcul des hachés.
• ${\displaystyle H^{(i)}}$ = la valeur de hachage n°i. ${\displaystyle H^{(0)}}$ est la valeur initiale du hachage. ${\displaystyle H^{(N)}}$ est la dernière valeur de hachage.
• ${\displaystyle H_{j}^{(i)}}$ = le mot (w bits) n°j de la valeur de hachage n°i, où ${\displaystyle H_{0}^{(i)}}$ est le mot de poids le plus fort (à gauche) de la valeur de hachage i.
• ${\displaystyle K_{t}}$ = constantes itératives selon la valeur de t, utilisées dans le calcul de hachage
• k = nombre de 0 ajoutés au message lors du prétraitement (complément)
• l = longueur du message M, en bits
• m = nombre de bits contenus dans un bloc, soit 512 bits
• M = message à traiter
• ${\displaystyle M^{(i)}}$ = bloc n°i (m bits), du message M
• ${\displaystyle M_{j}^{(i)}}$ = mot (w bits) n°j, du bloc (m bits) n°i, du message M
• n = nombre de bits de décalage ou de rotation à appliquer au mot quand associé à une fonction binaire
• N = nombre de blocs de m bits contenus dans le message M après complément
• T = variable temporaire, mot de w bits, utilisée dans le calcul de condensé
• w = nombre de bits contenus dans un mot, soit 32 bits.
• ${\displaystyle W_{t}}$ = le mot n°t du tableau déduit du message

La notation hexadécimale utilisée ici sera: ${\displaystyle {\mbox{0x}}}$ (exemple : ${\displaystyle H_{0}^{(0)}={\mbox{0x12ab34ef}}}$)

• ${\displaystyle \wedge }$ = opération binaire AND
• ${\displaystyle \vee }$ = opération binaire OR
• ${\displaystyle \oplus }$ = opération binaire XOR
• ${\displaystyle \lnot }$ = complément binaire
• ${\displaystyle +}$ = addition modulo ${\displaystyle 2^{w}}$
• ${\displaystyle <<}$ = décalage binaire à gauche, où ${\displaystyle x<<n}$ s'obtient en supprimant les n bits de gauche de x et ajoutant n zéros à droite.
• ${\displaystyle >>}$ = décalage binaire à droite, où ${\displaystyle x>>n}$ s'obtient en supprimant les n bits de droite de x et ajoutant n zéros à gauche.

Elles utilisent les conventions suivantes :

• opérations binaires bit à bit (cf. symboles)
• addition modulo ${\displaystyle 2^{w}}$, soit ${\displaystyle 2^{32}}$
  L'opération ${\displaystyle x+y}$ est définie comme suit. Soient deux mots ${\displaystyle x{\mbox{ et }}y}$ représentant les nombres entiers ${\displaystyle X{\mbox{ et }}Y}$, tels que ${\displaystyle 0\leq X<2^{32}}$ et ${\displaystyle 0\leq Y<2^{32}}$, on a ${\displaystyle Z}$ le résultat de l'addition modulo ${\displaystyle 2^{32}}$ de ${\displaystyle X{\mbox{ et }}Y}$.
  ${\displaystyle Z=(X+Y){\mbox{ mod }}2^{32}{\mbox{, }}0\leq Z<2^{32}}$. On convertit ${\displaystyle Z}$ en un mot ${\displaystyle z}$, et on définit alors ${\displaystyle z=x+y}$
• l'opération de rotation binaire par la gauche ${\displaystyle ROTL^{n}(x)}$, où x est un mot de 32 bits et ${\displaystyle 0\leq n\leq 32}$, est définie par: ${\displaystyle ROTL^{n}(x)=(x<<n)\vee (x>>32-n)}$

Cette section décrit les fonctions utilisées lors du calcul des valeurs de hachage. SHA-1 utilise une succession de fonctions logiques ${\displaystyle f_{0},f_{1},...,f_{79}~}$. Chaque fonction ${\displaystyle f_{t}~}$, où ${\displaystyle 0\leq t\leq 79}$, travaille sur trois variables entières de 32 bits ${\displaystyle (b,c,d)~}$ et retourne un entier de 32 bits :

${\displaystyle f_{t}=\left\{{\begin{array}{lcl}Choix&{\text{si}}&0\leq t\leq 19\\Parite&{\text{si}}&20\leq t\leq 39\\Majorite&{\text{si}}&40\leq t\leq 59\\Parite&{\text{si}}&60\leq t\leq 79\\\end{array}}\right.~}$

définie par une des trois fonctions binaires classiques suivantes, où

${\displaystyle {\begin{array}{lcl}Choix(b,c,d)&=&(b\wedge c)\vee ((\lnot b)\wedge d)\\&=&(b\wedge c)\oplus ((\lnot b)\wedge d)\\&=&(b\wedge c)+((\lnot b)\wedge d)\\&=&d\oplus (b\wedge (c\oplus d))\\&=&\operatorname {vec_{--}sel} (d,c,b)\\\end{array}}~}$

est la fonction binaire (plusieurs formules équivalentes ci-dessus) de choix entre les bits correspondants des deux premières variables, selon la valeur du bit correspondant de la troisième variable,

${\displaystyle {\begin{array}{lcl}Majorite(b,c,d)&=&(b\wedge c)\vee (b\wedge d)\vee (c\wedge d)\\&=&(b\wedge c)\oplus (b\wedge d)\oplus (c\wedge d)\\&=&(b\wedge c)\vee (d\wedge (b\vee c))\\&=&(b\wedge c)\vee (d\wedge (b\oplus c))\\&=&(b\wedge c)\oplus (d\wedge (b\oplus c))\\&=&(b\wedge c)+(d\wedge (b\oplus c))\\&=&\operatorname {vec_{--}sel} (c,b,c\oplus d)\\&=&Choix(c\oplus d,b,c)\\\end{array}}~}$

est la fonction binaire (plusieurs formules équivalentes ci-dessus, ainsi que d'autres car elle est commutative sur ses 3 variables) indiquant si la majorité (au moins deux) des trois bits correspondants des trois variables sont à 1, et

${\displaystyle Parite(b,c,d)=b\oplus c\oplus d~}$

est la fonction binaire (commutative sur toutes ses variables) d'union exclusive ou parité des trois variables.

SHA-1 utilise quatre valeurs réparties dans les 80 constantes ${\displaystyle K_{0},K_{1},...,K_{79}~}$, d'après la règle

${\displaystyle K_{t}=\left\{{\begin{matrix}{\mbox{0x5a827999}},&{\mbox{si }}0\leq t\leq 19\\{\mbox{0x6ed9eba1}},&{\mbox{si }}20\leq t\leq 39\\{\mbox{0x8f1bbcdc}},&{\mbox{si }}40\leq t\leq 59\\{\mbox{0xca62c1d6}},&{\mbox{si }}60\leq t\leq 79\end{matrix}}\right.}$

Cette opération se déroule en trois étapes : compléter le message M, découper le résultat en blocs, et initialiser les valeurs de hachage ${\displaystyle H^{(0)}~}$

Il s'agit ici d'ajouter des informations à M pour qu'il soit d'une taille multiple de 512 bits.
pour ce faire, l'on ajoute un bit "1" à la fin du message M, puis k zéros, où k est la plus petite solution non négative de l'équation: l + 1 + k = 448 mod 512, avec l = taille de M en bits.
On ajoute alors un bloc de 64 bits correspondant à la représentation binaire de l.

Exemples :

• M = "abc", l = 8 x 3 = 24, k = 448 - (l + 1) = 448 - (24 + 1) = 423
  On ajoute "1", puis quatre cent vingt trois "0", puis 64 bits finissant par "011000" (pour 24) à M.
  On obtient alors un message complété à 512 bits.
• M quelconque tel que l = 500 bits, k = 448 - (l + 1) = 448 - (500 + 1) = -53
  Comme k ne peut pas être négatif, on lui ajoute 512 en prenant en compte le modulo de l'équation, pour obtenir ${\displaystyle k=459}$
  On ajoute "1", puis quatre cent cinquante neuf "0", puis 64 bits finissant par "111110100" (pour 500) à M.
  On obtient alors un message complété à 512 bits.

Le message complété est découpé en N blocs de 512 bits, notés ${\displaystyle M^{(1)},M^{(2)},...,M^{(N)}~}$. Chaque bloc de 512 bits est ensuite découpé en 16 mots de 32 bits, notés ${\displaystyle M_{0}^{(i)},M_{1}^{(i)},...,M_{15}^{(i)}}$.

Le vecteur initial est défini comme suit :

${\displaystyle \left({\begin{matrix}H_{0}^{(0)}\\H_{1}^{(0)}\\H_{2}^{(0)}\\H_{3}^{(0)}\\H_{4}^{(0)}\end{matrix}}\right):=\left({\begin{matrix}{\mbox{0x67452301}}\\{\mbox{0xefcdab89}}\\{\mbox{0x98badcfe}}\\{\mbox{0x10325476}}\\{\mbox{0xc3d2e1f0}}\end{matrix}}\right)~}$

Pour ce traitement on utilisera :

• la fonction d'expansion d'un bloc de 16 mots du message en un bloc intermédiaire de 80 mots :

  ${\displaystyle W_{t}^{(i)}=\left\{{\begin{matrix}M_{t}^{(i)}&{\text{si}}&0\leq t\leq 15\\ROTL^{1}\left(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16}\right)&{\text{si}}&16\leq t\leq 79\\\end{matrix}}\right.}$

• la fonction suivante de compression d'un bloc intermédiaire de 80 mots sur un vecteur de 5 mots :

  ${\displaystyle C_{t}\left(W,\left({\begin{matrix}a\\b\\c\\d\\e\end{matrix}}\right)\right)=\left({\begin{matrix}\operatorname {ROTL} ^{5}(a)+f_{t}(b,c,d)+e+K_{t}+W_{t}\\a\\\operatorname {ROTL} ^{30}(b)\\c\\d\end{matrix}}\right)~}$

  où ${\displaystyle f_{t}~}$ notée ci-après est la fonction binaire, décrite plus haut.

• cinq variables contenant les valeurs de hachage, notées ${\displaystyle H_{0}^{(i)}}$ et initialisées précédemment en ${\displaystyle H_{0}^{(0)}}$.
  Ces variables contiendront itérativement de nouvelles valeurs de hachage, ${\displaystyle H^{(i)}~}$, pour finalement contenir le condensé de M, dans ${\displaystyle H^{(N)}~}$.

On traite successivement les blocs de M selon les étapes suivantes, pour ${\displaystyle 1\leq i\leq N~}$ :

1. On étend un bloc ${\displaystyle M^{(i)}~}$ de 16 mots du message en un bloc temporaire ${\displaystyle W_{t}^{(i)}}$ de 80 mots où ${\displaystyle 0\leq t\leq 79~}$, selon

   ${\displaystyle W_{t}^{(i)}=\left\{{\begin{matrix}M_{t}^{(i)}&{\text{si}}&0\leq t\leq 15\\ROTL^{1}\left(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16}\right)&{\text{si}}&16\leq t\leq 79\\\end{matrix}}\right.}$

2. On initialise un vecteur temporaire avec les valeurs de hachage du tour précédent :

   ${\displaystyle \left({\begin{matrix}a\\b\\c\\d\\e\end{matrix}}\right):=\left({\begin{matrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{(i-1)}\\H_{3}^{(i-1)}\\H_{4}^{(i-1)}\end{matrix}}\right)~}$

3. On réduit le bloc temporaire ${\displaystyle W_{t}^{(i-1)}}$ sur ce vecteur temporaire :

   ${\displaystyle \left({\begin{matrix}a\\b\\c\\d\\e\end{matrix}}\right):=\left({\begin{matrix}\operatorname {ROTL} ^{5}(a)+f_{t}(b,c,d)+e+K_{t}+W_{t}\\a\\\operatorname {ROTL} ^{30}(b)\\c\\d\end{matrix}}\right)~}$

   où ${\displaystyle f_{t}~}$ notée ci-après est la fonction logique, décrite plus haut.

4. On combine le vecteur obtenu avec le condensé intermédiaire par une simple addition :

   ${\displaystyle \left({\begin{matrix}H_{0}^{(i)}\\H_{1}^{(i)}\\H_{2}^{(i)}\\H_{3}^{(i)}\\H_{4}^{(i)}\end{matrix}}\right):=\left({\begin{matrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{(i-1)}\\H_{3}^{(i-1)}\\H_{4}^{(i-1)}\end{matrix}}\right)+\left({\begin{matrix}a\\b\\c\\d\\e\end{matrix}}\right)~}$

Après répétition des quatre étapes ci-dessus pour les N blocs du message M, le condensé de 160 bits de M est obtenu par concaténation des valeurs

${\displaystyle H_{0}^{(N)}||H_{1}^{(N)}||H_{2}^{(N)}||H_{3}^{(N)}||H_{4}^{(N)}~}$

Remarque : Il existe d'autres méthodes de calcul du condensé SHA-1 donnant des résultats identiques.

• On doit noter notamment que la rotation de 30 bits vers la gauche ${\displaystyle c=ROTL^{30}(b)~}$ calculée sur 32 bits est trivialement équivalente à une rotation de 2 bits vers la droite ${\displaystyle c=ROTR^{2}(b)~}$.
• Comme le montrent Laurent et Peyrin dans leur article de 2019, les opérations de chacune des 80 boucles de l'étape 3 sont également réductibles, de façon équivalente, à une seule opération

  ${\displaystyle A_{t+1}=ROTL^{5}\left(A_{t-1}\right)+f_{t}\left(A_{t-1},\,ROTR^{2}\left(A_{t-2}\right),\,ROTR^{2}\left(A_{t-3}\right)\right)+ROTR^{2}\left(A_{t-4}\right)+K_{t}+W_{t}~}$

  où les 5 variables ${\displaystyle (a,b,c,d,e)~}$ sont en fait parties d'un unique registre d'état ${\displaystyle A_{t}~}$ de 160 bits, dont on ne doit mémoriser à chaque boucle que les 4 valeurs précédentes

  Cela ne nécessite que de connaitre les valeurs d'initialisation des 3 « valeurs précédentes » associées à la valeur initiale ${\displaystyle A_{0}}$ du registre pour les 3 première boucles, ce qui est possible car les valeurs initiales (de l'étape 2) sont inversibles pour la fonction ${\displaystyle f_{0}=Ch~}$ sur seulement 3 étapes, cette même fonction étant utilisée sans changement pour les 20 premières boucles dont les 3 premières, et toutes les fonctions ${\displaystyle f_{t}~}$ définies à l'origine sur 32 bits sont extensibles sans changement à 160 bits).

  D'autre part, les rotations de cette dernière formule (réduite à une opération) portent sur des valeurs de 160 bits (et non 32 bits), de sorte qu'alors ${\displaystyle ROTR^{2}(A_{t})=ROTL^{158}(A_{t})~}$.

• La fonction de compression obtenue par ces 80 boucles est donc une composition récursive de fonctions à une seule variable de 160 bits (portant sur l'expansion triviale et inversible à 160 bits ${\displaystyle W^{(i)}~}$, à l'étape 1, d'un bloc de 32 bits ${\displaystyle M^{(i)}~}$ extrait du message en clair), terminée par l'addition de la valeur de hachage intermédiaire du message jusqu'au bloc précédent (ou la valeur initiale constante ${\displaystyle H^{(0)}~}$ de la fonction de hachage) :

  ${\displaystyle H^{(i)}=\left(Parity^{20}\,\circ \,Maj^{20}\,\circ \,Parity^{20}\,\circ \,Ch^{20}\right)\left(W^{(i)}\right)+H^{(i-1)}~}$

  Noter que dans cette définition, les fonctions initialement définies sur 32 bits ${\displaystyle Parity,Maj,Ch}$ sont modifiées pour être étendues à 160 bits en utilisant la formule à une seule opération, où viennent s'ajouter les rotations sur 5 bits vers la gauche ou 2 bits vers la droite des valeurs précédentes de ${\displaystyle A_{t}}$ et les additions de constantes ${\displaystyle K_{t}~}$.

• La résistance aux collisions de SHA-1 est liée directement à la non-inversibilité (conjecturée) de la fonction composée obtenue ${\displaystyle Parity^{20}\,\circ \,Maj^{20}\,\circ \,Parity^{20}\,\circ \,Ch^{20}~}$, puisque la fonction d'expansion ${\displaystyle W^{(i)}~}$des messages ${\displaystyle M^{(i)}~}$est trivialement inversible.

Même si un gain de 2¹⁷ opérations permettait de diviser le temps de recherche par un facteur de 131 072, l'attaque de 2009 avec ses 2⁶³ opérations était à la limite de ce qui était réalisable. Adi Shamir a toutefois laissé entendre que l'attaque pouvait probablement être abordée via un calcul distribué à l'échelle planétaire. Mais maintenant (en avril 2019 avec la méthode publiée par Leurent et Peyrin) avec un gain d'au moins 2³³ opérations (soit un facteur d'accélération voisin de dix milliards), une telle attaque est tout à fait réalisable de façon pratique avec des moyens facilement accessibles, d'autant plus qu'en 10 ans la performance des systèmes s'est considérablement accrue, avec en plus l'arrivée massive et à bas coût sur le marché mondial des GPU (ainsi qu'avec la multiplication des offres peu onéreuses d'hébergement d'applications privées sur le « cloud » permettant de les utiliser), capables de réaliser localement des calculs massivement parallèles et de façon discrète, sans faire nécessairement appel à des ressources externes distribuées (également détournées de façon illégale et aujourd'hui à très grande échelle) accessibles sur un réseau planétaire où une telle mise en œuvre pourrait être détectée assez facilement.

La règle veut qu'une attaque plus rapide que les attaques génériques (celle des anniversaires en l'occurrence) rende l'algorithme non sûr du point de vue cryptographique. De plus, la structure de SHA-1 reste assez proche de celle de MD5 (qui est déconseillé pour les nouvelles applications) pour lequel on a trouvé effectivement des collisions. Depuis l'annonce de l'attaque de Wang et al., SHA-1 a tendance à être retiré progressivement, au moins de certaines applications cryptographiques, essentiellement au profit de SHA-256 (d'autres fonctions de hachage sont également utilisées comme Whirlpool, Tiger, RIPEMD-160, et d'autres plus récentes comme ChaCha20, Curve25519, NTRU, ainsi que BLAKE2b ou BLAKE2s qui sont suggérés en mai 2019 pour les empreintes de mots de passe et pour la sécurisation des échanges de clés de chiffrement, en remplacement de SHA-1 et même de SHA-2 ou SHA-3). SHA-1 reste malheureusement encore largement utilisé, d'autant que la sécurité de certaines applications repose sur la résistance à la recherche de préimage (ce qui n'est plus le cas depuis avril 2019 si cette recherche est techniquement réalisable), et non sur la seule résistance aux collisions[17].

Vu les faiblesses constatées sur SHA-1, et la conception de SHA-2 qui est voisine, une compétition a été organisée par la NIST, afin de trouver un nouveau standard de hachage (SHA-3) comme cela fut le cas il y a quelques années pour la cryptographie symétrique avec AES. Toutefois les révélations d'Edouard Snowden concernant la manipulation par la NSA des constantes utilisées dans des algorithmes de sécurité standardisés par le NIST (y compris dans les algorithmes de chiffrement récents, et dans des algorithmes de génération de nombres pseudo-aléatoires basés sur les courbes elliptiques nécessaires à la production des clés de chiffrement) ont levé le doute sur la réelle sécurité des fonctions de hachage de la famille SHA : ainsi concernant SHA-1, les constantes d'initialisation n'obéissent de façon évidente à aucun critère cryptographique satisfaisant et ont un intérêt seulement mnémonique, elles pourraient ainsi constituer des portes dérobées volontairement introduites ou laissées par la NSA pour faciliter la découverte de collisions avec les moyens techniques dont disposait alors la NSA au moment de sa standardisation et sa publication par le NIST en 1995.

L'attaque produite par Wang et al. ne concerne que des collisions quelconques (tout comme leur fameuse collision complète sur le MD5). C’est-à-dire que l'on peut trouver deux messages au contenu aléatoire qui produisent la même signature. En revanche, à partir d'une signature donnée, il était considéré comme impossible (jusqu'en avril 2019) de forger un second message qui conduise à la même valeur, à condition d'utiliser un système d'authentification de messages (tel que HMAC) en complément de la fonction de hachage nécessaire à ce système. Or, c'est ce type d'attaque qui pourrait mettre en péril les applications comme PGP et l'authenticité des données.

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

• Secure Hash Algorithm pour les autres algorithmes de cette famille

• (fr) Un calculateur de hash en SHA-1
• (en) SHA1 dictionary attack
• (en) Vidéo de CRYPTO 2005, avec la présentation de l'attaque améliorée par Adi Shamir
• (en) Slides d'Adi Shamir à CRYPTO 2005[PDF]
• (en) A New Statistical Testing for Symmetric Ciphers and Hash Functions, test statistique de Eric Filiol
• (en) SHACAL[PDF], description de SHA-1 en mode chiffrement (SHACAL)
• (en) RFC 3174, US Secure Hash Algorithm 1 (SHA1)
• (en) SHA-1 collisions now 2⁵², L'attaque sur SHA-1 présentée à Eurocrypt 2009.