Aprende programación






23 ago 2009

Experimento práctico - ¡¡¡ Vamos a romper MD5 !!!


En esta ocasión me gustaría proponer un experimento para que podais participar: ¡Romper el algoritmo MD5!. Bueno ... de hecho, ya está roto. Hace ya unos años que explicaron que se encontraban colisiones. Me gustaría romperlo de una manera muy particular. Para el que no entienda de que estoy hablando, vamos con un poco de historia.

Lo primero que creo que debo explicar es:
"¿Que es MD5?".
Este es un algoritmo que permite crear un código de 128 bits a partir de un documento, texto o fichero. Las propiedades teóricas de este código es una función sin inversa, es decir a partir del código no se puede sacar el documento o texto original. Por ello se suele utilizar para guardar las claves, guardando en vez de la clave en texto plano, el código obtenido. Otra supuesta propiedad que tiene es que su clave es unica. Es decir, dos documentos no pueden generar la misma clave. Por ello, se utiliza para comprobar que cuando descargamos un documento de internet podamos verificar que todo ha llegado y no he descargado otro que alguien haya modificado con un virus o algo parecido.

Pues bién, esta última propiedad de dos documentos siempre generan claves diferentes es lo que hay en entredicho. En realidad hay un ley matemática que en resumidas cuentas dice "de donde no hay no se puede sacar". Esto significa que es muy utópico que en 128 bits seamos capaces de representar todos los documentos que podamos generar sin que se repitan. Intentar que todos los posibles documentos que ocupan megas se representen en 128 bits, incluso en 160 como SHA1, no tiene razón matemática por la limitación de la clave. Si es cierto que cuantos más bits tiene la clave, menos probabilidad, pero no es imposible.

¿De que noticia está basada el experimento?
El experimento que me gustaría proponer tiene como referencia una noticia del 2006 en el que un australiano recurrió una multa de tráfico. El caso es que la defensa alegó que la foto de la policía estaba modificada por haber cambiado la matrícula del coche. En ese momento los técnicos de la acusación ("policia") comentaron que eso era imposible porque guardaban también la clave Hash(MD5) de la imagen capturada. La parte de la defensa les pidieron que demostrarán que era imposible crear claves iguales a partir de diferentes imagenes, pero estos no supieron demostrar esa propiedad y el hombre se libró de pagar la multa. (No sé si es verídico pero esta noticia apareció en varios sitios).
http://www.geonoticias.com/noticias/software/usar-md5-para-multas-de-tr%E1fico.html

¿En que consiste el experimento?
Pues bién, me gustaría hacer eso mismo. He preparado dos imagenes del mismo coche pero uno con la matricula manipulada con el gimp y el objetivo es precisamente este, conseguir que las dos imagenes tengan el mismo MD5 sin que la imagen del coche quede alterada a la vista.



¿Y como lo podemos conseguir?
En los ficheros que podeis descargar teneis dos imagenes BMP de 24 bits con los coches. Estos ficheros almacenan la información rojo-verde-azul uno en cada byte. Un color por lo tanto se representa en ocho bits y segun sea su intensidad de color el valor del byte va incrementando.

Ej: Imaginemos que tomamos un byte rojo. Si el valor que tiene es '00000000' significa que no existe rojo en ese pixel y si el valor que tiene es '11111111' significa que tiene la tonalidad roja al máximo. Mezclando este byte con los otros dos bytes es cuando podemos crear otros colores. Ahora bién, no todos los bits tienen la misma importancia. Los bits de menos peso prácticamente son inapreciables al ojo humano, y eso es lo que vamos a aprovechar. Si tenemos el siguiente byte '11111111' y lo cambiamos por '11111110' vas a comprobar que el color es el mismo. En realidad no lo es, pero tu no lo detectarás. Incluso el segundo bit también podríamos cambiarlo '11111111' por '11111100' y seguirás viendo el mismo color.

Pues bién, he puesto a disposición para que podais descargar un algoritmo en java que hace precisamente esto. Comprueba que el MD5 de la imagen A y la B sean iguales. Si no lo es, modifica 2 bits aleatorios en la imagen de los que tienen menos peso y vuelve a comprobar si coincide el MD5 de la imagen A y B.

¿Y es posible que exista una colisión matematicamente?.
Las imagenes de estos coches tienen un tamaño de 450x300. Esto significa que hay 135000 pixeles. Cada pixel tiene 3 colores RGB y de cada color modificamos los ultimos 2 bits -> 135000 * 3 * 2=810000 bits que podemos estar cambiando. Es decir, que el número de documentos posibles que podemos generar es 2^810000 que es muy superior a 2^128 del MD5.

