¿Por qué el tiempo de búsqueda de fuerza bruta para algoritmos de hashing es 2 ^ (num_bits / 2)?

Question

¿Por qué el tiempo de búsqueda de fuerza bruta para algoritmos de hashing es 2 ^ (num_bits / 2)?

#1 de Thomas Pornin (2 votos)
#2 de David (0 votos)

1

Me di cuenta de que los tiempos de fuerza bruta (el tiempo que lleva encontrar un mensaje que contiene un hash determinado) de varios algoritmos de hash parece ser 2^(num_bits / 2) . Por ejemplo, la gente dice que el% de fuerza forzada SHA1 (sin usar la vulnerabilidad que reduce el tiempo de fuerza bruta a 2^69 ) es 2^80 . De hecho, si observa esta tabla , la columna "Seguridad (bits)" parece ser siempre la mitad del número de bits, y creo que se refiere al tiempo de búsqueda. ¿Cómo están obteniendo estos números? Pensaría que para forzar bruscamente un hash de 160 bits, uno debería al menos probar los mensajes 2^160 , o tal vez los valores 2^159 en promedio para encontrar mensajes. No creo que el ataque de cumpleaños sea relevante aquí, ya que parece tratarse de cualquier colisión, a diferencia de una colisión específica.

brute-force hash sha

pregunta gsingh2011 09.09.2014 - 19:38

fuente

2 respuestas

Lea otras preguntas en las etiquetas brute-force hash sha

No reemplaza el certificado SSL en un servidor Unix reconstruido y anteriormente rooteado ¿Puedo ver con seguridad una miniatura de las imágenes descargadas en Ubuntu 14.04?

score 2 · Answer 1

Cuando una función hash tiene una salida de tamaño n bits, entonces:

El algoritmo genérico para encontrar una preimagen (o una segunda preimagen) tiene un costo promedio de 2 ⁿ evaluaciones de la función hash.
El algoritmo genérico para encontrar una colisión tiene un costo promedio de aproximadamente 2 evaluaciones ^{n / 2} de la función hash.

Por "genérico" queremos decir "el algoritmo que funciona contra cada función hash, por muy perfecta que sea esa función". En el caso de preimágenes y segundas preimágenes, el algoritmo genérico también se conoce como "suerte" (intentamos mensajes de entrada hasta que tengamos suerte). Para colisiones, hay varios algoritmos inteligentes que son todas las facetas de la llamada birthday paradox . Escribí "acerca de" porque estos algoritmos inteligentes también incurren en algún costo de RAM o algunas limitaciones en el paralelismo, por lo que el costo real de encontrar una colisión realmente no se puede expresar como un solo número; o, si lo prefiere, el costo matemático no se traduce exactamente en una cantidad proporcional de dólares, si realmente desea hacer el cálculo.

Varios protocolos usan funciones hash por varias razones. Es difícil determinar si un protocolo dado es inmune a las colisiones o no. En algunos casos, un ataque real puede requerir un cálculo de preimagen; o tal vez una colisión es suficiente; O la situación podría ser más compleja. Entonces, solo para estar seguros, generalmente asumimos lo peor y por lo tanto observamos la resistencia más baja. Por lo tanto, calificamos una función hash con una salida de 160 bits para que tenga una potencia de "80 bits" (o 2 ⁸⁰). Sabemos que podemos ser demasiado conservadores aquí; No podemos estar seguros.

score 0 · Answer 2

No veo nada que indique que "Seguridad (bits)" está buscando un ataque previo a la imagen frente a una colisión, por lo que creo que su suposición de que la paradoja del cumpleaños es irrelevante probablemente no sea exacta. Las colisiones siguen siendo un problema de seguridad importante, de hecho se han utilizado utilizadas para falsificar certificados SSL . Un ataque de preimagen (encontrar otra entrada que coincida con un valor particular) todavía requiere 2 ^ n operaciones (debilidades de módulo en el algoritmo hash).