Diferencia entre la segunda resistencia de pre-imagen y la resistencia a la colisión en las funciones criptográficas de hash

7

Estoy estudiando el tema de estas notas. Sin embargo, no está claro cuál es la diferencia entre las propiedades de "Segunda resistencia de pre-imagen" y "Resistencia a la colisión" de las funciones criptográficas de hash.

Como dicen las notas en "Segunda resistencia de pre-imagen", dado x1 no es computacionalmente deducible x2 tal que h (x1) = h (x2). ¿Cuál es la relación entre x1 y x2 aquí?

En "Resistencia a la colisión", es computacionalmente imposible encontrar un x1! = x2 tal que h (x1) = h (x2). ¿Es ese un caso secundario de "Segunda resistencia de pre-imagen", donde x1! = X2?

¿Podría aclarar la diferencia entre estos dos?

    
pregunta Michael 10.10.2014 - 20:29
fuente

2 respuestas

8

La resistencia a la colisión se trata de la imposibilidad de encontrar dos entradas distintas m y m ' de manera que > h ( m ) = h ( m '). El atacante puede elegir arbitrariamente m y m ', siempre y cuando termine con dos mensajes distintos que tengan el mismo valor.

La resistencia de la segunda preimagen es muy similar, excepto que el atacante no puede elegir m . En su lugar, le damos m y lo desafiamos a encontrar m ' (distinto de m ) de manera que h ( m ) = h ( m ').

Una segunda imagen previa también es una colisión, pero mantenemos el concepto distinto porque se supone que las segundas imágenes previas son sustancialmente más difíciles. Si la función hash tiene una salida de n bits y es "perfecta" (no se conoce ninguna debilidad), el costo de encontrar una colisión es 2 n / 2 , mientras que el costo de encontrar una segunda imagen es 2 n (es decir, mucho más).

Supongamos que estamos hablando de firmas. Como un algoritmo de firma comienza con el hash de los datos que se van a firmar, y luego trabaja solo con el valor de hash resultante, entonces se deduce que si h ( m ) = < em> h ( m '), entonces una firma s en el mensaje m también será una firma válida en el mensaje m '. El objetivo del atacante es falsificar una firma, es decir, obtener una firma que parezca válida en un mensaje de su elección.

Si el atacante ve un mensaje firmado y válido m , es posible que desee encontrar un mensaje m ' que tenga el mismo valor. Este es el segundo modelo de preimagen. Para que el sistema de firmas sea robusto, la función hash debe proporcionar una resistencia de segunda imagen.

La resistencia a la colisión, por otro lado, no es necesaria en ese caso. Sin embargo, es necesario con otro modelo donde el atacante pueda obtener una firma en un mensaje m que parezca inocente, y quiera que esa firma también sea válida en un mensaje m ' Con contenidos menos benignos. Por ejemplo, yo soy el atacante y te envío un contrato donde prometes enviarme 1 $. Sin embargo, elaboré ese contrato m de manera que colisiona (hashes al mismo valor) con un contrato ligeramente diferente m ', donde prometes enviarme $ 1000000. Si puedo hacer que firme el primer contrato, entonces, gracias a la colisión, su firma también se aplica al segundo (y usted pierde).

Por lo tanto, la resistencia a la colisión y la resistencia de la segunda imagen son dos conceptos distintos, y lo que necesita depende del contexto. En el caso de firmas, necesita al menos resistencia a la segunda imagen; pero si el contexto es tal que el atacante puede obtener firmas en los datos que elija, entonces también se necesita resistencia a la colisión. Esto ha sido demostrado con MD5 como función hash y certificados X.509 (tenga en cuenta los detalles: la el ataque de colisión en MD5 podría aplicarse a los certificados porque los investigadores encontraron una CA que genera números de serie de certificados de una manera predecible).

    
respondido por el Tom Leek 10.10.2014 - 21:24
fuente
2

La segunda resistencia de pre-imagen simplemente tiene más restricciones que la resistencia a la colisión.

En sus ejemplos, x1 y x2 son las entradas, y h (x1) y h (x2) son las salidas.

Para la segunda resistencia de pre-imagen, se le da x1, y debe encontrar una entrada (x2) que haga hashes al mismo valor de salida. No puedes elegir x1 en este ataque.

No hay tal restricción para la resistencia a la colisión. Usted es libre de elegir ambos x1 y x2 en un intento de encontrar una colisión de las salidas.

    
respondido por el Xander 10.10.2014 - 20:37
fuente

Lea otras preguntas en las etiquetas