Introduction

Les fonctions de hachage ont pour fonction essentielle de projeter une quantité indéterminée de données sur une empreinte de longueur finie et donnée.  Les fonctions de hachage sont des fonctions déterministes et publiquement connues.  Ce sont des surjections de tous les nombres naturels sur le jeu de nombres naturels plus petits que N.  Ainsi, il est inévitable que plusieurs jeux de données auront la même empreinte.  Il est aussi désirable que tous les nombres plus petits que N sont l'image d'un jeu de données.  C'est pour cela qu'une fonction de hachage est bien une surjection de l'ensemble de tous les nombres naturels (tous les jeux de données) sur l'ensemble de nombres {0,1,2,... N-1}.  Une fonction de hachage triviale est par exemple: f(x) = x mod N.

Une fonction de hachage cryptographique est une fonction de hachage qui a les propriétés suivantes:

  1. résistance pré-image
  2. résistance deuxième pré-image
  3. résistance de collision

Ces exigences sont de plus en plus sévères.  La première exigence veut dire, que si on a juste l'empreinte d'un jeu de données, il est (pratiquement) impossible d'inventer un jeu de données qui a la même empreinte (même si un nombre infini de ces données existent bien sûr).  Pratiquement impossible doit être vu dans le sens cryptographique: le calcul pour le trouver n'est pas faisable avec les ressources de calcul dont l'adversaire pourrait disposer.

La deuxième exigence est la même que la première, à ceci près: on dispose non seulement de l'empreinte, mais aussi des données qui ont donné lieu à cette empreinte, et il doit être pratiquement impossible de trouver un autre jeu de données qui fabrique la même empreinte.   La deuxième condition est plus sévère que la première.  Effectivement, si on sait faire 1, forcément, 2 est faisable.  Si on sait déjà trouver un jeu de données qui donne la même empreinte sans connaissance des données d'origine, forcément on sera capable de trouver un tel jeu avec cette connaissance.  Mais si on serait capable de trouver un autre jeu en connaissant les données d'origine, cela n'implique pas qu'on serait capable de trouver un tel jeu si on ne connaissait pas ces données d'origine.

La troisième propriété indique qu'il est pratiquement impossible d'inventer deux jeux de données, tel qu'ils donnent la même empreinte.  La différence avec 1 et 2 réside dans le fait que l'empreinte ne nous est pas imposée.  La troisième condition est donc automatiquement plus sévère que 1 et 2: si on peut trouver un jeu de données quand l'empreinte nous est imposée, forcément que nous serons capable de trouver un jeu quand nous pouvons librement choisir cette empreinte (il suffit de choisir la même !).

On peut se demander pourquoi on spécifie ces trois propriétés, quand la troisième inclut les deux autres.  Dépendant de l'application cryptographique, nous n'avons parfois pas besoin de la condition 3, où même de la condition 2.  Ainsi, une fonction de hachage peut être vulnérable à une attaque sur la condition 3, si l'application en question ne nécessite que la condition 1, l'application est encore à l'abri de l'attaque.

Dans cette partie, nous n'allons pas étudier les fonctions de hachage même, mais nous allons étudier l'élément primitif qui permet de construire une telle fonction: la fonction de compression cryptographique.  La fonction de compression cryptographique est semblable au chiffrement par bloc: c'est un élément de base à partir on peut construire des fonctions de cryptographie symétrique mais bien d'autres fonctions et applications.  Il faut distinguer l'algorithme de l'élément de base et l'algorithme de la mise en oeuvre de cette fonction dans une application cryptographique.  Une fonction de hachage est une application cryptographique ; une fonction de compression cryptographique est un composant de base à partir duquel il est possible de construire cette application.Un chiffrement par bloc, et une fonction de compression cryptographique sont très similaire, et en fait, on peut utiliser les deux pour une certaine application, comme une fonction de hachage.  Mais il y a des différences fondamentales.  Un chiffrement par bloc fait ceci:

    C'est une fonction qui prend un bloc de n bits (le texte en clair) et une clé de k bits, et elle produit un bloc de n bits, le texte chiffré: X = f(C,K)Il existe une fonction inverse qui peut reconstruire le texte en clair du texte chiffré et la clé: C = g(X,K)Il n'est pratiquement pas possible de retrouver la clé d'une pair de texte chiffré et texte en clair (ou de beaucoup de ces pairs): K = ?(C,X)

