Comment KECCAK fonctionne-t-il sur un tableau d'état rempli de zéros ?
J'essaie d'implémenter une éponge en Java. L'état commence par un tableau vide de 200 octets de tous les zéros. Dans le document d'exemples KMAC du NIST, voici ce qui se passe :
(la ligne noire est un saut de page pdf)
La façon dont je lis ceci est qu'un état avec un tas de zéros a été envoyé dans KECCAK, puis un état avec des données apparemment aléatoires a été renvoyé. SHA3/KECCAK transforme-t-il les données vides en données aléatoires ? Est-ce que je pose les bonnes questions ici? Toute aide est appréciée.
Réponses
Personnellement, je trouve le document Keccak.team Psuedo Code très utile pour comprendre comment Keccak-p.
Comme DannyNiu l'a dit dans les commentaires, la plupart (toutes?) Les permutations cryptographiques utilisent des "constantes rondes". Ces constantes sont en quelque sorte mélangées dans l'état de Keccak.
Le document pseudocode donne les constantes rondes sous forme de tableau :
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
et explique comment ils sont utilisés. Dans l'étape iota de la$n^\text{th}$Keccak-p rond, le$n^\text{th}$constante ronde$RC[n]$est introduit et obtient XOR dans le premier mot, première voie.
En dehors des constantes rondes, la permutation de Keccak a une très bonne diffusion : un seul bit quelque part dans l'état initial contribuera de manière significative à de nombreux bits de sortie.
La combinaison des deux signifie que votre permutation Keccak semble très aléatoire. Il ne peut, bien sûr, transformer l'entropie nulle en aléatoire, car aucun algorithme fini ne peut le faire, mais le but de Keccak est de mélanger les choses et de les faire apparaître aléatoires.
La fonction de permutation de Keccak mapperait normalement l'entrée zéro (tous les bits sont 0) sur la sortie zéro, sinon pour l'étape iota, dans laquelle un mot de l'état est XOR avec une constante non nulle.
Environ trois tours (sur 24) sont suffisants pour une diffusion complète, c'est-à-dire que chaque bit de l'état affecte tous les autres bits trois tours plus tard. On pourrait dire que la permutation mélange l'état huit fois complètement. Cela signifie que si un seul bit est 1, il se diffusera rapidement sur l'état de sorte que 3 tours plus tard, environ la moitié des bits d'état sont 1.
Laisser$R$être l'ensemble des valeurs d'état qui peuvent raisonnablement être appelées "recherche régulière" (quelle que soit la définition exacte), par exemple tous ou presque tous les bits ont la même valeur, ou un court motif de bits se répète régulièrement. Parmi tous les$2^{1600}$États, ceux de$R$sont une très petite fraction. Il est très peu probable qu'un État de$R$est mappé sur une sortie également dans$R$. Cela tient tant que$|R| \ll 2^{800}$(voir "paradoxe de l'anniversaire").
Cela signifierait qu'il n'y a pas d'entrée de recherche régulière mappée sur une sortie de recherche régulière. Et la probabilité qu'un état donné soit mappé sur une sortie dans$R$est négligeable, c'est-à-dire que la sortie aura toujours l'air aléatoire, sauf que quelqu'un construit délibérément l'entrée en calculant l'inverse de la permutation.