math - online - md5 vulnerable
¿Cuál es el par de cuerdas más corto que causa una colisión MD5? (3)
Actualizar
Irónicamente, unas semanas después de publicar la respuesta anterior, dos investigadores chinos, Tao Xie y Dengguo Feng, publicaron una nueva colisión de bloque único para MD5 . No estaba al tanto de ese papel hasta ahora. Un solo bloque MD5 significa que el tamaño de entrada es de 64 bytes o 512 bits. Tenga en cuenta que las entradas son básicamente las mismas, que difieren solo en 2 bits .
Su metodología no se publicará hasta enero de 2013, pero su colisión se puede verificar ahora, usando números del periódico:
>>> from array import array
>>> from hashlib import md5
>>> input1 = array(''I'', [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])
>>> input2 = array(''I'', [x^y for x,y in zip(input1,
[0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])
>>> input1 == input2
False
>>> md5(input1).hexdigest()
''cee9a457e790cf20d4bdaa6d69f01e41''
>>> md5(input2).hexdigest()
''cee9a457e790cf20d4bdaa6d69f01e41''
Actualización: El documento ha sido publicado en marzo de 2013: Tao Xie y Fanbao Liu y Dengguo Feng - Ataque de colisión rápida en MD5
Sin embargo, si tiene más espacio para jugar, las colisiones de algunos kilobytes son MUCHO más rápidas de calcular, se pueden calcular en cuestión de horas en CUALQUIER computadora normal.
Respuesta anterior
La colisión más corta anterior usó al menos dos bloques MD5 por valor de entrada, es decir, 128 bytes, 1024 bits. Un prefijo en el primer bloque puede ser elegido arbitrariamente por el atacante, el resto se computará y aparecerá como un galimatías.
Aquí hay un ejemplo de dos entradas colisionantes diferentes, puedes probarlo tú mismo en Python:
>>> from binascii import unhexlify
>>> from hashlib import md5
>>> input1 = ''Oded Goldreich/nOded Goldreich/nOded Goldreich/nOded Go'' + unhexlify(
... ''d8050d0019bb9318924caa96dce35cb835b349e144e98c50c22cf461244a4064bf1afaecc582''
... ''0d428ad38d6bec89a5ad51e29063dd79b16cf67c12978647f5af123de3acf844085cd025b956'')
>>> len(input1)
128
>>> md5(input1).hexdigest()
''d320b6433d8ebc1ac65711705721c2e1''
>>> input2 = ''Neal Koblitz/nNeal Koblitz/nNeal Koblitz/nNeal Koblitz/n'' + unhexlify(
... ''75b80e0035f3d2c909af1baddce35cb835b349e144e88c50c22cf461244a40e4bf1afaecc582''
... ''0d428ad38d6bec89a5ad51e29063dd79b16cf6fc11978647f5af123de3acf84408dcd025b956'')
>>> md5(input2).hexdigest()
''d320b6433d8ebc1ac65711705721c2e1''
La generación de estas dos entradas en particular tomó 2 días en un clúster de 215 nodos de Playstation 3, por Mark Stevens :)
¿Hasta qué longitud de cadena es posible usar MD5 como hash sin tener que preocuparse por la posibilidad de una colisión?
Esto se calcularía supuestamente generando un hash MD5 para cada cadena posible en un conjunto de caracteres particular, en longitud creciente, hasta que aparezca un hash por segunda vez (una colisión). La longitud máxima posible de una cuerda sin colisión sería entonces un carácter menos que el más largo del par que colisiona.
¿Ya se ha probado para MD5, SHA1, etc.?
Dudo que haya una longitud útil en la que no haya posibles colisiones. Esos algoritmos no se usan realmente para ese propósito. Intenta ser único para pequeños cambios en los datos (como archivos dañados) en lugar de ser únicos en todos los conjuntos de datos posibles.
Las matemáticas de la paradoja del cumpleaños hacen que el punto de inflexión de la probabilidad de colisión sea aproximadamente sqrt (N), donde N es el número de intervalos distintos en la función hash, por lo que para un hash de 128 bits, a medida que obtienes 64 bits estás es moderadamente probable que tenga 1 colisión. Así que supongo que para el conjunto completo de cadenas de 8 bytes es bastante probable que haya una colisión, y para las cadenas de 9 bytes es muy probable.
editar: esto supone que el algoritmo de hash MD5 causa una asignación de bytes de entrada a hash de salida que está cerca de "aleatorio". (frente a uno que distribuye cadenas de forma más uniforme entre el conjunto de hashes posibles, en cuyo caso sería más cercano a 16 bytes).
También para una respuesta numérica más específica, si nos fijamos en una de las aproximaciones para calcular la probabilidad de colisión, obtienes
p (k) ≈ 1 - e -k (k-1) / (2 * 2 128 ) donde k = el tamaño del espacio de posibles entradas = 2 m donde la cadena de bytes de entrada tiene m bits de longitud.
el conjunto de cadenas de 8 bytes: p (2 64 ) ≈ 1 - e -0.5 ≈ 0.3935
el conjunto de cadenas de 9 bytes: p (2 72 ) ≈ 1 - e -2 144 / (2 * 2 128 ) = 1 - e -2 15 = 1 - e -32768 ≈ 1
También tenga en cuenta que estos asumen el conjunto completo de cadenas de m / 8 bytes. Si solo usa caracteres alfanuméricos, necesitaría más bytes para obtener una colisión probable.