security - huella - ¿Cuándo es seguro usar una función hash rota?

huella hash (6)

Es trivial utilizar una función hash segura como SHA-256, y continuar utilizando MD5 para la seguridad es un comportamiento imprudente. Sin embargo, hay algunas complejidades para las vulnerabilidades de la función hash que me gustaría entender mejor.

Se generaron colisiones para MD4 y MD5 . Según NIST, MD5 no es una función de hash segura. Solo se necesitan 2 ³⁹ operaciones para generar una colisión y nunca se debe usar para contraseñas . Sin embargo, SHA-1 es vulnerable a un ataque de colisión similar en el que se puede encontrar una colisión en 2 ⁶⁹ operaciones, mientras que la fuerza bruta es 2 ⁸⁰ . Nadie ha generado una colisión SHA-1 y el NIST todavía enumera SHA-1 como una función segura de resumen de mensajes .

Entonces, ¿cuándo es seguro usar una función hash rota? Aunque una función está rota, aún puede ser "lo suficientemente grande". De acuerdo con Schneier, una función hash vulnerable a un ataque de colisión aún se puede usar como un HMAC . Creo que esto se debe a que la seguridad de un HMAC depende de su clave secreta y no se puede encontrar una colisión hasta que se obtenga esta clave. Una vez que tiene la clave utilizada en un HMAC, ya está rota, por lo que es un punto discutible. ¿Qué vulnerabilidades de la función hash afectarían la seguridad de un HMAC?

Llevemos esta propiedad un poco más allá. ¿Se vuelve seguro usar un resumen de mensaje muy débil como MD4 para las contraseñas si se agrega una sal a la contraseña? Tenga en cuenta que los ataques MD4 y MD5 son ataques de prefijación, y si se agrega una sal, el atacante no puede controlar el prefijo del mensaje. Si la sal es realmente un secreto, y el atacante no la conoce, ¿importa si se adjunta a la contraseña? ¿Es seguro asumir que un atacante no puede generar una colisión hasta que se haya obtenido todo el mensaje?

¿Conoces otros casos en los que se puede utilizar una función hash rota en un contexto de seguridad sin introducir una vulnerabilidad?

(¡Por favor, publique evidencia de apoyo porque es increíble!)

Cuando no te importa si es seguro o no.

En serio, no requiere ningún esfuerzo adicional utilizar una función hash segura en casi todos los idiomas, y el impacto en el rendimiento es insignificante, por lo que no veo por qué no lo harías.

[Editar después de leer su pregunta]

Según Schneier, una función hash vulnerable a un ataque de colisión aún se puede usar como un HMAC. Creo que esto se debe a que la seguridad de un HMAC depende de su clave secreta y no se puede encontrar una colisión hasta que se obtenga esta clave.

En realidad, es esencialmente porque poder generar una colisión para un hash no necesariamente lo ayuda a generar una colisión para el hash-de-a-hash (combinado con el XORing utilizado por los HMAC).

¿Se vuelve seguro usar un resumen de mensaje muy débil como md4 para las contraseñas si se agrega una sal a la contraseña?

No, no si el hash tiene un ataque de preimagen que le permite anteponer los datos a la entrada. Por ejemplo, si el hash era H(pass + salt) , necesitaríamos un ataque de preimagen que nos permita encontrar el paso 2 tal que H(pass2 + salt) = H(pass + salt) .

Ha habido ataques de anexión en el pasado, por lo que estoy seguro de que los ataques anteriores son posibles.

La única vez que es seguro usar una función hash rota es cuando las consecuencias de una colisión son inofensivas o triviales, por ejemplo, al asignar archivos a un cubo en un sistema de archivos.

La mayoría de los que se preocupan por usar una contraseña como MD4 se relaciona menos con los ataques actualmente conocidos que con el hecho de que una vez que se ha analizado hasta el punto de que la generación de colisiones es fácil, generalmente se presume que es mucho más probable que alguien podrá usar ese conocimiento para crear un ataque de preimagen, y cuando eso ocurra, esencialmente todos los usos posibles de esa función de hash serán vulnerables.

