entendimiento SHA-1 debilidad colisión

Question

Según diversas fuentes, los ataques en busca de SHA-1 colisiones se han mejorado a 2^52 operaciones:

http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/

Lo que me gustaría saber es la implicación de estos descubrimientos en sistemas que no están bajo ataque. Es decir, si tengo datos aleatorios, ¿cuáles son las probabilidades estadísticas de una colisión? Dicho de otra manera, ¿la investigación reciente indica que un ataque de cumpleaños de fuerza bruta tiene una mayor probabilidad de encontrar colisiones que originalmente se propusieron?

Algunos comentarios, como el anterior, dicen que la obtención de una colisión SHA-1 mediante la fuerza bruta requeriría 2^80 operaciones. La mayoría de las fuentes dicen que 2^80 es un número teórico (supongo que porque ninguna función hash realmente se distribuye perfectamente incluso en su espacio de compendio).

¿Cuáles son algunas de las debilidades anunciadas de colisión sha1 en la distribución de hash fundamental? ¿O las mayores probabilidades de colisión solo son el resultado de ataques matemáticos guiados?

Me doy cuenta de que, al final, es solo un juego de probabilidades, y que su cambio es infinitamente pequeño y que su primer y segundo mensaje provocará una colisión. También me doy cuenta de que incluso 2^52 es un número realmente grande, pero aún quiero entender las implicaciones para un sistema que no está siendo atacado. Así que por favor no respondas con "no te preocupes".

Answer 1

El resultado anunciado en su enlace es ataque, una secuencia de pasos cuidadosos, elegidos algorítmicamente que generan colisiones con mayor probabilidad que un ataque aleatorio. No es una debilidad en la distribución de la función hash. Bueno, está bien, pero no es del tipo que hace probable un ataque aleatorio del orden de 2^52 para tener éxito.

Si nadie está tratando de generar colisiones en sus salidas hash, este resultado no le afecta.

Answer 2

Bueno, las buenas funciones de hash son resistentes a 3 tipos de ataques diferentes (como dice el artículo).

La resistencia más importante en un sentido práctico es la segunda resistencia a la imagen previa. Esto básicamente significa que dado un mensaje M1 y Hash (M1) = H1, es difícil encontrar un M2 tal que Hash (M2) = H1.

Si alguien encuentra una forma de hacerlo de manera eficiente, sería malo. Además, un ataque de preimagen no es susceptible a la paradoja del cumpleaños, ya que el mensaje M1 está arreglado para nosotros.

Esto no es una imagen previa o un segundo ataque previo a la imagen, simplemente un ataque de colisión. Para responder a su pregunta, ningún ataque de fuerza bruta NO tiene una mayor probabilidad de encontrar colisiones. Lo que esto significa es que el método ingenuo de fuerza bruta, combinado con los métodos de los investigadores, resulta en encontrar colisiones después de 2^52. Un ataque de fuerza bruta estándar aún toma 2^80.

Answer 3

La pregunta clave es "¿Puede el atacante modificar los mensajes m1 y m2" ?. Si es así, el atacante necesita encontrar m1, m2 tal que hash (m1) = hash (m2). Este es el ataque de cumpleaños y la complejidad se reduce significativamente: se convierte en raíz cuadrada. Si la salida de hash es de 128 bits (MD5), la complejidad es de 2^64, al alcance de la potencia informática actual.

El ejemplo habitual es que el vendedor le pide a su secretaria que escriba el mensaje "Lo venderé por 10 millones de dólares".La intrigante secretaria crea 2 documentos, uno que dice "Lo venderé por 10 millones de dólares" y otro que dice "Lo venderé por x millones de dólares", donde x es mucho menor que 10, modifica ambos mensajes agregando espacios, capitalizando palabras, etc., modifica x, hasta hash (m1) = hash (m2). Ahora, la secretaria muestra el mensaje correcto m1 al vendedor, y lo firma usando su clave privada, lo que resulta en hash h. La secretaria cambia el mensaje y lo envía (m2, h). Solo el vendedor tiene acceso a su clave privada y, por lo tanto, no puede repudiar y decir que no firmó el mensaje.

Para SHA1, que emite 160 bits, el ataque de cumpleaños reduce la complejidad a 2^80. Esto debería ser seguro por 30 años o más. Las nuevas regulaciones gubernamentales, las especificaciones de 4G 3gpp comienzan a requerir SHA256.

Pero si en su caso de uso, el atacante no puede modificar ambos mensajes (preimagen o segundos escenarios de preimagen), entonces para SHA1 la complejidad es 2^160. Debería estar seguro por la eternidad a menos que se descubra un ataque de fuerza no-bruta.