¿Cuándo es seguro de usar una función hash roto?

Question

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

Las colisiones han sido generado para MD4 y MD5 . De acuerdo con el NIST, MD5 no es una función hash seguro. Sólo se necesita 2 ^{39 operaciones} para generar una colisión y nunca debe ser utilizado para las contraseñas . Sin embargo SHA-1 es vulnerable a un similares ataque de colisión en la que una colisión puede encontrar en 2 ⁶⁹ operaciones, mientras que la fuerza bruta es 2 ⁸⁰ . Nadie ha generado una colisión SHA-1 y NIST todavía enumera SHA-1 como una mensaje seguro a digerir la función .

Así que cuando es seguro usar una función hash roto? A pesar de que una función se ha roto todavía puede ser "suficientemente grande". Según Schneier una función hash vulnerable a un ataque de colisión lata todavía ser utilizado como un HMAC . Creo que esto se debe a que la seguridad de un HMAC depende de su clave secreta y una colisión no se puede encontrar hasta obtener esta clave. Una vez que tenga la clave utilizada en un HMAC que ya está roto, por lo que es un punto discutible. Lo vulnerabilidades función hash comprometa la seguridad de un HMAC?

Vamos a tomar esta propiedad un poco más lejos. ¿Se luego se convierten en seguro de usar un mensaje muy débil digerir como MD4 para las contraseñas si una sal se antepone a la contraseña? Tenga en cuenta los ataques MD4 y MD5 están anteponiendo los ataques, y si se antepone una sal entonces un atacante no puede controlar el prefijo del mensaje. Si la sal es realmente un secreto, y no se sabe que el atacante, entonces qué importa si se añade a la contraseña? Es seguro asumir que un atacante no puede generar una colisión hasta que se haya obtenido todo el mensaje?

¿Conoce otros casos en los que una función hash roto puede ser utilizado en un contexto de seguridad sin introducir una vulnerabilidad?

(Por favor enviar evidencia de apoyo, ya que es impresionante!)

Answer 1

En realidad, las colisiones son más fáciles de lo que usted indicó en tanto MD5 y SHA-1. colisiones MD5 se pueden encontrar en el tiempo equivalente a 2 ^26,5 operación (donde una "operación" es el cálculo de MD5 en un mensaje corto). Ver esta página para algunos detalles y una implementación del ataque (escribí ese código, sino que encuentra una colisión dentro de un promedio de 14 segundos en un 2,4 GHz Core 2 x 86 en el modo de 64 bits)

.

Del mismo modo, la mejor ataque conocido en SHA-1 es en aproximadamente 2 ⁶¹ operaciones, no 2 ⁶⁹ . Todavía es teórica (sin colisión real se produjo aún), pero está dentro del ámbito de lo posible.

En cuanto a las implicaciones en la seguridad: funciones hash se suele decir que tiene tres propiedades:

• No hay imagen inversa: dada y , no debería ser factible encontrar x tal que h (x) = y
• No hay una segunda imagen inversa: dada x ₁ , que no debería ser factible encontrar x ₂ (distinto de x ₁ ) tal que h (x ₁ ) = h (x ₂ ) .
• No hay colisión: no debería ser factible encontrar ninguna x ₁ y x ₂ (distinto de entre sí) de tal manera que h (x ₁ ) = h (x ₂ ) .

Para una función hash con un n salida de bits, 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 el tercero. Si, por una función hash dado, se encontró un ataque, el cual, mediante la explotación de los detalles especiales de cómo opera la función hash, encuentra una imagen inversa, una segunda imagen inversa o una colisión más rápido que el ataque genérico correspondiente, entonces la función hash se dice que ser "roto".

Sin embargo, no todos los usos de las funciones hash se basan en las tres propiedades. Por ejemplo, las firmas digitales comienzan por hash de los datos, que se va a firmar, y luego el valor hash se utiliza en el resto del algoritmo. Esto se basa en la resistencia a preimages y segundo preimages, pero las firmas digitales no son, per se, impactado por las colisiones. Las colisiones pueden ser un problema en algunos escenarios específicos de la firma, donde el atacante tiene que elegir los datos que debe ser firmado por la víctima (básicamente, el atacante calcula una colisión, tiene un mensaje firmado por la víctima, y ??la firma se convierte en válida para el otro mensaje también). Esto puede ser contrarrestado por anteponiendo algunos bytes aleatorios en el mensaje firmado antes de computar la firma (el ataque y la solución en la que se demuestra en el contexto de los certificados X.509).

La seguridad de HMAC se basa en un otro propiedad de que la función hash debe cumplir; a saber, que la "función de compresión" (el ladrillo elemental sobre la que se construye la función hash) actúa como una función Pseudo-Random (PRF). Los detalles de lo que una PRF es son bastante técnica, pero, en términos generales, una PRF debería ser indistinguible de un Al azar Oracle . Un oráculo aleatorio se modela como un cuadro negro que contiene un gnomo, algunos dados y un libro grande. En algunos datos de entrada, el gnomo seleccionar una salida al azar (con los dados) y escribe en el libro el mensaje de entrada y la salida que fue seleccionado al azar. El GNOME usa el libro para comprobar si ya se vio el mismo mensaje de entrada: si es así, entonces el gnomo devuelve el mismo resultado que antes. Por construcción, se puede saber nada acerca de la salida de un oráculo aleatorio en un mensaje dado hasta que probarlo.