La respuesta depende completamente de para qué la uses. Si necesita evitar que alguien produzca una colisión con unos pocos milisegundos, estaría menos preocupado que si necesitara evitar que alguien produzca una colisión en unas pocas décadas.

¿Qué problema estás tratando de resolver?

Los sitios de descarga utilizan el hash MD5 como una suma de comprobación para determinar si el archivo se dañó durante la descarga, y yo diría que un hash roto es lo suficientemente bueno para ese propósito.

Digamos que un MITM decide modificar el archivo (digamos un archivo zip, o un exe). Ahora, el atacante tiene que hacer dos cosas:

Encuentra una colisión hash y crea un archivo modificado a partir de ella
Asegúrese de que el archivo recién creado sea también un archivo ejecutable o un archivo zip válido

Con un hash roto, 1 es un poco más fácil. Pero garantizar que la colisión se una simultáneamente con otras propiedades conocidas del archivo es demasiado costoso desde el punto de vista computacional.

Esta es totalmente mi propia respuesta, y podría estar terriblemente equivocado.

En realidad, las colisiones son más fáciles de lo que enumeras tanto en MD5 como en SHA-1. Las colisiones MD5 se pueden encontrar en el tiempo equivalente a la operación 2 ^26.5 (donde una "operación" es el cálculo de MD5 sobre un mensaje corto). Consulte esta página para obtener más detalles y una implementación del ataque (escribí ese código, encuentra una colisión dentro de un promedio de 14 segundos en un Core2 x86 de 2.4 GHz en modo de 64 bits).

Del mismo modo, el ataque más conocido contra SHA-1 está en alrededor de 2 ⁶¹ operaciones, no en 2 ⁶⁹ . Todavía es teórico (todavía no se produjo una colisión real), pero está dentro del ámbito de lo factible.

En cuanto a las implicaciones para la seguridad: generalmente se dice que las funciones hash tienen tres propiedades:

Sin preimagen: dado y , no debería ser posible encontrar x tal que h (x) = y .
No hay una segunda preimagen: dado x ₁ , no debería ser posible encontrar x ₂ (distinto de x ₁ ) tal que h (x ₁ ) = h (x ₂ ) .
Sin colisión: no debería ser posible encontrar x ₁ y x ₂ (distintos entre sí) de forma que h (x ₁ ) = h (x ₂ ) .

Para una función hash con salida n- bit, hay ataques genéricos (que funcionan independientemente de los detalles de la función hash) en 2 ⁿ operaciones para las dos primeras propiedades, y 2 ^{n / 2} operaciones para la tercera. Si, para una función hash dada, se encuentra un ataque que, al explotar detalles especiales de cómo funciona la función hash, encuentra una preimagen, una segunda preimagen o una colisión más rápida que el ataque genérico correspondiente, entonces se dice que la función hash estar quebrado".

Sin embargo, no todos los usos de las funciones hash se basan en las tres propiedades. Por ejemplo, las firmas digitales comienzan con el hash de los datos que se deben firmar, y luego el valor hash se usa en el resto del algoritmo. Esto se basa en la resistencia a las preimágenes y las segundas imágenes previas, pero las firmas digitales no se ven afectadas per se por las colisiones. Las colisiones pueden ser un problema en algunos escenarios de firmas específicos, donde el atacante puede elegir los datos que debe firmar la víctima (básicamente, el atacante calcula una colisión, tiene un mensaje firmado por la víctima y la firma se vuelve válida para el otro mensaje también). Esto puede contrarrestarse anteponiendo algunos bytes aleatorios al mensaje firmado antes de calcular la firma (el ataque y la solución se demuestran en el contexto de los certificados X.509).

