Spécifications SHA-1

Spécifications SHA-1

SHA-1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l'histoire, la cryptanalyse et d'autres aspects liés à cette fonction, voir l'article principal : SHA-1.

Sommaire

Introduction

Ce texte est adapté du document officiel FIPS 180-2 (Secure Hash Standard)[1]. Il décrit les spécifications du standard SHA-1, dont l'objectif est de calculer une représentation condensée de données électroniques (message).
Quand un message inférieur à 264 bits est passé à l'algorithme implémentant SHA-1, on obtient en sortie ce qu'on appelle un haché, ou condensé de ce message. La longueur d'un condensé obtenu via SHA-1 est de 160 bits.

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.

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é : 280 bits (attaque anniversaire); sécurité ramenée à 269, puis 263, ce qui rend SHA-1 plus vulnérable (cf. informations générales sur SHA-1).

Symboles et termes utilisés

Paramètres

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.

Kt = 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.
Wt = le mot n°t du tableau déduit du message

Symboles

La notation hexadécimale utilisée ici sera: 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 2w
< < = 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

Elles utilisent les conventions suivantes :

  • opérations binaires bit à bit (cf. symboles)
  • addition modulo 2w, soit 232
L'opération x + y est définie comme suit. Soient deux mots x et y représentant les nombres entiers X 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 232 de X 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 ROTLn(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

Fonctions

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) \oplus (\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) \oplus (x \wedge z) \oplus (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

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

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

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

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

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é)

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 = H0^{(i-1)}~
b = H1^{(i-1)}~
c = H2^{(i-1)}~
d = H3^{(i-1)}~
e = H4^{(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.

Liens externes

  1. ↑ FIPS PUB 180-2, Secure Hash Standard (incluant SHA-1, SHA-256, SHA-384 et SHA-512)
  • RFC 3174, US Secure Hash Algorithm 1 (SHA1)
  • [1], L'attaque récente sur SHA-1 présentée à Eurocrypt 2009.
v · Fonctions de hachage cryptographiques
Algorithmes APR1 · AR · Boognish · FFT-hash · HAS-160 · Haval · MD2 · MD4 · MD5 · MD6 · N-hash · PANAMA · RIPEMD · RIPEMD-128 · RIPEMD-160 · RIPEMD-256 · Famille SHA (SHA-0 · SHA-1 · SHA-224 · SHA-256 · SHA-384 · SHA-512) · Snefru · StepRightUp · Tiger · VSH · Whirlpool
Cryptanalyse Paradoxe des anniversaires · Linéaire · Différentielle · Attaque par force brute · Effet avalanche · Pseudo-collision
Architecture Remplissage · Fonction de compression · Construction de Merkle-Damgård · Construction de Miyaguchi-Preneel · Construction de Matyas-Meyer-Oseas · Construction de Davies-Meyer

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Spécifications SHA-1 de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Specifications SHA-1 — Spécifications SHA 1 SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1… …   Wikipédia en Français

  • Spécifications sha-1 — SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Specifications SHA-256 — Spécifications SHA 256 SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1… …   Wikipédia en Français

  • Spécifications sha-256 — SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Spécifications SHA-256 — SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1 Introduction 2 Symboles et… …   Wikipédia en Français

  • Sha-1 — Une itération de SHA 1 avec deux rotations vers la gauche et une fonction non linéaire qui dépend du numéro d itération, deux autres variables interviennent à chaque tour SHA 1 (Secure Hash Algorithm) est une fonction de hachage cryptographique… …   Wikipédia en Français

  • SHA-256 — (Secure Hash Algorithm) est une fonction de hachage cryptographique conçue par la National Security Agency des États Unis (NSA), et publiée en 2000. Elle produit un résultat (appelé « hash » ou condensat) de 256 bits et dérive du… …   Wikipédia en Français

  • Sha-256 — (Secure Hash Algorithm) est une fonction de hachage cryptographique conçue par la National Security Agency des États Unis (NSA), et publiée en 2000. Elle produit un résultat (appelé « hash » ou condensat) de 256 bits et dérive du SHA 1 …   Wikipédia en Français

  • SHA-1 — Une itération de SHA 1 avec deux rotations vers la gauche et une fonction non linéaire qui dépend du numéro d itération, deux autres variables interviennent à chaque tour SHA 1 (Secure Hash Algorithm) est une fonction de hachage cryptographique… …   Wikipédia en Français

  • Sha Tin Racecourse — (zh t|t=沙田馬場) is one of the two racecourses for horse racing in Hong Kong. It is located in Sha Tin in the New Territories. It is managed by Hong Kong Jockey Club.Penfold Park is encircled by the track.HistoryIt was first built in 1978 (under the …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”