SHA-3

Keccak (prononciation: Modèle:API, comme “ketchak”) 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 Modèle:Langue qui a élu l'algorithme Keccak le Modèle:Date. 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 épongeModèle:, dans laquelle les blocs du messages sont XORés avec des bits initiaux, ensuite 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.

La permutation par bloc de Keccak

Keccak est une fonction éponge dont nous allons décrire la transformation, appelée Modèle:Math dans la terminologie de la construction de l’éponge. Cette transformation est une permutation valable en choisissant un mot d’une taille qui soit une puissance de deux w = 2^ℓ. Dans le cas de Keccak les mots sont de 64-bits, soit Modèle:Math.

L’état interne de cette fonction sera vu comme une matrice de dimension 5×5×w. $a[i][j][k]$ sera le bit $(i*5+j)*w+k$ 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 Modèle:Math de Keccak est une permutation qui consiste en Modèle:Math itérations (soit 24) de cinq sous routines assez simples :

La routine Modèle:Math

Calculer la parité des 5×w colonnes (de 5 bits) de l’état, puis calculer le ou exclusif entre deux colonnes voisines. Modèle:Indente

La routine Modèle:Math

Décaler circulairement les 25 mots d’un nombre triangulaire (0, 1, 3, 6, 10, 15, …). $a[0][0]$ n’est pas décalé, et :

Modèle:Indente

La routine Modèle:Math

Permutation des 25 mots avec un motif fixé: Modèle:Indente

La routine Modèle:Math

Combiner bit à bit des lignes selon la formule $a=a\oplus (\mathrm{\neg }b\mathrm{\&}c)$:

Modèle:Indente

Cette opération est la seule dite non linéaire.

La routine Modèle:Math

Calculer le ou exclusif d’une constante avec un mot de l’état, qui dépend du numéro de l’itération ( Modèle:Math ):

Modèle:Indente

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

La construction de l’éponge pour les fonctions de hachages. Les p_i sont l’entrée, les z_i sont l’empreinte en sortie. La « capacité » Modèle:Var, inutilisée, devrait être le double de la résistance voulue aux collisions ou aux 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 Modèle:Math 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 Modèle:Math 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 à Modèle:Math, avec Modèle:Var la taille de l’empreinte voulue.

Ainsi Modèle:Var, 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 Modèle:Var 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 Modèle:Var fixé à 64.

Pour aligner le message sur une taille multiple de la taille d’un bloc de Modèle:Var bits, il est comblé (par 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 Modèle:Var-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 Modèle:Var 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 Modèle:Var premiers bits de l’état. Modèle:Var est toujours plus grand que Modèle:Var, 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, Modèle:Var 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 Modèle:Var 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 Modèle:Math, soit 32 octets par itération.

SHA-3, instanciation la construction de l’éponge, pourrait s’écrire en pseudo-code :

fonction Modèle:Math(Modèle:Var) :

paramètres de la construction :

Modèle:Math : une transformation de Modèle:Math bits → Modèle:Math bits, décrite dans la précédente section

Modèle:Var : le nombre de bits par bloc de sortie

Modèle:Math : une fonction de comblement du Modèle:Var d’entrée en blocs entiers de Modèle:Var bits

Modèle:Var : le nombre de blocs de sortie

variables internes :

Modèle:Var : un tableau de Modèle:Var bits, initialisés à 0, divisé en Modèle:Math[1..Modèle:Var] et Modèle:Var[[[:Modèle:Var]]+1..Modèle:Var]

Modèle:Var : un tableau de blocs de Modèle:Var bits chacun

Modèle:Var : une chaîne à retourner, de longueur Modèle:Var×Modèle:Var, initialisée vide

algorithme :

(* phase d’absorption *)

Modèle:Var ← découpe Modèle:Math(Modèle:Var) en blocs de taille Modèle:Var bits

pour chaque Modèle:Var dans Modèle:Var :

Modèle:Var ← Modèle:Math(Modèle:Var[1..Modèle:Var] ⊕ Modèle:Var)

(* phase d’essorage *)

répéter Modèle:Var fois :

Modèle:Var ← concatène(Modèle:Var, Modèle:Var[1..Modèle:Var])

Modèle:Var ← Modèle:Var(Modèle:Var)

retourne Modèle:Var

Annexes

Articles connexes

• Modèle:Lien h
• SHA-1
• SHA-2

Liens externes

• Site web de Keccak
• Une implémentation en Java de Keccak