El diseño de las funciones hash más utilizadas se basa en las iteraciones de la función de compresión por el método de construcción Merkle-Damgård (MD) con un vector de inicialización constante. Esta construcción mostró que la seguridad de la función hash, contra los ataques diferenciales y genéricos, depende de la seguridad de la función de compresión y para ello la comunidad criptográfica ha propuesto nuevas funciones basadas en diferentes variantes de MD, algunas de ellas muy cercanas a Merkle-Damgård y otras con un enfoque distinto.
LH – Linear Hash y XLH – Linear XOR Hash.
La función fue descrita por Mihir Bellare y Phillip Rogaway en 1.997. Acepta una entrada clave adicional en cada iteración. Además, cada clave es distinta y, por lo tanto, LH requiere un número de entradas clave que sea lineal en el tamaño del mensaje. Emplea distintas funciones de compresión para cada evaluación del bloque de mensaje. A diferencia de la función LH, en XLH agrega el mismo número de claves distintas al XOR con los valores de encadenamiento resultantes de cada iteración de la función MD. A la primera clave se le aplica un XOR con el vector de inicialización (IV) y a la clave final también se le aplica XOR con el valor de encadenamiento intermedio final, mientras que el resultado de hash final queda sin modificar.
SC (Sponge Construction).
La construcción de Esponja fue propuesta por G. Bertoni, J. Daemen, M. Peeters y G. Van Assche en 2.007 como una construcción iterativa de una función hash, es completamente diferente a MD. Las herramientas Keccak y PHOTON están basados en ella.
SC utiliza un algoritmo de permutación de longitud fija en lugar de una función de compresión que puede generar cadenas de salida de longitud infinita. Además, se puede utilizar para construir cifrados de flujo.
La Esponja opera en un estado de longitud fija s = {0,1}r+c compuesto de r bits (velocidad) y c bits (capacidad), a través de una función: f = {0,1}r+c → {0,1}r+c que produce una transformación o permutación de s. El proceso se realiza en dos fases, la de absorción y la de compresión.
- Absorción. El mensaje se divide en bloques de r bits (rellenados si es necesario) y cada bloque está XORed con la parte r de s (inicialmente, s = {0}r+c), luego f procesa iterativamente hasta que trata todos los bloques.
- Compresión. El estado continúa permutándose por f, pero esta vez las r partes de los estados se devuelven en cada iteración como bloques de salida. Dado que la construcción es compatible con la salida de longitud variable, el usuario la elige y se determinan cuántos bloques son devueltos.
Opcionalmente, entre las dos fases, se puede aplicar un número de rondas en blanco. En las rondas en blanco no hay entrada o salida del estado. Solo, f se aplica al estado s.
Si f se expresa como una función aleatoria, la construcción se llama T-sponge, de lo contrario, si se expresa como una permutación, entonces la construcción se llama P-esponja.
La seguridad de una construcción de esponja depende de su capacidad c, tamaño de hash n y función f. Para la construcción de esponja P, la complejidad de una colisión es Min (2c/2, 2n/2) y la complejidad de la preimagen y la segunda preimage es Min (2c/2, 2n).
La complejidad de colisión de la construcción de esponja en T es igual a la complejidad de colisión de la construcción de esponja en P. Encontrar el costo de preimagen es Min (2c, 2n) y encontrar el de segunda preimagen es Min (2c/L, 2n) para una esponja T, donde L es la longitud del mensaje original.
Tree Construction.
Una de las primeras propuestas fue construir un resumen basado en árboles, pero un árbol binario crece con la longitud del mensaje y lo hacía inviable Las primeras alternativas avanzadas fueron de Carter y Wegman en 1.979, su opción era construir funciones hash universales. Más adelante, en 1.989, M. Naor y M. Yung, después, en 1.997, M. Bellare y P. Rogaway en el contexto de UOWHF (Universal One Way Hash Functions) y finalmente M. Bellare y D. Micciancio, también en 1.997, propusieron distintas formas de abordar el problema.
No es hasta 2.001 que y (SS) proponen la construcción de un árbol optimizado paralelizado que pudiesen operar con distintas partes del mensaje. La principal diferencia entre la construcción SS y las anteriores es que los autores consideran que la cantidad de procesadores disponibles debe ser fija, mientras que la longitud del mensaje puede ser arbitrariamente larga. Por lo tanto, la construcción SS consideró un árbol de procesador fijo y lo utilizó para enviar mensajes largos y arbitrarios. Cada procesador simplemente calcula la función hash base.
