¿Cuál es la diferencia entre una colisión múltiple y un ataque de primer o segundo ataque previo a la imagen en una función hash?
Pregunta
¿Cuál es la diferencia entre una colisión múltiple en una función hash y una preimagen de primera o segunda?
Primer ataques de preimagen: Dado un hash h, encuentre un mensaje m de tal manera que
hash (m) = h.
Segundo ataques de preimagen: Dado un mensaje fijo M1, encuentre un mensaje diferente M2 de tal manera que
hash (m2) = hash (m1).
Ataques de colisión múltiple: generar una serie de mensajes m1, m2, ... mn, de modo que
hash (m1) = hash (m2) = ... = hash (mn).
Wikipedia nos dice que un ataque de preimagen difiere de un ataque de colisión en que hay un hash o mensaje fijo que se está atacando.
Estoy confundido por los documentos que hacen declaraciones como:
Las técnicas no solo son eficientes para buscar colisiones, sino también aplicables para explorar la segunda preimagen de MD4. Sobre el ataque de segundo preimagen, mostraron que un mensaje aleatorio era un mensaje débil con la probabilidad 2^–122 y solo necesitaba un cálculo de MD4 único para encontrar la segunda preimagen correspondiente al mensaje débil.
El ataque de segunda preimagen en MD4
Si entiendo lo que los autores parecen estar diciendo es que han desarrollado un ataque de colisión múltiple que abarca un conjunto lo suficientemente grande de mensajes que, dado un mensaje aleatorio, hay una posibilidad significativa, aunque extremadamente pequeña, se superpone con uno de sus múltiples colisiones.
Vi argumentos similares en muchos documentos. Mi pregunta cuándo un ataque deja de ser un ataque de colisión múltiple y se convierte en un segundo ataque de preimagen.
Si una colisión múltiple choca con otros 2^300 mensajes, eso cuenta como una segunda preimagen, ya que la colisión múltiple podría usarse para calcular la "preimagen" de uno de los mensajes con los que choca? ¿Dónde está la línea divisoria, 2^60, 2^100, 2^1000?
¿Qué pasa si puede generar una preimagen de todos los digestos hash que comienzan con 23? Ciertamente, no cumple con la definición estricta de una preimagen, pero tampoco es muy grave defecto en la función de hash criptográfico.
Si alguien tiene una gran colisión múltiple, siempre podría recuperar la imagen de cualquier mensaje que ha colisionado con la colisión múltiple. Por ejemplo,
hash (m1) = hash (m2) = hash (m3) = h
Alguien solicita la preimagen de H y responde con M2. ¿Cuándo deja de ser tonta esto y se convierte en un ataque real?
¿Reglas de juego? ¿Conocer algún buen recurso para evaluar los ataques de funciones hash?
Enlaces relacionados:
Solución
Se trata de un escenario de ataque. La diferencia radica en la elección de la entrada. En multi-colisión hay La libre elección de ambas entradas. La segunda preimagen se trata de encontrar cualquier segunda entrada que tenga la misma salida que cualquier entrada especificada.
Cuando una función no tiene resistencia de colisión múltiple, puede ser posible encontrar una colisión para algún tipo de mensajes, no todos. Entonces esto no implica la segunda debilidad de preimagen.
Otros consejos
Investigaste mucho antes de publicar la pregunta. No puedo responder mucho a un lado la pregunta de los recursos. Lo que es: uso la criptografía aplicada Be Menezes/Oorschot para casi todo lo que siempre quise saber sobre temas de criptografía, incluidos los hashes.
Tal vez encuentre una copia en la biblioteca de su universidades. Buena suerte.