math - descifrar - ¿Cuáles son las posibilidades de que dos mensajes tengan el mismo resumen MD5 y el mismo resumen SHA1?
sha-512 (5)
Dado dos mensajes diferentes, A y B (tal vez 20-80 caracteres de texto, si el tamaño importa en absoluto), ¿cuál es la probabilidad de que el resumen MD5 de A sea igual al resumen MD5 de B y el resumen SHA1 de A sea? lo mismo que el resumen SHA1 de B? Es decir:
(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))
No asuma ninguna intención maliciosa, es decir, que los mensajes no se seleccionen con el objetivo de encontrar un choque. Solo quiero saber las probabilidades de que esto ocurra naturalmente.
Estoy pensando que las posibilidades son "astronómicamente bajas", pero no estoy seguro de cómo verificar esto.
Más información: el tamaño del grupo de posibles mensajes está restringido, pero es grande (varios cientos de millones). Las situaciones de paradoja de cumpleaños son exactamente lo que me preocupa.
Asumiendo una dispersión uniforme en el rango de hashes MD5 y SHA-1 para cadenas aleatorias (que no es el caso), y asumiendo que solo estamos hablando de dos cadenas y no estamos hablando de un grupo de cadenas (entonces evitamos la paradoja del cumpleaños) complejidades de tipo):
Un hash MD5 tiene 128 bits de ancho, y SHA-1 es 160. Con los supuestos anteriores, dos cadenas A y B tienen una probabilidad de colisión P si ambos hash colisionan. Asi que
P(both collide) = P(MD5 collides) * P(SHA-1 collides)
Y
P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)
Asi que
P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87
De nuevo, si tiene un conjunto de cadenas de caracteres y está tratando de determinar las probabilidades de colisiones con el conjunto, está en el dominio de la paradoja del cumpleaños y esta probabilidad que he calculado aquí no se aplica. Eso y los hashes no son tan uniformes como deberían ser. En realidad, vas a tener una tasa de colisión mucho más alta, pero aún será muy pequeña.
EDITAR
Como se trata de una situación de paradoja de cumpleaños, aplique la misma lógica que la solución a la paradoja del cumpleaños. Veámoslo desde el punto de vista de una sola función hash:
N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)
Supongamos que tenemos un buen número par de hashes como 2 ^ 29 (aproximadamente 530 millones).
P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)
En resumen, ni siquiera quiero pensar en calcular este número. Ni siquiera estoy seguro de cómo puedes calcularlo. Al menos necesitará una calculadora de precisión arbitraria que pueda manejar grandes factoriales sin morir.
Tenga en cuenta que las probabilidades seguirán una curva que comienza en casi 0 cuando N = 1 or 2 , y alcanzará 1 cuando N >= 2^288 , similar en forma a la de la página de Wikipedia para la paradoja del cumpleaños.
La paradoja del cumpleaños alcanza P = .5 cuando N = 23 . En otras palabras, la probabilidad de una colisión es del 50% cuando N es del 6% de S. Si eso escala (no estoy seguro si lo hace), significa que habrá un 50% de probabilidad de una colisión cuando tenga 6% de 2 ^ 288 hashes. 6% de 2 ^ 288 es alrededor de 2 ^ 284. Su valor de N (varios cientos de millones) no se acerca a eso. Es prácticamente insignificante en comparación con tu S, así que no creo que tengas nada de qué preocuparte. Las colisiones no son muy probables.
En general, cuando se eligen N elementos al azar, es más fácil calcular el número de colisiones esperado que la probabilidad de una colisión. Dado que el número esperado de colisiones no puede ser menor que la probabilidad de una colisión, con frecuencia se puede usar como un límite superior adecuado.
Supongamos que p es la probabilidad de que dos elementos escogidos al azar colisionen. Si seleccionamos N elementos aleatorios, entonces hay N * (N-1) / 2 par de elementos y, por lo tanto, el número esperado de colisiones es
p * N * (N-1) / 2.
Por ejemplo, si suponemos que la probabilidad de una colisión para MD5 y SHA1 es p = 2 -288 , incluso después de seleccionar aleatoriamente 2 100 elementos, solo esperamos alrededor de 2 -89 colisiones.
Otro ejemplo: si seleccionamos 2 30 elementos aleatorios y solo computamos el MD5. Suponiendo que una colisión entre dos hash MD5 es p = 2 -128, esto da un número esperado de 2 -59 para el número de colisiones. Por lo tanto, incluso la probabilidad de que el hash MD5 colisione para dos entradas ya es muy pequeña.
La respuesta elegida es incorrecta porque usa las probabilidades incorrectas. Pasé una buena parte del día investigando esto (puedes ver mi proceso de pensamiento en los comentarios a esa respuesta), y creo que la respuesta real es la siguiente (para el ataque de cumpleaños de mensajes un poco más grandes que los que estás hablando) :
2^-61 * 2^-18 = una colisión en una vez en 2 ^ 79.
Y eso es si está bien simplemente multiplicar estas probabilidades (no estoy seguro de eso).
Esto es factible (menos de un par de meses y cayendo cada año) por las súper computadoras de hoy.
Tenga en cuenta que esto se basa en grupos de mensajes suficientemente grandes (para que la paradoja del cumpleaños sea significativa). Este es también el escenario por el que dijiste que estabas preocupado.
Ahora, una situación diferente es encontrar una colisión para un par de valores hash (SHA1 y MD5) de un mensaje específico . Esto te saca del territorio de la paradoja bday y es de órdenes de magnitud más difíciles. No estoy seguro si eso es 2 ^ (- 61 * 2) * 2 ^ (- 18 * 2) o algo más. Si alguien sabe qué es eso, publique un comentario en esta respuesta (sería muy apreciado).
Ahora preguntas:
Dado dos mensajes diferentes, A y B (tal vez 20-80 caracteres de texto, si el tamaño importa en absoluto)
Sí, el tamaño sí importa Haga clic en el enlace a la figura 2 ^ -18 y verá que ese valor es para dos bloques de entrada. En MD5, un bloque de entrada es de 512 bytes. 20-80 caracteres de texto es demasiado pequeño para eso, y el valor de bloque único es 2 ^ 41.
Por lo tanto, para esa cantidad de datos, obtienes 2 ^ -61 (creo) * 2 ^ -41 = 2 ^ -102.
Entonces para ese tamaño parece seguro (el enlace contiene la figura del hashrate de bitcoin actual dos veces de SHA256: 46626.93 TH / seg).
Si el tamaño del mensaje no está restringido, la probabilidad se aproxima al 100% de forma asintótica, ya que hay una cantidad infinita de mensajes posibles y un número finito de hashes posibles.
(nota: editar a pregunta hace que esto sea menos relevante ahora)
una adición a la publicación de Welbog:
Las relaciones de factoriales grandes se pueden calcular sin utilizar aritmética de precisión arbitraria, utilizando la aproximación de Stirling :
¡norte! ≈ sqrt (2πn) * (n / e) n
Entonces (S!) / (S ^ N * (S - N)!) ≈ sqrt (2πS) / sqrt (2π (SN)) * (S / e) S / ((SN) / e) SN / S N
= sqrt (S / (SN)) * (S / (SN)) SN * e- N
= sqrt (1 + α) * (1 + α) SN * e- N donde α = N / (SN) es pequeño.
La aproximación (1 + a / n) nx ≈ e ax se cumple como n → ∞ (o al menos se vuelve muy grande)
** entonces esto significa (1+ (N / (SN))) SN ≈ e N para SN >> N.
Entonces yo esperaría que
(S!) / (S ^ N * (S - N)!) ≈ sqrt (1 + N / (SN)) * e N * e -N = sqrt (1 + N / (SN)) para SN >> NORTE....
excepto que esto es mayor que 1 ... entonces una de las aproximaciones no es lo suficientemente buena. :pag
(** advertencia: N / S tiene que ser pequeño: para N = 22, S = 365 esto está desactivado por un factor de 2)