Une fonction de compression cryptographique, par contre, fait ceci:

  1. C'est une fonction qui prend un bloc de n bits, et qui produit un bloc de m < n bits: H = c(B)
  2. Il n'est pratiquement pas possible de trouver un bloc B' tel que étant donné un bloc H, nous avons c(B') = H (résistance pré-image)
  3. Il n'est pratiquement pas possible de trouver un bloc B, tel que étant donné un bloc B, nous avons c(B') = c(B) (résistance deuxième pré-image)
  4. Il n'est pratiquement pas possible de trouver deux blocs, B et B', tel que c(B) = c(B') (résistance à la collision).

Si nous avons un chiffrement en bloc, il est toujours possible de fabriquer une fonction de compression cryptographique:  considérons que B soit la composition d'un morceau de n bits et de k bits: B = {C,K}.  Alors un chiffrement par bloc f nous donne: X = f(C,K), un bloc de n bits.  On peut considérer cela comme X = c(B).

Effectivement, il n'est pas possible de trouver un B' = {C', K'} tel que X = f(C',K') étant donné C, K et X en général, même si cela n'est pas explicitement demandé à un chiffrement par bloc, car cela impliquerait une trop grande séparation de la clé et du texte en clair.  Mais l'exigence de réversibilité que nous avons pour un chiffrement en bloc est une faiblesse potentielle pour l'utiliser comme fonction de compression qui n'a pas cette exigence. 

Ainsi, même s'il est possible de construire une fonction de compression à partir d'un chiffrement par bloc, il peut être judicieux de concevoir des fonctions de compression spécifiques.  Cette contribution étudie exactement ces constructions-là.

En réalité, il ne faut même pas une fonction de compression pour construire une fonction de hachage, même si c'est la façon classique de la construire.  Une "fonction de compression" qui sort autant de bits de sortie que d'entrée peut aussi servir dans la construction d'une fonction de hachage, avec une technique appelée "construction éponge".  Nous allons illustrer cela avec Keccak.  Nous comprenons comment cela peut fonctionner: il suffit d'avoir une fonction de mélange 1-1, et de retenir qu'une partie du résultat, et nous avons automatiquement une compression.  Si nous avons une fonction qui transforme un bloc de 512 bit en un autre de 512 bit, nous pouvons nous limiter à prendre que les 160 premiers bits de sortie.  Si statistiquement chaque bit d'entrée a la même influence sur chaque bit de sortie, qu'on prenne les 160 premiers, out les 160 derniers bits de sortie ne changent pas la donne.  Une telle approche a l'avantage sur un chiffrement par bloc, que tous les bits d'entrée sont traités de façon égale (cela n'est pas le cas pour un chiffrement par bloc: certains bits d'entrée sont considéré données, et d'autres, la clé).  Nous allons voir que dans les fonctions de compression, il y a aussi une distinction entre les bits d'entrée, qui est donc inexistante pour les fonctions 1-1.  Ainsi, il y a de plus en plus, cryptographiquement, une préférence pour les fonctions 1-1.

SHA-1

Comme nous avons dit avant, nous allons nous limiter à la fonction de compression de SHA-1.  SHA-1 est en fait la définition d'une fonction de hachage complète et cette spécification contient donc aussi la façon dont on utilise la fonction de compression pour en fabriquer une fonction de hachage: nous n'allons pas discuter de cela, à part du fait que cette spécification est la variante Davis-Meyer de la construction Merkle-Damgard qui indique comment en général construire une fonction de hachage d'une fonction de compression.  Nous allons nous intéresser donc essentiellement à la fonction de compression.  Cet engin de compression prend un bloc "données" de 512 bits et une "entrée hash" de 160 bits, et fabrique une sortie de 160 bits.  Cela donne donc la forme suivante:

H = f(B = {C,G} ) où H et G sont de 160 bit, et C est de 512 bit.

En d'autres termes, f comprime un bloc de 512 + 160 = 672 bits en un bloc de 160 bits, mais pas tous les bits d'entrée sont égaux.  Ils font partie d'un bloc de 512 bits, où d'un bloc de 160 bits.  Cela ressemble beaucoup à un chiffrement par bloc, avec une clé de 512 bits, et un bloc de données de 160 bits.  En fait, SHA-1 ressemble trop à un chiffrement par bloc, et c'est son défaut principal.

Le bloc de "message" ressemble à une clé, et il y a un schéma de message, comme il y avait un schéma de clé dans un chiffrement par bloc.  Du bloc de 512 bits, on dérive 80 mots de 32 bits (en total donc 2560 bits) comme suite:

  1. Les 16 premiers mots W0 à W15 sont pris du message même
  2. les autres 64 mots sont dérivés de la formule d'itération:Wj = shift gauche un bit de XOR de (Wj-16 , Wj-14 , Wj-8 , Wj-3 )

La transformation du bloc de 160 bits va ainsi:

  1. Le mot de 160 bits est coupé en 5 mots de 32 bits: A, B, C, D et E
  2. 20 tours sont appliqués en étape 1, en utilisant W0,... W19, K1 et f1
  3. 20tours sont appliqués en étape 2, en utilisant W20 ... W39, K2 et f2
  4. 20tours sont appliqués en étape 3, en utilisant W40 ... W59, K3 et f3
  5. 20tours sont appliqués en étape 4, en utilisant W60 ... W79, K4 et f4
  6. au résultat  A', B',C',D',E', on ajoute respectivement  A, B, C, D, E du pas 1, modulo 232

Cela donne la sortie du bloc de 160 bits.

Chaque étape est similaire, sauf pour les entrées différentes mentionnées plus haut.  Les tours ont une structure Feistel, dans le sense que seulement une partie du mot est transformée par tour.  Des opérations différentes sont spécifiés pour les 5 mots de 32 bits:

  1. A devient E + fi(B,C,D) + shift-gauche-5-bits(A) + Wj + Ki (addition modulo 232)
  2. B devient A
  3. C devient shift-gauche-30-bits de B
  4. D devient C
  5. E devient D

Dans la première étape, K1 = 0x5A827999, dans la deuxième, K2 = 0x6ED9EBA1, dans la troisième étape K3= 0x8F1BBCDC et dans la quatrième K4 = 0xCA62C1D6.

Dans la première étape, f1(B,C,D) est (B et C) ou (B et D) ; dans la deuxième étape, f2(B,C,D) est le XOR de B, C et D ;dans la troisième étape f3(B,C,D) est (B et C) ou (B et D) ou (C et D) et dans la quatrième étape f4(B,C,D) est de nouveau le XOR de B, C et D.  Il faut comprendre ces opérations bit par bit.  Les fonctions f sont les parties non-linéaires de la fonction de compression.

Même si aucune attaque pratique de SHA-1 n'a été démontrée publiquement, il y a suffisamment d'attaques théoriques pour que la sécurité de SHA-1 est mis en doute pour le long terme.

SHA-2 en famille

Afin de remédier les faiblesses théoriques de SHA-1, une nouvelle famille de fonctions de hachage a été proposée.  C'est une famille de fonctions, car plusieurs tailles de blocs et de longueurs d'empreintes est proposée, mais les différentes fonctions sont similaires dans leurs descriptions algorithmiques.  C'est surprenant que la structure globale de SHA-2 est très semblable à SHA-1, et possède aussi une approche inspirée d'un chiffrement par bloc de type Feistel.  Cependant, la quantité d'opérations mélangeant les bits est bien supérieure dans SHA-2 et les attaques théoriques contre SHA-1 ont des difficultés de principe contre SHA-2.

