¿Es posible obtener un hash SHA1 idéntico? [duplicar]

Lo que usted describe se llama una colisión . Las colisiones necesariamente existen, ya que SHA-1 acepta muchos más mensajes distintos como entrada que puede producir salidas distintas (SHA-1 puede consumir cualquier cadena de bits de hasta 2^64 bits, pero solo produce 160 bits; por lo tanto, al menos un valor de salida debe aparecer varias veces). Esta observación es válida para cualquier función con una salida más pequeña que su entrada, independientemente de si la función es una función hash "buena" o no.

Suponiendo que SHA-1 se comporta como un "oráculo aleatorio" (un objeto conceptual que básicamente devuelve valores aleatorios, con la única restricción de que una vez que ha devuelto output v on input m, siempre debe devolver v on input m), entonces la probabilidad de colisión, para dos cadenas distintas S1 y S2, debe ser 2^(-160). Todavía bajo el supuesto de SHA-1 comportándose como un oráculo aleatorio, si usted recoge muchas cadenas de entrada, entonces usted comenzará a observar colisiones después de haber recogido cerca de 2^80 tales cuerdas.

(Eso es 2^80 y no 2^160 porque, con 2^80 cadenas puedes hacer alrededor de 2^159 pares de cadenas. Esto a menudo se llama la "paradoja del cumpleaños" porque es una sorpresa para la mayoría de las personas cuando se aplica a las colisiones en los cumpleaños. Ver la página de Wikipedia sobre el tema.)

Ahora sospechamos fuertemente que SHA-1 se comporta no realmente como un oráculo aleatorio, porque el enfoque de la paradoja de cumpleaños es el óptimo algoritmo de búsqueda de colisión para un oráculo aleatorio. Sin embargo, hay un ataque publicado que debería encontrar una colisión en aproximadamente 2^63 pasos, por lo tanto 2^17 = 131072 veces más rápido que el algoritmo de paradoja de cumpleaños. Tal ataque no debería ser factible en un verdadero oráculo aleatorio. Eso sí, este ataque no se ha completado realmente, sigue siendo teórico (algunas personas intentaron pero aparentemente no pudieron encontrar suficiente potencia de CPU)(Actualización: a principios de 2017, alguien hizo calcular un Colisión SHA-1 con el método mencionado anteriormente, y funcionó exactamente como se predijo). Sin embargo, la teoría parece sólida y realmente parece que SHA-1 no es un oráculo aleatorio. Correspondientemente, en cuanto a la probabilidad de colisión, bueno, todas las apuestas están fuera.

En cuanto a su tercera pregunta: para una función con una salida n-bit, entonces necesariamente hay colisiones si puede ingresar más de 2^n mensajes distintos, es decir, si la longitud máxima del mensaje de entrada es mayor que n. Con un límite m inferior a n, la respuesta no es tan fácil. Si la función se comporta como un oráculo aleatorio, entonces la probabilidad de la existencia de una colisión disminuye con m, y no linealmente, más bien con un corte pronunciado alrededor de m=n/2. Este es el mismo análisis que la paradoja del cumpleaños. Con SHA-1, esto significa que si m , entonces es probable que no hay colisión, mientras que m > 80 hace que la existencia de al menos una colisión muy probable(con m > 160 esto se convierte en una certeza).

Tenga en cuenta que hay una diferencia entre "existe una colisión" y "encuentra una colisión". Incluso cuando una colisión debe existir, todavía tiene su probabilidad de 2^(-160) cada vez que lo intenta. Lo que el párrafo anterior significa es que tal probabilidad no tiene sentido si no puedes (conceptualmente) intentar 2^160 pares de cadenas, por ejemplo, porque te restringes a cadenas de menos de 80 bits.