Fonction éponge

En cryptographie, une fonction éponge, ou construction de l’éponge est une classe de fonctions permettant de construire entre autres des fonctions de hachage cryptographique. Elle a notamment été utilisée pour la fonction SHA-3. D'un point de vue théorique, elles permettent aussi de construire des preuves de sécurité de ce type de fonction[1]. Leur originalité est d’accepter en entrée à la fois des chaînes de taille arbitraire et de permettre en sortie des chaînes de la taille que l’on souhaite. Elles généralisent à la fois les fonctions de hachage et le chiffrement de flux.

Schéma de fonctions éponge pour la construction de fonctions de hachage. les

p_{i}

sont des blocs de la chaîne d'entrée, et les

z_{i}

sont les blocs du hachage en sortie.

Définition

La construction de l’éponge est une manière générique de construire une fonction $F$ qui prend en paramètre une chaîne de n’importe quelle taille (un flux ou un fichier par exemple) et qui retourne une chaîne de la longueur qu’on souhaite. Ses paramètres sont une permutation, ou plus généralement une transformation $f$ opérant sur un nombre fixe $b$ de bits, qu’on appellera largeur, et une fonction de complément (ou padding) $p$ .

Son fonctionnement est le suivant : la chaîne d’entrée est complémentée par la fonction de complément pour aligner la taille de la chaîne d’entrée sur un nombre entier de blocs, puis découpée en blocs de $r$ bits. Les $b$ bits de l’état interne sont initialisés à zéros, puis le calcul se déroule en deux phases :

l’absorption: Dans cette phase, les blocs de $r$ bits sont Xorés avec les $r$ premiers bits de l’état, en alternance avec des applications de la fonction $f$ sur l’état. Cette phase se déroule jusqu’à ce que tous les blocs aient été traités.
l’essorage: Cette phase est la construction pas à pas de la sortie. Elle consiste en la répétition des deux étapes suivantes : 1. les $r$ premiers bits de l’état sont retournés comme blocs de sortie et 2. la fonction $f$ est appliquée sur l’état. Le nombre d’itération est au choix de l’utilisateur et la taille de la chaîne de sortie en dépend.

Les derniers $c$ bits de l’état ne sont jamais directement modifiés par les blocs d’entrée et ne sont jamais retournés pendant l’essorage.

L’algorithme pourrait s’écrire en pseudo code :

F(flux) :
 Paramètres de la construction :
    $f$ : une transformation de  $b$  bits →  $b$  bits    $p$ : une fonction de padding    $n_{s}$ : le nombre de blocs de sortie
 Variables : 
    $état$ :  un tableau de  $b$  bits, initialisés à 0
divisé en état[1.. $r$ ] et état[ $r+1$ .. $b$ ]    $blocs$  : un tableau de blocs de  $r$  bits chaque    $sortie$  : une chaine, initialisée vide Algorithme :
  début
   (* phase d’absorption *)
    $blocs$  ← découpe p(flux) en blocs de taille  $r$ 
   pour chaque bloc de blocs :
       $état$  ← f(état[1..r] ⊕ bloc)
  
   (* phase d’essorage *)
   répéter  $n_{s}$  fois :
       $sortie$  ← concatène( $sortie$ , état[1..r])
       $état$  ←  $f$ ( $état$ )
  
   retourne  $sortie$ 
  fin

Notes et références

(en) [PDF] Guido Bertoni, Joan Daemen, Michaël Peeters et Gilles Van Assche, « Cryptographic sponge functions », sur http://sponge.noekeon.org/

(en) Guido Bertoni, Joan Daemen, Michaël Peeters et Gilles Van Assche, « The Sponge Functions Corner »
Site web consacré à la présentation des fonctions éponges

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « sponge function » (voir la liste des auteurs).

Portail de la cryptologie

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) [PDF] Guido Bertoni, Joan Daemen, Michaël Peeters et Gilles Van Assche, « Cryptographic sponge functions », sur http://sponge.noekeon.org/