La seguridad HMAC depende de otra propiedad que la función hash debe cumplir; a saber, que la "función de compresión" (el ladrillo elemental sobre el cual se construye la función hash) actúa como una Función Pseudoaleatoria (PRF). Los detalles sobre lo que es un PRF son bastante técnicos, pero, hablando en términos generales, un PRF debe ser indistinguible de un Oracle aleatorio . Un oráculo al azar se modela como una caja negra que contiene un gnomo, algunos dados y un gran libro. En algunos datos de entrada, el gnomo selecciona una salida aleatoria (con los dados) y anota en el libro el mensaje de entrada y la salida que fue seleccionada al azar. El gnomo usa el libro para verificar si ya vio el mismo mensaje de entrada: si es así, entonces el gnomo devuelve el mismo resultado que antes. Por construcción, no puede saber nada sobre el resultado de un oráculo al azar en un mensaje dado hasta que lo pruebe.

El modelo de oráculo aleatorio permite cuantificar la prueba de seguridad HMAC en invocaciones del PRF. Básicamente, la prueba indica que HMAC no se puede romper sin invocar el PRF una gran cantidad de veces, y por "enorme" me refiero a computacionalmente inviable.

Desafortunadamente, no tenemos oráculos aleatorios, por lo que en la práctica debemos usar funciones hash. No hay ninguna prueba de que las funciones hash realmente existan, con la propiedad PRF; en este momento, solo tenemos candidatos, es decir, funciones para las cuales no podemos probar (todavía) que sus funciones de compresión no sean PRF.

Si la función de compresión es una PRF , la función hash es automáticamente resistente a las colisiones. Eso es parte de la magia de PRF. Por lo tanto , si podemos encontrar colisiones para una función hash, entonces sabemos que la función de compresión interna no es una PRF. Esto no convierte las colisiones en un ataque contra HMAC. Poder generar colisiones a voluntad no ayuda a romper HMAC. Sin embargo, esas colisiones demuestran que la prueba de seguridad asociada con HMAC no se aplica. La garantía es nula. Eso es lo mismo que una computadora portátil: abrir la carcasa no necesariamente rompe la máquina, pero después usted está solo.

En el artículo de Kim-Biryukov-Preneel-Hong , se presentan algunos ataques contra HMAC, en particular un ataque de falsificación en HMAC-MD4. El ataque explota las deficiencias de MD4 (sus "debilidades") que lo convierten en un no-PRF. Se usaron variantes de las mismas debilidades para generar colisiones en MD4 (MD4 está completamente roto, ¡algunos ataques generan colisiones más rápido que el cálculo de la función hash en sí!). Entonces las colisiones no implican el ataque HMAC, pero ambos ataques se alimentan de la misma fuente. Sin embargo, tenga en cuenta que el ataque de falsificación ha costado 2 ⁵⁸ , que es bastante alto (no se produjo falsificación real, el resultado sigue siendo teórico) pero sustancialmente menor que el nivel de resistencia esperado de HMAC (con una función hash robusta con n - bit de salida, HMAC debe resistir hasta 2 ⁿ factor de trabajo, n = 128 para MD4).

Entonces, aunque las colisiones no implican debilidades en HMAC, son malas noticias. En la práctica, las colisiones son un problema para muy pocas configuraciones. Pero saber si las colisiones afectan un uso dado de las funciones hash es lo suficientemente complicado, que es bastante imprudente seguir usando una función hash para la cual se demostraron las colisiones.

Para SHA-1, el ataque sigue siendo teórico, y SHA-1 está ampliamente desplegado. La situación se ha descrito así: "La alarma está encendida, pero no hay fuego visible ni humo. Es hora de caminar hacia las salidas, pero no de correr".

Para obtener más información sobre el tema, comience por leer el capítulo 9 del Manual de criptografía aplicada , de Menezes, van Oorschot y Vanstone, una lectura obligada para el aprendiz de criptógrafo (que no debe confundirse con "Applied Cryptography" de B. Schneier , que es una introducción bien escrita pero en ninguna parte tan completa como el "Manual").