La Función Merkle-Damgård (MD) es un método para crear funciones hash resistentes a la colisión a partir de funciones de compresión unidireccionales. Fue propuesta por Ralph Merkle en 1.979 en “A Certified Digital Signature”, posteriormente Ivan Damgård demostró, de forma independiente, que la estructura era sólida, es decir:
“si se usa un esquema de relleno apropiado y la función de compresión es resistente a la colisión, entonces la función hash también los será”
Esta construcción es la idea básica utilizada en todas las funciones hash criptográficas modernas. La función MD utiliza una función de relleno compatible con ella, la propuesta por Mihir-Bellare es idónea. Después de haber creado una entrada cuyo tamaño es un múltiplo de un número fijo, el proceso hash también divide el resultado en bloques de tamaño fijo y los procesa de uno en uno con la función de compresión, combinando cada vez un bloque de la entrada con la salida de la iteracción anterior.
El proceso sería el siguiente:
Construye una función hash iterada a partir de un componente de longitud fija llamada función de compresión que toma un valor de encadenamiento de entrada de n bits y un bloque de mensajes de m bits y deriva un nuevo valor de encadenamiento de salida de n bits.
- La cadena de entrada se rellena para garantizar que es un múltiplo entero de m bits de longitud y que la longitud del mensaje original, sin relleno, aparece en el último bloque del mensaje con relleno.
- El valor de encadenamiento del hash h[ i ] se inicia con un valor público fijo llamado Vector de Inicialización (IV) y se actualiza para cada bloque de mensaje sucesivo M[ i ] como h [ i ] = F ( h [i – 1], M [ i ] ).
- El valor de h [ i ], después de procesar el último bloque del mensaje rellenado es el valor de salida del hash.
Propuestas mínimas Merkle-Damgård en seguridad.
- Resistencia a la colisión: un atacante no debería poder encontrar, con un trabajo menor de 2n/2 , un par de mensajes M ≠ M‘ tal que el hash (M) = hash (M‘).
- Resistencia de preimagen: dado un posible valor de salida para el hash S, un atacante no debería poder encontrar, con un trabajo menor de 2n, una entrada X para que S = hash (X).
- Segunda resistencia de preimagen: dado un mensaje M, un atacante no debería poder encontrar un segundo mensaje M‘ , para satisfacer el hash (M) = hash (M‘ ) con un trabajo menor de 2n.
Problemas de la función:
- En 2.004 John Kelsey y Bruce Schneier encuentran que los ataques de segunda preimagen contra mensajes largos son viables y más rápidos que el ataque por fuerza bruta.
- Las multicolisiones (muchos mensajes con el mismo hash) se pueden encontrar con mayor frecuencia de lo que se podía esperar.
- En 2.006 John Kelsey y Tadayoshi Kohno proponen lo que denominan Herding attack / ataque Nostradamus.
- Extensión de longitud: dado el hash h(X) de una entrada desconocida X, es fácil encontrar el valor de h( R(X) || Y ), donde R es la función de relleno del hash. Es decir, es posible encontrar hashes de entradas relacionadas con X aunque X siga siendo desconocido.
Evolución de la función.
3C, 3C+ construction. Es la variante más simple de MD que mejora su seguridad contra el ataque de colisión de bloques múltiples, fue propuesta por Praveen Gauravaram, William Millan, Ed Dawson, Matt Henricksen, Juanma González Nieto y Kapali Viswanathan en 2.006.
La función de división procesa los valores de encadenamiento intermedios de la instrucción MD, manteniendo una segunda variable de encadenamiento que contiene un valor producido por un XOR repetido sobre las variables de encadeamiento mientras se procesa un mensaje de forma aleatoria, esta variable se procesa luego en una llamada de finalización adicional a la función de compresión.
Hay dos cadenas en la construcción: la cadena de acumulación y la cadena en cascada. La cadena de acumulación y la función de compresión tienen un acumulador XOR. La función trabaja de forma iterativa en la cadena de cascada, de manera similar a la construcción MD.
El proceso divide el mensaje en t bloques con IV0 , representando el valor inicial. ai y ci son las variables de encadenamiento en la cadena de acumulación y en la cadena en cascada. Las funciones de compresión se ejecutan tres veces para cada bloque: el bloque de datos de procesamiento, de relleno y la formación del bloque Z en la cadena de acumulación. El 3C es tan seguro como la construcción MD.
Para aumentar el nivel de seguridad de 3C, se ha propuesto el diseño 3C +. En la construcción de hash 3C +, hay una cadena adicional llamada la cadena final.
Dither Hash. Es otra variante de MD desarrollada por Ronald Rivest en 2.005 que incluye una entrada adicional similar a un contador. La intención del diseño es agregar una entrada dependiente de la iteración a la función de compresión para derrotar ciertos ataques genéricos. La entrada adicional, denominada entrada de “tramado” a la función de compresión, está formada por los elementos consecutivos de una secuencia fija. Esto da al atacante menos control sobre la entrada de la función de compresión y hace que el hash de un bloque de mensaje dependa de su posición en todo el mensaje. En particular, su objetivo es prevenir ataques basados en mensajes ampliables.
EMD (Enveloped Merkle-Damgård). Fue propuesto por Mihir Bellare y Thomas Ristenpart y se asemeja al diseño de HMAC propuesto por H. Krawczyk, M. Bellare y R. Canetti en 1.997. Utiliza dos vectores de inicialización (IV) fijos 0 y 1. El primero aplica el estilo Merkle-Damgård en la entrada a la primera función de compresión. El segundo se proporciona como entrada a la función de compresión final junto con la variable de encadenamiento y los bits del mensaje de entrada final, a este paso se le conoce como “envolvente”. Bellare y Ristenpart demostraron que el EMD conserva la resistencia a la colisión, la indiferenciación del “oráculo” aleatorio y lo indistinguible de la función seudoaleatoria PRF.
NI (Nested Iteration). NI es básicamente una variante codificada de la construcción Merkle-Damgård que utiliza dos claves k’, k” ∈, {0,1}k . Bellare y Ristenpart demostraron más tarde, en 2.007, que NI también es indistinguible de PRF, indiferenciable de RO y, si se usó el fortalecimiento, NI también es resistente a las colisiones.
HAIFA (HAsh Iterative FrAmework), es una construcción modificada de Merkle-Damgård propuesta por Eli Biham y Orr Dunkelman en 2.005 y 2.006. Introduce parámetros de entrada adicionales a la función de compresión, la inclusión de un contador de bits garantiza el sufijo y las propiedades de prefijo del diseño y ayuda a demostrar que es indiferenciable desde un “oráculo” aleatorio y trata de corregir las debilidades de MD en los ataques de extensión de longitud. Puede considerarse una función de hash de clave dedicada. Permite la creación de resúmenes de tamaño variable y definir familias de funciones como: hashing aleatorio, EMD o modos RMC y ROX. Las funciones resumen que han adoptado esta estructura son: BLAKE, ECHO, HNF-256, Sarmal, SHAvite-3 o SWIFFTX.
MDP (Merkle-Damgård Permutation). Es una variante del diseño original de MD propuesto por Shoichi Hirose, Je Hong Park y Aaram Yun en 2.008. La única diferencia con la construcción MD es que se aplica una permutación antes del proceso del último bloque de mensajes. La permutación enmascara el proceso interno de MD, de manera similar a la idea de EMD, y demuestra que el MDP es indiferente desde un “oráculo” aleatorio cuando la función de compresión subyacente es una función ideal.
