Colisión en MD5

Hace unas semanas me habló un amigo sobre un bug conocido en la función criptográfica del hash MD5, que data ya del 2005 y que fue descubierto por Xiaoyun Wang y Hongbo Yu. Por ese año no tenia ni pc, así que tengo excusa. No trato mucho con la criptografía, así que, me sorprendió como se podían generar dos binarios con código completamente diferente y que tuvieran el mismo hash (también pensé en los usos que le podría dar ;) ).

Lo que queremos hacer es que dos flujos de datos diferentes produzcan el mismo hash o lo que se conoce también como colisión, mediante un vector de iniciación que encontrará los pares de bloques. Nos vamos a valer de una herramienta desarrollada por la Universidad Dalhousie (Canada), que usa el algoritmo original mejorado por Patrick Stach's.

wget http://www.mscs.dal.ca/~selinger/md5collision/downloads/evilize-0.2.tar.gz

Vamos trabajando con el fichero (si teneis dudas en esto, leeros el README):

kike@localhost:~$ tar --extract --gunzip --file=evilize-0.2.tar.gz
kike@localhost:~$ cd evilize-0.2/
kike@localhost:~/evilize-0.2$ ls
AUTHORS ChangeLog COPYING crib.h evilize.c goodevil.c hello-erase.c Makefile MBSD-LICENSE md5.c md5coll.c md5coll_lib.c md5coll_lib.h md5.h README
kike@localhost:~/evilize-0.2$ make
gcc -O3 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"0.1s\" -DVERSION=\"0.2\" -c -o evilize.o evilize.c
gcc -O3 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"0.1s\" -DVERSION=\"0.2\" -c -o md5.o md5.c
gcc -O3 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"0.1s\" -DVERSION=\"0.2\" -c -o md5coll_lib.o md5coll_lib.c
gcc evilize.o md5.o md5coll_lib.o -o evilize
gcc -O3 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"0.1s\" -DVERSION=\"0.2\" -c -o md5coll.o md5coll.c
gcc md5coll.o md5coll_lib.o -o md5coll
gcc -O3 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"0.1s\" -DVERSION=\"0.2\" -c -o goodevil.o goodevil.c
kike@localhost:~/evilize-0.2$ ls
AUTHORS COPYING evilize evilize.o goodevil.o Makefile md5.c md5coll.c md5coll_lib.h md5coll.o md5.o
ChangeLog crib.h evilize.c goodevil.c hello-erase.c MBSD-LICENSE md5coll md5coll_lib.c md5coll_lib.o md5.h README
kike@localhost:~/evilize-0.2$

Bueno ya tenemos creadas todas las utilidades, el evilize que sacará el vector de iniciación, el md5coll que se encargará de la colisión y el goodevil.o que se lo pasaremos al compilar, vamos a ello. Vamos a crear un archivo en c, con algo de código siguiendo la estructura del fichero que nos dan como prueba (hello-erase.c). Dos funciones, una donde pondremos el código del programa "normal" main_good(), y otra donde pondremos el código malicioso main_evil(). Mis funciones:

 1 main_good() {
 2   printf("Hello, world!\n");
 3   return 0;
 4 }
 5
 6 main_evil() {
 7  printf("This program is evil!!!\n");
 8  printf("Erasing hard drive...");
 9  printf("1Gb...");
10  printf("2Gb...");
11  printf(" just kidding!\nNothing was erased.\n");
12  return 0;
13 }

Si, no estaba inspirado y solo modifique el código que dan como ejemplo, hasta quite los sleeps que es lo único que hacía un poco de gracia :-/ , total para un ejemplo vale cualquier cosa. Compilamos pasándole el objeto de antes.

kike@localhost:~/evilize-0.2$ gcc texto_evil.c goodevil.o -o texto_evil

Ahora vamos a calcular el vector de iniciación, que usaremos a continuación para generar los bloques de bytes, osea la colisión, y como imagináis esto tardará bastante, a mi creo recordar, entorno a una hora.

kike@localhost:~/evilize-0.2$ ./evilize texto_evil -i
Initial vector: 0x7d45dd5f 0x109ae40e 0x7e0e5631 0x42f7c0ba
kike@localhost:~/evilize-0.2$ ./md5coll 0x7d45dd5f 0x109ae40e 0x7e0e5631 0x42f7c0ba > init.txt
Progress: 186.510.447.57 (done)
kike@localhost:~/evilize-0.2$ cat init.txt
Random seed: 2031431393
unsigned int m0[32] = {
0x5730736e, 0x3ad3c85a, 0x211af6f5, 0x342faae3,
0x6e21fe46, 0x681d904d, 0xb85b3545, 0xf4872c32,
0x06342dc5, 0x4073fff9, 0x7d8ced67, 0xdc304d59,
0xa6a11ce1, 0x81702a2c, 0x30184573, 0x1a9c78f2,
0x300c38c3, 0xc6691625, 0x081ffdcd, 0x66b5ae27,
0x95963448, 0xdbf97c4e, 0x556cd922, 0xf0a10a52,
0x5d782fd1, 0x2b8af879, 0x0d4c6ba6, 0x9e0ee4bc,
0x21d240fe, 0x998be088, 0xd3cc37c9, 0x2aa99541,
};

unsigned int m1[32] = {
0x5730736e, 0x3ad3c85a, 0x211af6f5, 0x342faae3,
0xee21fe46, 0x681d904d, 0xb85b3545, 0xf4872c32,
0x06342dc5, 0x4073fff9, 0x7d8ced67, 0xdc30cd59,
0xa6a11ce1, 0x81702a2c, 0xb0184573, 0x1a9c78f2,
0x300c38c3, 0xc6691625, 0x081ffdcd, 0x66b5ae27,
0x15963448, 0xdbf97c4e, 0x556cd922, 0xf0a10a52,
0x5d782fd1, 0x2b8af879, 0x0d4c6ba6, 0x9e0e64bc,
0x21d240fe, 0x998be088, 0x53cc37c9, 0x2aa99541,
};

Y ya estamos listos para sacar los dos binarios, yo los llame p_bueno y p_malo:

kike@localhost:~/evilize-0.2$ ./evilize texto_evil -c init.txt -g p_bueno -e p_malo
Writing 'good' file p_bueno.
Writing 'evil' file p_malo.
kike@localhost:~/evilize-0.2$

Y ahora vamos a ver lo que tanto esperabamos:

kike@localhost:~/evilize-0.2$ ls -l p_*
-rw-r--r-- 1 kike kike 6940 mar 18 20:56 p_bueno
-rw-r--r-- 1 kike kike 6940 mar 18 20:56 p_malo
kike@localhost:~/evilize-0.2$ chmod u+x p_*
kike@localhost:~/evilize-0.2$ ls -l p_*
-rwxr--r-- 1 kike kike 6940 mar 18 20:56 p_bueno
-rwxr--r-- 1 kike kike 6940 mar 18 20:56 p_malo
kike@localhost:~/evilize-0.2$ ./p_bueno
Hello, world!
kike@localhost:~/evilize-0.2$ ./p_malo
This program is evil!!!
Erasing hard drive...1Gb...2Gb... just kidding!
Nothing was erased.
kike@localhost:~/evilize-0.2$ md5sum p_bueno
35ceb3d4b440f0a952c296e4e44405ef p_bueno
kike@localhost:~/evilize-0.2$ md5sum p_malo
35ceb3d4b440f0a952c296e4e44405ef p_malo
kike@localhost:~/evilize-0.2$

Como vemos mismo hash, para salir de dudas mejor sha1:

kike@localhost:~/evilize-0.2$ sha1sum p_bueno
d842e8c2aa91fe69a6878c569d41a8946b1b264c p_bueno
kike@localhost:~/evilize-0.2$ sha1sum p_malo
22fdb1fc4c6aa52a70838e80b33daf914c85f56c p_malo
kike@localhost:~/evilize-0.2$

Espero que vosotros también lo probéis, ya que es una buena forma de ir “cojiendole cariño” a la criptografía, con ejemplos prácticos como este. Os recomiendo también que busquéis como trabaja el algoritmo MD5 antes de hacer la practica para ver todo más claro.

Saludos.