← Blog

PNG que muestra su propio MD5: el hashquine The Arma Of Efe

Cómo generamos un PNG que escribe su propio resumen MD5 en sus píxeles sin usar una plantilla: claves de colisión, capas del PNG y la búsqueda de efe23…23efe con una RTX 5070, con explicaciones interactivas.

La imagen de arriba no es un logo cualquiera. Sobre el arco de la derecha, de arriba abajo, está escrito efe235ae1b88c53e73d1c11515623efe, y ese es el resumen MD5 del propio archivo. Si descarga la imagen y ejecuta md5sum, verá los mismos 32 caracteres.

A este tipo de archivos se les llama hashquine. El ejemplo famoso que circula por internet es el PNG del dragón de retr0id, y mucha gente usa esa plantilla ya hecha. Nosotros no usamos ninguna plantilla: lo generamos desde cero, con nuestro propio logo (The Arma Of Efe), nuestro propio enlace al blog y un resumen especial que empieza y termina con efe. A continuación lo explico paso a paso, tal como fuimos probando.

El hashquine PNG con dragón de Retr0id, que muestra su propio MD5

El hashquine PNG de David “Retr0id” Buchanan, MD5 1337e2ef42b9bee8de06a4d223a51337. Imagen: Retr0id, vía corkami/collisions.

¿Qué es un hash y por qué cambia con cada letra?

Un hash (resumen) es una huella digital de longitud fija que se calcula a partir del contenido de un archivo. MD5 es una función de resumen diseñada por Ronald Rivest en 1991: tanto si la entrada tiene 1 byte como 50 GB, la salida siempre tiene 128 bits, es decir, 32 caracteres formados por 0-9 y a-f.

La propiedad clave de las funciones de resumen es el efecto avalancha: el cambio más pequeño en la entrada altera la salida por completo. Pruebe a escribir algo aquí:

El problema del huevo y la gallina

Por culpa del efecto avalancha, una imagen que lleve su propio MD5 parece imposible a primera vista:

  1. Dibuja la imagen y calcula su MD5, por ejemplo 4a8c91e0….
  2. Escribe ese código sobre la imagen y guarda el archivo.
  3. Como los píxeles han cambiado, el MD5 del archivo ya es otro, por ejemplo 9f02d71a….
  4. Escribe el nuevo código y el resumen vuelve a cambiar.

Para romper este ciclo hay que mirar dentro del MD5.

La idea que rompe el ciclo: claves que no alteran el MD5

MD5 no procesa el archivo de una sola vez. Lo divide en bloques de 64 bytes y los procesa en orden: el estado inicial (IV) se mezcla con el primer bloque y da un estado intermedio (IHV). Ese estado intermedio se mezcla con el siguiente bloque, y así hasta el final del archivo. El último estado intermedio es el MD5 de 32 caracteres.

Lo crítico es esto: pueden existir dos fragmentos de datos distintos de 128 bytes (A y B), alineados con el límite de 64 bytes, que llegan al mismo estado intermedio. Eso se llama colisión de prefijo común, y herramientas como FastColl la producen en poco tiempo. Como cada bloque posterior a ese fragmento ve el mismo estado intermedio:

  • si se incluye el fragmento A, aparece un trazo en pantalla; si se incluye B, no aparece,
  • pero el MD5 al final del archivo no cambia nunca.

Así, cada par de colisión es una clave que se abre y se cierra sin alterar el MD5. Primero se calcula el MD5 del archivo y después se ajustan las claves para que dibujen exactamente ese resumen. Como el resumen no cambia, el ciclo queda roto.

¿Cómo se dibujó el arco letra a letra?

En nuestro archivo, los 32 caracteres se distribuyen de arriba abajo siguiendo una curva que sigue el arco del logo. Cada carácter es un dígito de siete segmentos y cada segmento lo dibuja su propia clave: en total, 224 claves de colisión. Con el control deslizante puede seguir cómo el resumen se coloca en el arco:

Como no usamos una plantilla, el PNG tuvo que superar cuatro capas de verificación a la vez:

  1. Alineación de 64 bytes: cada clave debe caer exactamente en el límite desplazamiento % 64 == 0 del archivo. Alineamos cada clave añadiendo a la secuencia DEFLATE bloques vacíos de longitud cero.
  2. Filtros Sub y Up de PNG: pusimos los índices 0..254 de la paleta en negro y solo el índice 255 en blanco. Las dos mitades de un par de colisión se diferencian en el bit más alto de unos pocos bytes. En una fila con filtro Sub, esa diferencia desplaza 128 los píxeles siguientes y se convierte en una línea horizontal; las filas con filtro Up la llevan hacia abajo. Elegimos los bytes posteriores a la clave de forma que la línea sea exactamente 255 (blanco) en un estado y negra en el otro.
  3. Compensación de Adler-32 en zlib: al descomprimir, los datos pasan por la suma de comprobación Adler-32, y cada clave desplaza esa suma varios cientos de unidades. Colocamos 160 claves de compensación en las líneas negras; el subconjunto que devuelve la suma exactamente a su valor lo elegimos con programación dinámica y una búsqueda de encuentro en el medio.
  4. Verificación CRC-32 de IDAT: al final de cada fragmento IDAT hay un CRC-32 de 32 bits. Justo después del flujo comprimido añadimos 40 bloques extra y resolvimos un sistema de ecuaciones lineales sobre GF(2) con eliminación de Gauss, fijando el valor de CRC-32 en 0x1807EFE0.

Resumen personalizado: cada carácter multiplica el trabajo por 16

No bastaba con que el archivo mostrara su propio MD5; queríamos que el resumen empezara y terminara con efe. Para eso cambiamos el bloque de nonce de 64 bytes al final del archivo y probamos miles de millones de resúmenes.

Como cada carácter puede tomar 16 valores distintos, fijar un carácter más multiplica por 16 el número medio de intentos: para N caracteres fijos hacen falta 16^N intentos en promedio. En un procesador de 24 núcleos, un bucle simple en C prueba 177 millones de MD5 por segundo. Al escribir un kernel OpenCL que se ejecuta directamente sobre libOpenCL.so en la tarjeta gráfica RTX 5070 de un portátil, la velocidad subió a 3,54 mil millones por segundo, unas 20 veces más. Para efe23…23efe se necesitan de media 1,1 billones de intentos; el nuestro apareció tras 90 mil millones, en unos 25 segundos.

Mueva el control deslizante para cambiar el número de caracteres fijos; los resultados que realmente encontramos aparecen en los puntos marcados:

Compruébelo usted mismo

Descargue la imagen y ejecute el comando en la terminal. En Windows, use certutil -hashfile dosya.png MD5; en macOS, md5 dosya.png:

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

Los 32 caracteres de la salida coinciden exactamente con el código que aparece escrito de arriba abajo sobre el arco.

El código que genera la imagen está completo en GitHub: the-arma-of-owl/the-arma-of-efe-hashquine. Como el esqueleto de colisiones también está en el repositorio, puede generar un nuevo hashquine con su propio valor de nonce.

Fuentes: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