SHA-1

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 F2 des booléens) qui dépend du numéro de tour t ;
⊞ est l'addition modulo 232 (l'addition des entiers machines non signés de 32 bits), qui est non linéaire sur F2 ;
Kt est une constante (32 bits) qui dépend du numéro de tour t ;
Wt 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 (Secure Hash Algorithm) 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.

Origine : SHA-0 et SHA-1[modifier | modifier le code]

Le SHA-1 est le successeur du SHA-0 qui a été rapidement mis de côté par le 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 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 août 2004 et laisse penser que le SHA-1 pourrait lui aussi subir une attaque.

Exemples[modifier | modifier le code]

Voici la signature obtenue sur une phrase (encodé en iso8859-1) : SHA1("Wikipédia, l'encyclopédie libre et gratuite") = AFBA34A2A11AB13EEBA5D0A7AA22BBB6120E177B.

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

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. Un test conduit par Eric Filiol a confirmé la qualité mathématique des sorties qui sont « plus aléatoires » que celles de RIPEMD-160 ou SHA-0.

Fonctionnement du SHA-1[modifier | modifier le code]

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

Pour chaque bloc l'algorithme calcule 80 tours (ou rondes, « rounds » en anglais) successifs et applique une série de transformations sur l'entrée. La première étape consiste à calculer 80 valeurs sur 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 XOR, il utilise pour cela 4 mots obtenus dans les itérations précédentes. On définit ensuite 5 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 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 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 = 160 bits) représentent la signature.

Caractéristiques[modifier | modifier le code]

Les caractéristiques de SHA-1 sont les suivantes :

  • taille du message : 264 bits maximum
  • taille des blocs : 512 bits
  • taille des mots : 32 bits
  • taille du condensé : 160 bits
  • niveau de sécurité : collision en 263 opérations.
L'attaque générique des anniversaires permet de trouver une collision en 280 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 269 connue depuis 2005[1], qui a été améliorée en une attaque en 263 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[modifier | modifier le code]

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[2]. Elles sont reprises dans les versions successives de ce document, FIPS-180-2, FIPS-180-3 et FIPS-180-4[3].

L'algorithme SHA-1 transforme un message de longueur inférieure à 264 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
    1. de compléter le message par des informations le rendant compatible avec l'algorithme SHA-1 (remplissage)
    2. son analyse pour le découper en blocs de 512 bits
    3. 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[modifier | modifier le code]

Paramètres[modifier | modifier le code]

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

Symboles[modifier | modifier le code]

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

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

Opérations sur les mots[modifier | modifier le code]

Elles utilisent les conventions suivantes :

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

Fonctions et constantes[modifier | modifier le code]

Fonctions[modifier | modifier le code]

Cette section décrit les fonctions utilisées lors du calcul des valeurs de hachage. SHA-1 utilise une succession de fonctions logiques f_0, f_1, ..., f_{79}~. Chaque fonction f_t~, où 0 \le t \le 79, travaille sur trois mots de 32 bits, x, y, z et génère un mot de 32 bits en sortie. La fonction f_t~ est définie comme suit:

f_t(x,y,z) = \left\{\begin{matrix} Ch(x,y,z) = (x \wedge y) \vee (\lnot x \wedge z), & \mbox{si }0 \le t \le 19 \\ Parity(x,y,z) = x \oplus y \oplus z, & \mbox{si }20 \le t \le 39 \\ Maj(x,y,z) = (x \wedge y) \vee (x \wedge z) \vee (y \wedge z), & \mbox{si }40 \le t \le 59 \\ Parity(x,y,z) = x \oplus y \oplus z, & \mbox{si }60 \le t \le 79 \end{matrix}\right.

Constantes[modifier | modifier le code]

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

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.

Prétraitement[modifier | modifier le code]

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 H^{(0)}~

Complément de M[modifier | modifier le code]

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
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 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.

Découpage en blocs[modifier | modifier le code]

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

Initialisations[modifier | modifier le code]

Les cinq variables suivantes sont affectées de valeurs initiales comme suit :

  • H_0^{(0)} = \mbox{0x67452301}
  • H_1^{(0)} = \mbox{0xefcdab89}
  • H_2^{(0)} = \mbox{0x98badcfe}
  • H_3^{(0)} = \mbox{0x10325476}
  • H_4^{(0)} = \mbox{0xc3d2e1f0}

Calcul du condensé (haché)[modifier | modifier le code]

Pour ce traitement on utilisera

  • un tableau de 80 mots, notés W_0, W_1, ..., W_{79}~
  • cinq variables notées a, b, c, d, e ~
  • cinq variables contenant les valeurs de hachage, notées H_0^{(i)} et initialisées précédemment en H_0^{(0)}
    Ces variables contiendront itérativement de nouvelles valeurs de hachage, H^{(i)}~, pour finalement contenir le condensé de M, dans H^{(N)}~.
  • une variable T, mot de 32 bits

On traite successivement les N blocs de M selon les étapes suivantes

Pour i = 1 à N 
{
 1. On remplit le tableau W_t \mbox{ si }0 \le t \le 79, selon
W_t=\left\{\begin{matrix} M_t^{(i)}, & 0\le t\le 15 \\ \\ ROTL^1 \left( W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16} \right), & 16\le t\le 79 \end{matrix}\right. 2. On initialise a, b, c, d et e avec les valeurs de hachage du tour précédent a = H_0^{(i-1)}~ b = H_1^{(i-1)}~ c = H_2^{(i-1)}~ d = H_3^{(i-1)}~ e = H_4^{(i-1)}~ 3. Pour t = 0 à 79 { (f_t~ notée ci-après est la fonction logique, décrite plus haut) T = ROTL^5(a) + f_t(b,c,d)+ e + K_t + W_t ~ e = d~ d = c~ c = ROTL^{30}(b)~ b = a~ a = T~ } 4. Calcul des valeurs de hachage intermédiaires H_0^{(i)} = a + H_0^{(i-1)}~ H_1^{(i)} = b + H_1^{(i-1)}~ H_2^{(i)} = c + H_2^{(i-1)}~ H_3^{(i)} = d + H_3^{(i-1)}~ H_4^{(i)} = e + H_4^{(i-1)}~ }

Après répétition de quatre étapes ci-dessus pour les N blocs du message M, (i.e., après traitement de M^{(N)}~), le condensé de 160 bits de M est obtenu par concaténation des valeurs

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.

Attaques[modifier | modifier le code]

Une attaque basée sur le paradoxe des anniversaires permet de trouver une collision complète sur le SHA-1 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 le paradoxe 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 269 à 263, soit une division par 64 de la complexité originale.

Lors de l'Eurocrypt 2009 (avril), une amélioration[4] 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[5] fut retiré[6] suite à la découverte d'une erreur dans l'évaluation de cette complexité.

Conséquences[modifier | modifier le code]

Même si un gain de 217 opérations permet de diviser le temps de recherche par un facteur de 131 072, l'attaque avec ses 263 opérations est à la limite de ce qui est réalisable. Adi Shamir a toutefois laissé entendre que l'attaque pouvait probablement être abordée via un calcul distribué à l'échelle planétaire.

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 ou RIPEMD-160). Il reste cependant largement utilisé, d'autant que la sécurité de certaines applications repose sur la résistance à la recherche de pré-image, et non sur la résistance aux collisions[1].

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.

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 est impossible de forger un second message qui conduise à la même valeur. Or, c'est ce type d'attaque qui pourrait mettre en péril les applications comme PGP et l'authenticité des données.

Le SHA-1 en mode chiffrement[modifier | modifier le code]

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[modifier | modifier le code]

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

  1. a et b RFC 6194
  2. FIPS 180-1, Federal Information Processing Standards Publication 180-1 Announcing the Standard for Secure Hash Standard, 17 avril 1995 lire en ligne
  3. voir page (en)Secure Hashing du NIST. En plus de SHA-1, le standard inclut les algorithmes de la famille SHA-2 à partir de la version (en)FIPS-180-2[PDF] (août 2002), avec de nouvelles variantes pour SHA-2 dans les versions successives (en)FIPS-180-3[PDF] (octobre 2008) et (en)FIPS-180-4[PDF] (mars 2012).
  4. http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf
  5. http://www.ictlex.net/wp-content/iacrhash.pdf
  6. http://eprint.iacr.org/2009/259

Voir aussi[modifier | modifier le code]

Sources[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]