Colisiones en MD-5 y SHA-1

Hace unas semanas, aprovechando una noticia curiosa, escribí un corto boletín para “una-al-día” en el que explicaba como un abogado australiano había utilizado las debilidades del algoritmo MD5 como argumento que impedía demostrar la no alteración de una prueba.

El boletín no dejaba de ser una explicación de algo anecdótico y, en el momento de redactarlo, expliqué algunos conceptos de forma muy superficial y recordando conceptos de memoria. No tenía el objetivo de explicar MD5 para neófitos o entendidos, únicamente quería realizar una visión superficial.

Por desgracia esa visión superficial no fue del todo acertada… Es más, había bastantes errores al explicar el funcionamiento de un algoritmo para la obtención de sumas de control y sus debilidades.

Algunos lectores de “una-al-día” nos enviaron diversos mensajes haciendo notar la existencia de estos errores. Desde aquí mi agradecimiento a todos aquellos que se tomaron la molestia de enviarnos un mensaje indicando los errores en el boletín.

Uno de estos lectores nos facilitó en enlace de un artículo, Attacking Hash Functions by Poisoned Messages – “The Story of Alice and her Boss”, cuya dirección indicamos en el apartado “Más información”.

Se trata de un corto artículo, en inglés, donde nos facilitan dos archivos en formato .PS (PostScript) con dos documentos absolutamente diferentes. No obstante, ambos archivos generan la misma suma de control MD5.

Estos archivos se han podido generar utilizando una técnica para la identificación de colisiones aleatorias en la función de compresión MD5. Con solo algunas horas de proceso en un ordenador PC fue posible la construcción de estos dos archivos PostScript. En una presentación realizada en Eurocrypt 2005 (en ‘Más información’ facilitamos el enlace al archivo PDF de dicha presentación) se explica someramente el funcionamiento de esta técnica.

Colisiones en SHA-1

En el pasado Crypto 2005, celebrado a mediados de agosto en California, Adi Shamir (la “S” de RSA) anunció los resultados de la investigación de Xiaoyun Wang, que no pudo asistir a la conferencia ya que las autoridades norteamericanas no le concedieron el visado de entrada. Esta investigadora mostró reducir la complejidad de romper el estándar SHA-1 a 2^63, es decir, 64 veces más rápido que anteriormente.