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


Esta pregunta ya tiene una respuesta aquí:

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.


74
2018-03-19 17:33


origen


Respuestas:


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 el resultado) v en la entrada metro, siempre debe regresar v en la entrada metro), entonces la probabilidad de colisión, para dos cadenas distintas S1 y S2, debería 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 cumpleaños. Ver la página de Wikipedia sobre el tema.)

Ahora sospechamos fuertemente que SHA-1 lo hace no realmente se comporta como un oráculo al azar, porque el enfoque de cumpleaños-paradoja 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 intentado, pero aparentemente no pudo encontrar suficiente potencia de la CPU) (Actualizar: a partir de principios de 2017, alguien hizo calcular un SHA-1 colisión 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 un nortesalida de bit, entonces necesariamente hay colisiones si puede ingresar más de 2 ^norte mensajes distintos, es decir, si la longitud máxima del mensaje de entrada es mayor que norte. Con un límite metro Más bajo que norte, 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 metro, y no linealmente, sino con un corte pronunciado m = n / 2. Este es el mismo análisis que la paradoja del cumpleaños. Con SHA-1, esto significa que si m <80 entonces es probable que no haya colisión, mientras 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 una colisión debe existe, todavía tienes tus 2 ^ (- 160) probabilidades cada vez que lo intentes. Lo que el párrafo anterior significa es que tal probabilidad no tiene sentido si no puedes (conceptualmente) probar 2 ^ 160 pares de cadenas, p. porque te limitas a cadenas de menos de 80 bits.


111
2018-03-19 21:54



Sí, es posible debido a la 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.


31
2018-03-19 17:45



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, los ataques contra MD5 se han realizado contra la firma de certificados de servidor SSL el año pasado, como se muestra en el ejemplo Seguridad ahora episodio de podcast 179. Esto permitió a los atacantes sofisticados generar un certificado de servidor SSL falso para un sitio web deshonesto y parece ser lo último. Por esta razón, se recomienda encarecidamente evitar la compra de certificados firmados por MD5.


4
2018-03-20 02:02



git utiliza hashes SHA1 como ID y hay 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.


4
2017-07-21 21:50



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).


3
2018-03-19 17:38