Función de esponja
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2019; las comprobaciones requieren 7 ediciones .En criptografía , la función de esponja (o simplemente una esponja ) ( ing. construcción de esponja o función de esponja ) es una clase de algoritmos con un estado interno finito, que recibe una cadena binaria de longitud arbitraria como entrada , y que también devuelve una cadena binaria de longitud arbitraria f : {0,1 } n → {0,1} * . La función de esponja se puede usar para crear funciones hash , cifrados de flujo y bloque , y generadores de números pseudoaleatorios que tienen longitudes de entrada arbitrarias.
Estructura
Una esponja es una construcción iterativa para crear una función con entrada de longitud arbitraria y salida de longitud arbitraria basada en las transformaciones f. La esponja tiene un estado interno S - con datos de un tamaño fijo b (bits). En este caso, los datos se dividen en 2 partes: la primera S1 de tamaño r y la segunda S2 de tamaño c. El valor de r se denomina tasa de bits y el valor de c se denomina potencia; b=r+c.
En la fase de inicialización, un bloque de datos de tamaño b se llena con ceros y los datos de entrada M se dividen en bloques de tamaño r. El trabajo adicional de la esponja se lleva a cabo en 2 etapas:
- En la fase de “absorción”, la operación XOR se realiza para el siguiente bloque del mensaje original con la primera parte del estado S1 de tamaño r(bits), la parte restante del estado S2 con capacidad c permanece inalterada. El resultado se coloca en S1, y luego el estado S es procesado por la función f, una permutación pseudoaleatoria sin llave de múltiples rondas, y esto se repite hasta que se agotan los bloques del mensaje original.
- En la fase de "expresión", el estado S se alimenta a la función f, después de lo cual la parte S1 se alimenta a la salida. Estas acciones se repiten hasta obtener una secuencia de la longitud deseada (por ejemplo, la longitud del hash).
Los últimos bits de c dependen solo indirectamente de los bloques de entrada y no se emiten durante la fase de compresión.
Aplicación
Generador de números pseudoaleatorios basado en esponja
Simulación de PRNG con datos de entrada variablesDefinamos un PRNG de origen mutable como un objeto con estado que admite dos tipos de solicitudes, en cualquier orden:
- Feed request, feed(σ) - alimenta el valor original, que consiste en una cadena no vacía σ ϵ , en el estado PRNG;
- Aceptar solicitud, buscar (l): indica al PRNG que devuelva l bits.
Entonces el material de siembra suministrado a la entrada del generador es la concatenación de σ obtenida en todas las solicitudes de alimentación.
Informalmente, los requisitos para PRNG con datos iniciales variables se pueden definir de la siguiente manera:
En primer lugar, su salida (es decir, las respuestas a las solicitudes de envío) debe depender de todos los materiales de origen. En segundo lugar, debería ser imposible para un atacante que no conoce el material de origen pero ha observado parte de la salida para inferir el resto de la salida.
Definimos un PRNG ideal como una construcción usando un oráculo aleatorio.
La estructura que hemos definido se puede describir de la siguiente manera. Mantiene como estado una secuencia de todas las solicitudes de envío y aceptación que ha recibido, haciendo historial h. Cuando recibe una solicitud de alimentación (σ), actualiza el historial adjuntando esa solicitud. Al recibir una solicitud de aceptación fetch(l), envía una cadena a un oráculo aleatorio, que a su vez cifra el historial con la cadena y devuelve los bits z a z+l-1 de su respuesta, donde z es el número de bits solicitados en la solicitud de envío. Por lo tanto, la concatenación de respuestas a las solicitudes de alimentación es solo una respuesta aleatoria de Oracle a una sola solicitud. Esto se muestra en la figura. Llamemos a esta construcción un modo de preservación de la historia con la función de encriptación e(h). Por lo tanto, la definición de un modo de conservación de la historia converge con la definición de esta función de cifrado.
Dado que la salida del PRNG debe depender de todo el material fuente recibido, la función de cifrado e(h) debe ser inyectiva con el material fuente. En otras palabras, para dos secuencias de consulta cualesquiera con material de origen diferente, las dos asignaciones e(h) deben ser diferentes. A esto lo llamamos semilla-completitud. En una función de encriptación de fuente completa, la solicitud de aceptación producirá diferentes respuestas para diferentes cadenas de entrada. De ello se deduce que el PRNG devuelve bits independientes.
Por lo tanto, se propone la siguiente definición de un PRNG ideal con datos de entrada variables.
Un PRNG ideal con entradas mutables es un modo de conservación de la historia llamado oráculo aleatorio con una función de cifrado e(h) con material fuente completo.
Creando un PRNG usando la función de esponjaParece natural incluir la solicitud de suministro en la fase de "absorción" y la solicitud de aceptación en la fase de "apretón". Sin embargo, la ejecución de la función de esponja solo tiene una fase de remojo (una entrada) seguida de una fase de "apretón" (es decir, una salida de longitud arbitraria) y no se puede utilizar para producir varias fases.
Obviamente, esta dificultad se elude fácilmente. Basta con suponer que cada vez que se reciben los bits pseudoaleatorios, se solicita otra ejecución de la función esponja con una entrada diferente.
Al construir la función esponja, el mensaje de entrada m ϵ debe dividirse en bloques de r bits y rellenarse. Sea p(m) la función que hace esto, y suponga que esta función solo agrega los bits después de m. Supongamos que queremos reutilizar el estado de una esponja cuya cadena de entrada fue el mensaje m1 y cuyos bits de salida fueron "exprimidos" en l>0. El estado de la función esponja en este punto es como si el mensaje parcial m'1 = p(m1) || 0 r(⌈l/r⌉-1) fue “absorbido”. Tenga en cuenta que los bloques cero constituyen iteraciones adicionales debido a la fase de compresión. Reiniciar la esponja desde este punto significa que la entrada será el mensaje m2, para el cual m'1 es el prefijo.
Para definir formalmente un PRNG, debemos especificar una función de cifrado e(h) con material fuente completo, que represente la secuencia de envío y aceptación de solicitudes. La salida e(h) se usa como entrada para la función esponja.
En la práctica, la idea no es llamar a la función esponja en e(h) cada vez que recibimos una solicitud de aceptación. En su lugar, la construcción usa la función esponja en forma de cascada, reutilizando el estado como se describe en la sección 3.2.[ ¿dónde? ] Para permitir la reutilización de la función esponja, el estado e(h) debe ser tal que si h' = h || buscar(l) || feed(σ), luego p(e(h)) || 0 r(⌈l/r⌉-1) — prefijo e(h').
Para relacionar la construcción con la implementación práctica, primero describimos una construcción con dos restricciones. El primer límite está en la longitud de las consultas de valor de origen. Para un entero fijo k, requerimos que la longitud de alimentación σ en cualquier solicitud de alimentación (σ) sea tal que |p(σ)| = corona En otras palabras, después del relleno, el material fuente cubre exactamente k bloques de r bits. La segunda limitación es que la primera solicitud debe ser una solicitud de presentación.
Una construcción tiene estado si su estado consta de mϵ N bits recibidos desde la última solicitud de envío. Comencemos con una nueva ejecución de la función de esponja, establezca m = 0. Denote por e una fila, un mapeo de consultas e (h) agregadas al historial h.
- Si llegó una solicitud fetch(l):
La ejecución produce l bits de salida al "exprimirlos" de la función de esponja. Formalmente, e se adaptará durante la próxima solicitud de envío.
Se cambia el valor de m: m = m + l.
- Si llegó una solicitud de feed (σ):
Formalmente, esta solicitud de alimentación invoca una solicitud a la función esponja con e como entrada. Si esta no es la primera solicitud, solo se actualiza a la última solicitud de envío. Por lo tanto, los resultados de las solicitudes de obtención desde la última solicitud de envío deben incluirse en e como si e hubiera sido "absorbido" previamente. Primero, e se vuelve igual a p(e) para simular el llenado cuando se cambia a la fase de "apretón" después de la solicitud de alimentación anterior. Luego, se agregan ⌈m\r⌉ −1 bloques de r ceros a e para tener en cuenta las llamadas adicionales a f en solicitudes de alimentación posteriores. Ahora m se restablece: m = 0. (Esta parte solo afecta a e; nada debería cambiar en la ejecución).
Entonces σ se “absorbe”. Formalmente, esto se expresa sumando σ a e.
Finalmente, la ejecución cambia la función de esponja a la fase de "apretar". Esto significa que se deben completar los datos "empapados" y aplicar la permutación f al estado. (Formalmente, esto no cambia e, ya que el llenado, por definición, se realiza al pasar a la fase de centrifugado).
El límite de tamaño fijo para las solicitudes de envío es opcional y se puede eliminar. Para permitir una longitud variable del material de origen y preservar la integridad del material de origen, se debe introducir algún tipo de relleno dentro de la función de cifrado para garantizar que se puedan identificar los límites del material de origen. Además, deberá agregar una forma de distinguir los bloques con material de origen cero de los bloques cero. Esto se puede hacer, por ejemplo, poniendo un 1 en cada bloque que contiene el material de origen.
La restricción de que la primera solicitud sea una solicitud de alimentación se puede eliminar, ya que no tiene sentido generar bits pseudoaleatorios sin la primera alimentación del material de origen. Si la primera solicitud es una aceptación, la ejecución llena inmediatamente (con una cadena vacía) la entrada, cambia las funciones de esponja a la fase de "apretar" y produce bits de salida con el "apretón". Formalmente, en la próxima solicitud de envío, esto debe tenerse en cuenta en e asignando a e el valor p (cadena vacía) ||0 r([m=r]-1) .