Crea tus propias colisiones MD5

Question

Estoy haciendo una presentación sobre las colisiones MD5 y me gustaría dar a las personas una idea de la probabilidad de una colisión.

Sería bueno tener dos bloques de texto que coincidan con la misma cosa, y explicar cuántas combinaciones de [a-zA-Z] se necesitaban antes de golpear una colisión.

La respuesta obvia es hash todas las combinaciones posibles hasta alcanzar dos hashes iguales. Entonces, ¿cómo vas a codificar esto? Como experimento rápido intenté hacer hash cada combinación de 5 columnas de [A-Z], almacenar esto en una tabla hash .net y capturar la excepción de colisión. Dos problemas con esto: la tabla de aciertos finalmente termina, y estoy seguro de que necesitaré MUCHOS más caracteres.

Obviamente, esta estructura de datos es demasiado grande para manejar en la memoria, por lo que ahora tendré que obtener una base de datos involucrada. También suena como un buen proyecto para probar azul, un poco como these guys.

¿Alguien me puede indicar en una dirección eficiente manera de hacer esto?

Answer 1

Estas dos siguientes 128 secuencias de bytes diferentes hash al mismo:

MD5 Hash: 79054025255fb1a26e4bc422aef54eb4

Las diferencias a continuación se ponen de relieve (negrita). Lo siento es algo difícil de ver.

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 

y

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 

La visualización de la colisión/Bloque 1 (Fuente: Links.Org)

La visualización de la colisión/Bloque 2 (Fuente: Links.Org)

Answer 2

Me gustaría echar un vistazo a Hashcash. Con un algoritmo hash efectivo, como md5, el tiempo para calcular una colisión a exponencial con el número de bits. Lo que Hashcash hace es calcular colisiones parciales. Es decir, una coincidencia de, digamos, los 16 bits más bajos del hash. Para obtener los 16 bits más bajos para que coincidan, uno debería intentar mezclar 2^15 combinaciones diferentes en promedio. Si sabe cuánto tiempo lleva una colisión de 16, 24 o 32 bits, puede calcular fácilmente el tiempo para un mayor número de bits.

Answer 3

Si está hablando de la probabilidad de una colisión directa (una donde no hay un intento deliberado de causarla), entonces se sentirá decepcionado: tendría que generar un promedio de 2^64 planos antes puede esperar ver una colisión, y eso es mucho más de lo que podrá hacer en un tiempo razonable (o incluso, incluso un _un_ razonable).

Si está buscando demostrar la dificultad de crear deliberadamente una colisión, otras respuestas ya lo han demostrado. La restricción adicional de requerir que las cadenas sean completamente textuales hace que incluso esos enfoques sean en gran medida poco prácticos.

Answer 4

El objetivo de tales algoritmos es que las colisiones son extremadamente improbables.No va a generar uno por casualidad: su máquina casi seguramente morirá antes de que tenga éxito. ¡El objetivo de usar un hash desaparecería si pudiéramos generar colisiones de manera razonable!

Answer 5

Es difícil hacerlo solo con archivos de texto, AFAIK. Puede obtener algunas colisiones, pero tenerlas también desde [a-zA-Z] no es fácil (todavía).

Por otro lado, si solo desea dos archivos "con sentido" con el mismo hash, puede hacerlo con algo así como, por ejemplo, PostScript: tener diferentes blobs binarios que causan la colisión y usar una expresión condicional para mostrar diferentes resultados en consecuencia.

Véase p. this problem (la parte H2) y solution. Por ejemplo, this PS file y this one tienen el mismo MD5sum pero ambos son archivos PostScript bien formados que tienen textos completamente diferentes en ellos cuando los abre.