Solución al reto 12: Encuentra las 7 diferencias

Seguro que recordáis las imágenes de las playas abarrotadas de nuestro último reto, en las que había que encontrar 7 diferencias.

Estas diferencias no eran visuales, es decir, si las comparábamos pixel a pixel el resultado era este:



Pero antes de continuar, veamos un resultado válido de esta comparación, por ejemplo si agregamos a la primera imágen a Wally ;)


Utilizamos el siguiente código en PHP:

$original = imagecreatefromgif('crowded-beach1.gif');

$modified = imagecreatefromgif('crowded-beach3.gif');
$size = getimagesize('crowded-beach1.gif');
$output = imagecreate($size[0], $size[1]);
imagecolorallocate($output, 255, 255, 255);
$cblack = imagecolorexact($output, 0, 0, 0);
for ($a = 0; $a < $size[0]; $a++) {
for ($b = 0; $b < $size[1]; $b++) {
$colororiginal = imagecolorat($original, $a, $b);
$colormodified = imagecolorat($modified, $a, $b);
if ($colororiginal != $colormodified)
imagesetpixel($output, $a, $b, $cblack);
}
}
imagepng($output, 'resultado.png');

y ahora si vemos como se resalta la figura del famoso personaje:



¿Lo ves ahora? XDDDD

Ahora bien, esta comparación visual no era válida para nuestro reto, por lo que el siguiente paso natural es comparar los binarios.


Antes de seguir, comentaros que las modificaciones se realizaron con Notepad++ y que su plugin 'Compare' curiosamente no encuentra una octava diferencia que si ven otros editores hexadecimales. Podéis comprobarlo vosotros mismos porque quizás se trata de un bug pendiente de reportar...

Una vez aclarado esto, queríamos presentaros el proceso de resolución completo que Daniel Correa amablemente nos ha facilitado y que podréis encontrar también en el portal siempre recomendable de Sinfocol (Seguridad Informática Colombiana). En el veréis como el autor además profundiza en el funcionamiento y algoritmo de la stego-herramienta utilizada.

Sin más preámbulos os dejo con el impresionante solucionario:


Resolución
por Daniel Correa

Lo primero que hice fue descargar ambas imágenes, había que tener cierto cuidado con la segunda ya que en en el atributo src de la etiqueta img no se proporcionaba la variable attredirects que tiene como propósito mostrar el archivo tal como es, sin dicha variable, la imagen mostrada es un PNG que obviamente es una distracción.

Incluyendo attredirects la respuesta del servidor es como sigue.

HTTP/1.1 Moved Temporarily - 302
Location: http://1783545483851967320-a-1802744773732722657-s-sites.googlegroups.com/site/h4ckpl4y3s/crowded-beach2.gif
...

Teniendo las dos imágenes GIF, lo primero que hice fue comparar pixel por pixel en busca de diferencias visuales, usando la clase ImageCompare incluida con este documento, se puede apreciar que las dos imágenes tienen mucha variación en sus pixeles.


Al no tener un resultado positivo con el análisis visual, el siguiente paso es entonces hacer una comparación binaria. Utilizando mi editor hexadecimal preferido,
010 editor, pude encontrar las 'siete' diferencias, que en realidad son ocho.

Este es el resumen de las diferencias.

crowded-beach1.gif: 8qpBHgdz
crowded-beach2.gif: shufflee

Y dejando las siete diferencias, tenemos la palabra para la primera parte del reto: shuffle

Gracias a Vicente, pude resolver la segunda parte del reto. Siguiendo la palabra obtenida con las diferencias, más la cadena GIF y stegano, encontré la herramienta Gifshuffle.

Con los parámetros correctos y usando shuffle como contraseña, podemos obtener la respuesta final.

GIFSHUF.EXE -C -p shuffle crowded-beach1.gif
weapon12

Esteganografía a través de ordenamiento

Pero esto no acaba, fui un poco más lejos y encontré un interesante método. Existe una forma de esconder información reordenando listas, esto es, tratando una lista como un sistema de numeración de base igual al número de elementos en la lista.

A continuación, un ejemplo que permite esconder la letra 'S' en una lista de números. Primero debemos calcular el número total de elementos en la lista que permite esconder x bits de información, para esto usamos la operación gamma inversa.

Si tenemos un número n de elementos en una lista, el cálculo para obtener el número total de bits que podemos almacenar es.

Haciendo los cálculos para 7 bits con Wolfram Alpha, vemos que necesitamos de 6 elementos en la lista para esconder la información.

Codificando la información

Estos son los pasos para codificar la información en una lista previamente definida.

  1. Creamos una lista de n = 6 elementos y la enumeramos desde 0.

    1. Avira

    2. BitDefender

    3. ESET NOD32

    4. F Secure

    5. G Data

    6. ZoneAlarm

  2. Obtenemos el valor decimal para la letra 'S', el cual es representado por su valor ASCII y lo asignamos a la variable m. Agregamos un 1 al inicio de la cadena binaria (101010011). m = 339.

  3. Iteramos i desde 1 hasta n (El ejercicio se deja al lector).

    1. Se envia el elemento ni a la posición m % i de la nueva lista. Si la posición está previamente ocupada, el elemento en la posición m % i y mayores son re posicionados un nivel adelante.

    2. Ahora m será m / i, se redondea al menor entero cercano. m = floor(m / i).

  4. La lista está reordenada y lista para transmitirse.

    1. ESET NOD32

    2. ZoneAlarm

    3. Avira

    4. F Secure

    5. G Data

    6. BitDefender

Decodificando apartir de la lista reordenada

