En criptografía , la construcción de Merkle–Damgård o función hash de Merkle–Damgård es un método para construir funciones hash criptográficas resistentes a colisiones a partir de funciones de compresión unidireccional 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 de Merkle-Damgård fue descrita en la tesis doctoral de Ralph Merkle en 1979. [2] Ralph Merkle e Ivan Damgård demostraron de forma independiente que la estructura es sólida: es decir, si se utiliza un esquema de relleno apropiado y la función de compresión es resistente a colisiones , entonces la función hash también será resistente a colisiones. [3] [4]
La función hash de 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. Luego, la función hash divide el resultado en bloques de tamaño fijo y los procesa uno a la vez con la función de compresión, combinando cada vez 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. Esto se llama relleno de longitud o fortalecimiento de 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 (específico del algoritmo o de la implementación). Para cada bloque de mensaje, la función de compresión (o compactación) f toma el resultado hasta el momento, 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. (Vea a continuación un ejemplo detallado de relleno de longitud).
Para endurecer aún más el hash, el último resultado se pasa a veces por 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 un efecto de avalancha en los bits de la suma del hash. La función de finalización se construye a menudo 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 rellenar la longitud se denomina "finalización". [ cita requerida ] )
La popularidad de esta construcción se debe al hecho, demostrado por Merkle y Damgård , de que si la función de compresión unidireccional f es resistente a colisiones , entonces también lo es la función hash construida con ella. Desafortunadamente, esta construcción también tiene varias propiedades indeseables:
Debido a varias debilidades estructurales de la construcción Merkle–Damgård, especialmente el problema de extensión de longitud y los ataques de colisión múltiple, Stefan Lucks propuso el uso del hash de tubería ancha [11] en lugar de la construcción Merkle–Damgård. El hash de tubería ancha es muy similar a la construcción Merkle–Damgård pero tiene un tamaño de estado interno mayor, lo que significa que la longitud de bits que se utiliza internamente es mayor que la longitud de bits de salida. Si se desea un hash de n bits, entonces la función de compresión f toma 2 n bits del valor de encadenamiento y m bits del mensaje y los comprime a una salida de 2 n bits.
Por lo tanto, en un paso final, una segunda función de compresión comprime el último valor hash interno ( 2 n bits) al valor hash final ( n bits). Esto se puede hacer tan simplemente como descartar la mitad de la última salida de 2 n 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 2 n .
Mridul Nandi y Souradyuti Paul han demostrado que una función hash de tubería ancha se puede hacer aproximadamente dos veces más rápida si el estado de la tubería ancha se puede dividir por la mitad de la siguiente manera: una mitad se ingresa en la función de compresión siguiente mientras que la otra mitad se combina con la salida de esa función de compresión. [12]
La idea principal de la construcción del hash es reenviar la mitad del valor de encadenamiento anterior para aplicarle una operación XOR en la salida de la función de compresión. De este modo, la construcción incluye bloques de mensajes más largos en cada iteración que el ancho original de la tubería. Al utilizar la misma función f que antes, se utilizan valores de encadenamiento de n bits y n + m bits del mensaje. Sin embargo, el precio a pagar es la memoria adicional que se utiliza en la construcción para la realimentación.
La construcción MD es inherentemente secuencial. Existe un algoritmo paralelo [13] que construye una función hash resistente a colisiones a partir de una función de compresión resistente a colisiones. La función hash PARSHA-256 [14] se diseñó utilizando el algoritmo paralelo y la función de compresión de SHA-256.
Como se mencionó en la introducción, el esquema de relleno utilizado en la construcción Merkle–Damgård debe elegirse con cuidado para garantizar la seguridad del esquema. Mihir Bellare proporciona condiciones suficientes que debe cumplir un esquema de relleno para garantizar que la construcción MD sea segura: basta con que el esquema sea "compatible con MD" (el esquema de relleno de longitud original utilizado por Merkle es un ejemplo de relleno compatible con MD). [1] : 145 Las condiciones son:
Aquí, | X | denota la longitud de X . Con estas condiciones establecidas, existe una colisión en la función hash MD exactamente cuando hay una colisión en la función de compresión subyacente. Por lo tanto, la construcción de Merkle–Damgård es demostrablemente segura cuando la función de compresión subyacente es segura. [1] : 147
Para poder enviar el mensaje a la función de compresión, el último bloque debe rellenarse con datos constantes (generalmente con ceros) hasta completar el bloque. Por ejemplo, supongamos que el mensaje que se va a codificar es "HashInput" (cadena de 9 octetos, 0x48617368496e707574 en ASCII ) y el tamaño del bloque de la función de compresión es de 8 bytes (64 bits). Obtenemos dos bloques (los octetos de relleno se muestran con el color de fondo azul claro):
Esto implica que otros mensajes que tengan el mismo contenido pero que terminen con ceros adicionales al final generarán 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), lo que genera:
Sin embargo, las implementaciones más comunes utilizan un tamaño de bit fijo (generalmente 64 o 128 bits en algoritmos modernos) en una posición fija al final del último bloque para insertar el valor de longitud del mensaje (consulte el 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:
Almacenar la longitud del mensaje fuera de banda en los metadatos, o de otra manera incrustado al comienzo del mensaje, es una mitigación efectiva del ataque de extensión de longitud [ cita requerida ] , siempre que la invalidación de la longitud del mensaje y la suma de verificación se consideren una falla en la verificación de integridad.
{{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda )