Secure Hash Algorithm 2 est une famille de fonctions de hachage cryptographique composée de six membres. Leur différence immédiatement visible est la taille de leur condensat. On rappelle que, comme pour toute fonction de hachage cryptographique, son objectif est simple : à partir d’une donnée de taille quelconque en entrée, elle produit un condensat de taille fixe tout en répondant aux Propriétés fondamentales d’une fonction de hachage cryptographique . SHA-2 est formellement défini et adopté par le standard FIPS 180-4 du NIST.

Cette famille est composée des fonctions suivantes dont les deux derniers membres voient leurs condensats tronqués à 224 bits et 256 bits respectivement :

  • SHA-224,
  • SHA-256,
  • SHA-384,
  • SHA-512,
  • SHA-512/224,
  • SHA-512/256.

Fonction de compression de Davies-Meyer

SHA-2, pour fournir son condensat, exploite une fonction de compression des données. Celle-ci n’a rien à voir avec les algorithmes de compression bidirectionnels dont l’objectif est la diminution de l’espace occupé sur un support numérique. La compression unidirectionnelle de SHA-2 est basée sur la construction de Davies-Meyer. Pour être précis, la construction algorithmique de Merkle-Damgård dont SHA-2 est issue, intègre à la chaine une fonction de compression unidirectionnelle de type Davies-Meyer. Cette fonction de compression est composée d’un algorithme de chiffrement symétrique par bloc “sans clé”. Il faut comprendre “sans clé” dans le sens où l’utilisateur ne fournit pas directement une clé de chiffrement. C’est l’algorithme qui s’en occupe en s’auto-alimentant.

Définissons maintenant les entrées, la sortie et les paramètres de la fonction de compression unidirectionnelle de type Davies-Meyer dont \(\small m\) est la donnée originale complète à compresser :

  • \(\small i\) le nombre d’itérations à effectuer,
  • \(\small k\) la taille en bits des blocs de \(\small m\),
  • \(\small m_{i}\) le bloc de la i-ème itération,
  • \(\small H_{i-1}\) le condensat précédent,
  • \(\small H_{i}\) le condensat intermédiaire,
  • \(\small E_{m_i}\) le résultat de la fonction de chiffrement par bloc \(\small E\) traitant \(\small m_{i}\).
Il s'agit d'une représentation visuelle sous forme de diagramme de la notation mathématique ci-dessous.
Construction de Davies-Meyer qui transforme un algorithme de chiffrement par bloc en une fonction de compression unidirectionnelle utilisable par une fonction de hachage. - Crédit : wikipedia.org + moi

La notation mathématique de cette fonction de compression est \(\small H_{i} = E_{m_i}(H_{i-1}) \oplus H_{i-1}\) où \(\small \oplus \) représente l’opération “XOR” aussi appelé “OU exclusif”. \(\small i\) et \(\small k\) varient en fonction de la fonction SHA-2.

Algorithme de SHA-256

Continuons avec une description des différentes étapes algorithmiques de SHA-256, parce qu’évidemment la réalité est plus complexe. Il faut bien stocker en mémoire les données intermédiaires à traiter et celles calculées. Pour SHA-256, \(\small i=64\), \(\small k=512\) et le nom de la fonction de chiffrement par bloc pour la construction de Davies-Meyer \(\small E\) est SHACAL-2.

Étape 1 : padding, découpage en blocs puis mots

Cette première étape consiste à ajouter un padding à la donnée originale à hacher, \(\small m\) de longueur \(\small k\).

  1. À \(\small m\), on ajoute un bit à 1,
  2. Puis on ajoute \(\small n\) bits à 0 tel que \(\small (k + 1 + n + 64) \equiv 0 \bmod 512\) avec \(\small n\) la quantité minimal de bits,
  3. Enfin, on ajoute la valeur binaire de \(\small k\) codée sur 64 bits en orientation big-endian. Ainsi, la longueur du “Message Block” paddé est toujours un multiple de 512.

Étape 2 : réservation d’un tableau puis peuplement

On réserve en mémoire un tableau “Message schedule” à une dimension défini par w[0..63] de type dword soit \(\small 64 \times 32 = 2048\) bits. On copie ensuite le premier bloc de 512 bits du “Message Block” dans les 16 premières cellules de w.

Étape 3 : extension des mots dans le tableau

