cryptography - online - sha-256 algorithm

¿Es posible obtener el hash SHA1 idéntico?

Question

Esta pregunta ya tiene una respuesta aquí:

• Probabilidad de colisiones SHA1 3 respuestas

Dadas dos cadenas diferentes S1 y S2 (S1! = S2) es posible que:

SHA1(S1) == SHA1(S2)

¿es verdad?

1. En caso afirmativo, ¿con qué probabilidad?
2. ¿Si no, porque no?
3. ¿Hay un límite superior en la longitud de una cadena de entrada, para la cual la probabilidad de obtener duplicados es 0? O, ¿el cálculo de SHA1 (por lo tanto, probabilidad de duplicados) es independiente de la longitud de la cadena?

El objetivo que intento lograr es manipular una cadena de identificación sensible (posiblemente unida a otros campos como la ID principal), de modo que pueda usar el valor hash como ID (por ejemplo, en la base de datos).

Ejemplo:

Resource ID: X123
Parent ID: P123

No quiero exponer la naturaleza de mi recurso identifica para permitir que el cliente vea "X123-P123".

En cambio, quiero crear un nuevo hash de columna ("X123-P123"), digamos que es AAAZZZ. Entonces el cliente puede solicitar recursos con ID AAAZZZ y no saber sobre mi id interno, etc.

Answer 1

De lo que estás hablando se llama colisión. Aquí hay un artículo sobre colisiones SHA1: http://www.rsa.com/rsalabs/node.asp?id=2927

Editar: Entonces, otro respondedor me ganó para mencionar el principio de palomar LOL, pero para aclarar esto, es por eso que se llama principio del casillero, porque si tienes algunos agujeros cortados para que las palomas mensajeras aniden, pero tienes más palomas que agujeros , entonces algunas de las palomas (un valor de entrada) deben compartir un agujero (el valor de salida).

Answer 2

Lo que describes se llama colisión . Las colisiones existen necesariamente, ya que SHA-1 acepta muchos más mensajes distintos como entrada que pueden producir salidas distintas (SHA-1 puede comer cualquier cadena de bits de hasta 2 ^ 64 bits, pero produce solo 160 bits, por lo tanto, al menos una salida el valor 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 de 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 la salida v en la entrada m , siempre debe devolver v en la entrada m ), entonces la probabilidad de colisión, para dos cadenas distintas S1 y S2, debe ser 2 ^ (- 160). Aún bajo la suposición de que SHA-1 se comporta como un oráculo al azar, si recolectas muchas cadenas de entrada, entonces comenzarás a observar colisiones después de haber recolectado alrededor de 2 ^ 80 de estas cadenas.

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

Ahora sospechamos firmemente que SHA-1 en realidad no se comporta como un oráculo al azar, porque el enfoque de paradoja de cumpleaños es el algoritmo de búsqueda de colisión óptimo para un oráculo al azar. 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 cumpleaños-paradoja. Tal ataque no debería ser factible en un verdadero oráculo al azar. Eso sí, este ataque no se ha completado realmente, sigue siendo teórico (algunas personas lo intentaron pero aparentemente no pudieron encontrar suficiente potencia de CPU ) ( Actualización: a principios de 2017, alguien calculó una 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 al azar. En consecuencia, en cuanto a la probabilidad de colisión, bueno, todas las apuestas están apagadas.

En cuanto a su tercera pregunta: para una función con una salida en n bits, 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 menor que 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 <80 es probable que no haya colisión, mientras que m> 80 hace que la existencia de al menos una colisión sea muy probable (con m> 160 esto se convierte en una certeza).

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

Answer 3

Sí, es posible debido al principio de la alcantarilla .

La mayoría de los hashes (también sha1) tienen una longitud de salida fija, mientras que la entrada es de tamaño arbitrario. Entonces, si lo intentas lo suficiente, puedes encontrarlos.

Sin embargo, las funciones hash criptográficas (como la sha-family, la familia md, etc.) están diseñadas para minimizar tales colisiones. El mejor ataque conocido requiere 2 ^ 63 intentos para encontrar una colisión, por lo que la probabilidad es de 2 ^ (- 63) que es 0 en la práctica.

Answer 4

Una colisión casi siempre es posible en una función hash. SHA1, hasta la fecha, ha sido bastante seguro en la generación de colisiones impredecibles. El peligro es que cuando se pueden predecir las colisiones, no es necesario conocer la entrada hash original para generar la misma salida hash.

Por ejemplo, se realizaron ataques contra MD5 contra la firma de certificados de servidor SSL el año pasado, como se ilustró en el podcast 179 de Security Now. Esto permitió a atacantes sofisticados generar un certificado de servidor SSL falso para un sitio web fraudulento y parece ser lo último . Por esta razón, se recomienda encarecidamente evitar la compra de certificados firmados por MD5.

Answer 5

git utiliza hashes SHA1 como ID y todavía no se conocen colisiones SHA1 en 2014. Obviamente, el algoritmo SHA1 es mágico. Creo que es una buena apuesta que las colisiones no existan para cadenas de tu longitud, ya que se habrían descubierto por ahora. Sin embargo, si no confías en la magia y no eres un apostador, puedes generar cadenas aleatorias y asociarlas con tus ID en tu base de datos. Pero si usa hashes SHA1 y se convierte en el primero en descubrir una colisión, puede cambiar su sistema para usar cadenas aleatorias en ese momento, conservando los valores hash SHA1 como cadenas "aleatorias" para ID heredados.