Keccak (prononciation:[kɛtʃak], comme “ketchak”)[1] est unefonction de hachage cryptographique conçue par Guido Bertoni,Joan Daemen, Michaël Peeters etGilles Van Assche à partir de la fonctionRadioGatún.
SHA-3 est issu de laNIST hash function competition qui a élu l'algorithmeKeccak[2] le. Elle n’est pas destinée à remplacerSHA-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 standardsMD5,SHA-0 etSHA-1.
Keccak est unefonction éponge[3],[4] dans laquelle les blocs du messages sontXORés avec desbits initiaux, ensuitepermuté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[5].
Keccak est unefonction éponge dont nous allons décrire la transformation, appeléef dans la terminologie de la construction de l’éponge. Cette transformation est une permutation valable en choisissant unmot d’une taille qui soit une puissance de deux w = 2ℓ. Dans le cas de Keccak les mots sont de 64-bits, soitℓ=6.
L’état interne de cette fonction sera vu comme unematrice de dimension 5×5×w. sera le bit de l’entrée. Le calcul des indices est effectué modulo 5 pour les deux premières dimensions, et modulow pour la troisième.
La fonctionf de Keccak est une permutation qui consiste en12+2ℓ itérations (soit 24) de cinq sous routines assez simples :
SHA-3 utilise laconstruction de l’éponge, dans laquelle l’entrée est, métaphoriquement dans une première phraseabsorbée par l’état, à une certaine vitesse, et dans une deuxièmeessorée, à la même vitesse.
Pour absorberr bits des données, la donnée estXORée dans les premiers bits de l’état, puis la permutation par blocs est appliquée si une sortie additionnelle est désirée.
Lacapacité de la fonction de hachage, lesc=25w-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 àc=2n, avecn la taille de l’empreinte voulue.
Ainsir, 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 tauxr sont 1152, 1088, 832, ou 576 (144, 136, 104 ou 72octets) pour des tailles d’empreinte de 224, 256, 384 et 512 bits, respectivement, pourw fixé à 64.
Pour aligner le message sur une taille multiple de la taille d’un bloc der bits, il est comblé (parremplissage, oupadding en anglais) avec le motif binaire10...01 : un premier bit à 1, suivi éventuellement du nombre approprié de bits à 0 (au maximumr-1 bits), mais toujours suivi d’un autre bit à 1. Ce dernier bit est une précondition nécessaire à lapreuve 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 der bits. L’entrée est absorbée par l’état, c’est-à-dire que pour chaque bloc elle estXORé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 desn premiers bits de l’état.r est toujours plus grand quen, il n’y a par conséquent jamais besoin d’appliquer plusieurs permutations lors de la phase d’essorage. Dans d’autres applications commeOptimal Asymmetric Encryption Padding (OAEP) une sortie de taille variable est utile. Dans ce cas,n est unparamè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 tauxr 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 sir=800−2×256=288, soit 32 octets par itération.
SHA-3, instanciation la construction de l’éponge, pourrait s’écrire enpseudo-code :
| Algorithmes | |
|---|---|
| Cryptanalyse | |
| Architecture | |
