Escribí este artículo hace más de dos años pero nunca lo había publicado, hasta el día de hoy. Nunca estuve seguro si fuese correcto publicarlo, pero como pasó mucho tiempo y el desafío ya no está disponible, decidí hacerlo.

Uno de los centros de desarrollo de Amazon, particularmente el de Cape Town, posee una serie de desafíos (Take the Amazon Challenge) para aquellos talentos que aspiren a una posición en la empresa.

Por curiosidad decidí echar un vistazo y, entre todos los desafíos disponibles, me llamó la atención el "Cipher challenge" (debido a mi pasado desempeñándome como consultor en Seguridad Informática):

Amazon Cipher Challenge

En uno de mis ratos libres me dispuse a resolverlo. He aquí la experiencia.



Al ver el texto (y el título del desafío), es evidente que se trata de un mensaje cifrado utilizando algún algoritmo desconocido. Lo que primero me llamó la atención fueron los signos de puntuación, espacios en blanco, números y caracteres especiales. Estos parecían no estar cifrados, lo que me hizo pensar que se trataba de algún algoritmo de cifrado por transposición.

Por lógica supuse que originalmente se trataba de un mensaje escrito en inglés (se trata de una empresa norteamericana, instalada en un país de habla inglesa, el idioma del sitio Web es el inglés, etc.)

Siguiendo esta teoría, me llamó la atención la presencia de las palabras "a", "w" y "J". A diferencia del español, donde existen las palabras 'a', 'e', 'o', 'u' e 'y' (y sus versiones con tilde o diéresis), en el idioma inglés existe sólo una palabra de una letra: 'a' (un/una en español). Esto claro, exceptuando nombres o abreviaturas de una letra.

Lo cual me dio la pauta de que la palabra 'a' era codificada de forma diferente dependiendo de su posición y/o texto precedente.

Luego de examinar el texto durante un tiempo, buscando patrones o pistas que me hagan entender cómo era codificado el mensaje, encontré varias palabras repetidas, tales como "pze", "jmmxwr", "as", "dssd" y otras. Supuse entonces que el texto era codificado utilizando un patrón regular de corrimientos.

Seguí observando el texto hasta que me concentré en los números. El número "1321" precedido por las tres letras "NXC" en mayúscula me sonó a "RFC 1321". Y justamente la RFC 1321 describe el algoritmo de cifrado MD5, así que muy equivocado no debería estar. Suponiendo, claro está, que este algoritmo de cifrado no le estaba aplicando trasposición alguna a los números.

Siguiendo esta línea de pensamiento, para transformar "NXC" en "RFC" debía trasponer 4 posiciones a 'N' y 8 a 'X' (siguiendo el orden del alfabeto inglés). En definitiva sumar 4, luego 8, y no modificar la tercera letra:

'N' + 4 = 'R'
'X' + 8 = 'F'
'C' + 0 = 'C'

Aplicando estos corrimientos sobre el texto precedente (excluyendo símbolos de puntuación, números y caracteres especiales), descubrí el siguiente texto:

makswye zagakt (NXC 1321)
 ++ ++  ++ ++   ++
 48 48  48 48   48
 vv vv  vv vv   vv
message digest (RFC 1321)

Volví a aplicar la misma trasposición sobre otra palabra que me llamó la atención, para estar seguro:

OZA-2
++
48
vv
SHA-2

Evidentemente había encontrado el patrón de cifrado del algoritmo. Entonces procedí a descifrar el resto del mensaje aplicando el patrón de trasposición 048048048048048 sobre cada párrafo (sólo a las letras del alfabeto):

    Ap dewkt kfe jmmxwr J wxekto oipz tdw ijlenwspanc hrkhenly pzap lwk kpauibac yjyllocjalziy zaozeo gf pze jmmxwr ozanw a ygmign ljebax kx skee hwnclh (szej lha fuiten as pjewlez ss w ktnanc snz lha zaozeo sra guphup an dwxwveyamwd).
    At least one number N exists with the interesting property that two specific cryptographic hashes of the number share a common prefix of some length (when the number is treated as a string and the hashes are output in hexadecimal).

    Ij lhek pngbhwm, pze dssd xujutegno sra Jirwsp'k makswye zagakt (NXC 1321) wfd pze OZA-2 dssd (kpauibacwdlu lha lwk zujvrav ajv fextu-kit tip nanaajl).
    In this problem, the hash functions are Rivest's message digest (RFC 1321) and the SHA-2 hash (specifically the two hundred and fifty-six bit variant).

    Lal tdas jmmxwr J te pze oeahdeol nqebaj gnwapwr pzaj reng fkj wdacd lha uoieoj hraxit gf pze poo zagakto as kx lafgpz 5.
    Let this number N be the smallest number greater than zero for which the common prefix of the two digests is of length 5.

    Wdst ek tdw lwjgakt ljiiw fwutkj ob F?
    What is the largest prime factor of N?

Lo que en español se traduce a:

    Existe al menos un número N con la interesante propiedad de que dos hashes criptográficos específicos aplicados sobre dicho número comparten un prefijo de una cierta longitud (cuando el número es tratado como un string y la salida de los hashes en hexadecimal).

    En este problema, las funciones hash son MD5 y SHA-2 (específicamente la variante de 256 bits).

    Sea el número N el menor número mayor a cero para el cual la longitud del prefijo en común es igual a 5.

    Cuál es el más grande factor primo de N?

Interesante propiedad de las funciones hash, la cual desconocía hasta el momento de resolver este desafío. El problema planteaba obtener un número entero mayor a cero tal que sus hashes MD5 y SHA-256 (expresados en hexadecimal) coincidan en las primeras 5 posiciones.

Para obtener la respuesta decidí implementar el siguiente script Bash que haga fuerza bruta desde 1 en adelante hasta encontrar la solución:

#!/bin/bash
N=1 # Número actual
M=0 # Hash MD5
S=1 # Hash SHA-256
while [ "$M" != "$S" ]
do
            MD5=$(echo -n $N | md5)
            SHA256=$(echo -n $N | sha256)
            M=${MD5:0:5} # Primeros 5 caracteres del hash MD5
            S=${SHA256:0:5} # Primeros 5 caracteres del hash SHA-256
            if [ "$M" == "$S" ]; then
                    echo $N
                    break
            fi
            N=$[$N + 1]
done

Notar que, al momento de computar los hashes, el script trabaja con el número como si fuese un string. Por otro lado, las herramientas md5 y sha256 por defecto retornan el hash en formato hexadecimal.

Luego de unos minutos de ejecución el script retorno el valor 282033.

Se puede comprobar que es correcto ejecutando:

emi@hal9000:~ % echo -n 282033 | md5
93976292ab76477fcffbaf18aa6ac6ac
emi@hal9000:~ % echo -n 282033 | sha256
939761aff3d8edba5dbba18475bdeeab7b34697ca15e9b54eb8e50835d87acce

Ahora bien, ya tenía el número N, sólo me faltaba obtener su máximo factor primo. Para ello recurrí a la herramienta factor incluida en todo sistema GNU/Linux y *BSD:

emi@hal9000:~ % factor 282033
282033: 3 3 31337

Espero que les haya gustado ;)


Tal vez pueda interesarte


Compartí este artículo