Colisión MD5 (by k133)

Buenas, cuando estuve de admin en el antiguo nuevo HxC y aun se tenia blog, kike (quien ahora se ve por ahi como k133) publicó este hermoso articulo que pude rescatar de uno de lo backups que logre bajar del server a mi PC se los comparto y no puedo darles la URL de referencia del articulo porque como saben el blog ya no existe, sin embargo dejo en claro que todo el crédito es de kike/k133, y ahí va:

---

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 tenéis 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:

main_good() {
        printf("Hello, world!\n");
        return 0;
    }

    main_evil() {
        printf("This program is evil!!!\n");
        printf("Erasing hard drive...");
        printf("1Gb...");
        printf("2Gb...");
        printf(" just kidding!\nNothing was erased.\n");
        return 0;
    }

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.