Voir la source de SHA-1

[[Image:SHA-1.svg|thumb|right|300px|Un tour de la fonction de compression de SHA-1 :<br/>  
''A'', ''B'', ''C'', ''D'', ''E'' sont des mots de 32 bits ;<br/>
<<<<sub>''n''</sub> désigne une rotation des bits par décalage de ''n'' bits vers la gauche ;<br/>
''F'' est une fonction (non linéaire sur le [[corps fini|corps]] '''F'''<sub>2</sub> des booléens) qui dépend du numéro de tour ''t'' ;<br/>
⊞ est l'addition modulo 2<sup>32</sup> (l'addition des entiers machines non signés de 32 bits), qui est non linéaire sur '''F'''<sub>2</sub> ;<br/>
''K<sub>t</sub>'' est une constante (32 bits) qui dépend du numéro de tour ''t'' ;<br/>
''W<sub>t</sub>'' 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''' ({{lang|en|''[[Secure Hash Algorithm]]''}}, prononcé {{API|/ʃa.œ̃/}}<ref>{{lien vidéo|url=https://www.youtube.com/watch?v=6NmrBX_aEo0&t=54|titre=Qu'est-ce qu'un certificat de signature de code ?|auteur=GoDaddy Canada|temps=54 s}}</ref>) est une [[fonction de hachage cryptographique]] conçue par la {{lang|en|''[[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]] ({{lang|en|''[[Federal Information Processing Standard]]''}} du {{lang|en|''[[National Institute of Standards and Technology]]''}} (NIST)). Elle produit un résultat (appelé « {{lang|en|''hash''}} » ou ''condensat'') de {{unité|160|[[bit]]s}} (20 octets), habituellement représenté par un nombre hexadécimal de 40 caractères.

SHA-1 n'est plus considéré comme sûr contre des adversaires disposant de moyens importants. En 2005, des [[Cryptanalyste|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<ref>{{lien web|langue=en|url=https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html|titre=Schneier on Security: Cryptanalysis of SHA-1|date=18 février 2005|auteur=Schneier, Bruce}}</ref>. Depuis 2010, de nombreuses organisations ont recommandé son remplacement par [[SHA-2]] ou [[SHA-3]]<ref>{{lien web|langue=en|url=http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html|titre=NIST.gov - Computer Security Division - Computer Security Resource Center}}</ref>{{,}}<ref name="shappening">{{lien web|langue=en|url=https://sites.google.com/site/itstheshappening/|titre=The SHAppening: freestart collisions for SHA-1|consulté le=2015-10-09|prénom1=Marc|nom1=Stevens1|prénom2=Pierre|nom2=Karpman|prénom3=Thomas|nom3=Peyrin}}</ref>{{,}}<ref>{{lien web|langue=en|url=https://www.schneier.com/blog/archives/2015/10/sha-1_freestart.html|auteur=Bruce Schneier|date=8 octobre 2015|titre=SHA-1 Freestart Collision|série=Schneier on Security}}</ref>. [[Microsoft]]<ref>{{lien web|langue=en|url=http://social.technet.microsoft.com/wiki/contents/articles/32288.windows-enforcement-of-authenticode-code-signing-and-timestamping.aspx|titre=Windows Enforcement of Authenticode Code Signing and Timestamping|éditeur=Microsoft|date=2015-09-24|consulté le=2016-08-07}}</ref>, [[Google]]<ref>{{lien web|langue=en|url=https://groups.google.com/a/chromium.org/d/msg/blink-dev/2-R4XziFc7A/i_JipRRJoDQJ|titre=Intent to Deprecate: SHA-1 certificates|éditeur=Google|date=2014-09-03|consulté le=2014-09-04}}</ref> et [[Mozilla Foundation|Mozilla]]<ref>{{lien web|langue=en|url=https://bugzilla.mozilla.org/show_bug.cgi?id=942515|titre=Bug 942515 - stop accepting SHA-1-based SSL certificates with notBefore >= 2014-03-01 and notAfter >= 2017-01-01, or any SHA-1-based SSL certificates after 2017-01-01|éditeur=Mozilla|consulté le=2014-09-04}}</ref>{{,}}<ref>{{lien web|langue=en|url=https://wiki.mozilla.org/CA:Problematic_Practices#SHA-1_Certificates|titre=CA:Problematic Practices - MozillaWiki|éditeur=Mozilla|consulté le=2014-09-09}}</ref>{{,}}<ref>{{lien web|langue=en|url=https://blog.mozilla.org/security/2014/09/23/phasing-out-certificates-with-sha-1-based-signature-algorithms/|titre=Phasing Out Certificates with SHA-1 based Signature Algorithms <nowiki>|</nowiki> Mozilla Security Blog|éditeur=Mozilla|date=2014-09-23|consulté le=2014-09-24}}</ref> ont annoncé que leurs navigateurs respectifs cesseraient d'accepter les [[Certificat électronique|certificats]] SHA-1 au plus tard en 2017.

== Origine : SHA-0 et SHA-1 ==
Le SHA-1 est le successeur du [[SHA-0]] qui a été rapidement mis de côté par le [[National Institute of Standards and Technology|NIST]] pour des raisons de sécurité insuffisante. Le 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 du SHA-0 et certains constats que l'on attribue à la [[National Security Agency|NSA]], le SHA-0 s'est vu modifié peu après sa sortie (1993) et complexifié pour devenir le SHA-1 (1995). Une collision complète sur le SHA-0 a été découverte par [[Antoine Joux]] ''et al.'' en {{date-|août 2004}}. En 2005, la cryptanalyste [[Wang Xiaoyun|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 plus efficace que l'[[attaque des anniversaires]] (l'attaque générique de référence)<ref>{{Lien web|titre = Cryptanalysis of SHA-1 - Schneier on Security|url = https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html|site = www.schneier.com|consulté le = 2015-05-27}}</ref>. L'attaque complète sera publiée à Crypto 2015<ref>{{Lien web|titre=Finding Collisions in the Full SHA-1|url=https://www.iacr.org/cryptodb/data/paper.php?pubkey=1826|site=www.iacr.org|consulté le=2017-06-29}}</ref>. Le [[National Institute of Standards and Technology|NIST]] pour sa part recommande de passer sur un algorithme SHA-2 ou SHA-3 quand c'est possible. Depuis 2013, [[Microsoft]] a déclaré l’[[obsolescence]] du SHA-1<ref>{{Lien web|titre = SHA1 Deprecation Policy - Windows PKI blog - Site Home - TechNet Blogs|url = http://blogs.technet.com/b/pki/archive/2013/11/12/sha1-deprecation-policy.aspx|site = blogs.technet.com|consulté le = 2015-05-27}}</ref> et en 2014. L'[[Agence nationale de la sécurité des systèmes d'information|ANSSI]] déconseille son utilisation dans la seconde version de son [[Référentiel général de sécurité|Référentiel Général de Sécurité]] (RGS)<ref>{{Article|langue=fr-FR|auteur1=ANSSI|titre=Liste des documents constitutifs du RGS v.2.0|périodique=ANSSI|date=1er juillet 2014|lire en ligne=https://www.ssi.gouv.fr/administration/reglementation/confiance-numerique/le-referentiel-general-de-securite-rgs/liste-des-documents-constitutifs-du-rgs-v-2-0/|consulté le=2017-06-29|pages=}}</ref> d'application au {{date-|1 juillet 2014}}. Enfin, [[Google]] annonce que ses versions de Chrome n'accepteront plus, de façon graduelle, le SHA-1 jusqu'à le refuser pour les certificats expirant après le {{date-|1 janvier 2017}}<ref>{{Lien web|titre = Google Groupes|url = https://groups.google.com/a/chromium.org/d/msg/blink-dev/2-R4XziFc7A/i_JipRRJoDQJ|site = groups.google.com|consulté le = 2015-05-27}}</ref>.

En {{date-|février 2017}} [[Google]] et le [[Centrum voor Wiskunde en Informatica]] annoncent une attaque effective et la première collision sur SHA-1<ref>{{lien web |langue=en |titre=Announcing the first SHA1 collision |url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html |site=Google Online Security Blog |consulté le=22-10-2020}}.</ref>.

== Exemples ==
Voici la signature obtenue sur une phrase (codée en utf8) : 
{{retrait|1= <tt>SHA1("Wikipédia, l'encyclopédie libre et gratuite")</tt> = <tt>6153A6FA0E4880D9B8D0BE4720F78E895265D0A9</tt>. }}

En modifiant un caractère, la signature change radicalement : 
{{retrait|1= <tt>SHA1("Wikipédia, l'encyclopédie libre et gratuit'''E'''")</tt> = <tt>11F453355B28E1158D4E516A2D3EDF96B3450406</tt>. }}

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.

== Fonctionnement du SHA-1 ==
Le SHA-1 prend un message d'un maximum de 2<sup>64</sup> bits en entrée. Son fonctionnement est similaire à celui du [[MD4]] ou [[MD5]] de [[Ronald Rivest]]. Quatre [[Application (mathématiques)|fonctions]] booléennes sont définies, elles prennent 3 mots de {{unité|32|bits}} en entrée et calculent un mot de {{unité|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 {{unité|64|bits}}. La  série de 0 a une longueur telle que la séquence ainsi prolongée a une longueur multiple de {{unité|512|bits}}. L'algorithme travaille ensuite successivement sur des blocs de {{unité|512|bits}}.

Pour chaque bloc l'algorithme calcule 80 tours (ou rondes, « {{lang|en|''rounds''}} » en anglais) successifs et applique une série de transformations sur l'entrée. La première étape consiste à calculer 80 valeurs sur {{unité|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 [[OU exclusif|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 {{unité|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 [[Fonction booléenne|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 = {{unité|160|bits}}) représentent la signature.

== Caractéristiques ==
Les caractéristiques de SHA-1 sont les suivantes :
* taille du message : 2<sup>64</sup> bits maximum
* taille des blocs : 512 bits
* taille des mots : 32 bits
* taille du condensé : 160 bits
* niveau de sécurité :  collision en 2<sup>63</sup> opérations.
{{retrait|L’[[Attaque des anniversaires|attaque générique des anniversaires]] permet de trouver une collision en 2<sup>80</sup> 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<sup>69</sup> connue depuis 2005<ref name="rfc">[[:rfc:6194|RFC 6194]]</ref>, qui a été améliorée en une attaque en 2<sup>63</sup> opérations. Ces attaques, bien que théoriques, ouvrent la possibilité que de réelles collisions soient découvertes (ce qui est également une question de temps et de moyens).}}

== Détails de l'algorithme ==
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<ref>FIPS 180-1, ''Federal Information Processing Standards Publication 180-1 Announcing the Standard for Secure Hash Standard'', 17 avril 1995 [http://www.itl.nist.gov/fipspubs/fip180-1.htm lire en ligne]</ref>. Elles sont reprises dans les versions successives de ce document, FIPS-180-2, FIPS-180-3 et FIPS-180-4<ref>voir page {{en}} [http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html Secure Hashing du NIST]. En plus de SHA-1, le standard inclut les algorithmes de la famille [[SHA-2]] à partir de la version {{en}} [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS-180-2]{{pdf}} (août 2002), avec de nouvelles variantes pour SHA-2 dans les versions successives {{en}} [http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf FIPS-180-3]{{pdf}} (octobre 2008) et {{en}} [http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf FIPS-180-4]{{pdf}} (mars 2012).</ref>.

L'algorithme SHA-1 transforme un message de longueur inférieure à 2<sup>64</sup> bits en un haché, ou condensé de ce message, qui est de longueur 160 bits. Il adopte la [[construction de Merkle-Damgård]] : schéma itératif à partir d'une [[fonction de compression]] dont l'entrée est de taille fixe, et ajout en fin de message de sa longueur (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.

Cet algorithme peut être découpé en deux phases : le prétraitement et le calcul du condensé.

* Le prétraitement implique 
*# de compléter le message par des informations le rendant compatible avec l'algorithme SHA-1 ([[remplissage (cryptographie)|remplissage]])
*# son analyse pour le découper en blocs de 512 bits
*# l'initialisation de variables de travail
* Le calcul du condensé génère un tableau à partir du message complété, puis le transforme via l'utilisation de fonctions, de constantes, d'opérations binaires détaillées plus loin. L'ensemble effectué de manière itérative permet de générer des séries de valeurs de hachage à chaque tour. Le condensé final est le dernier état de ces valeurs de hachage.

=== Symboles et termes utilisés ===
==== Paramètres ====
* a, b, c, d, e = variables de travail (en l'occurrence des mots de w bits), utilisées dans le calcul des hachés.
* <math>H^{(i)}</math> = la valeur de hachage n°i. <math>H^{(0)}</math> est la valeur initiale du hachage. <math>H^{(N)}</math> est la dernière valeur de hachage.
* <math>H_j^{(i)}</math> = le mot (w bits) n°j de la valeur de hachage n°i, où <math>H_0^{(i)}</math> est le mot de poids le plus fort (à gauche) de la valeur de hachage i.
* <math>K_t</math> = 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
* <math>M^{(i)}</math> = bloc n°i (m bits), du message M
* <math>M_j^{(i)}</math> = 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.
* <math>W_t</math> = le mot n°t du tableau déduit du message

==== Symboles ====
La notation hexadécimale utilisée ici sera: <math>\mbox{0x}</math> (exemple : <math>H_0^{(0)} = \mbox{0x12ab34ef}</math>)

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

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

=== Fonctions et constantes ===
==== Fonctions ====
Cette section décrit les fonctions utilisées lors du calcul des valeurs de hachage.
SHA-1 utilise une succession de fonctions logiques <math>f_0, f_1, ..., f_{79}~</math>. Chaque fonction <math>f_t~</math>, où <math>0 \le t \le 79</math>, travaille sur trois variables entières de 32 bits <math>(b, c, d)~</math> et retourne un entier de 32 bits :
: <math>f_t = \left\{\begin{array}{lcl}
  \text{Choix}    & \text{si} &  0 \le t \le 19 \\
  \text{Parité}   & \text{si} & 20 \le t \le 39 \\
  \text{Majorité} & \text{si} & 40 \le t \le 59 \\
  \text{Parité}   & \text{si} & 60 \le t \le 79 \\
  \end{array}\right.~</math>
définie par une des trois fonctions binaires classiques suivantes, où
: <math>\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}~</math>
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,
: <math>\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}~</math>
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
: <math>Parite(b, c, d) = b \oplus c \oplus d~</math>
est la fonction binaire (commutative sur toutes ses variables) d'union exclusive ou parité des trois variables.

==== Constantes ====
SHA-1 utilise quatre valeurs réparties dans les 80 constantes <math>K_0, K_1, ..., K_{79}~</math>, d'après la règle

<math>K_t = \left\{\begin{matrix} \mbox{0x5a827999}, & \mbox{si }0 \le t \le 19 \\ \mbox{0x6ed9eba1}, & \mbox{si }20 \le t\le 39 \\ \mbox{0x8f1bbcdc}, & \mbox{si }40\le t\le 59 \\ \mbox{0xca62c1d6}, & \mbox{si }60\le t\le 79\end{matrix}\right.</math>

=== Prétraitement ===
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 <math>H^{(0)}~</math>

==== Complément de M ====
Il s'agit ici d'ajouter des informations à M pour qu'il soit d'une taille multiple de 512 bits.<br />
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.<br />
On ajoute alors un bloc de 64 bits correspondant à la [[Système binaire|représentation binaire]] de l.

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

==== Découpage en blocs ====
Le message complété est découpé en N blocs de 512 bits, notés <math>M^{(1)}, M^{(2)}, ..., M^{(N)}~</math>.
Chaque bloc de 512 bits est ensuite découpé en 16 mots de 32 bits, notés <math>M_0^{(i)}, M_1^{(i)}, ..., M_{15}^{(i)}</math>.

==== Initialisation ====
Le vecteur initial est défini comme suit :

: <math>\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)~</math>

=== Calcul du condensé (haché) ===
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 :
*: <math>W_t^{(i)} = \left\{\begin{matrix}
     M_t^{(i)} & \text{si} & 0\le t\le 15 \\
     ROTL^1 \left( W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16} \right) & \text{si} & 16 \le t \le 79 \\
   \end{matrix}\right.</math>
* la fonction suivante de compression d'un bloc intermédiaire de 80 mots sur un vecteur de 5 mots :
*:<math>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)~</math>
*: où <math>f_t~</math> notée ci-après est la fonction binaire, décrite plus haut.
* cinq variables contenant les valeurs de hachage, notées <math>H_0^{(i)}</math> et initialisées précédemment en <math>H_0^{(0)}</math>.<br /> Ces variables contiendront itérativement de nouvelles valeurs de hachage, <math>H^{(i)}~</math>, pour finalement contenir le condensé de M, dans <math>H^{(N)}~</math>.

On traite successivement les blocs de M selon les étapes suivantes, pour <math>1 \le i \le N~</math> :
# On étend un bloc <math>M^{(i)}~</math> de 16 mots du message en un bloc temporaire <math>W_t^{(i)}</math> de 80 mots où <math>0 \le t \le 79~</math>, selon
#: <math>W_t^{(i)} = \left\{\begin{matrix}
     M_t^{(i)} & \text{si} & 0\le t\le 15 \\
     ROTL^1 \left( W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16} \right) & \text{si} & 16 \le t \le 79 \\
   \end{matrix}\right.</math>
# On initialise un vecteur temporaire avec les valeurs de hachage du tour précédent :
#: <math>\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)~</math>
# On réduit le bloc temporaire <math>W_t^{(i-1)}</math> sur ce vecteur temporaire :
#:<math>\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)~</math>
#: où <math>f_t~</math> notée ci-après est la [[fonction logique]], décrite plus haut.
# On combine le vecteur obtenu avec le condensé intermédiaire par une simple addition :
#: <math>\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)~</math>

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
: <math>H_0^{(N)}||H_1^{(N)}||H_2^{(N)}||H_3^{(N)}||H_4^{(N)}~</math>

''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 <math>c = ROTL^{30}(b)~</math> calculée sur 32 bits est trivialement équivalente à une rotation de 2 bits vers la droite <math>c = ROTR^2(b)~</math>.
* 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
*:<math>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 ~</math>
*: où les 5 variables <math>(a, b, c, d, e)~</math> sont en fait parties d'un unique registre d'état <math>A_t~</math> 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 <math>A_0</math> 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 <math>f_0 = Ch~</math> 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 <math>f_t~</math> 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 <math>ROTR^2(A_t) = ROTL^{158}(A_t)~</math>.
* 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 <math>W^{(i)}~</math>, à l'étape 1, d'un bloc de 32 bits <math>M^{(i)}~</math> 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 <Math>H^{(0)}~</math> de la fonction de hachage) :
*: <math>H^{(i)} = \left(Parity^{20} \, \circ \, Maj^{20} \, \circ \, Parity^{20} \, \circ\, Ch^{20}\right)\left(W^{(i)}\right) + H^{(i-1)}~</math>
*: Noter que dans cette définition, les fonctions initialement définies sur 32 bits <math>Parity, Maj, Ch</math> 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 <math>A_t</math> et les additions de constantes <math>K_t~</math>.
* La résistance aux collisions de SHA-1 est liée directement à la non-inversibilité (conjecturée) de la fonction composée obtenue <math>Parity^{20} \, \circ \, Maj^{20} \, \circ \, Parity^{20} \, \circ\, Ch^{20}~</math>, puisque la fonction d'expansion <math>W^{(i)}~</math>des messages <math>M^{(i)}~</math>est trivialement inversible.

== Attaques ==
Une [[Attaque des anniversaires|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 <math>2^{80}</math>.

En 2005, [[Vincent Rijmen|Rijmen]] et [[Elisabeth Oswald|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 <math>2^{80}</math> opérations.

En {{date-|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 Xiaoyun|Wang]], Yin et Yu. Leur méthode permet de trouver : 

* une collision dans le SHA-1 complet de {{unité|128|bits}} avec <math>2^{69}</math> opérations au lieu de <math>2^{80}</math> par l’[[attaque des anniversaires]]
* une collision dans le [[SHA-0]] complet avec seulement <math>2^{39}</math> opérations
* une collision dans une version simplifiée du SHA-1 (58 tours) avec <math>2^{33}</math> opérations

La description de l'attaque a été publiée en {{date-|juin 2005}}.

Le {{date|17|août|2005|en informatique}}, 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{{exp|69}} à 2{{exp|63}}, soit une division par 64 de la complexité originale.

Lors de l'Eurocrypt 2009 (avril), une amélioration<ref>http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf</ref> de l'attaque aurait permis de réduire à nouveau sa complexité jusqu'à atteindre <math>2^{52}</math>. Toutefois, ces résultats furent démentis et l'article<ref>http://www.ictlex.net/wp-content/iacrhash.pdf</ref> fut retiré<ref>{{lien web |langue=en |titre=Cryptology ePrint Archive : Report 2009/259 - Differential Path for SHA-1 with complexity $O(2^{52})$<!-- Vérifiez ce titre --> |url=http://eprint.iacr.org/2009/259 |site=iacr.org |consulté le=31-03-2021}}.</ref> à 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 {{date-|23 février 2017}} qu'ils avaient réussi à obtenir une collision entre deux documents<ref>{{Lien web |langue=fr |auteur=Julien Cadot |titre=SHAttered : Google a cassé la méthode de chiffrement SHA-1 |url=http://www.numerama.com/tech/235436-shattered-google-a-casse-la-methode-de-chiffrement-sha-1.html |date=23 février 2017 |site=numerama |consulté le=23 février 2017}}</ref>{{,}}<ref>{{en}} [http://shattered.io/ site montrant deux documents ayant la même signature et explicant que SHA-1 est cassé]</ref>.

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 {{date-|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 <math>2^{66.9}</math>  et <math>2^{69.4}</math><ref name=":0" />, ce qui réduit le coût d'obtention de collisions à moins de {{unité|150000|$}}, à 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 {{date-|décembre 2019}}, ces mêmes chercheurs ont annoncé avoir amélioré leur attaque  et pouvoir obtenir une collision en <math>2^{63.7}</math> opérations, pour un coût de 45k$<ref>{{Article |langue=Anglais |auteur1=G. Leurent |titre=SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust |périodique=Usenix |date=december 2019 |lire en ligne=https://www.usenix.org/conference/usenixsecurity20/presentation/leurent |pages= }}</ref>. 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) [[Keyed-hash message authentication code|HMAC]] basées sur SHA-1<ref>{{Lien web |langue=en |auteur=Catalin Cimpanu |titre=SHA-1 collision attacks are now actually practical and a looming danger |url=https://www.zdnet.com/article/sha-1-collision-attacks-are-now-actually-practical-and-a-looming-danger/ |date=13 mai 2019 |site=ZDNet |consulté le=17 mai 2019}}.</ref>{{,}}<ref name=":0">{{Lien web |langue=en |auteur=Gaëtan Leurent et Thomas Peyrin |titre=From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1. |url=https://eprint.iacr.org/2019/459.pdf |format=pdf |date=avril 2019 |site=IACR.org |consulté le=17 mai 2019}}, pour EUROCRYPT 2019, paru dans ''Advances in Cryptology'', pp. 5247-555 (DOI: 10.1007/978-3-030-17659-4_18).</ref>. Un code libre de démonstration et des données d'analyse seront bientôt mis en ligne sur [[GitHub]] afin d'évaluer correctement son impact notamment dans la sécurité de protocoles Internet comme [[Transport Layer Security|TLS]] (utilisé notamment par [[HyperText Transfer Protocol Secure|HTTPS]]) et des certificats de serveurs, avec la possibilité alors de créer à bas coût une [[autorité de certification]] (CA) malveillante, notamment pour créer des failles de contournement de la sécurité de sites Internet (dont 5 % des plus connus et les plus visités utilisent encore en {{date-|mai 2019}} des certificats basés sur SHA-1, plusieurs années après la fin de leur recommandation, y compris encore [[Microsoft]] pour certains de ses services connectés comme [[Skype]]) ainsi que l'utilisabilité de la méthode pour casser d'autres algorithmes de hachages connus qui restent recommandés (dont [[RIPEMD-160]], [[SHA-2]] et [[SHA-3]]) et d'autres qui ne le sont pas encore.

=== Conséquences ===
Même si un gain de 2<sup>17</sup> opérations permettait de diviser le temps de recherche par un facteur de {{formatnum:131072}}, l'attaque de 2009 avec ses 2<sup>63</sup> 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 {{date-|avril 2019}} avec la méthode publiée par Leurent et Peyrin) avec un gain d'au moins 2<sup>33</sup> 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 [[Global Processing Unit|GPU]] (ainsi qu'avec la multiplication des offres peu onéreuses d'hébergement d'applications privées sur le « ''[[Cloud computing|cloud]]'' » permettant de les utiliser), capables de réaliser localement des [[Parallélisme (informatique)|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 (algorithme)|Whirlpool]], [[Tiger (hash)|Tiger]], [[RIPEMD-160]], et d'autres plus récentes comme [[ChaCha20]], [[Curve25519]], [[NTRUEncrypt|NTRU]], ainsi que [[BLAKE2b]] ou [[BLAKE2s]] qui sont suggérés en {{date-|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 {{date-|avril 2019}} si cette recherche est techniquement réalisable), et non sur la seule [[résistance aux collisions]]<ref name="rfc" />.

Vu les faiblesses constatées sur SHA-1, et la conception de SHA-2 qui est voisine, une [[NIST hash function competition|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 [[Standard de chiffrement avancé|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érateur de nombres pseudo-aléatoires|génération de nombres pseudo-aléatoires]] basés sur les [[Courbe elliptique|courbes elliptiques]] nécessaires à la production des [[Clé de chiffrement|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 [[Porte dérobée|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 [[Hasard|aléatoire]] qui produisent la même signature. En revanche, à partir d'une signature donnée, il était considéré comme impossible (jusqu'en {{date-|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 [[Keyed-hash message authentication code|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 [[Pretty Good Privacy|PGP]] et l'[[authentification|authenticité]] des données.

== Le SHA-1 en mode chiffrement ==
Les primitives des fonctions de hachage cryptographiques sont assez proches de celles des [[cryptographie symétrique|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)
{{Références}}

== Voir aussi ==
=== Sources ===
{{Crédit d'auteurs|interne|Spécifications SHA-1}}

=== Articles connexes ===
* [[Secure Hash Algorithm]] pour les autres algorithmes de cette famille

=== Liens externes ===
* {{fr}} [http://www.sha1.fr/ Un calculateur de hash en SHA-1]
* {{en}} [http://hash.db.hk/ SHA1 dictionary attack]
* {{en}} [http://www.iacr.org/conferences/crypto2005/r/2.mov Vidéo de CRYPTO 2005, avec la présentation de l'attaque améliorée par Adi Shamir]
* {{en}} [http://www.iacr.org/conferences/crypto2005/r/2.pdf {{lang|en|''Slides''}} d'Adi Shamir à CRYPTO 2005]{{pdf}}
* {{en}} [http://eprint.iacr.org/2002/099 {{lang|en|''A New Statistical Testing for Symmetric Ciphers and Hash Functions''}}], test statistique de Eric Filiol
* {{en}} [http://www.gemplus.com/smart/rd/publications/pdf/HN00shac.pdf SHACAL]{{pdf}}, description de SHA-1 en mode chiffrement (SHACAL)
* {{en}} [http://www.ietf.org/rfc/rfc3174.txt RFC 3174], ''US Secure Hash Algorithm 1 (SHA1)''
* {{en}} [http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf SHA-1 collisions now 2<sup>52</sup>], ''L'attaque sur SHA-1'' présentée à Eurocrypt 2009.

{{Palette|Fonctions de hachage cryptographiques}}
{{Portail|Cryptologie}}

[[Catégorie:Algorithme de hachage]]