¿Cuál es la diferencia entre un segundo ataque de preimagen y un ataque de colisión?

24

Wikipedia define un segundo ataque de preimagen como:

dado un mensaje fijo m1, busque un mensaje diferente m2 tal que hash (m2) = hash (m1).

Wikipedia define un ataque de colisión como:

encuentre dos mensajes diferentes arbitrarios m1 y m2 de manera que hash (m1) = hash (m2).

La única diferencia que puedo ver es que en un segundo ataque de preimagen, m1 ya existe y el atacante lo conoce. Sin embargo, eso no me parece significativo: el objetivo final sigue siendo encontrar dos mensajes que produzcan el mismo hash.

¿Cuáles son las diferencias esenciales en cómo se llevan a cabo un segundo ataque de preimagen y un ataque de colisión? ¿Cuáles son las diferencias en los resultados?

(Por otro lado, no puedo etiquetar esta pregunta correctamente. Estoy tratando de aplicar las etiquetas "colisión previa a la imagen de seguridad de criptografía" pero no tengo suficiente reputación. ¿Alguien puede aplicar las etiquetas apropiadas?)

Thomas Owens
fuente
1
Su impresión es correcta, esa es la diferencia. La parte en la que eres incorrecto es que esta es una GRAN diferencia en la práctica. Una cosa es poder encontrar dos cosas que tienen una colisión, y otra muy distinta es encontrar una colisión para un texto plano específico. Por ejemplo, si desea falsificar un mensaje en particular, es inútil poder cometer una falsificación existencial: necesita otro mensaje que coincida con el mensaje que ha interceptado.
Adrian Petrescu
@Adrian Petrescu: ¿Podrías responder eso y tal vez dar más detalles? Agregue cosas como cuando cada una (¿proporciona una situación para el ataque de preimagen, pero no para el ataque de colisión) es la más adecuada?
Thomas Owens

Respuestas:

27

Puedo motivar la diferencia para ti con escenarios de ataque.

En un primer ataque de preimagen , le pedimos a un adversario, dado solo , que encuentre m o algo de m tal que H ( m ) = H ( m ) . Supongamos que un sitio web almacena { u s e r n a m e , H ( p a s s w o r d ) } en sus bases de datos en lugar de { u s rH(m)mmH(m)H(m){username,H(password)} . El sitio web aún puede verificar la autenticidad del usuario al aceptar su contraseña y comparar H ( i n p u t ) = ? H ( p un s s w o r d ) (con una probabilidad de 1 / 2 n por alguna gran n{username,password}H(input)=?H(password)1/2nn de falsos positivos). Ahora suponga que esta base de datos se filtra o se comprime de otra manera. UNAEl primer ataque de preimagen es la situación en la que un adversario solo tiene acceso a un resumen de mensaje y está tratando de generar un mensaje que tenga hash a este valor.

En un segundo ataque de preimagen , le permitimos al adversario más información. Específicamente, no solo le damos sino que también le damos m . Considere la función hash H ( m ) = m dH(m)m donde p y q son números primos grandes yd es una constante pública. Obviamente, para unprimer ataque de preimagen,este se convierte en el problema de RSA y se cree que es difícil. Sin embargo, en el caso delsegundo ataque de preimagen,encontrar una colisión se vuelve fácil. Si uno establece m = m p q + m , H ( m p q + m ) = ( m p q + m ) dH(m)=mdmodpqpqdm=mpq+m . Y así, el adversario ha encontrado una colisión con poco o ningún cálculo.H(mpq+m)=(mpq+m)dmodpq=mdmodpq

Nos gustaría que las funciones hash unidireccionales sean resistentes a los segundos ataques de preimagen debido a los esquemas de firma digital, en cuyo caso se considera información pública y se transmite (a través de un nivel de indirección) con cada copia del documento Aquí un atacante tiene acceso tanto a d o c u m e n t como a H ( d o c u m e n t )H(document)documentH(document). Si el atacante puede llegar a una variación en el documento original (o un mensaje completamente nuevo) tal que H ( d ) = H ( d o c u m e n t ) podría publicar su documento como si fuera El firmante original.dH(d)=H(document)

Un ataque de colisión le da al adversario aún más oportunidades. En este esquema, le pedimos al adversario (¿puedo llamarlo Bob?) Que encuentre dos mensajes y m 2 de modo que H ( m 1 ) = H ( m 2 ) . Debido al principio del casillero y la paradoja del cumpleaños, incluso las funciones hash 'perfectas' son cuadráticamente más débiles a los ataques de colisión que los ataques de preimagen. En otras palabras, dada una función de resumen de mensaje impredecible e irreversible f ( { 0 , 1 } ) = { 0m1m2H(m1)=H(m2) que toma O ( 2 n ) tiempo para la fuerza bruta, siempre se puede encontrar una colisión en el tiempo esperado O ( s q r t ( 2 n ) ) = O ( 2 n / 2 ) .f({0,1})={0,1}nO(2n)O(sqrt(2n))=O(2n/2)

Bob puede usar un ataque de colisión a su favor de muchas maneras. Este es uno de los más simples: Bob encuentra una colisión entre dos binarios y b ( H ( b ) = H ( b ) ) de modo que b es un parche de seguridad válido de Microsoft Windows y b es malware. (Bob trabaja para Windows). Bob envía su parche de seguridad a la cadena de comando, donde, detrás de una bóveda, firman el código y envían el binario a los usuarios de Windows de todo el mundo para corregir una falla. Bob ahora puede contactar e infectar todas las computadoras con Windows en todo el mundo con b ' y la firma que Microsoft calculó para bbbH(b)=H(b)bbb. Más allá de este tipo de escenarios de ataque, si se cree que una función hash es resistente a colisiones, es más probable que esa función hash sea resistente a la imagen previa.

Ross Snider
fuente
Eso está muy bien explicado. Mucho más matemática de la que estaba buscando, pero aprecio mucho el esfuerzo: te seguí a través de cada una. Gracias.
Thomas Owens
Y guau. Un compañero de RIT.
Thomas Owens
1
¿Cómo te va, Thomas? Creo que tenías física con mi amigo Alan Meekins. ¡Es bueno ver a la gente de RIT aquí! Además, gracias por aceptar la respuesta.
Ross Snider
Bastante bueno. Si va a estar cerca del campus en el otoño y está interesado en la seguridad, tal vez podamos ponernos al día en persona. He estado haciendo un trabajo de seguridad aplicado (aplicando estenografía, esteganálisis, cifrado de clave pública, firmas digitales) este verano y me encantaría saber sobre el lado teórico (por mucho que me interese, no tengo el tiempo o antecedentes matemáticos para pasar por muchos de los documentos sobre el tema).
Thomas Owens
[email protected]
Ross Snider
2

Los ataques de colisión pueden ser mucho más fáciles, pero si tienen éxito, son mucho menos útiles.

Jukka Suomela
fuente
1

El problema que Ross menciona como el problema del registro discreto es en realidad un problema completamente diferente, el problema RSA, que está mucho más relacionado con las raíces informáticas que con el registro discreto.


fuente
2
¡Esto es ciertamente cierto! Ups Originalmente utilicé el problema de registro discreto y luego edité los detalles del esquema. Buena atrapada. No estoy seguro de que esto constituya una nueva respuesta; probablemente fue más apropiado dejarlo como comentario debajo de mi respuesta.
Ross Snider