Implementación de colisión en MD5

Este artículo describe la Implementación de colisión en MD5 (Xiaoyun Wang y Hongbo Yu) creada por Peter Selinger.

El algoritmo de Xiaoyun Wang y Hongbo Yu^[1] puede ser utilizado para crear archivos de longitud arbitraria que tengan hash MD5 idéntico y que difieren en solo 128 bytes en algún lugar en mitad del fichero (archivo). Este tipo de ataques se conocen como ataques de tipo chosen-prefix. Peter Selinger publicó en 2006 una implementación de este método que permite generar dos ficheros (archivos) ejecutables con el mismo valor de hash MD5 y distinto comportamiento.^[2]

Fundamento teórico

Para empezar debemos recordar cómo funciona la encriptación con MD5, se usa un método de iteración conocido como método de Merkle-Damgard por el que a un archivo de entrada se le añaden una serie de bits para que cumpla un criterio de longitud, entonces se divide en bloques y se aplica recursivamente la función de compresión MD5 (llamada en adelante f () ) a través de una serie de estados. El primero de estos estados tiene un valor fijo que se conoce como vector de inicialización. El valor del estado final es el valor de hash para MD5.

El método de Wang y Yu hace posible, para un vector de inicialización s, encontrar dos pares de bloques M, M' y N, N' tales que:

f ( f (s, M), M') = f ( f (s, N), N')

Observación: Nótese que esto funciona para cualquier vector de inicialización y no solo para el estándar.

Entonces, aplicando lo anterior podemos crear ficheros que tengan el mismo valor de hash y que difieran en estos dos bloques (128 bytes). Estos dos ficheros como secuencias de bloques de 64 bytes son:

M0, M1,..., Mi-1, Mi, Mi+1, Mi+2,..., Mn,

M0, M1,..., Mi-1, Ni, Ni+1, Mi+2,..., Mn.

Los bloques al principio de los ficheros, M0,..., Mi-1, pueden elegirse arbitrariamente.

Supongamos que el estado interno de la función de hash de MD5 después de procesar esos bloques iniciales es si, Podemos aplicar entonces el método de Wang al vector de inicialización si para encontrar nuestros pares de bloques M, M' y N, N' tales que:

si+2 = f ( f (si, Mi), Mi+1) = f ( f ( si, Ni), Ni+1)

Esto nos asegura que el estado interno Si+2 después del (i+2)-ésimo bloque será el mismo para los dos ficheros. Finalmente los bloques restantes Mi+2,..., Mn pueden elegirse arbitrariamente.

Podemos usar esto para generar dos programas que difieren en esos bloques y tienen el mismo valor de hash con MD5 pero que se comportaran de forma muy distinta:

Programa 1:

Si (bloques1 == bloques1) entonces

comportamiento1()

sino

comportamiento2()

Programa 2:

Si (bloques2 == bloques1) entonces

comportamiento1()

sino

comportamiento2()

Implementación

Existe una implementación del proceso descrito en el apartado anterior creada por Patrick Stach, puede descargarse desde su web donde aparece una detallada explicación de su funcionamiento y uso en inglés.

Las instrucciones de uso son sencillas, basta con crear un archivo en ANSI C con dos funciones, cada una de las cuales definen el comportamiento de los dos programas (se puede usar como base el fichero proporcionado en su web "hello-erase.c"). Después compilamos este programa:

 gcc hello-erase.c goodevil.o -o hello-erase

Y se lo pasamos como argumento al ejecutable que nos proporciona, el programa se pone inmediatamente a buscar una colisión por nosotros:

 ./evilize hello-erase -g good -e evil

Pasadas unas horas el programa encuentra los bloques que necesita para formar la colisión.

Sobre la base de esos bloques y con el método explicado en el apartado anterior el programa genera dos ejecutables (de nombres good y evil en el ejemplo) con el mismo valor de hash en MD5 pero distinto comportamiento.