¿Por qué encontrar una colisión fuerte solo es la mitad del trabajo de una colisión débil?

Question

¿Por qué encontrar una colisión fuerte solo es la mitad del trabajo de una colisión débil?

#1 de Tim McLean (3 votos)
#2 de Ammar Bandukwala (2 votos)

1

Con respecto a las colisiones hash, un atacante solo tiene que hacer la mitad del trabajo para encontrar una colisión cuando puede controlar ambos mensajes en comparación con cuando están tratando de encontrar una colisión débil. Esto se puede explicar con la paradoja del cumpleaños.

Entiendo la paradoja del cumpleaños, pero no puedo ver cómo se relaciona completamente con las colisiones fuertes y por qué muestra que solo toman la mitad del trabajo de las colisiones débiles. Con la paradoja del cumpleaños, cada persona ya conoce su propio cumpleaños por adelantado, por lo que cuando la primera persona "dice" su cumpleaños, todos los demás pueden comparar eso con el suyo, y así sucesivamente.

Si un atacante está tratando de encontrar dos mensajes con hash del mismo valor, los hashes de los mensajes recién modificados aún no se conocen (a diferencia de los cumpleaños de las personas), por lo que un atacante no tendría que crear una carga de hashes para uno de los mensajes, guárdelos y luego haga lo mismo con el otro mensaje y comience a comparar, ¿cómo es esto más rápido que encontrar una colisión débil?

Mi pregunta es, ¿cómo intentaría un atacante encontrar dos mensajes con el mismo valor, de modo que solo tome la mitad del trabajo como si intentaran encontrar una colisión débil?

Gracias.

hash

pregunta RJSmith92 25.10.2015 - 00:29

fuente

2 respuestas

2

Encontrar una colisión usando el problema de cumpleaños significa que durante tu ataque estás almacenando los hashes de todos los intentos anteriores, y para cada hash nuevo, lo estás comparando con todos los hashes anteriores.

En lugar de apuntar a un determinado hash, buscamos la búsqueda de cualquier colisión.

Suponiendo que tengamos mucha memoria y podamos verificar rápidamente todos los hashes anteriores, se volverá más rápido.

respondido por el Ammar Bandukwala 25.10.2015 - 00:44

fuente

Lea otras preguntas en las etiquetas hash

¿Cuál es la configuración típica de la computadora y la disposición de alojamiento de los robots malintencionados? ¿Cuándo el inicio de sesión automático puede ser aceptable desde el punto de vista de la seguridad?

score 3 · Accepted Answer

Para encontrar una colisión, el atacante genera una gran cantidad de mensajes únicos y sus hashes correspondientes. El ataque tiene éxito cuando cualesquiera dos hases coinciden. Esto es igual que la paradoja del cumpleaños, que habla de la probabilidad de que dos personas tengan la misma fecha de nacimiento.

solo toma la mitad del trabajo

Cuidado, 2 ^ 128 no es la mitad de 2 ^ 256. 2 ^ 128 es la raíz cuadrada de 2 ^ 256. 2 ^ 128 es un "2 ^ 128th" de 2 ^ 256.

el atacante tiene 2 mensajes 'coloque 10 $ en mi cuenta' y 'coloque $ 1000 en mi cuenta' y quieren que tengan el mismo valor [...] que el atacante continuaría cambiando ambos mensajes hasta que al mismo valor

En esta situación, el atacante recibe m1 y m2, y quiere encontrar un x1 y un x2 tal que H (m1 + x1) = H (m2 + x2). Supongamos que H es una función hash de 256 bits, como SHA-256. El atacante intenta 2 ^ 128 valores diferentes para x1, calculando y almacenando 2 ^ 128 hashes H (m1 + x1). El atacante ahora intenta diferentes valores para x2, computando los hashes H (m2 + x2), buscando uno que coincida con uno de los hashes x1. Eventualmente, esto tendrá éxito, pero ¿después de cuántos intentos?

Hay 2 ^ 256 valores hash posibles, por lo que la probabilidad de que cada intento tenga éxito es 2 ^ 128/2 ^ 256 = 1/2 ^ 128. Por lo tanto, podemos esperar que este paso requiera alrededor de 2 ^ 128 intentos. Al sumar los dos pasos, este ataque requeriría, en promedio, aproximadamente 2 ^ 128 + 2 ^ 128 = 2 ^ 129 evaluaciones de la función hash.

No creo que esto usualmente se llame "ataque de cumpleaños", ya que la probabilidad matemática es bastante diferente. Sin embargo, ambos ataques tienen una complejidad similar (alrededor de una raíz cuadrada del espacio de búsqueda, o 2 ^ (n / 2) para una función hash de n bits).