Herramientas de desarrollo · Calculadora de hash SHA
Merkle–Damgård explicado: La construcción detrás de SHA-1 y SHA-2
· Antecedentes
sha-256 criptografía APIS del navegador
Una función de compresión de tamaño fijo no puede aplicar hash a una entrada arbitraria por sí sola. Merkle-Damgård lo encadena bloque a bloque; Este post explica la construcción, su idea de prueba y las debilidades que conlleva.
Entrada arbitraria, salida fija: el problema que toda función hash debe resolver primero
Una función hash debe asignar una entrada arbitraria a una salida fija. Un mensaje de tres bytes y un mensaje de tres megabytes deben producir exactamente 256 bits de salida para SHA-256. El hash debe ser determinista, por lo que la misma entrada siempre produce la misma salida. La salida debe parecer aleatoria; cambiar un solo bit de la entrada debería cambiar aproximadamente la mitad de los bits de salida.
Estos son requisitos contradictorios a primera vista, porque un único algoritmo rápido no puede manejar mensajes de longitud arbitraria y producir una salida uniforme de ancho fijo. La construcción Merkle-Damgård resuelve esto utilizando una función de compresión de tamaño fijo repetidamente, alimentando la salida de cada aplicación a la entrada de la siguiente. Esta construcción la utilizan SHA-1 y todos SHA-2 (SHA-256, SHA-384 y SHA-512).
La función de compresión: un mezclador de tamaño fijo que toma un estado y un bloque y devuelve un nuevo estado
Una función de compresión es la primitiva criptográfica central que impulsa un hash Merkle-Damgård. Se necesita un estado de tamaño fijo, generalmente 256 bits para SHA-256 o 512 bits para SHA-512, y un bloque de entrada de tamaño fijo, generalmente 512 bits para SHA-256 o 1024 bits para SHA-512. La función de compresión los mezcla mediante operaciones bit a bit, rotaciones y búsquedas de tablas, produciendo un nuevo estado del mismo tamaño. Esta función debe ser resistente a colisiones: encontrar dos pares diferentes (estado, bloque) que produzcan la misma salida debe ser difícil.
La función de compresión en sí no es una función hash completa: no maneja longitudes de entrada arbitrarias y ni siquiera maneja la primera entrada, que no tiene un estado previo. Más bien, es el bloque de construcción alrededor del cual se construye una construcción más grande. La función de compresión es la única operación criptográfica que se ejecuta repetidamente; todo lo demás es contabilidad que conecta esta función con un hash completo.
Encadenamiento y vector de inicialización: cómo los bloques se alimentan entre sí desde un estado inicial fijo
El vector de inicialización es el estado inicial fijo, elegido cuidadosamente para evitar simetrías o debilidades. Para SHA-256, el IV son ocho palabras de 32 bits derivadas de las partes fraccionarias de las raíces cuadradas de los primeros ocho números primos. Estos valores son arbitrarios pero deterministas, por lo que cada implementación produce el mismo resultado. El primer bloque de mensaje se mezcla con el IV usando la función de compresión, produciendo un nuevo estado. El segundo bloque de mensaje se mezcla con ese estado, lo que produce otro estado nuevo, y así sucesivamente a lo largo de cada bloque del mensaje.
Este encadenamiento es la parte crucial: la salida de un bloque depende de todos los bloques anteriores, por lo que cambiar cualquier bit de cualquier bloque anterior cambia todos los bloques posteriores. Cuando se procesa el bloque final, el estado contiene información sobre cada bit de la entrada. El relleno es el truco que hace que esta construcción suene. Un mensaje no siempre se divide uniformemente en bloques. La construcción Merkle-Damgård utiliza fortalecimiento MD: agregue un solo bit al mensaje, luego agregue ceros hasta que quede casi un bloque completo, luego agregue la longitud original del mensaje.
Relleno con la longitud del mensaje: por qué el fortalecimiento MD es lo que hace que la construcción sea sólida
El argumento de seguridad de Merkle-Damgård dice que si la función de compresión es resistente a colisiones, entonces todo el hash es resistente a colisiones. La prueba es una reducción: si pudiera encontrar una colisión en el hash, podría extraer una colisión en la función de compresión, lo que contradice la suposición de que la función de compresión es difícil de colisionar. La intuición es que cualquier colisión en el hash debe eventualmente producir una colisión en una de las llamadas a la función de compresión, porque el estado se transmite por completo.
Las debilidades en Merkle-Damgård se descubrieron con el tiempo, a pesar de que la construcción básica es sólida. La extensión de longitud es una: un atacante que ve el resumen de un mensaje puede extender el mensaje y calcular un resumen válido para el mensaje más largo sin saber nada sobre la entrada. Los segundos ataques de preimagen son otro: dado un mensaje, encontrar un mensaje diferente con el mismo hash es más fácil de lo que debería ser para algunos tipos de mensajes. Estas debilidades motivaron el diseño de SHA-3, que utiliza un enfoque diferente llamado construcción de esponja.
El relleno de codificación de longitud separa los mensajes rellenados; una prueba de seguridad completa está fuera del repositorio de evidencia
La función de compresión para SHA-256 toma un estado de 256 bits (ocho palabras de 32 bits) y un bloque de 512 bits. La operación utiliza 64 rondas, cada una mezclando el estado con una constante y una palabra del bloque. La mezcla utiliza operaciones bit a bit: XOR, AND, NOT. Utiliza rotaciones y cambios que mueven bits sin cambiar qué bits están configurados. Utiliza búsquedas en tablas que proporcionan una mezcla no lineal que XOR por sí solo no puede lograr.
SHA-512 usa la misma construcción que SHA-256 pero con operaciones de 64 bits en lugar de operaciones de 32 bits. El estado es 512 bits (ocho palabras de 64 bits) y el tamaño del bloque es 1024 bits. La función de compresión tiene 80 rondas en lugar de 64, y las constantes y las búsquedas de tablas son diferentes. Para SHA-384, el estado y la función de compresión son los mismos que SHA-512, pero solo se generan los primeros 384 bits del estado final. Se descartan los últimos 128 bits. Este truncamiento es la razón por la que SHA-384 es resistente a la extensión de longitud.
La extensión de longitud es el límite de construcción verificado; Se omiten las afirmaciones de multicolisión y SHA-3 motivación.
La seguridad de un hash Merkle-Damgård depende de varias propiedades. La función de compresión debe ser resistente a colisiones, por lo que atacarla directamente es inviable. El esquema de relleno debe garantizar que diferentes mensajes produzcan diferentes formas de relleno, por lo que cada colisión en el hash debe implicar una colisión de función de compresión. El tamaño del bloque y el tamaño del estado deben ser lo suficientemente grandes como para que la fuerza bruta sea inviable. Un estado más amplio amplía el espacio de búsqueda genérica, pero este artículo no adjunta un recuento de operaciones o una fecha de viabilidad sin una derivación en línea y una fuente revisada.
Si un atacante encuentra una debilidad en la función de compresión, o si las computadoras cuánticas se vuelven prácticas y pueden buscar un espacio no estructurado en tiempo sqrt(2^n) en lugar de 2^n, entonces los márgenes de seguridad se erosionan. La debilidad que motivó a SHA-3 no fue una ruptura en la función de compresión, sino el problema de la extensión de longitud y otras vulnerabilidades estructurales. Una construcción de esponja los evita al no revelar nunca su estado interno completo.
Lo que esto no cubre: las funciones de ronda específicas de SHA-256, cubiertas en una publicación separada
La forma en que la construcción Merkle-Damgård maneja cada tamaño de entrada es la consecuencia práctica de su diseño. Divida el mensaje en bloques de 512 bits, rellene el último bloque, procese cada bloque a través de la función de compresión en secuencia y genere el estado final. Para una entrada de un byte, el relleno produce un bloque de 512 bits (un byte de mensaje, un bit de relleno, 447 bits de ceros y 64 bits para la longitud). El número de compresiones es el número de bloques de 512 bits, que es proporcional a la longitud del mensaje.
Cada resumen que produce la calculadora de hash ToolAcre SHA proviene de esta construcción. El resumen de 64 caracteres SHA-256 es el estado final de 256 bits impreso en hexadecimal. El resumen de 128 caracteres SHA-512 es el estado final de 512 bits impreso en hexadecimal. El resumen de 96 caracteres SHA-384 son los primeros 384 bits del estado final de 512 bits. El relleno detrás de escena garantiza que cada mensaje posible produzca exactamente la cantidad correcta de bloques y el ancho de resumen correcto. Esta es la construcción estándar de Merkle-Damgård que se ejecuta en el navegador.
Conclusión: el mismo esqueleto detrás de cuatro algoritmos: cada resumen que produce la calculadora de hash SHA ToolAcre proviene de esta construcción
Comprender la construcción es útil para saber por qué los resúmenes tienen siempre el mismo ancho y por qué cambiar un bit de la entrada cambia todo el resumen. La propiedad de encadenamiento significa que cada bit de la entrada afecta a cada bit de la salida a través de una serie de operaciones de mezcla. Un cambio de un bit al principio del mensaje se propagará a través de todas las compresiones posteriores, por lo que el resumen final es completamente diferente. Esta propiedad se llama efecto de avalancha y es una firma de una función hash de sonido.
La construcción Merkle-Damgård se ha utilizado durante décadas y constituye la base de las funciones hash más utilizadas. SHA-1 y SHA-2 se basan en esta construcción y muchos sistemas implementados dependen de sus resultados. La construcción es más establecida que experimental, pero esa historia no hace que todos los usos sean seguros; la extensión de longitud es un límite documentado. Comprender esta construcción ayuda a los desarrolladores a comprender por qué se mantienen ciertas propiedades de seguridad y por qué existen ciertos vectores de ataque.