La famille complète est: SHA-224, SHA-256, SHA-384 et SHA-512 ; nous allons nous intéresser dans la fonction de compression dans SHA-256.

La fonction de compression de SHA-256 prend un bloc de données de 512 bits, et un mot de 256 bits, et va produire un mot de 256 bits.  C'est comme un chiffrement par bloc avec un bloc de texte en clair de 256 bits, et une clé de 512 bits.  Le coeur de la fonction de compression est basé sur des mots de 32 bits.

La fonction de compression va ainsi:

  1. Prendre l'entrée de 256 bits (l'empreinte d'entrée) et le couper en 8 mots de 32 bits A, B, C ... H.
  2. Appliquer 64 tours (index j = 0 à 63) de modifications de ce jeu de 8 mots de 32 bits, avec une "clé data" Wj et une constante Kj
  3. Assembler les 8 mots en un bloc de 256 bits: c'est la sortie.

Chaque tour en va ainsi, et on reconnaîtra la structure Feistel:

  1. H devient G
  2. G devient F
  3. F devient E
  4. E devient D + H + t(E) + c(E,F,G) + Kj + Wj
  5. D devient C
  6. C devient B
  7. B devient A
  8. A devient H + t(E) + c(E,F,G) + Kj + Wj + s(A) + m(A,B,C)

Les + sont des additions sur 32 bits modulo 232 et t(), c(), s() et m() sont des fonctions de mots de 32 bits, donnant 32 bits.

Ces fonctions sont:

c(X,Y,Z) = (X and Y) XOR (NOT X and Z)

m(X,Y,Z) = (X and Y) XOR (X and Z) XOR (Y and Z)

s(X) = rotate-droite-2-bit(X) XOR rotate-droite-13-bit(X) XOR rotate-droite-22-bit(X)

t(X) = rotate-droite-6-bit(X) XOR rotate-droite-11-bit(X) XOR rotate-droite-25-bit(X)

Le "schéma de données" consiste à considérer le bloc de 512 bits comme la source de 64 mots de 32 bits Wj :

  1. Les 16 premiers mots (i va de 0 à 15) sont les mots de 32 bits qui forment le bloc de données
  2. Les 48 mots suivants (pour i allant de 16 à 63) sont donnés par une formule d'itération:

Wj = u(Wj-2) + Wj-7 + v(Wj-15) + Wj-16

avec u et v deux fonctions:

u(X) = rotate-droite-17-bit(X) XOR rotate-droite-19-bit(X) XOR shift-droite-10-bit(X)

v(X) = rotate-droite-7-bit(X) XOR rotate-droite-18-bit(X) XOR shift-droite-3-bit(X)

Les 64 constantes Kj en notation hexadécimale:

428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5 
d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174 
e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da 
983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967 
27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85 
a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070 
19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3 
748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2

Ces constantes sont données de K0 à K63.  Ce sont les parties fractionnelles des racines cubes des 64 premiers nombres premiers (ceci pour éviter le soupçon de porte dérobée).

Il faut reconnaître que la structure de SHA-2 n'est pas très différente de SHA-1.  Il y a plus de constantes "arbitraires", et les fonctions de substitution sont plus compliquées, mais la structure générale est la même: un schéma avec des blocs de données, et un "chiffrage" du bloc de l'empreinte.

Nous avons discuté la fonction de compression dans SHA-256.  Celle de SHA-512 ne diffère guère, seulement les points suivants la diffèrent:

  • Le bloc de données est maintenant 1024 bits et les mots A ... H sont des mots de 64 bits
  • Il y a 80 tours au lieu de 64
  • Le schéma de message produira 80 mots de 64 bits au lieu de 64 mots de 32 bits
  • Les constantes Kj sont les versions 64 bit de la partie fractionnelle de la racine cube des 80 premiers nombres premiers
  • Les nombres de bits décalés ou tournés dans les fonctions s, t, u et v sont différents