Un paso fundamental para el proceso de decodificación es tener la lista ordenada de los elementos, sin esta es imposible recuperar el texto original ya que el proceso en sí es similar al cifrado One Time Pad (OTP), donde la clave usada son los índices de la lista.

  1. Escoger el primer elemento de la lista reordenada y buscar el índice en la lista original (Los índices comienzan de 0). Para este caso, ESET NOD32 se encuentra en la posición 2.

  2. El elemento es eliminado de la lista original, los índices se reacomodan para empezar de 0 de nuevo.

  3. El siguiente elemento es ZoneAlarm, que ahora ocupa la posición 4.

  4. Avira se encuentra en la posición 0.

  5. F Secure ahora se encuentra en la posición 1.

  6. La lista en estos momentos debe estar ordenada de la siguiente forma.

    1. BitDefender

    2. G Data

  7. G Data que es el próximo en la lista reordenada, ocupa la posición 1.

  8. Por último, BitDefender, se mantiene en la posición 0.

  9. El resultado es entonces el número 240110.

  10. Convertimos el número a base 10: 2*5! + 4*4! + 0*3! + 1*2! + 1*1! + 0*0! = 339.

  11. 339 en binario es 101010011, eliminamos el 1 que agregamos en el proceso de codificación: 01010011, y obtenemos el carácter codificado: S (93 decimal).

La magia de GIFShuffle

Antes de iniciar con el formato, les recomiendo que lean el documento de Darren Meyer sobre formatos de archivos gráficos que se encuentra aquí.

A continuación un resumen del formato GIF para el archivo de ejemplo presentado en este documento.

Tenemos la siguiente imagen.



Este GIF se compone de 5 bloques.
  1. GIF Header

    1. 47 49 46 38 39 61 (GIF89a)

  2. Logical Screen Descriptor

    1. 08 00 01 00 A2 00 00

      • Width: 8px

      • Height: 1px

        • Global Color Table: true

        • Color Resolution: 2

        • Sort Flag: false

        • Size of Global Color Table: 2: 2^(2+1): 8 colores

      • Background Color Index: 1

      • Pixel Aspect Ratio: 1

  3. Global Color Table

    1. FF FF FF FF FF 00 FF 00 FF FF 00 00 00 FF FF 00 FF 00 00 00 FF 00 00 00

      • #FFFFFF (Blanco)

      • #FFFF00 (Amarillo)

      • #FF00FF (Magenta)

      • #FF0000 (Rojo)

      • #00FFFF (Aqua)

      • #00FF00 (Verde)

      • #0000FF (Azul)

      • #000000 (Negro)

  4. Data

    1. 21 F9 04 00 07 00 FF 00 2C 00 00 00 00 08 00 01 00 00 03 06 38 65 41 02 27 01 00

      • Graphic Control Extension (21 F9 04 00 07 00 FF 00)

      • ImageDescriptor (2C 00 00 00 00 08 00 01 00 00)

      • ImageData (03 06 38 65 41 02 27 01 00)

        • LZW Minimum Code Size: 3

        • DataSubBlocks

          • Size: 6

          • LZW + RLE: 38 65 41 02 27 01 00

          • Raw Pixel Indexes: 03 05 06 01 04 02 00 07 (Índices que apuntan a la tabla de colores, así se va formando la imagen, de izquierda a derecha, de arriba a abajo: índice 3 apunta al rojo, 5 al verde, 6 al azul, etcétera).

  1. Trailer

    1. 3B

En este resumen visual podemos apreciar los cinco componentes de nuestro GIF.


GIF Shuffle actua de forma idéntica al método de la esteganografía a través de ordenamientos.

Lo primero que hace es ordenar los colores en su forma natural siguiendo la fórmula.

Para el ejemplo este ordenamiento sería.

0: 00h 00h 00h : 0
1: 00h 00h ffh : 255
2: 00h ffh 00h : 65280
3: 00h ffh ffh : 65535
4: ffh 00h 00h : 16711680
5: ffh 00h ffh : 16711935
6: ffh ffh 00h : 16776960
7: ffh ffh ffh : 16777215

Después de ordenar la lista, aplica compresión y/o cifrado al mensaje, descomprime los datos de la imagen (ImageData) y asigna los nuevos índices de colores.

Este método de esteganografía no altera de ninguna forma la apariencia visual del objeto portador, esto ocurre porque solo está modificando el orden de los colores y no sus valores, como lo haría por ejemplo un típico cambio en el bit menos significativo. Los únicos indicios que tenemos para descubrir un mensaje oculto es el orden de la tabla de colores.

Es posible almacenar 15.2 bits de información para una tabla global de colores de 8 elementos (GIF soporta un total de 256 colores únicos lo cual permite almacenar aproximadamente 210 bytes de información), para el ejemplo y para mayor facilidad, lo haré con 8 bits, que corresponden a la letra “d”.

GIFSHUF.EXE -m "d" 8.gif 8_mod.gif

Message used approximately 56.25% of available space.

Al comparar las dos imágenes vemos que la tabla global de colores y los índices de colores para los datos de la imagen son diferentes debido al reordenamiento. (En los recursos adjuntos pueden encontrar el proceso manual para este ejemplo).


8.gif

8_mod.gif

Tabla Global de Colores

0: ffh ffh ffh 1: ffh ffh 00h
2: ffh 00h ffh 3: ffh 00h 00h
4: 00h ffh ffh 5: 00h ffh 00h
6: 00h 00h ffh 7: 00h 00h 0
0h

0: 00h 00h 00h 1: 00h 00h ffh
2: ffh 00h ffh 3: ffh 00h 00h
4: 00h ffh 00h 5: 00h ffh ffh
6: ffh ffh 00h 7: ffh ffh ffh

Índices de Colores

03 05 06 01 04 02 00 07

03 04 01 06 05 02 07 00


Comentarios