Para cada uno de nuestros activos binarios generamos un hash MD5. Esto se usa para verificar si un determinado 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?
hash
cryptography
md5
hash-collision
Lieven Cardoen
fuente
fuente
MD5 es una función hash , así que sí, dos cadenas diferentes pueden generar absolutamente códigos MD5 en colisión.
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. Sin embargo, el número de cadenas (de cualquier longitud) es definitivamente ilimitado, por lo que lógicamente se deduce que debe haber colisiones.
fuente
Sí, es posible. De hecho, este es un problema de cumpleaños . Sin embargo, la probabilidad de que dos cadenas elegidas al azar tengan el mismo hash MD5 es muy baja.
Vea esta y esta pregunta para ver ejemplos.
fuente
Sí, por supuesto: los hash MD5 tienen una longitud finita, pero hay un número infinito de cadenas de caracteres posibles que pueden tener hash MD5.
fuente
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:
Generan una suma SHA-1 diferente, pero el mismo valor 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:
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 artículo ).
Otra prueba:
Diferente suma SHA-1, el mismo hash MD5.
La diferencia está en un byte:
El ejemplo anterior está adaptado de Tao Xie y Dengguo Feng: Construct MD5 Collisions Using Just A Single Block Of Message , 2010.
Relacionado:
fuente
Sí, es posible. Se llama colisión Hash .
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 conocer.
fuente
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 1 a 1 (sino unidireccional) entre el conjunto inicial y el resultante.
Bijection en wikipedia
EDITAR: para ser completo existen funciones hash inyectivas: se llama hash perfecto .
fuente
¡Sí lo es! La colisión será una posibilidad (aunque el riesgo es muy pequeño). Si no, ¡tendría un método de compresión bastante efectivo!
EDITAR : Como dice Konrad Rudolph: Un conjunto de entrada potencialmente ilimitado convertido en un conjunto finito de salida (32 caracteres hexadecimales) dará como resultado un número infinito de colisiones.
fuente
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 se encuentre con colisiones: he usado MD5 para tomar huellas digitales de cientos de miles de archivos de imagen de varios formatos de imagen (JPG, mapa de bits, PNG, sin formato) 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 que una entrada dé como resultado la misma salida de dos algoritmos diferentes es casi imposible.
fuente
Me doy cuenta de que esto es antiguo, pero pensé en contribuir 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 sustancial.
Lo que he hecho es juntar algunos hash en función de la cadena de entrada para obtener una cadena resultante mucho más larga que considere su hash ...
Entonces mi pseudocódigo para esto es:
Eso es prácticamente improbabilidad 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 los ciclos de computación) ...
De acuerdo, no es la solución más limpia, pero esto ahora le permite jugar mucho más con la poca frecuencia con la que se encontrará con una colisión. Hasta el punto que 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 poco frecuente 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. Si bien podría dedicar mucho tiempo a la cantidad de combinaciones que esto podría obtener, diré que, en teoría, lo llevará SIGNIFICATIVAMENTE más que el número citado anteriormente de
Probablemente unos cien dígitos más. El máximo teórico que esto podría darte sería
Posible número de cadenas resultantes:
528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336
fuente
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 de hash en mi proyecto. Estoy usando la envoltura de Python de xxhash para hacer hash. Enlace: https://github.com/ewencp/pyhashxx
Causó un problema de almacenamiento en caché muy complicado en el sistema, luego finalmente descubrí que es una colisión de hash.
fuente