s(X) = rotate-right-28-bit(X) XOR rotate-right-34-bit(X) XOR rotate-right-39-bit(X)

t(X) = rotate-right-14-bit(X) XOR rotate-right-18-bit(X) XOR rotate-right-41-bit(X)

u(X) = rotate-right-19-bit(X) XOR rotate-right-61-bit(X) XOR shift-right-6-bit(X)

v(X) = rotate-right-1-bit(X) XOR rotate-right-8-bit(X) XOR shift-right-7-bit(X)

Il faut se rappeler que nous nous sommes limités à la fonction de compression et que nous n'avons pas discuté du standard total de SHA-2.

SHA-3 - Keccak

SHA-1 et SHA-2 ont été conçus par la NSA aux USA.  Même si aucun n'a été cassé publiquement dans une démonstration pratique, des faiblesses théoriques ont été démontrés dans SHA-1, et même si SHA-2 ne souffre pas de ces mêmes défauts, la similarité entre les deux a inspiré la demande pour un autre standard qui pourrait être utilisé si jamais SHA-2 se montrerait vulnérable publiquement.  Une autre raison est que comme SHA-1 et SHA-2 ont été conçus par la NSA, qui a aussi comme mission de casser des systèmes cryptographiques, on peut avoir un doute sur la sincérité avec laquelle la NSA va concevoir des systèmes cryptographiques solides, qu'elle est de l'autre coté sensé d'essayer de casser.  Pire, on pourrait soupçonner la NSA de mettre des portes dérobés dans les standards cryptographiques qu'elle conçoit, et ce ne serait pas la première fois.  C'est pour éviter un tel soupçon, même sans fond, que pour la définition de SHA-3, on a fait appel à un concours ouvert.  C'est relativement remarquable que le gagnant de l'autre concours, AES (à savoir Rijndael) et le gagnant du concours de SHA-3, à savoir Kecak, ont un concepteur en commun, le cryptographe Belge Joan Daemen.

Nous allons seulement discuter de la fonction de compression de Keccak, pas du protocol en entier.  Seulement, Keccak est une fonction de hachage totalement différente de SHA-1 et SHA-2, et ne ressemble pas du tout à un chiffrement en bloc.  Tous les bits d'entrée sont traités de façon égale.  La fonction de compression de Keccak est 1-1, et fait partie d'une construction dite "éponge", pas d'un système de style Merkle-Damgard qui invite une structure comme un chiffrement en bloc.

La fonction de compression de Keccak est simplement un mixer de bits.  Le bloc dont les bits sont mixés prend la forme d'une matrice 5x5 de mots de 2l bits ; pour la version SHA-3 de Keccak, l = 6, ainsi, la fonction mixe 5 x 5 x 64 = 1600 bits.  Mais la définition de Keccak est plus large et peut prendre des blocs pour toute valeur de l.

Le mixeur de Keccak a 12 + 2 l tours.  Pour l = 6, cela veut donc dire 24 tours dans SHA-3.

Chaque tour a 5 transformations de l'état qui ont des noms de lettres Grecques: thêta, rhô, pi, Xi et iota.

Les bits sont numérotés: i : 0-4, j: 0-4, k: 0 - 2l-1.  i est l'index de la rangé, j est l'index de la colonne, et k est l'index du bit.  Quand les mots de 64 bits sont interprétés comme des nombres non signés, la convention little-endian s'applique.

Thêta:

Les 5 2l (= 320 si l = 6)bits de parité sont calculés sur les rangés: p(j,k) =  bit de parité des 5 bits a [ 0..4, j, k ].  Le pas thêta consiste en la production d'un nouveau

 a[ i, j, k] := a [ i, j, k ] XOR p(j - 1, k) XOR p(j + 1, k - 1) où nous prenons j - 1, j + 1 et k - 1modulo 5.

