¿Pueden dos cadenas diferentes generar el mismo código hash MD5?

MD5 es una función hash – así que sí, dos cadenas diferentes pueden generar absolutamente códigos MD5 colisionantes.

En particular, tenga en cuenta que los códigos MD5 tienen una longitud fija, por lo que el número posible de códigos MD5 es limitado. El número de cadenas (de cualquier longitud), sin embargo, es definitivamente ilimitado por lo que lógicamente se sigue que debe ser colisiones.

Sí, es posible. Esto es de hecho un problema de cumpleaños . Sin embargo, la probabilidad de que dos cadenas elegidas al azar tengan el mismo hash MD5 es muy baja.

Ver thisy this preguntas para ejemplos.

Sí, por supuesto: los hashes MD5 tienen una longitud finita, pero hay un número infinito de cadenas de caracteres posibles que pueden ser hashes MD5.

Sí, es posible que dos cadenas diferentes puedan generar el mismo código hash MD5.

Aquí hay una prueba simple usando un mensaje binario muy similar en cadena hexadecimal:

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc  -
008ee33a9d58b51cfeb425b0959121c9

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca  -
008ee33a9d58b51cfeb425b0959121c9

Generan una suma SHA-1 diferente, pero el mismo valor hash MD5. En segundo lugar, las cuerdas son muy similares, por lo que es difícil encontrar la diferencia entre ellas.

La diferencia se puede encontrar con el siguiente comando:

$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63  2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
 af
 bf
 a2
-00
+02
 a8
 28
 4b
@@ -53,7 +53,7 @@
 6d
 a0
 d1
-55
+d5
 5d
 83
 60

El ejemplo de colisión anterior está tomado de Marc Stevens: Colisión de bloque único para MD5, 2012; explica su método, con código fuente ( enlace alternativo al documento).

Otra prueba:

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82  -
cee9a457e790cf20d4bdaa6d69f01e41

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb  -
cee9a457e790cf20d4bdaa6d69f01e41

Suma SHA-1 diferente, el mismo hash MD5.

La diferencia está en un byte:

$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63  2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
 03
 65
 9e
-70
+74
 4f
 85
 34
@@ -41,7 +41,7 @@
 a3
 f4
 15
-5c
+dc
 bb
 86
 07

El ejemplo anterior está adaptado de Tao Xie y Dengguo Feng: Construir Colisiones MD5 Usando Solo Un Bloque De Mensaje, 2010.

Relacionado:

• Son hay dos cadenas conocidas que tienen el mismo valor de hash MD5? at Crypto.SE

Sí, es posible. Se llama una colisión Hash .

Dicho esto, algoritmos como MD5 están diseñados para minimizar la probabilidad de una colisión.

La entrada de Wikipedia en MD5 explica algunas vulnerabilidades en MD5, que debe tener en cuenta.

Solo para ser más informativo. Desde un punto de vista matemático, las funciones Hash no son inyectivas.
Significa que no hay una relación de 1 a 1 (sino de una manera) entre el conjunto inicial y el resultante.

Biyección en wikipedia

EDITAR: para ser funciones hash inyectivas completas existen: se llama Hashing perfecto.

Sí, lo es! La colisión será una posibilidad (aunque el riesgo es muy pequeño). Si no, usted tendría un método de compresión bastante eficaz!

EDITAR : Como dice Konrad Rudolph: Un conjunto potencialmente ilimitado de entrada convertido en un conjunto finito de salida (32 caracteres hexadecimales) resultará en un número infinito de colisiones.

Como otras personas han dicho, sí, puede haber colisiones entre dos entradas diferentes. Sin embargo, en su caso de uso, no veo que sea un problema. Dudo mucho que se encuentre con colisiones: He utilizado MD5 para tomar huellas digitales de cientos de miles de archivos de imagen de varios formatos de imagen (JPG, mapa de bits, PNG, raw) en un trabajo anterior y no tuve una colisión.

Sin embargo, si está tratando de tomar huellas dactilares de algún tipo de datos, tal vez podría usar dos algoritmos hash: las probabilidades de una entrada que resulta en la misma salida de dos algoritmos diferentes es casi imposible.

Creo que debemos tener cuidado al elegir el algoritmo de hash según nuestro requisito, ya que las colisiones de hash no son tan raras como esperaba. Recientemente encontré un caso muy simple de colisión de hash en mi proyecto. Estoy usando Python wrapper de xxhash para hashing. Enlace: https://github.com/ewencp/pyhashxx

s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266

Causó un problema de almacenamiento en caché muy complicado en el sistema, luego finalmente descubrí que es una colisión de hash.

Me doy cuenta de que esto es viejo, pero pensé que aportaría mi solución. Hay 2^128 combinaciones posibles de hash. Y por lo tanto un 2^64 probabilidad de una paradoja de cumpleaños. Si bien la solución a continuación no eliminará la posibilidad de colisiones, seguramente reducirá el riesgo en una cantidad muy sustancial.

2^64 = 18,446,744,073,709,500,000 possible combinations

Lo que he hecho es juntar algunos hashes basados en la cadena de entrada para obtener una cadena resultante mucho más larga que consideres tu hash...

Así que mi pseudo-código para esto es:

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))

Eso es la improbabilidad práctica de una colisión. Pero si quieres ser súper paranoico y no puedes permitir que suceda, y el espacio de almacenamiento no es un problema (ni lo es los ciclos de computación)...

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string)) 
         & Hash(Reverse(SpellOutLengthWithWords(Length(string)))) 
         & Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))

Está bien, no es la solución más limpia, pero esto ahora te da mucho más juego con la poca frecuencia con la que te toparás con una colisión. Hasta el punto de que podría suponer imposibilidad en todos los sentidos realistas del término.

Por mi bien, creo que la posibilidad de una colisión es lo suficientemente infrecuente como para considerar que esto no es" seguro", pero es tan poco probable que suceda que se adapte a la necesidad.

Ahora las combinaciones posibles aumentan significativamente. Mientras que usted podría pasar mucho tiempo en la cantidad de combinaciones que esto podría conseguir, voy a decir que en teoría te aterriza SIGNIFICATIVAMENTE más que el número citado anteriormente de

2^64 (or 18,446,744,073,709,551,616) 

Probablemente por cien dígitos más o menos. El máximo teórico que esto podría darle sería

Número posible de resultados cadenas:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336