Implementación de colisión en MD5
From Wikipedia, the free encyclopedia
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]
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()
