Crea tu propia colisión MD5
Publicado por Pedro C. el 15-10-2012
Seguro que muchos de los que habeis asistido a los Cursos o nos leeis en las listas, habreis oido hablar de las colisiones MD5 y de las consolas, GPU’s y demás para conseguirlas. Hoy con un simple equipo actual, en muy poco tiempo la podemos generar.
En esta entrada, vamos a ver cómo generar una colisión MD5 en un fichero binario para Microsoft© Windows o GNU/Linux pero realmente, son dos ficheros con comportamientos completamente opuestos donde comparten el mismo hash MD5.
Como ya hemos hablado hasta la saciedad, el MD5 está roto. En Marzo de 2005 (no ha llovido nada, eh?) Xiaoyun Wang y Hongbo Yu de la Universidad de China, publicaron un artículo donde donde se describía el algoritmo que encontraba 2 secuencias diferentes de 128 bytes con el mismo hash MD5.
Un bloque de los más famosos es el siguiente:
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70
Junto con el siguiente:
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70
Busca las 6 diferencias!!! ¿Dónde está Wally? :-D
Los dos bloques obtienen el mismo hash MD5:
79054025255fb1a26e4bc422aef54eb4
Ben Laurie en su web visualiza de forma gráfica la colisión y para el que quiera ver una explicación de la función hash, Steve Frield’s en su blog personal lo representa "for dummies".
A partir de dicho estudio, os podeis imaginar la cantidad de ficheros iguales que han salido ya que permite crear ficheros de longitud variable con los mismos hashes MD5 y que varien sólo 128 bytes en cualquier parte central del fichero.
En concreto y como no tendreis ganas de seguir leyendo rollo, teneis una explicación completa de Peter Selinger, del Departamento de Matemáticas y Estadística de la Universidad de Dalhousie (Canadá) basada en la mejora de la implementación de Patrick Stach’s y de la que nos valdremos para generar los ejecutables.
Lo primero, será descargar el software para poder generarlos:
wget http://www.mscs.dal.ca/~selinger/md5collision/downloads/evilize-0.2.tar.gz
Descomprimirlo y crear la librería y herramientas:
tar -zxvf evilize-0.2.tar.gz cd evilize-0.2 make
Habremos obtenido los programas evilize que nos dará el vector de inicialización, md5coll que se encargará de la colisión y el fichero de objeto goodevil.o que emplearemos posteriormente para compilar.
Ahora, crearemos un programa en C con múltiples comportamientos pero en vez de usar la función main(), emplearemos las funciones main_good() y main_evil() para ello. Podeis echarle un vistazo al original hello-erase.c.
En concreto, nuestro programa llamado madesyp-md5poc.c será el siguiente:
/*
MD5-PoC By Academia MADESYP
Based on Peter Selinger
*/
#include <stdio.h>
#include <unistd.h>
/* No hacer nada malo */
int main_good(int ac, char *av[]) {
char buf[10];
fprintf(stdout, "Academia MADESYP – MD5 PoC\nSoy tu parte buena!\n");
return 0;
}
/* Hacer algo malo */
int main_evil(int ac, char *av[]) {
char buf[10];
fprintf(stdout, "Academia MADESYP – MD5 PoC\n");
fprintf(stdout, "Soy tu parte mala y me hago pasar por la buena!\n");
return 0;
}
Ahora, lo compilaremos incluyendo el fichero de objeto anteriormente creado:
gcc madesyp-md5poc.c goodevil.o -o madesyp-md5poc
Vamos a crear ahora el vector de inicialización para poder generar a continuación los bloques de bytes y producir la colisión.
Lo primero crear el vector de inicialización:
./evilize madesyp-md5poc –i
Como vereis, con el vector de incialización creado y ojo a los valores que cambian y son particulares a cada código fuente, ahora, tendremos que generar la colisión. No asustaros si tarda tiempo, pues pueden ser varias horas. Si seguís el ejemplo, en unos 30 minutos lo tendreis. Asi que, al café! (pero primero dejar el comando en ejecución y mirar el progress)... Puede llegar a varios millones!!! Para el caso concreto nuestro, se da en 296.381.151.6 ;-D)
./md5coll 0x7eb4cb5a 0xe5075366 0x8ebe5035 0x4247259c > init.txt
Podemos mirar el fichero init.txt generado:
cat init.txt
Random seed: 1276585469
unsigned int m0[32] = {
0x9f9dc4ae, 0x57e576b3, 0xbf88ca96, 0xd2c1f2b7,
0xb9bc1490, 0xf0d3ff98, 0xc937b36a, 0x7424e933,
0x0633ad41, 0x81b435fc, 0x845afa9b, 0xd79a6f77,
0xcdfdcee4, 0x265b8df2, 0x23c5f782, 0x9c7209a6,
0x7e213eb4, 0xf6db0ebb, 0xf29990e7, 0x9dea5924,
0x14999014, 0x1cefc03e, 0x3729f91c, 0xd05d1b50,
0x163eafcd, 0x6d747b4a, 0x9bc56792, 0x3e36d08d,
0xc88ea11d, 0xf5b7b858, 0x174893be, 0x9747987c,
};
unsigned int m1[32] = {
0x9f9dc4ae, 0x57e576b3, 0xbf88ca96, 0xd2c1f2b7,
0x39bc1490, 0xf0d3ff98, 0xc937b36a, 0x7424e933,
0x0633ad41, 0x81b435fc, 0x845afa9b, 0xd79aef77,
0xcdfdcee4, 0x265b8df2, 0xa3c5f782, 0x9c7209a6,
0x7e213eb4, 0xf6db0ebb, 0xf29990e7, 0x9dea5924,
0x94999014, 0x1cefc03e, 0x3729f91c, 0xd05d1b50,
0x163eafcd, 0x6d747b4a, 0x9bc56792, 0x3e36508d,
0xc88ea11d, 0xf5b7b858, 0x974893be, 0x9747987c,
};
Y por fin, vamos a crear los ficheros que queremos. Les llamaremos bueno y malo. ¿Qué original, no?
evilize madesyp-md5poc -c init.txt -g bueno -e malo
Le damos al usuario permiso de ejecución con chmod u+x y comprobaremos sus hashes MD5:
md5sum bueno 6f8b63d36835b2c462fd671f023c7018 md5sum malo 6f8b63d36835b2c462fd671f023c7018
Luego obtienen el mismo hash MD5 (6f8b63d36835b2c462fd671f023c7018) pero al ejecutarlos... Tachán!!! Sorpresa!!!
Para los impacientes, tras compilar, podrían haber dejado directamente ./evilize madesyp-md5poc -g bueno -e malo
Como conclusión, podemos decir que si hubieran sido ficheros con otro código, podríamos haber sido víctimas aun a pesar de haber comprobado su hash MD5. Sin embargo, si hubieramos probado con SHA1, el resultado hubiera sido diferente:
sha1sum bueno 26d8edbd262ecda64f54ab037361c08efa185e40 sha1sum malo ac98315db9ffe003b43537fbf6c008b6d1bdaa60
Suponemos que cuando se ofrece un fichero con una doble comprobación (MD5 y SHA1) lo comprobamos "doblemente", no? La base de éste artículo, nos servirá en futuras entradas para ir demostrando cómo conseguir colisiones válidas en Criptografía. Para aquell@s que no quieran probar, os dejamos el código fuente, vectores, hash de colisión y binarios para Windows y GNU/Linux ya preparados para probar directamente en madesyp-md5poc.zip nuestro repositorio "maligno". Ahora, si habeis hecho las pruebas, podreis decirnos en las listas qué os parece el generar las colisiones... ¿Es importante una GPU? ¿64 bits? ¿Clustering? ¿Y generar una colisión para un Certificado SSL válido como habeis visto los de OWASP? Contarnos vuestras experiencias y podreis conseguir una plaza completamente *GRATUITA* en nuestros Cursos Privados de OWASP 3.0!!!
Recuerda que en Academia MADESYP nos encontramos impartiendo Cursos especializados en Seguridad Informática donde realizamos y establecemos las contramedidas para las pruebas de concepto con todo ésto y mucho más...
Ser buenos y no hagais maldades!!!
