En criptografía , la construcción Merkle-Damgård o la función hash Merkle-Damgård es un método para construir funciones hash criptográficas resistentes a colisiones a partir de funciones de compresión unidireccionales resistentes a colisiones . [1] : 145 Esta construcción se utilizó en el diseño de muchos algoritmos hash populares como MD5 , SHA-1 y SHA-2 .
La construcción Merkle-Damgård se describió en el Ph.D. de Ralph Merkle . tesis en 1979. [2] Ralph Merkle e Ivan Damgård demostraron independientemente que la estructura es sólida: es decir, si se usa un esquema de relleno apropiado y la función de compresión es resistente a colisiones , la función hash también será resistente a colisiones. [3] [4]
La función hash Merkle-Damgård primero aplica una función de relleno compatible con MD para crear una entrada cuyo tamaño sea un múltiplo de un número fijo (por ejemplo, 512 o 1024); esto se debe a que las funciones de compresión no pueden manejar entradas de tamaño arbitrario. La función hash luego divide el resultado en bloques de tamaño fijo y los procesa uno a la vez con la función de compresión, cada vez combinando un bloque de la entrada con la salida de la ronda anterior. [1] : 146 Para que la construcción sea segura, Merkle y Damgård propusieron que los mensajes se rellenen con un relleno que codifique la longitud del mensaje original. A esto se le llama acolchado largo o fortalecimiento Merkle-Damgård .
En el diagrama, la función de compresión unidireccional se denota por f , y transforma dos entradas de longitud fija en una salida del mismo tamaño que una de las entradas. El algoritmo comienza con un valor inicial, el vector de inicialización (IV). El IV es un valor fijo (algoritmo o implementación específica). Para cada bloque de mensaje, la función de compresión (o compactación) f toma el resultado hasta ahora, lo combina con el bloque de mensaje y produce un resultado intermedio. El último bloque se rellena con ceros según sea necesario y se añaden bits que representan la longitud de todo el mensaje. (Consulte a continuación para obtener un ejemplo detallado de relleno de longitud).
Para endurecer aún más el hash, el último resultado a veces se alimenta a través de una función de finalización . La función de finalización puede tener varios propósitos, como comprimir un estado interno más grande (el último resultado) en un tamaño de hash de salida más pequeño o garantizar una mejor mezcla y efecto de avalancha en los bits en la suma de hash. La función de finalización a menudo se construye utilizando la función de compresión. [ cita requerida ] (Tenga en cuenta que en algunos documentos se utiliza una terminología diferente: el acto de relleno de longitud se llama "finalización". [ cita requerida ] )
Características de seguridad
La popularidad de esta construcción se debe al hecho, probado por Merkle y Damgård , de que si la función de compresión unidireccional f es resistente a colisiones , también lo es la función hash construida con ella. Desafortunadamente, esta construcción también tiene varias propiedades indeseables:
- Los ataques de segunda preimagen contra mensajes largos son siempre mucho más eficientes que la fuerza bruta. [5]
- Las multicolisiones (muchos mensajes con el mismo hash) se pueden encontrar con solo un poco más de trabajo que las colisiones. [6]
- " Herding attack s", que combina la construcción en cascada para la detección de colisiones múltiples (similar a la anterior) con las colisiones encontradas para un prefijo dado (colisiones de prefijo elegido). Esto permite construir documentos de colisión altamente específicos, y se puede hacer para más trabajo que encontrar una colisión, pero mucho menos de lo que se esperaría para hacer esto para un oráculo aleatorio . [7] [8]
- Extensión de longitud : dado el hashde una entrada desconocida X , es fácil encontrar el valor de, donde pad es la función de relleno del hash. Es decir, es posible encontrar valores hash de entradas relacionadas con X aunque X siga siendo desconocido. [9] Los ataques de extensión de longitud se utilizaron en realidad para atacar una serie de esquemas comerciales de autenticación de mensajes web, como el utilizado por Flickr . [10]
Construcción de tubería ancha
Debido a varias debilidades estructurales de la construcción Merkle-Damgård, especialmente el problema de la extensión de longitud y los ataques de multicolisión, Stefan Lucks propuso el uso del hash de tubo ancho [11] en lugar de la construcción Merkle-Damgård. El hash de tubo ancho es muy similar a la construcción Merkle-Damgård pero tiene un tamaño de estado interno más grande, lo que significa que la longitud de bits que se usa internamente es mayor que la longitud de bits de salida. Si se desea un hash de n bits, la función de compresión f toma 2n bits de valor de encadenamiento y m bits del mensaje y los comprime a una salida de 2n bits.
Por lo tanto, en un paso final, una segunda función de compresión comprime el último valor hash interno ( 2n bit) al valor hash final ( n bit). Esto se puede hacer tan simplemente como descartar la mitad de la última salida de 2n bits. SHA-512/224 y SHA-512/256 toman esta forma ya que se derivan de una variante de SHA-512. SHA-384 y SHA-224 se derivan de manera similar de SHA-512 y SHA-256, respectivamente, pero el ancho de su tubería es mucho menor que 2n .
Construcción de tubería ancha rápida
Mridul Nandi y Souradyuti Paul han demostrado que la función hash de Widepipe se puede hacer aproximadamente dos veces más rápido si el estado de widepipe se puede dividir por la mitad de la siguiente manera: una mitad se ingresa a la función de compresión subsiguiente mientras que la otra mitad es combinado con la salida de esa función de compresión. [12]
La idea principal de la construcción hash es reenviar la mitad del valor de encadenamiento anterior a XOR a la salida de la función de compresión. Al hacerlo, la construcción toma bloques de mensajes más largos en cada iteración que el tubo ancho original. Usando la misma función f que antes, toma n valores de encadenamiento de bits y n + m bits del mensaje. Sin embargo, el precio a pagar es la memoria adicional que se utiliza en la construcción del feed-forward.
Acolchado compatible con MD
Como se mencionó en la introducción, el esquema de acolchado utilizado en la construcción Merkle-Damgård debe elegirse cuidadosamente para garantizar la seguridad del esquema. Mihir Bellare da las condiciones suficientes para que un esquema de acolchado posea para garantizar que la construcción de MD sea segura: basta con que el esquema sea "compatible con MD" (el esquema de acolchado de longitud original utilizado por Merkle es un ejemplo de acolchado compatible con MD) . [1] : 145 Condiciones:
- es un prefijo de
- Si luego
- Si luego el último bloque de es diferente del último bloque de
Con estas condiciones en su lugar, encontramos una colisión en la función hash MD exactamente cuando encontramos una colisión en la función de compresión subyacente. Por lo tanto, la construcción Merkle-Damgård es probadamente segura cuando la función de compresión subyacente es segura. [1] : 147
Ejemplo de relleno de longitud
Para poder enviar el mensaje a la función de compresión, el último bloque debe rellenarse con datos constantes (generalmente con ceros) a un bloque completo. Por ejemplo, suponga que el mensaje que se va a aplicar hash es "HashInput" (cadena de 9 octetos, 0x48617368496e707574 en ASCII ) y el tamaño de bloque de la función de compresión es de 8 bytes (64 bits). Obtenemos dos bloques (los octetos de relleno se muestran con un color de fondo azul claro):
- 48 61 73 68 49 6e 70 75, 74 00 00 00 00 00 00 00
Esto implica que otros mensajes que tengan el mismo contenido pero que terminen con ceros adicionales al final darán como resultado el mismo valor hash. En el ejemplo anterior, otro mensaje casi idéntico (0x48617368496e7075 74 00 ) generará el mismo valor hash que el mensaje original "HashInput" anterior. En otras palabras, cualquier mensaje que tenga ceros adicionales al final lo hace indistinguible del que no los tiene. Para evitar esta situación, el primer bit del primer octeto de relleno se cambia a "1" (0x80), dando como resultado:
- 48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00
Para hacerlo resistente contra el ataque de extensión de longitud , la longitud del mensaje se agrega en un bloque adicional al final (mostrado con color de fondo amarillo):
- 48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00 , 00 00 00 00 00 00 00 09
Sin embargo, las implementaciones más comunes usan un tamaño de bit fijo (generalmente 64 o 128 bits en los algoritmos modernos) en una posición fija al final del último bloque para insertar el valor de la longitud del mensaje (ver pseudocódigo SHA-1 ). Se pueden realizar mejoras adicionales insertando el valor de longitud en el último bloque si hay suficiente espacio. Al hacerlo, se evita tener un bloque adicional para la longitud del mensaje. Si asumimos que el valor de longitud está codificado en 5 bytes (40 bits), el mensaje se convierte en:
- 48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 09
Tenga en cuenta que almacenar la longitud del mensaje fuera de banda en los metadatos, o incrustada de otro modo al comienzo del mensaje, es una mitigación eficaz del ataque de extensión de longitud [ cita requerida ] , siempre que la invalidación de la longitud del mensaje y la suma de comprobación sean ambas considerado fallo de comprobación de integridad.
Referencias
- Manual de criptografía aplicada de Menezes, van Oorschot y Vanstone (2001), capítulo 9.
- Introducción a la criptografía moderna , por Jonathan Katz y Yehuda Lindell. Chapman y Hall / CRC Press, agosto de 2007, página 134 (construcción 4.13).
- Criptografía simplificada por Nigel Smart (2015), capítulo 14.
- ^ a b c d Goldwasser, S. y Bellare, M. "Notas de la conferencia sobre criptografía" . Curso de verano sobre criptografía, MIT, 1996-2001
- ^ RC Merkle . Sistemas de secreto, autenticación y clave pública. Stanford Ph.D. tesis 1979, páginas 13-15.
- ^ RC Merkle . Una firma digital certificada . En Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed. Springer-Verlag, 1989, págs. 218-238.
- ^ I. Damgård . Un principio de diseño para funciones hash . En Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed. Springer-Verlag, 1989, págs. 416-427.
- ^ Kelsey, John; Schneier, Bruce (2004). "Segundas preimágenes en funciones hash de n-bit para mucho menos de 2 ^ n trabajos" (PDF) , a través de Cryptology ePrint Archive: Informe 2004/304. Cite journal requiere
|journal=
( ayuda ) - ^ Antoine Joux. Multicolisiones en funciones hash iteradas. Aplicación a la construcción en cascada. In Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, vol. 3152, M. Franklin, ed. Springer-Verlag, 2004, págs. 306–316.
- ^ John Kelsey y Tadayoshi Kohno. Herding Hash Functions and the Nostradamus Attack en Eurocrypt 2006, Lecture Notes in Computer Science, vol. 4004, págs. 183–200.
- ^ Stevens, Marc; Lenstra, Arjen ; de Weger, Benne (30 de noviembre de 2007). "Nostradamus" . El proyecto HashClash . TU / e . Consultado el 30 de marzo de 2013 .
- ^ Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton. Salvamento de Merkle – Damgård para aplicaciones prácticas . Versión preliminar en Advances in Cryptology - Actas de EUROCRYPT '09, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed. Springer-Verlag, 2009, págs. 371–388.
- ^ Thai Duong, Juliano Rizzo, Vulnerabilidad de falsificación de firmas de API de Flickr , 2009
- ^ Suertes, Stefan (2004). "Principios de diseño para funciones hash iteradas" , a través de Cryptology ePrint Archive, Informe 2004/253. Cite journal requiere
|journal=
( ayuda ) - ^ Mridul Nandi y Souradyuti Paul. Aceleración del Widepipe: hash rápido y seguro. En Guang Gong y Kishan Gupta, editor, Indocrypt 2010, Springer, 2010.