matemáticamente / teóricamente, ¿cuál es la posibilidad de que 2 entradas diferentes tengan los mismos resultados que 2 funciones hash diferentes?
Como ejemplo, usaré 2 algoritmos hash más débiles, el MD5 (Vulnerabilidades de colisión) y SHA- 1 Vulnerabilidades de colisión . Así que tengo una contraseña . Lo hago con MD5 y luego lo hago con SHA-1. matemáticamente / teóricamente, ¿cuál es la posibilidad de que haya otra entrada con el mismo hash SHA y hash MD5 como mi resultado?
Si tengo dos cadenas aleatorias (s1, s2) que son diferentes ( s1 != s2 ), debes saber la probabilidad de que md5(s1) == md5(s2) AND sha1(s1) == sha1(s2) .
Bueno, primero para dos cadenas específicas elegidas al azar, ¿cuál es la probabilidad de que md5(s1) == md5(s2) ? Responda su 1/2 ^ 128 ya que el primer hash es una cadena de 128 bits, y las posibilidades de que el segundo hash sea igual al segundo es 1 en 2 ^ 128 o aproximadamente 2.9 x 10 ^ -37%.
Del mismo modo, P(sha1(s1) == sha1(s2)) = 2^-160 ~ 6.8 x 10^-47 % .
Ahora, la probabilidad de que ambas condiciones sean verdaderas asumiendo que son condiciones independientes (es decir, las funciones de hashing son fundamentalmente independientes entre sí), se encuentra al multiplicar las probabilidades desde P(X AND Y) = P(X) P(Y) y P(md5(s1)==md5(s2) AND sha1(s1) == sha1(s2)) = 2^-288 ~ 2 x 10^-85 % .
Por supuesto, asumimos que las funciones de hashing actúan de forma independiente en la cadena, lo cual es una suposición justa para md5 y sha1 como funciones de hashing. Pero si en lugar de comparar MD5 y SHA-1, comparáramos MD5 y una nueva función de hashing que solo se aplica a MD5 100 veces, encontraríamos que siempre que md5 (s1) == md5 (s2), también tendríamos md5 ^ 100 (s1) == md5 ^ 100 (s2), por lo que la probabilidad de que ambos choquen es la misma que la probabilidad de tener una colisión.
De forma similar, si tuviéramos una función "hash" tonta que solo fuera silly_hash (s) = md5 (s) ++ s (donde ++ significa concatenar), entonces podría mostrar que si s1! = s2 y md5 ( s1) == md5 (s2) luego silly_hash (s1)! = silly_hash (s2) - lo que significa que nunca podrías tener una doble colisión con md5 y silly_hash.
Matemáticamente? 100% de probabilidad. Es casi seguro que existe alguna otra entrada con el mismo hash MD5 y SHA.
¿Prácticamente? 0% de probabilidad. Si bien existe otra entrada existente , no se conoce ninguna forma de encontrarla en la vida del universo.
Usted está preguntando acerca de la segunda resistencia de pre-imagen. Hasta donde sé, se cree que al menos SHA1 (y probablemente también MD5) proporcionan una fuerte resistencia a la pre-imagen. De ahí el comentario de que no hay forma conocida de encontrar otra entrada con los mismos hashes, durante la vida del universo conocido.
Los ataques de colisión son específicamente para el caso en el que puede elegir las dos entradas en colisión según sea necesario. Para el escenario de contraseña que describe, la contraseña generalmente se determina de antemano, por lo que no es una colisión sino un ataque previo a la imagen. Dado que la contraseña probablemente tampoco sea conocida por el adversario, lo que le preocupa es un ataque de "primera pre-imagen". Este es el ataque más difícil ya que le da al adversario el menor grado de libertad. SHA1 y MD5 están actualmente protegidos contra este tipo de ataque. Lo que significa que la probabilidad de encontrar otra entrada para un hashsum dado es cero para todos los propósitos prácticos.
Dicho de otra forma: si este ataque funcionara, la mayoría de los protocolos de red actuales serían inseguros. (La gente realmente verificó los protocolos actuales para ver si los ataques de colisión son peligrosos y decidieron que podemos continuar usándolos).
Lea otras preguntas en las etiquetas hash cryptography