¿Cómo opera KECCAK en una matriz de estado llena de ceros?
Estoy tratando de implementar una esponja en Java. El estado comienza como una matriz vacía de 200 bytes de ceros. En el documento de muestras de KMAC de NIST, sucede lo siguiente:
(la línea negra es un salto de página de pdf)
La forma en que estoy leyendo esto es que se envió un estado con un montón de ceros a KECCAK, y luego se devolvió un estado con datos aparentemente aleatorios. ¿SH3/KECCAK convierte datos vacíos en datos aleatorios? ¿Estoy haciendo las preguntas correctas aquí? Cualquier ayuda es apreciada.
Respuestas
Personalmente, considero que el documento Keccak.team Psuedo Code es muy útil para comprender cómo funciona Keccak-p.
Como dijo DannyNiu en los comentarios, la mayoría de las permutaciones criptográficas (¿todas?) emplean "constantes redondas". Estas constantes se mezclan de alguna manera en el estado de Keccak.
El documento de pseudocódigo da las constantes redondas como una tabla:
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
y explica cómo se utilizan. En el paso de iota del$n^\text{th}$Ronda Keccak-p, la$n^\text{th}$constante redonda$RC[n]$se presenta y obtiene XOR en la primera palabra, primer carril.
Aparte de las constantes redondas, la permutación de Keccak tiene una muy buena difusión: un solo bit en algún lugar del estado inicial contribuirá significativamente a muchos bits de salida.
La combinación de ambos significa que su permutación de Keccak parece muy aleatoria. Por supuesto, no puede convertir la entropía cero en aleatoria, ya que ningún algoritmo finito puede hacer eso, pero el objetivo de Keccak es mezclar cosas y hacer que parezcan aleatorias.
La función de permutación de Keccak normalmente asignaría la entrada cero (todos los bits son 0) a la salida cero, si no fuera por el paso iota, en el que una palabra del estado se XOR con una constante distinta de cero.
Aproximadamente tres (de 24) rondas son suficientes para una difusión completa, es decir, cada parte del estado afecta a cada otra parte tres rondas más tarde. Se podría decir que la permutación mezcla el estado ocho veces por completo. Eso significa que si solo un bit es 1, se difundirá rápidamente sobre el estado, de modo que 3 rondas más tarde, aproximadamente la mitad de los bits de estado son 1.
Dejar$R$ser el conjunto de los valores de estado que razonablemente pueden llamarse "aspecto regular" (por cualquier definición exacta), por ejemplo, todos o casi todos los bits tienen el mismo valor, o un patrón de bits corto se repite regularmente. entre todos los$2^{1600}$estados, aquellos en$R$son una fracción muy pequeña. Es muy poco probable que algún estado en$R$se asigna a una salida también en$R$. Esto se mantiene mientras$|R| \ll 2^{800}$(ver "paradoja del cumpleaños").
Eso significaría que no hay una entrada de aspecto normal que se asigne a una salida de aspecto normal. Y la probabilidad de que cualquier estado dado se asigne a una salida en$R$es insignificante, es decir, la salida siempre parecerá aleatoria, excepto que alguien construya deliberadamente la entrada calculando la inversa de la permutación.