como - hash md5 archivo
¿Pueden dos cadenas diferentes generar el mismo código hash MD5? (11)
Para cada uno de nuestros activos binarios generamos un hash MD5. Esto se usa para verificar si un cierto activo binario ya está en nuestra aplicación. Pero es posible que dos activos binarios diferentes generen el mismo hash MD5. Entonces, ¿es posible que dos cadenas diferentes generen el mismo hash MD5?
¡Sí lo es! La colisión será una posibilidad (aunque, el riesgo es muy pequeño). Si no, ¡tendrías un método de compresión bastante efectivo!
EDITAR : Como dice Konrad Rudolph: Un conjunto de entrada potencialmente ilimitado convertido a un conjunto finito de salida (32 caracteres hexadecimales) dará como resultado un número interminable de colisiones.
Como han dicho otras personas, sí, puede haber colisiones entre dos entradas diferentes. Sin embargo, en su caso de uso, no veo que eso sea un problema. Dudo mucho que te encuentres con colisiones: utilicé MD5 para tomar huellas dactilares de cientos de miles de archivos de imágenes de varios formatos de imagen (JPG, mapa de bits, PNG, sin procesar) 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 posibilidades de que una entrada resulte en la misma salida de dos algoritmos diferentes es casi imposible.
Creo que debemos tener cuidado al elegir el algoritmo hash según nuestro requisito, ya que las colisiones hash no son tan raras como esperaba. Recientemente encontré un caso muy simple de colisión hash en mi proyecto. Estoy usando el contenedor de Python de xxhash para hash. Enlace: https://github.com/ewencp/pyhashxx
s1 = ''mdsAnalysisResult105588''
s2 = ''mdsAlertCompleteResult360224''
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266
Causó un problema de caché muy complicado en el sistema, luego finalmente descubrí que se trataba de una colisión hash.
MD5 es una función hash , así que sí, dos cadenas diferentes pueden generar códigos MD5 colisionantes.
En particular, tenga en cuenta que los códigos MD5 tienen una longitud fija, por lo que la cantidad posible de códigos MD5 es limitada. Sin embargo, el número de cadenas (de cualquier longitud) es definitivamente ilimitado, por lo que lógicamente se deduce que debe haber colisiones.
Me doy cuenta de que esto es antiguo, pero pensé que contribuiría con mi solución. Hay 2 ^ 128 posibles combinaciones de hash. Y así una probabilidad de 2 ^ 64 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 importante.
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 consideras tu hash ...
Entonces mi pseudo-código para esto es:
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
Eso es una improbabilidad práctica de una colisión. Pero si quieres ser súper paranoico y no puedes tenerlo, el espacio de almacenamiento no es un problema (ni los ciclos informáticos) ...
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
& Hash(Reverse(SpellOutLengthWithWords(Length(string))))
& Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))
De acuerdo, no es la solución más limpia, pero esto ahora te hace jugar mucho más con la poca frecuencia con la que te encontrarás en una colisión. Hasta el punto, podría asumir la 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 "infalible", pero es tan poco probable que suceda que se adapte a la necesidad.
Ahora las combinaciones posibles aumentan significativamente. Si bien podrías pasar mucho tiempo pensando en cuántas combinaciones podrías obtener, te diré en teoría que te deja SIGNIFICATIVAMENTE más que el número mencionado arriba.
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
Posible número de cadenas resultantes:
528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336
Para un conjunto de miles de millones de activos, las posibilidades de colisiones aleatorias son insignificantemente pequeñas , nada de lo que deba preocuparse. Teniendo en cuenta la paradoja del cumpleaños , dado un conjunto de 2 ^ 64 (o 18,446,744,073,709,551,616) activos, la probabilidad de una sola colisión MD5 dentro de este conjunto es del 50%. En esta escala, probablemente superarías a Google en términos de capacidad de almacenamiento.
Sin embargo, debido a que la función hash MD5 se ha roto (es vulnerable a un ataque de colisión ), cualquier atacante determinado puede producir 2 activos colisionantes en cuestión de segundos con la potencia de la CPU. Por lo tanto, si desea usar MD5, asegúrese de que dicho atacante no comprometa la seguridad de su aplicación.
Además, considere las ramificaciones si un atacante puede forzar una colisión a un activo existente en su base de datos. Si bien no existen ataques conocidos (ataques de preimagen ) contra MD5 (a partir de 2011), podría ser posible al ampliar la investigación actual sobre los ataques de colisión.
Si esto resulta ser un problema, sugiero consultar la serie SHA-2 de funciones hash (SHA-256, SHA-384 y SHA-512). La desventaja es que es un poco más lento y tiene una salida hash más larga.
Sí, es posible que dos cadenas diferentes puedan generar el mismo código hash MD5.
Aquí hay una prueba simple que usa un mensaje binario muy similar en una 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 diferentes SHA-1 suma, pero el mismo valor de hash MD5. En segundo lugar, las cadenas 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 anterior de colisión está tomado de Marc Stevens: Colisión de bloque único para MD5 , 2012; él explica su método, con el 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
Diferente suma SHA-1, 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: Construct MD5 Collisions usando Just A Single Block of Message , 2010.
Relacionado:
Sí, es posible. Este 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.
Sí, es posible. Se llama colisión Hash .
Una vez dicho esto, los 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.
Sí, por supuesto: los hashes MD5 tienen una longitud finita, pero hay un número infinito de posibles cadenas de caracteres que pueden tener hash MD5.
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 sola vía) entre el conjunto inicial y el resultante.
EDITAR: para completar las funciones hash injective existen: se llama hashing perfecto .