title: Grøstl
text: # Grøstl
  
  Grøstl est une fonction de hachage soumise à la compétition SHA-3 par Praveen Gauravaram, Lars Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, et Søren S. Thomsen. Grøstl a été sélectionné comme l'un des cinq finalistes de la compétition le 10 décembre 2010. Il utilise la même boîte de substitution que l'AES. Les auteurs annoncent un débit de 21,4 cycles/octet sur un Intel Core 2 Duo.
  
  D'après le document de soumission, le nom « Grøstl » est un jeu de mots multilingue se référant à un plat autrichien de type hachis.
  
  Comme les autres fonctions de hachage MD5 ou la famille SHA, Grøstl divise l'entrée en blocs et calcule itérativement $h_i$ = $f(h_{i−1},$ $m_i).$ Cependant, Grøstl maintient un état interne (ou variable de chaînage) d'au moins deux fois la taille du haché de sortie (512 ou 1024 bits). Cet état interne est tronqué en fin de calcul.
  
  La fonction de compression f est basée sur une paire de fonctions de permutation sur 256 ou 512 bits P et Q. f est ainsi définie :
  
      f(h, m) = P(h ⊕ m) ⊕ Q(m) ⊕ h
  
  Les fonctions de permutation P et Q sont basées sur l'algorithme de chiffrement par bloc Rijndael (AES) mais opèrent sur des tableaux d'octets 8x8 ou 16x16, plutôt que 4x4. Comme l'AES, chaque ronde consiste en quatre opérations :
  
  * AddRoundKey (les sous-clés de Grøstl sont fixes mais diffèrent entre P et Q) ;
  * SubBytes (cette opération utilise la S-box AES, autorisant un partage de ressource avec une implémentation AES) ;
  * ShiftBytes (comme l'AES mais étendu à la matrice 8x8 ou 16x16 ; cette opération diffère entre P et Q ainsi qu'entre les versions 512 et 1024 bits) ;
  * MixColumns (utilise une matrice 8x8 (l'AES utilisant une matrice 4×4)).
  
  Contrairement à l'AES, toutes les rondes sont identiques et il n'y a pas d'opération AddRoundKey finale. 10 rondes sont recommandées pour la permutation 512 bits, et 14 pour la version 1024 bits.
  
  La variable de chaînage finale supporte une transformation finale :
  
      Ω(h) = h ⊕ P(h)
  
  Cette transformation est équivalente à une itération finale de la fonction de compression en utilisant un bloc de message m tout-a-zéro, suivi par un ou exclusif avec la constante Q(0). La variable de chaînage est alors tronquée à la longueur désirée (512 ou 1024 bits) pour en dériver le haché final.
  
  