Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

De MD5, colisiones, presidentes de EE.UU. y PS3

Ayer Lunes comentaron en Barrapunto ( y previamente en meneame ) acerca de una predicción sobre el resultado de las próximas elecciones de los Estados Unidos realizada por unos investigadores de la universidad donde estoy ( TU Eindhoven ), concretamente Benne de Weger ( profesor de Cryptography 2, a parte de haber dado este año la parte de RSA de Cryptography 1 ) junto con Marc Stevens y Arjen Lenstra.

Lo que han hecho ha sido crear varios documentos PDF con las posibles predicciones, pero que todos tengan el mismo hash MD5 (es decir, encontrar colisiones en MD5). Aquí voy a explicar sin entrar en mucho detalle y lo mejor que pueda qué es lo que han hecho para quien esté interesado y no tenga ganas/tiempo de leer el documento.

Antes de empezar, conviene conocer un par de términos (enlace a Wikipedia en inglés): hash collision y hash function (ver también el enlace a función hash criptográfica) . Desde allí se puede ir también a la versión española 🙂

Asumiendo que ya conocemos qué es un hash y qué es una colisión, cabe mencionar que generalmente las funciones de hash funcionan en base a varias iteraciones sobre una función de compresión, utilizando en cada iteración un bloque de datos del mensaje y un valor de hash intermedio ( IHV, Intermediate Hash Value ). El valor obtenido con el último bloque del mensaje (al que probablemente se haya añadido relleno para que sea múltiplo del tamaño de bloque ) es el hash buscado.

Pese a que en 2004 ya se publicó cómo obtener colisiones con MD5 ( prof. Xiaoyun Wang ), en este caso se trataba de mensajes aleatorios, lo cual hace que aunque dos mensajes tengan el mismo hash, probablemente solo uno de ellos tenga cierto significado. En el caso del nuevo ataque, que describen como chosen-prefix collisions, el documento puede tener una parte inicial arbitraria, siempre que a partir de cierto momento todos los documentos sean iguales.

Lo que describen en su paper Benne de Wenger y sus co-autores es un mensaje con los 3 siguientes campos:

• Un prefijo cualquiera
• Un relleno aleatorio, para que el tamaño de los 3 campos sea múltiplo del bloque
• Una cadena elegida de forma que la diferencia entre IHVs en este campo tenga ciertas propiedades

Con esto, la diferencia entre IHVs conseguida no es nula, pero es posible obtener una colisión mediante lo que ellos llaman near-collision blocks, consturidos para reducir estas diferencias.

A partir de aquí, tenemos dos documentos con un hash idéntico, aunque con cierta basura, y podemos añadir lo que queramos detrás siempre que sea igual para ambos archivos.

Lo que han hecho en este caso, es poner esa basura en una imagen oculta dentro del PDF, y aunque no he examinado los documentos, supongo que la parte final idéntica en todos cierra la imagen y añade todos los campos que necesite el formato PDF (que desconozco) para tener un documento válido.

La mejora de este método frente a lo descrito en el CITS, es que en el nuevo método no es posible encontrar rastros de que existe el documento fraudulento, mientras que en el anterior el documento postscript contenía dos bloques de contenido y se podía ver el otro documento.

¿Y qué tiene que ver la PS3 con todo esto? Pues simplemente que han usado una PS3 con sus múltiples cores para realizar los cálculos, además de un PC quad core. En su paper inicial comentan que les tomó unos 6 meses de trabajo con miles de PCs para encontrar las colisiones, pero con la técnica nueva unos 2 días son suficientes, usando una PS3 y un PC quad core.