El modelo del oráculo aleatorio permite la prueba de seguridad de HMAC a ser cuantificada en invocaciones de la PRF. Básicamente, los estados de prueba que HMAC no puede romperse sin invocar la PRF un gran número de veces, y por "enorme" Me refiero a computacionalmente infeasible.

Por desgracia, no tenemos oráculos aleatorios, por lo que en la práctica hay que utilizar las funciones de hash. No hay ninguna prueba de que existen realmente las funciones de hash, con la propiedad de PRF; en este momento, sólo tenemos candidatos, es decir, las funciones para las que no podemos probar (todavía) que sus funciones de compresión no son PRF.

la función de compresión es una PRF después la función hash es resistente a colisiones automáticamente. Eso es parte de la magia de la PRF. Por lo tanto , si podemos encontrar colisiones de una función hash, entonces sabemos que la función de compresión interna no es una PRF. Esto no se enciende las colisiones en un ataque contra HMAC. Ser capaz de 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 un ordenador portátil:. Abrir la caja no necesariamente romper la máquina, pero después usted está en su propia

En el artículo de la Kim-Biryukov-Preneel-Hong , algunos ataques contra HMAC son presenta, en particular, un ataque de falsificación de HMAC-MD4. El ataque explota las deficiencias de MD4 (sus "debilidades") que lo convierten en un no-PRF. Las variantes de las mismas debilidades se utilizaron para generar colisiones en MD4 (MD4 se rompe a fondo; algunos ataques generan las colisiones más rápido que el cómputo de la misma función hash!). Por lo que las colisiones no implican el ataque HMAC, pero ambos ataques se alimentan de la misma fuente. Nota, sin embargo, que el ataque falsificación tiene costo 2 ⁵⁸ , que es bastante alto (sin falsificación real fue producida, el resultado es todavía teórico) pero sustancialmente inferior a la resistencia el nivel esperado de HMAC (con una función hash robusto con un n salida de bits, HMAC debe resistir hasta 2 ⁿ factor de trabajo; n = 128 para MD4).

Así, mientras que las colisiones no lo hacen por sí implican debilidades en HMAC, son malas noticias. En la práctica, las colisiones son un problema para muy pocas configuraciones. Pero saber si los choques de impacto de un uso determinado de funciones hash es bastante complicado, que es muy poco aconsejable seguir utilizando una función hash para los que se demostraron las colisiones.

Para SHA-1, el ataque es todavía teórico, y SHA-1 es ampliamente desplegado. La situación ha sido descrita así: ". La alarma está encendida, pero no hay fuego o humo visible Es tiempo de caminar hacia las salidas - pero no para correr"

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

Answer 2

El único momento en que es seguro de usar una función hash roto es cuando las consecuencias de una colisión son inofensivos o trivial, por ejemplo, en la asignación de archivos a un cubo en un sistema de archivos.

Answer 3

Cuando no le importa si es seguro o no.

En serio, no se necesita ningún esfuerzo adicional para utilizar una función hash seguro en casi todos los idiomas, y de impacto en el rendimiento es insignificante, por lo que no veo por qué no lo haría.

[Edición después de leer realmente su pregunta]

De acuerdo con Schneier una función hash vulnerable a un ataque collsion todavía se puede utilizar como un HMAC. Creo que esto se debe a que la seguridad de un HMAC depende de su clave secreta y una colisión no se puede encontrar hasta obtener esta clave.

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

¿Se luego se convierten en seguro de usar un mensaje muy débil digerir como md4 de contraseñas si una sal se perpended a la contraseña?

No, no si el hash tiene un imagen inversa ataque que le permite estar precedidos de datos a la entrada. Por ejemplo, si el hash era H(pass + salt), necesitaríamos un ataque imagen inversa, que nos permite encontrar PASS2 tal que H(pass2 + salt) = H(pass + salt).

Ha habido ataques de agregación en el pasado, así que estoy seguro que son posibles ataques de anexo.

Answer 4

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

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

1. Encuentra una colisión de hash y crear un archivo modificado de ella
2. Asegúrese de que el archivo recién creado también a exe válida o un archivo zip

Con un hash rota, 1 es un poco más fácil. Pero asegurando que la colisión se reúne al mismo tiempo otras propiedades conocidas del archivo es computacionalmente demasiado caro.

Esto es totalmente mi propia respuesta, y yo podría ser muy mal.

Answer 5

La respuesta depende totalmente de lo que lo está utilizando para. Si usted necesita para evitar que alguien que produce una colisión con unos pocos milisegundos que estaría menos preocupado que si es necesario para evitar que alguien que produce una colisión dentro de unas décadas.

¿Cuál es el problema que en realidad tratando de resolver?

Answer 6

La mayor parte de la preocupación sobre el uso de algo así como MD4 una contraseña se relaciona menos a los ataques conocidos en la actualidad, que al hecho de que una vez que se ha analizado hasta el punto de que la generación de colisión es fácil, por lo general se presume que es considerablemente más es probable que alguien será capaz de utilizar ese conocimiento para crear un ataque imagen inversa -. y cuando / si eso sucede, básicamente todos los usos posibles de esa función hash se vuelven vulnerables