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.