Voir la source de SHA-3

'''Keccak''' (prononciation: {{API|[kɛtʃak]}}, comme “ketchak”)<ref>{{Lien Web|langue=en|titre=The Keccak sponge function family: Specifications summary |url=http://keccak.noekeon.org/specs_summary.html |consulté le=2011-05-11|site=keccak.noekeon.org|auteurs=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche}}.</ref> est une [[fonction de hachage cryptographique]] conçue par Guido Bertoni, [[Joan Daemen]], Michaël Peeters et [[Gilles Van Assche]] à partir de la fonction [[RadioGatún]].

'''SHA-3''' est issu de la {{Langue|en|[[NIST hash function competition]]}} qui a élu l'algorithme '''Keccak'''<ref>{{Lien Web|auteur=Patrick Guignot|site=[[Linuxfr]]|titre=Keccak remporte la mise et devient SHA-3|url=https://linuxfr.org/news/keccak-remporte-la-mise-et-devient-sha-3}}.</ref> le {{Date|2|octobre|2012}}. Elle n’est pas destinée à remplacer [[SHA-2]], qui n’a à l'heure actuelle pas été compromise par une attaque significative, mais à fournir une autre solution à la suite des possibilités d'attaques contre les standards [[MD5]], [[SHA-0]] et [[SHA-1]].

Keccak est une [[fonction éponge]]<ref>{{Lien Web|langue=en|url=http://sponge.noekeon.org/ |titre=Sponge Functions |éditeur=Ecrypt Hash Workshop 2007 |auteur=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche}}.</ref>{{,}}<ref>{{Lien web|langue=en|url=http://sponge.noekeon.org/ |titre=On the Indifferentiability of the Sponge Construction |éditeur=EuroCrypt 2008 |auteur=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche}}.</ref> dans laquelle les blocs du messages sont [[XOR]]és avec des [[bit]]s initiaux, ensuite [[permutation|permutés]] de manière réversible.

L'algorithme Keccak tel que soumis initialement est parfois utilisé, il diffère de l'algorithme spécifié par le NIST car le NIST a spécifié la manière de compléter le message lorsque la longueur du message n'est pas égale à la taille requise en entrée par la fonction éponge. Les résultats sont différents<ref>[https://asecuritysite.com/encryption/s3?m=abc Valeur de hash de la chaine 'abc' pour plusieurs variantes de l'algorithme]</ref>.

== La permutation par bloc de Keccak ==
Keccak est une [[fonction éponge]] dont nous allons décrire la transformation, appelée {{math|f}} dans la terminologie de la construction de l’éponge. Cette transformation est une permutation valable en choisissant un [[mot (informatique)|mot]] d’une taille qui soit une puissance de deux w = 2<sup>ℓ</sup>. Dans le cas de Keccak les mots sont de 64-bits, soit {{math|1=ℓ=6}}.

L’état interne de cette fonction sera vu comme une [[matrice (mathématiques)|matrice]] de dimension 5×5×''w''. <math>a[i][j][k]</math> sera le bit <math>(i*5+j)*w+k</math> de l’entrée. Le calcul des indices est effectué modulo 5 pour les deux premières dimensions, et modulo ''w'' pour la troisième.

La fonction {{math|f}} de Keccak est une permutation qui consiste en {{math|12+2ℓ}} itérations (soit 24) de cinq sous routines assez simples :
; La routine {{math|θ}}
: Calculer la [[parité (arithmétique)|parité]] des 5×''w'' colonnes (de 5 bits) de l’état, puis calculer le [[Xor|ou exclusif]] entre deux colonnes voisines. {{indente|1= <math>a[i][j][k] \leftarrow a[i][j][k] \oplus parite(a[0..4][j-1][k]) \oplus parite(a[0..4][j+1][k-1])</math> }}<!--


-->
; La routine {{math|ρ}}
: [[Décalage circulaire|Décaler circulairement]] les 25 mots d’un [[nombre triangulaire]] (0, 1, 3, 6, 10, 15, …). <math>a[0][0]</math> n’est pas décalé, et :
:{{indente|'''pour chaque''' {{math|0 ≤ t < 24}} ''':'''<!--
       -->{{indente|<!--

                  --><math>\begin{pmatrix} i \\ j \end{pmatrix} \leftarrow \begin{pmatrix} 3 & 2 \\ 1 & 0 \end{pmatrix}^t \begin{pmatrix} 0 \\ 1 \end{pmatrix}</math><br><!--

                  --><math>a[i][j][k] \leftarrow a[i][j][ k-(t+1)(t+2)/2]</math>
          }}
    }}<!--

-->
; La routine {{math|π}}
: Permutation des 25 mots avec un motif fixé: {{indente|1=<math>a[3i+2j][i] = a[i][j]</math>}}<!--

-->
; La routine {{math|χ}}
: Combiner bit à bit des lignes selon la formule <math>a = a \oplus (\lnot b \& c)</math>:
: {{indente|<math>a[i][j][k] \leftarrow a[i][j][k] \oplus  \lnot (a[i][j+1][k]) \& (a[i][j+2][k])</math>}}
: Cette opération est la seule dite non linéaire.<!--

-->
; La routine {{math|ι}}
: Calculer le ou exclusif d’une constante avec un mot de l’état, qui dépend du numéro de l’[[itération]] ( {{math|n}} ):
:<!--    -->{{indente|''' pour chaque ''' {{math|0 ≤ m ≤ ℓ}} ''':'''<!--

               -->{{indente| <math>a[0][0][2^m-1]</math> est [[Xor]]é avec le bit numéroté {{math|m+7n}} d’une séquence [[LFSR]] de degré 8.}}}}
: Cette dernière étape a pour objectif de casser les dernières symétries laissées par les précédentes.

== Hacher des messages de taille variable ==
[[Image:SpongeConstruction.svg|vignette|upright=1.35|droite|alt=Illustration d'une fonction éponge|La construction de l’éponge pour les fonctions de hachages. Les p<sub>i</sub> sont l’entrée, les z<sub>i</sub> sont l’empreinte en sortie. La « capacité » {{var|c}}, inutilisée, devrait être le double de la résistance voulue aux [[attaque de collisions|collisions]] ou aux [[attaque de préimage|attaques de préimage]].]] 

SHA-3 utilise la [[construction de l’éponge]], dans laquelle l’entrée est, métaphoriquement dans une première phrase ''absorbée'' par l’état, à une certaine vitesse, et dans une deuxième ''essorée'', à la même vitesse.

Pour absorber {{math|r}} bits des données, la donnée est ''XOR''ée dans les premiers bits de l’état, puis la permutation par blocs est appliquée si une sortie additionnelle est désirée.

La ''capacité'' de la fonction de hachage, les {{math|1={{var|c}}=25{{var|w}}-{{var|r}}}} bits d’états qui ne sont jamais directement touchés par l’entrée ou la sortie, est un paramètre important. Elle peut être ajustée en fonction de la sécurité attendue de la construction, mais la norme SHA-3 la fixe raisonnablement à {{math|1={{var|c}}=2{{var|n}}}}, avec {{var|n}} la taille de l’empreinte voulue.

Ainsi {{var|r}}, la quantité de bits du message traitée à chaque permutation, dépend de la taille d’empreinte désirée. Les différents choix de taux {{var|r}} sont 1152, 1088, 832, ou 576 (144, 136, 104 ou 72 [[octets]]) pour des tailles d’empreinte de 224, 256, 384 et 512 bits, respectivement, pour {{var|w}} fixé à 64.

Pour aligner le message sur une taille multiple de la taille d’un bloc de {{var|r}} bits, il est comblé (par [[Remplissage (cryptographie)|remplissage, ou ''padding'']] en anglais) avec le motif binaire '''10...01''' : un premier bit à 1, suivi éventuellement du nombre approprié de bits à 0 (au maximum {{var|r}}-1 bits), mais toujours suivi d’un autre bit à 1. Ce dernier bit est une précondition nécessaire à la [[preuve de sécurité]] de la construction de l’éponge (le dernier bloc de message doit être non nul).

L’algorithme se déroule ainsi : l’état est initialisé à 0, l’entrée est comblée, découpée en blocs de {{var|r}} bits. L’entrée est absorbée par l’état, c’est-à-dire que pour chaque bloc elle est ''XOR''ée avec l’état puis la permutation est appliquée sur le résultat.

Une fois toutes les permutations effectuées, l’empreinte résultat est constituée des {{var|n}} premiers bits de l’état. {{var|r}} est toujours plus grand que {{var|n}}, il n’y a par conséquent jamais besoin d’appliquer plusieurs permutations lors de la phase d’essorage. Dans d’autres applications comme ''[[Optimal Asymmetric Encryption Padding]]'' (OAEP) une sortie de taille variable est utile. Dans ce cas, {{var|n}} est un [[paramètre de sécurité]] plus qu’une simple taille de sortie.

Des variantes de la fonction de permutation permettant de générer des hachages plus petits  sont également disponibles pour des tailles de hachage allant jusqu’à la moitié de la taille de leur état interne, si le taux {{var|r}} est suffisamment faible. Elles n’étaient pas nécessaire pour la candidature à la compétition SHA. Par exemple, il est possible de calculer une empreinte de 256 bits en utilisant 25 mots de 32 bits si {{math|1={{var|r}}=800−2×256=288}}, soit 32 octets par itération.

SHA-3, instanciation la construction de l’éponge, pourrait s’écrire en [[pseudo-code]] :
: '''fonction''' {{math|SHA-3}}({{var|flux}}) :
: '''paramètres de la construction :'''
::   {{math|f}} : une transformation de {{math|b}} bits → {{math|b}} bits, décrite dans la précédente section
::   {{var|r}} : le nombre de bits par bloc de sortie
::   {{math|pad}} : une fonction de comblement du {{var|flux}} d’entrée en blocs entiers de {{var|r}} bits
:: {{var|n<sub>s</sub>}} : le nombre de blocs de sortie
: '''variables internes :'''
::   {{var|état}} : un tableau de {{var|b}} bits, initialisés à 0, divisé en {{math|état}}[1..{{var|r}}] et {{var|état}}[{{var|r}}+1..{{var|b}}]
::   {{var|blocs}} : un tableau de blocs de {{var|r}} bits chacun
::   {{var|z}} : une chaîne à retourner, de longueur {{var|n<sub>s</sub>}}×{{var|r}}, initialisée vide
: '''algorithme :'''
::''(* phase d’absorption *)''
::   {{var|blocs}} ← '''découpe''' {{math|pad}}({{var|flux}}) '''en blocs de taille''' {{var|r}} bits
::   '''pour chaque''' {{var|p}} '''dans''' {{var|blocs}} :
:::{{var|état}} ← {{math|f}}({{var|état}}[1..{{var|r}}] ⊕ {{var|p}})
::   ''(* phase d’essorage *)''
::   '''répéter''' {{var|n<sub>s</sub>}} '''fois''' :
:::     {{var|z}} ← '''concatène'''({{var|z}}, {{var|état}}[1..{{var|r}}])
:::     {{var|état}} ← {{var|f}}({{var|état}})
::   '''retourne''' {{var|z}}

== Notes et références ==
{{Traduction/Référence|en|Keccak|516802067|type=note}}
{{Références}}

== Annexes ==
=== Articles connexes ===
* {{Lien h|Secure Hash Algorithm}}
* [[SHA-1]]
* [[SHA-2]]

=== Liens externes ===
* [http://keccak.noekeon.org/ Site web de Keccak]
* [https://github.com/kocakosm/pitaya/blob/master/src/org/kocakosm/pitaya/security/Keccak.java Une implémentation en Java de Keccak]

{{Palette|Fonctions de hachage cryptographiques}}
{{Portail|cryptologie|sécurité informatique}}

[[Catégorie:Algorithme de hachage]]