Important

Les additions binaires des Étapes 3 et 5 sont calculées modulo \(\small 2^{32}\). Les variables sont des entiers non signés codés sur 32 bits.

On itère sur chaque mot de w[16] à w[63] tel que :

for i from 16 to 63:
  σ0 = (w[i-15] rightrotate 7) XOR (w[i-15] rightrotate 18) XOR (w[i-15] rightshift  3)
  σ1 = (w[i-2] rightrotate 17) XOR (w[i-2] rightrotate 19) XOR (w[i-2] rightshift 10)
  w[i] = w[i-16] + σ0 + w[i-7] + σ1
  • Rightrotate n : rotation vers la droite de n bits. Les bits de poids faible passent en bits de poids fort (on parle aussi de décalage circulaire),
  • Rightshift n : décalage vers la droite de n bits. Les bits de poids faible en excès sont écartés. Pour le remplissage des bits de poids fort, c’est le bit le plus fort initial qui est recopié autant de fois que nécessaire.

À ce stade, après 48 itérations, le tableau “Message schedule” w est totalement rempli.

Étape 4 : initialisation des constantes

SHA-256 nécessite des constantes représentées par les 32 premiers bits des parties fractionnaires des racines carrées des 8 premiers nombres premiers :

h0 : 0x6a09e667
h1 : 0xbb67ae85
h2 : 0x3c6ef372
h3 : 0xa54ff53a
h4 : 0x510e527f
h5 : 0x9b05688c
h6 : 0x1f83d9ab
h7 : 0x5be0cd19

Prenons un exemple avec h3. Le nombre premier correspondant est 7 donc \(\small \sqrt{7} \approx 2,6457513110645905905016157536392\). On conserve la partie décimale que l’on multiplie par \(\small 2^{32}\) donc \(\small 2^{32} \times 0,6457513110645905905016157536392 \approx 2773480762\). En hexadécimal cela donne 0xA54FF53A.

Un second tableau contenant d’autres constantes est nécessaire. Il contient les 32 premiers bits des parties fractionnaires des racines carrées des 64 premiers nombres premiers. Nous le définissons par k[0..63] sans toutefois le représenter ici vu sa taille.

Note

Ces constantes sont de type “Nombre rien-dans-la-manche/Nothing-up-my-sleeve number”. Il s’agit de nombres dont on ne peut suspecter en cryptographie le caractère malveillant. Ils sont utilisés par des fonctions cryptographiques de hachage et de chiffrement.

Étape 5 : compression avec SHACAL-2

Maintenant les enfants ça se corse donc on s’accroche. Le coeur de SHA-256 se cache ici. On commence par initialiser les variables :

a = h0
b = h1
c = h2
d = h3
e = h4
f = h5
g = h6
h = h7

Lors du calcul, elles seront mises à jour comme suit :

h = g
g = f
f = e
e = d + Temp1
d = c
c = b
b = a
a = Temp1 + Temp2

Voici l’algorithme tant redouté :

for i from 0 to 63:
  Σ1 = (e rightrotate 6) XOR (e rightrotate 11) XOR (e rightrotate 25)
  Choice = (e AND f) XOR ((not e) AND g)
  Temp1 = h + Σ1 + Choice + k[i] + w[i]
  Σ0 = (a rightrotate 2) XOR (a rightrotate 13) XOR (a rightrotate 22)
  Majority = (a AND b) XOR (a AND c) XOR (b AND c)
  Temp2 = Σ0 + Majority
Il s'agit d'une représentation visuelle sous forme de diagramme du pseudocode ci-dessus.
Algorithme de compression de type Davies-Meyer basé sur la fonction de chiffrement par bloc SHACAL-2. Sur cette figure, les carrés rouges représentent les additions binaires modulo \(\small 2^{32}\). Les composants bleus cachent les opérations détaillées dans le pseudocode précédent. - Crédit : wikipedia.org

Étape 6 : condensat final

h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e
h5 = h5 + f
h6 = h6 + g
h7 = h7 + h

On additionne les variables aux constantes puis on procède à leur concaténation à l’issue de laquelle nous obtiendrons le condensat final. Condensat SHA-256 = Condensat SHA-256 = \(\small h0 || h1 || h2 || h3 || h4 || h5 || h6 || h7\).

Outillage et documentation