Como o KECCAK opera em uma matriz de estado preenchida com zeros?
Estou tentando implementar uma esponja em Java. O estado começa como uma matriz vazia de 200 bytes de todos os zeros. No documento de amostras KMAC do NIST, acontece o seguinte:
(a linha preta é uma quebra de página do pdf)
A maneira como estou lendo isso é que um estado com um monte de zeros foi enviado para o KECCAK e, em seguida, um estado com dados aparentemente aleatórios foi retornado. O SHA3/KECCAK transforma dados vazios em dados aleatórios? Estou fazendo as perguntas certas aqui? Qualquer ajuda é apreciada.
Respostas
Pessoalmente, acho o documento Keccak.team Psuedo Code muito útil para entender como o Keccak-p.
Como DannyNiu disse nos comentários, a maioria (todas?) as permutações criptográficas empregam "constantes redondas". Essas constantes são de alguma forma misturadas no estado Keccak.
O documento de pseudocódigo fornece as constantes de rodada como uma tabela:
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
e explica como são usados. No iota-passo do$n^\text{th}$Rodada Keccak-p, a$n^\text{th}$constante de rodada$RC[n]$é apresentado e recebe XOR na primeira palavra, primeira faixa.
Além das constantes de rodada, a permutação de Keccak tem uma difusão muito boa: um único bit em algum lugar no estado inicial contribuirá significativamente para muitos bits de saída.
A combinação de ambos significa que sua permutação Keccak parece muito aleatória. Ele não pode, é claro, transformar entropia zero em aleatório, já que nenhum algoritmo finito pode fazer isso, mas o objetivo de Keccak é misturar as coisas e fazê-las parecer aleatórias.
A função de permutação Keccak normalmente mapearia a entrada zero (todos os bits são 0) na saída zero, se não fosse pelo passo iota, no qual uma palavra do estado é XORed com uma constante diferente de zero.
Cerca de três (de 24) rodadas são suficientes para difusão completa, ou seja, cada bit do estado afeta todos os outros bits três rodadas depois. Pode-se dizer que a permutação mistura o estado oito vezes completamente. Isso significa que, se apenas um bit for 1, ele se difundirá rapidamente pelo estado, de modo que 3 rodadas depois, cerca de metade dos bits de estado sejam 1.
Deixar$R$ser o conjunto de valores de estado que pode razoavelmente ser chamado de "aparência regular" (por qualquer definição exata), por exemplo, todos ou quase todos os bits têm o mesmo valor ou um padrão de bit curto se repete regularmente. Entre todos os$2^{1600}$estados, aqueles em$R$são uma fração muito pequena. É muito improvável que qualquer estado em$R$é mapeado em uma saída também em$R$. Isso se mantém enquanto$|R| \ll 2^{800}$(veja "paradoxo do aniversário").
Isso significaria que não há entrada de aparência regular mapeada para uma saída de aparência regular. E a probabilidade de qualquer estado dado ser mapeado para uma saída em$R$é insignificante, ou seja, a saída sempre parecerá aleatória, exceto que alguém deliberadamente constrói a entrada calculando o inverso da permutação.