grande O para encontrar el hash de longitud n O (2 ^ n) u O (2 ^ (n-1))?

3

nota El artículo de wikipedia no usa la notación O grande correctamente. Por lo tanto, O (2 n ) solo significa 2 n intentos

Leí en wikipedia (CGA) que encontrar una colisión es una preimagen para una hash cryptographich de 59 bit de longitud es aproximadamente O (2 59 ) en notación O grande. Sin embargo, en mi opinión, es O (2 58 ) ya que en promedio encontraremos la misma salida después de buscar crear la mitad del objetivo espacio de nombres (espacio de nombres = rango 0 hasta 2 59 ).

Supongo que es debido a que aproximadamente ambas declaraciones serían correctas. En un artículo académico, ¿qué es preferible usar?

Supongo que, en promedio, deberemos crear la mitad del espacio de nombres de 59 bits (objetivo) para encontrar una imagen previa. Ahora, si tuviéramos funciones crypto hash que distribuyeran perfectamente la salida (que no tenemos) en el espacio de 59 bits, solo necesitaríamos (en promedio) 2 58 intentos de encontrar un hash ( como 2 58 entradas distintas producirían 2 58 salidas distintas, suponiendo una distribución perfecta). Como se indica en la respuesta, no tenemos funciones hash perfectas, por lo tanto, las distintas entradas darán las mismas salidas, por lo que, en promedio, el intento se aproxima a 2 59 . Eso es de donde viene el aproximadamente . Estoy en lo correcto?

    
pregunta jannikb 10.06.2015 - 14:05
fuente

2 respuestas

14

Primero, lees mal la página: no se trata de colisiones . La página de Wikipedia dice:

  

el costo de encontrar un conjunto de parámetros de CGA que produzcan los 59 bits deseados es aproximadamente O (2 59 )

La palabra importante aquí es "deseada". El atacante desea encontrar una entrada que haga hashes a una salida específica, dada. Esto se denomina ataque preimage . Por el contrario, un ataque de colisión consiste en encontrar dos entradas distintas que tengan el mismo valor, sin ninguna restricción en ese valor de salida común; esto no es lo mismo (y las colisiones son de hecho mucho más fáciles, hasta aproximadamente 2 30 evaluaciones para una salida de 59 bits).

Dicho esto, el costo promedio de ataque es de hecho 2 59 , no 2 58 , porque esta es una función hash, no a cifrado de bloque. Usted habla de "buscar la mitad del espacio de nombres" pero, de hecho, no existe tal cosa como un "espacio de nombres" en ese caso.

Cuando intentas forzar la fuerza bruta una clave de 59 bits, hay un espacio definido de posibles claves (todas las secuencias de 59 bits) de tamaño 2 59 , y sabes que una de ellas es la solución, y puede probarlas todas en el debido orden, sin intentar nunca el doble . Bajo estas condiciones, puede esperar encontrar la correcta después de, en promedio, probar la mitad de las claves posibles.

Esto no es así aquí. En el caso de CGA, el problema es encontrar una entrada (que es bastante más grande que 59 bits) tal que la salida es una secuencia de 59 bits objetivo específica. Cuando prueba varias entradas posibles, obtiene las salidas correspondientes, pero (ese es el punto crítico) estas salidas son (desde su punto de vista) aleatorias (como en " random oracle "), y, en particular, puedes obtener el mismo varias veces. De hecho, se espera que obtenga su primer duplicado después de probar aproximadamente 2 30 entradas (eso es lo que se denomina birthday paradox ), y, a medida que acumules esos resultados aleatorios, obtendrás más y más colisiones. Si prueba 2 entradas distintas 59 y las mezcla todas, entonces no obtendrá todas las 2 salidas posibles 59 , sino sustancialmente menos (alrededor del 63% de ellas).

En otras palabras, cuando realiza el ataque de fuerza bruta en la función hash, se desperdicia parte de su esfuerzo, ya que produce salidas de 59 bits que ya tenía con otra entrada posible. Esto reduce la tasa de éxito y, por lo tanto, aumenta el costo general del ataque.

Suponiendo que la función hash se comporte como un oráculo aleatorio (es decir, sin debilidad estructural conocida), la probabilidad de encontrar la salida correcta de 59 bits cada vez que intente una nueva entrada es exactamente 2 -59 y, por definición, esto significa que tiene que probar en promedio 2 veces 59 antes de encontrar una coincidencia. Este es un promedio : puede tener suerte y encontrar una coincidencia antes; También puede tener mala suerte y encontrar un partido más tarde, sin límite superior. Esto (de nuevo) contrasta con la situación de "buscar la clave para un cifrado de bloque", donde se sabe que el ataque funcionará después de intentar, como máximo, todas las claves posibles; en el ataque de preimagen para una función hash, ni siquiera obtienes tal garantía, solo un promedio.

    
respondido por el Thomas Pornin 10.06.2015 - 14:25
fuente
0
  1. O (2 59 ) es lo mismo que O (1). Wikipedia está abusando de la notación.

    Debería decir

      

    Para un CGA con Sec igual a 0, esto significa que el costo de encontrar un conjunto de parámetros de CGA que produzcan los 59 bits deseados es aproximadamente 2 59

  2. Usted tiene razón al decir que el costo promedio de encontrar un valor con el mismo hash es 2 58 . El costo real puede ser tan bajo como 1, y puede ser tan alto como 2 59 . La probabilidad de encontrarlo aumenta linealmente con los intentos de respeto. Por lo tanto, el costo promedio es 2 58 .

    Eso sin embargo, asume una distribución perfecta. En el caso de una distribución imperfecta, es incluso menor que 2 58 . En el exterme, si todo tiene el mismo valor, su costo es 1.

respondido por el Paul Draper 10.06.2015 - 21:31
fuente

Lea otras preguntas en las etiquetas