El ataque criptográfico de colisiones de hash, utilizado por ciberespías para subvertir a Windows Update de Microsoft se ha generalizado, revelando así que el algoritmo MD5 está irremediablemente roto.

El investigador de seguridad Nat McHugh creó dos imágenes de distintos íconos del rock and roll, James Brown y Barry White, con el mismo hash MD5. “Las imágenes fueron tomadas de Internet … de hecho pude haber elegido cualquier imagen o cualesquiera datos arbitrarios y creado una colisión con ellos”, informa McHugh.

MD5 = e06723d4961a0a3f950e7786f3766338

MD5 = e06723d4961a0a3f950e7786f3766338

El proceso de cálculo de datos de relleno para producir la colisión entre dos imágenes disímiles se llevó a cabo en una instancia de cómputo en la nube en cuestión de horas, a un costo estimado por McHugh de menos de un dólar.

Los intentos de fuerza bruta para encontrar colisiones de hashes criptográficos (se produce al aplicar a dos archivos distintos una función hash y que éstos arrojen la misma salida) son todavía poco prácticos para cualquiera que no cuente con acceso a una supercomputadora.

Lo que McHugh logró hacer fue agregar datos binarios al final de dos imágenes JPEG distintas, de tal forma que los dos archivos modificados dieron el mismo valor hash. Colisiones MD5 de este tipo, es decir, generadas a partir de dos valores de entrada fijos, fueron demostradas con éxito por primera vez en 2007.

En una colisión con valores de entrada fijos, los datos que preceden a los bloques de colisión especialmente diseñados pueden ser completamente diferentes, como es el caso de las imágenes del padrino del soul y la morsa del amor.

En una entrada de blog, McHugh explica cómo fue capaz de averiguar qué datos binarios añadir al final de los dos archivos de imagen.

El ataque de colisión para valores fijos funciona mediante la adición repetida de bloques “cerca de la colisión” que trabajan gradualmente para eliminar las diferencias en el estado interno del MD5, hasta que son el mismo. Antes de que esto pueda llevarse a cabo, los archivos deben ser de la misma longitud y las pequeñas diferencias deben ser de una forma particular. Esto requiere un ataque de fuerza bruta conocido como ataque de cumpleaños, que prueba valores aleatorios hasta que se encuentran dos que funcionen. Esto sin duda tiene una complejidad mucho menor que un ataque de fuerza bruta completo.

Otro investigador, Marc Stevens, creó un framework para automatizar el descubrimiento de rutas diferenciales y utilizarlas para crear colisiones de valores fijos. McHugh optó por ejecutar la herramienta de investigación de Stevens HashClash en Linux, utilizando un script en bash para automatizar los pasos repetitivos necesarios en una instancia AWS GPU. “Me di cuenta de que era capaz de ejecutar el algoritmo en alrededor de 10 horas en una instancia AWS GPU” a un costo aproximado de 0.65 dólares más impuestos, según McHugh.

McHugh concluye que su ejercicio demuestra que MD5 es irremediablemente débil, obsoleto y no apto para usos prácticos.

Marc Stevens también ha publicado una herramienta para la detección de archivos que han sido procesados de esta manera. Ejecuta esta herramienta sobre cualquiera de los archivos puede detectar que se han añadido bloques de colisión.