¿Y en cuanto tiempo se puede obtener?
Aquí es donde está la pega. Este tipo de algoritmos son lo que se denomina "por fuerza bruta". Es decir, probar cosas hasta que sale. Ahora mismo en el código hay un sleep de 50 milisegundos para que si lo poneis funcionando, podais estar haciendo más cosas y el ordenador no se quede colgado. Este valor lo podeis cambiar. Si lo dejais como está se supone que prueba unos 14.400.000 casos al día. Es decir que para comprobar todos los casos tardaría unos 2^128/((14.5 millones)*365) = 64741698424836085133823174929,941 años. (Creo que es más probable acertar con el salvapantallas de buscar vida extraterrestre). Yo en su día lo puse durante 1 semana y finalmente lo quité. Ahora lo he vuelto a intentar a ver si hay suerte :).

En todo caso, es más interesante entender como funciona el algoritmo MD5 y atacar por ahí. Así que si quereis intentarlo de otro modo, adelante!!.

Os dejo aquí el algoritmo de fuerza bruta por lo quereis probar suerte y quien quiera usar otros métodos, perfecto. Quién consiga crear el mismo MD5 le publicaremos algún tipo de noticia en su nombre y lo intentaremos promocionar por meneame y webs parecidas. Creo, aunque me puedo equivocar, que este experimento concreto no se ha hecho en el mundo, al menos hecho público, por lo que lo veo muy interesante.


7 comentarios:

  1. jeje interesante experimento jorge, yo siempre tuve esa de duda de que tan confiable era un hash de n-bits de un archivo que es muuuuuchisimo mas grande. Y siempre algo me dijo de que por muy rebuscado que sea la funcion de hashing algun codigo se debe repetir, pero obviamente como tu experimiento lo demuestra la probabilidad de que pase es muuuy elabada

    saludos

    att. Marioko! xD

    ResponderEliminar
  2. :). Aproximadamente el código que genera la foto primera, utilizando los bits que comento, se puede obtener de 2^(810000-128) = 2^809872 formas diferentes en la imagen 2.

    Normalmente siguen la regla exponencial. Un hash de 4 bits=16 combinaciones, si queremos buscarlo modificando 5 bits=32 combinaciones veremos que hay 2 formas diferentes. 2^(5-4) = 2. Con 6 bits =64 aparecerá de 4 formas diferentes 2^(6-4). Así que animo a buscarlo! Hay muchas formas posibles!.

    Si buscais en google MD5 Collision Demo vereis un ejemplo que han hecho con ejecutables hello.exe y erase.exe. Sin embargo, con fotos modificando la matricula, no he visto nada. Comentar que cuanto más pequeños son los ficheros más fácil es hacer ingenieria inversa por lo que nuestro experimento, en caso de conseguirlo, tiene más mérito :)

    A ver se puede demostrar lo que vale la comunidad hispano hablante ... y estamos a la vanguardia!

    ResponderEliminar
  3. Buenas, Me parece también interesante la conversación que siguen en meneame como una posible resolución al problema. Pongo el link:
    http://meneame.net/story/experimento-practico-vamos-romper-md5

    ResponderEliminar
  4. Estaría bien que se generase un fichero de texto o similar para que, en caso de cerrarlo, al iniciarlo de nuevo continuase donde estaba.

    ResponderEliminar
  5. Buenas, En principio no lleva un orden establecido. Los bits que va cambiando se realizan de manera aleatoria. De esta manera si parais la aplicación y la volveis a arrancar es poco o nada probable que repitais la secuencia.

    Saludos, Jorge

    ResponderEliminar
  6. Yo les recomiendo este otro sitio que me funciono mejor en 2 contraseñas que buscaba http://md5.unidadlocal.com
    espero les ayude como a mi

    ResponderEliminar
  7. Interesante, pero si el algoritmo altera 2 bits aleatoriamente en cada pasada es posible que aunque dejes corriendo el programa durante más tiempo del que en teoría se requiere y aun así no garantizas que cada modificación sea única ya que aunque tienes un gran número de opciones, estas siguen siendo limitadas y es probable que en el algoritmo aleatorio vuelva a repetirse una configuración pasada. Es como decir que tengo un dado de 2^810000 caras y que lo lanzaré 2^810000 veces pensando que una misma cara no caerá más de una vez.

    En mi opinión este algoritmo para ser efectivo debería usar la fuerza bruta de forma progresiva en vez de aleatoria, de ser así se tendría que esperar toda una eternidad hasta terminar, mientras que si es aleatorio teóricamente es posible encontrar varias colisiones sin llegar a completar las 2^810000 pasadas, o incluso, como es aleatorio puede ser que siempre se repita la misma condición. El azar no dice que una moneda debe caer en cara o cruz, pero tampoco niega que puede caer X lado durante toda la eternidad.

    ResponderEliminar