algorithm - que - Crea tus propias colisiones MD5
que es sha en informatica (5)
Estoy haciendo una presentación sobre las colisiones MD5 y me gustaría darles 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 cada combinación posible hasta que golpee dos hashes de la misma. Entonces, ¿cómo vas a codificar esto? Como experimento rápido, probé hash cada combinación de 5 columnas de [AZ], almacenando esto en una tabla hash .net y capturando 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 memoria, así que ahora tendré que involucrar una base de datos. También suena como un buen proyecto para probar el azul, un poco como estos tipos .
¿Alguien puede dirigirme hacia una manera eficiente de hacer esto?
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!
Es difícil hacerlo solo con archivos de texto, AFAIK. Puedes obtener algunas colisiones, pero que también sean de [a-zA-Z] no es fácil (todavía).
Por otro lado, si solo quieres dos archivos "con sentido" con el mismo hash, puedes hacerlo con algo 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.
Ver, por ejemplo, este problema (la parte H2) y la solution . Por ejemplo, este archivo PS y este tienen el mismo MD5sum pero ambos son archivos PostScript bien formados que tienen textos completamente diferentes en ellos cuando los abre.
Estos siguen dos secuencias de 128 bytes diferentes hash al mismo:
Hash MD5 : 79054025255fb1a26e4bc422aef54eb4
Las diferencias a continuación están resaltadas (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 / bloque1 (Fuente: Links.Org )
La visualización de la colisión / bloque2 (Fuente: Links.Org )
Si está hablando de la probabilidad de una colisión directa (una en la que no hay un intento deliberado de causarla), se decepcionará: tendría que generar un promedio de 2 ^ 64 palabras simples antes de poder esperarlo. 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.
Hashcash 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.