rhô:

Chacun des 25 mots est tourné d'un nombre triangulaire de bitrs: a[ i, j, k ] := a [ i, j, (k - (t+1)(t+2)/2 ]

où t est la solution de l'équation matricielle:

Quand t prend les valeurs de 0 à 24, toutes les paires (modulo 5) d'indices i,j sont générées.

pi:

Permutation des 25 mots sous la relation: a [ j, 2i + 3j , k ] := a[ i, j, k]

Chi:

C'est l'opération non-linéaire de Keccak:

a[ i, j, k ] := a[ i, j, k ] XOR (NOT a[ i, j+1, k ] AND a[ i, j+2, k ] )

iota:

Quelques bits du premier mot a[0,0,k] sont changés: dans le tour n, les l+1 bits avec m = 0...l: a[0,0,2m-1] sont changés.  Dans le tour n ils sont XORé avec le bit m+7n qui sort d'un registre linéaire de décalage avec contre-réaction de degré 8.  Cela revient à dire que le mot a[0,0,k] est XORé avec les constantes de 64 bits suivantes:

RC[ 0]	0x0000000000000001 	RC[12]	0x000000008000808B
RC[ 1]	0x0000000000008082 	RC[13]	0x800000000000008B
RC[ 2]	0x800000000000808A 	RC[14]	0x8000000000008089
RC[ 3]	0x8000000080008000 	RC[15]	0x8000000000008003
RC[ 4]	0x000000000000808B 	RC[16]	0x8000000000008002
RC[ 5]	0x0000000080000001 	RC[17]	0x8000000000000080
RC[ 6]	0x8000000080008081 	RC[18]	0x000000000000800A
RC[ 7]	0x8000000000008009 	RC[19]	0x800000008000000A
RC[ 8]	0x000000000000008A 	RC[20]	0x8000000080008081
RC[ 9]	0x0000000000000088 	RC[21]	0x8000000000008080
RC[10]	0x0000000080008009 	RC[22]	0x0000000080000001
RC[11]	0x000000008000000A 	RC[23]	0x8000000080008008

Nous ne décrivons pas le registre de décalage, il sert juste à montrer que ces constantes ne sont pas "magiques" mais viennent d'une procédure ouverte et ne cachent dont pas une porte dérobée que personne ne pourrait découvrir.

Ceci termine la description de la fonction de "compression" 1-1 dans Keccak.   Il s'avère que cette fonction est réversible !  Dans la construction éponge, où elle sera mise en oeuvre, l'irréversibilité viendra donc du fait qu'on rejettera une partie de l'état interne, mais il faut donc se dire que la fonction même n'a aucune résistance pré-image du tout.

Conclusion

Nous avons étudié 3 primitives de hachage, les fonctions de compression, très connues.  SHA-1 et SHA-2 sont très similaires et ont une structure comme un chiffrement en bloc, avec deux sortes de données d'entrée: l'entrée "empreinte" qui a la même longueur que la sortie, et une entrée "data" qui ressemble à la clé dans un chiffrement par bloc et correspond au nombre de bits qui seront "comprimés".  SHA-3 est d'une nature totalement différente, et a une fonction de compression 1-1 où tous les bits sont traités de façon égale.

Ces primitives sont utilisés pour construire des fonctions de hachage (et d'autres fonctions de base cryptographiques d'ailleurs).  Nous avons distingué un peu artificiellement la fonction de compression de la construction de hachage: dans la plupart des spécifications, la primitive et la construction sont spécifiés ensemble.  Nous avons fait cela pour illustrer notre conception de la structure en couche de la cryptographie, comme dans la structure de réseaux, qui forment une pile de protocols: HTTP sur TCP, TCP sur IP, IP sur, par exemple, ethernet.   Il y a bien plus de fonctions de hachage que les 3 standards qu'on vient d'étudier, bien sûr.