Hack It 5 — Game Failez

El fichero adjunto se llama sonic.md, pesa 262.144 bytes y no tiene nada de markdown: es una ROM de Sega Mega Drive, con su header SEGA MEGA DRIVE en el offset 0x100. El juego arranca, pide una contraseña de ocho letras y, teclees lo que teclees, falla. «Game Failez». Hay que encontrar las ocho letras que lo hacen pasar.

La pantalla que hay que ganar y lo único que devuelve: eliges ocho letras una a una, confirmas, se pone todo rojo y vuelta a empezar. Con cualquier combinación. Las dos capturas son de rejugar la ROM en un emulador ahora, tecleando AAAAAAAA; no son de la noche del concurso.

El título y el enunciado cuentan la misma broma —un bootleg de bazar que no rula— y durante unas cuantas horas nos la creímos al pie de la letra: llegamos a escribir, con todas sus letras, que el juego estaba roto y que ninguna contraseña podía ganarlo. Era mentira. Este writeup va tanto de cómo se resuelve como de por qué ese diagnóstico era falso, porque el error de fondo es de los que se repiten.

La ROM son 256 KB de código 68000 y gráficos comprimidos, con entropía alta por todas partes; a simple vista no hay nada. Pero dentro, escondido entre lo que parecían datos de tiles, hay una máquina virtual completa de Brainfuck —un lenguaje minimalista de ocho instrucciones— y la comprobación de la contraseña es un programa de Brainfuck de 206.758 instrucciones que corre en ella. Todo el reto está en entender ese programa.

Dónde se compara la contraseña

Antes de nada hay que localizar quién mira lo que teclea el jugador. Un strings sobre la ROM suelta un literal muy claro, PASSWORD, y siguiendo quién lo referencia se llega a dos funciones: una que pinta la pantalla de introducir la clave, y otra que la valida. La que valida deja el buffer de la contraseña en 0xFF0000 (ocho bytes) y salta a una rutina en 0x1afc. Y ahí no hay ninguna comparación de strings: hay un bucle que lee bytes, los pasa por una tabla de traducción y despacha sobre el valor traducido. Punteros que suben y bajan, una cinta de bytes en RAM, ocho casos. Eso es un intérprete.

Dentro de la ROM hay un intérprete de Brainfuck

Brainfuck tiene ocho símbolos: mover el puntero a izquierda o derecha, sumar o restar uno a la celda actual, leer un byte, y abrir o cerrar bucle. La ofuscación está en que el programa no se parece a Brainfuck ni de lejos hasta que aplicas la tabla de traducción de la ROM: 256 entradas que mapean cada byte a un opcode canónico, con nueve valores distintos —los ocho símbolos más un NOP—. Cada símbolo tiene varias codificaciones, así que el programa parece ruido. Con la tabla, extraerlo es un pegote de diez líneas:

rom   = open('sonic.md', 'rb').read()
TABLE = rom[0x78c6:0x78c6 + 256]
raw   = rom[0x79c6:0x79c6 + 0x327a6]              # 0x327a6 = 206758
M = {0x80: '>', 0xcf: '<', 0xd9: '+', 0xcc: '-',
     0xc2: ',', 0x62: '[', 0x05: ']', 0x23: '#'}
prog = ''.join(M.get(TABLE[b], '') for b in raw)  # los NOP se caen solos

Lo que sale son 206.758 comandos: 8 lecturas (,), 6.126 pares de corchetes y un noveno símbolo que no existe en Brainfuck estándar, #. Ese # es el que cierra el reto. Su handler, leído del desensamblado 68000, hace una sola cosa: return celda[puntero] == 0x4F y devuelve de la rutina en el acto. 0x4F es la O de «OK». O sea: el primer # que se ejecute decide el resultado, y gana quien consiga que la celda bajo el puntero valga 0x4F en ese momento.

Con eso ya se puede escribir un intérprete fiel —cincuenta líneas de Python, sacando la semántica del desensamblado y no suponiéndola— y hacer la primera medición:

MYMEGAPW → 0x4f        (la 'O' de OK)
AAAAAAAA → 0x4e        (0x4e es 'N')
ZZZZZZZZ → 0x4e

Ese 0x4e es una N, justo un valor por debajo del que hace falta. Y aquí es donde el reto nos ganó unas horas.

El callejón: «esto es inganable»

Ejecutamos 5.000 entradas aleatorias A–Z. Todas dieron 0x4e. También todo el rango 0–255. Siempre 0x4e. Instrumentando la cinta se veía que la entrada sí se procesaba, pero justo antes de la decisión las celdas relevantes valían lo mismo para cualquier clave. De ahí salió la conclusión, escrita con todas sus letras: el check es independiente de la entrada, ningún password lo gana. Y encajaba perfectamente con «Game Failez» y con el «no funciona como esperaba». El bootleg roto que no valida nada. Una lectura preciosa.

Era falsa, y por dos errores encadenados. El primero es estadístico: 5.000 muestras no dicen nada sobre un espacio efectivo de 2⁶⁴. La probabilidad de que un muestreo aleatorio acierte un check de 64 bits es indistinguible de cero, así que «5.000 intentos fallidos» es exactamente lo que esperas tanto si el checker está roto como si es perfecto. El experimento no distinguía entre las dos hipótesis, luego no era evidencia de ninguna. Un muestreo aleatorio no prueba una ausencia.

El segundo fue de lectura. En la cola del programa aparece un patrón, [ >…[-] <…[-] ], que pone a cero dos celdas a la vez, y lo interpretamos como un «move destructivo»: una comparación que en vez de restar borra los dos operandos, y por tanto destruye el hash de la entrada antes de compararlo. El bug del autor, el chiste del reto. Tampoco: ese patrón es el idiom compilado estándar de if (x) { y = 0; }. Encadenando bloques así, con celdas preseteadas a 1, se construyen NOT y AND lógicos, que es justo lo que necesita un checker que compara bits y los combina. Lo que parecía un bug era el compilador de Brainfuck haciendo su trabajo.

La corrección no llegó mirando más fuerte, sino empezando de cero en frío, sin heredar nada del análisis anterior. Sin el marco «esto está roto», fue directa a descompilar la cola y a validar el instrumento en vez de a confirmar la teoría. La regla que nos llevamos: cuando dos análisis parten del mismo dato sesgado, el consenso entre ellos no valida nada; lo que rompe el bloqueo es un analista que no comparte el marco.

La palanca: el puntero se resuelve sin ejecutar

En un Brainfuck normal no sabes en qué celda estás sin ejecutar el programa: el puntero depende del flujo. Aquí sí se sabe, y esta es la observación que vuelve el problema tratable. Recorriendo el programa y llevando la cuenta del desplazamiento, los 6.126 bucles tienen desplazamiento neto cero: el puntero a la entrada de cada [ es el mismo que a la salida de su ]. Es la firma del código generado por un compilador, que asigna cada variable a una celda fija y deja el puntero donde lo encontró.

Consecuencia: se puede calcular a qué celda apunta cada uno de los 206.758 comandos con una única pasada lineal, sin ejecutar nada.

dp, dpat, stack, bad = 0, [0] * len(bf), [], []
for i, c in enumerate(bf):
    dpat[i] = dp
    if   c == '>': dp += 1
    elif c == '<': dp -= 1
    elif c == '[': stack.append((i, dp))
    elif c == ']':
        j, d0 = stack.pop()
        if d0 != dp: bad.append((j, i))     # bucle no balanceado

bad sale vacía y el rango del puntero es exactamente 0..81:

$ python3 dpmap.py
final dp 1 unbalanced loops: 0
dp range 0 81

Dos regalos. Uno: como el puntero nunca sale de 0..81 y la cinta tiene 82 celdas, el recorte que hace la ROM para no salirse nunca se activa —el intérprete «acotado» y el «infinito» son el mismo programa, y toda la sospecha de si ese recorte era el bug queda cerrada—. Y dos: ahora se puede descompilar con números de celda absolutos, y el río de >>>><<<<+++ se convierte en un programa legible:

$ python3 bfdis.py 206325 206460
206328 c80  c80 +1
206332 c77  while c77:          <- el gate
206335 c79    c79 +1
206347 c79  while c79:          <- camino de éxito
206350 c81    while c81:
206351 c81      c81 -1
206353 c81    c81 +79           <- escribe 0x4f = 'O'
206432 c81    #  (c81)          <- ve 'O' -> PASA

A partir de aquí es ingeniería inversa normal.

La grieta: la clave se valida en dos mitades

Con el desensamblador de celdas absolutas, la cola del programa se lee de un tirón: es una cadena de comparaciones sobre 32 celdas más una condición extra, compilada como un && gigante. Y al medir qué caracteres influyen en esos 32 bits aparece algo desconcertante: los caracteres 0–3 no afectan al hash. Solo importan del 4 al 7. Parece que el autor tiró media contraseña a la basura.

No la tiró: hay un reseed escondido en la cola del bloque del cuarto carácter. El programa funciona en dos mitades independientes. Primero mezcla los caracteres 0–3 en un estado de 32 bits, lo compara contra una constante, y aparca el resultado (sí/no) en una sola celda, c44. Luego reinicializa el estado y mezcla los caracteres 4–7, comparando contra otra constante. Al final pliega c44 dentro del segundo resultado. Gana la contraseña si ambas mitades cuadran.

Esto no hay que creérselo: se mide parando la ejecución en los dos puntos y volcando el estado. La columna izquierda solo depende de los cuatro primeros caracteres; la derecha, solo de los cuatro últimos:

              estado tras chars 0-3   estado tras chars 4-7   c44
MYMEGAPW      0xD2EECDC7              0xB937BA6D              1
MYMEAAAA      0xD2EECDC7              0x3889C54B              1
AAAAGAPW      0x8F36C537              0xB937BA6D              0
AAAAAAAA      0x8F36C537              0x3889C54B              0

Léelo por columnas: cambiar la segunda mitad no toca el estado de la primera, y al revés. c44 se enciende exactamente cuando los cuatro primeros son los buenos, pase lo que pase con el resto. La prueba redonda es cambiar un único carácter del final:

MYMEGAPW → primer # = 0x4f
MYMEGAPX → primer # = 0x4e     <- falla, pero con la 1ª mitad ya validada

MYMEGAPX falla con el flag de la primera mitad puesto: las dos mitades ni se miran. Y esa es la grieta del diseño. Un autor que quiere un crackme duro no parte la clave en dos mitades independientes, porque eso convierte el espacio de búsqueda en algo trivial:

no son 26⁸ = 208.827.064.576 combinaciones, son dos espacios de 26⁴ = 456.976. Un factor de 228.500.

Validar el instrumento antes de creerse su negativo

Después del callejón de las «5.000 pruebas fallidas», lo último que podíamos hacer era volver a fiarnos de un resultado negativo sin comprobar que el instrumento medía bien. Así que antes de gastar cómputo, validamos la cadena de comparación: se inyecta a mano el vector de requisitos en la cinta, justo antes de que empiece la comparación, y se mira qué opina el #.

• Forzando el vector completo (las 32 celdas más c44): el primer # ve 0x4f.
• Volteando cualquiera de las 33 condiciones, una a una: 0x4e.

$ python3 -c "…inyecta el vector y voltea cada condición…"
vector completo -> primer #  0x4f
condiciones volteadas 33 | las que NO dieron 0x4e: 0

Las 33 mueven el veredicto. Eso vale por dos: confirma que hemos leído bien la cadena, y —lo que más falta hacía— demuestra que la cadena funciona correctamente. El checker nunca estuvo roto. La regla: un instrumento que no has validado contra un positivo conocido no produce evidencia de nada, y menos evidencia negativa. Si no tienes un positivo, fabrícalo e inyéctalo.

La búsqueda

Con las dos mitades separadas, la fuerza bruta es trivial. Cada mitad son 456.976 combinaciones de cuatro letras, y cada ejecución del programa comprimido baja a un par de milisegundos. No hace falta ni llegar al final: para la primera mitad se comprueba c44 en el punto del reseed; para la segunda, las 32 celdas justo antes de la cadena. En paralelo, cada mitad se recorre entera en poco más de un minuto:

$ python3 search.py 2       # caracteres 4-7
HITS: ['GAPW']              # ~62 s

$ python3 search.py 1       # caracteres 0-3
HITS: ['MYME']             # ~89 s

Un único hit en cada mitad, sobre el espacio completo. No es una heurística ni un candidato mejor rankeado: es exhaustivo, así que la solución es única. Dos minutos y medio en total, frente a los cientos de días que costaría la fuerza bruta ingenua sobre los 26⁸.

La contraseña

MYMEGAPW

«MY MEGA PW». Un chiste de Mega Drive, que es la confirmación blanda de que dimos con la intended y no con una colisión. La verificación final, contra el intérprete y sin parchear nada, es que el programa imprime su propio veredicto si lo dejas correr más allá del primer #:

MYMEGAPW → b'OK\n'
AAAAAAAA → b'NOK\n'

Lo que nos llevamos

1. Instrumenta antes de teorizar. El intérprete fiel, validado contra el desensamblado, es lo que convierte 206 KB de ruido en algo sobre lo que se puede experimentar.
2. El muestreo aleatorio no prueba una ausencia. 5.000 entradas sobre un espacio de 2⁶⁴ dan el mismo resultado con un checker roto que con uno perfecto. Si tu experimento no distingue entre las dos hipótesis que te importan, no es evidencia: es ruido con formato de conclusión.
3. Desconfía de la hipótesis que encaja demasiado bien con el enunciado. «Game Failez» nos empujó a querer que el crackme estuviera roto, y una vez querido, apareció el bug que lo demostraba. La coincidencia temática no es evidencia mecánica.
4. Busca la propiedad estructural que hace el problema tratable. Aquí fue el desplazamiento neto cero: una pasada lineal que convierte Brainfuck en un lenguaje con variables.
5. Valida el instrumento contra un positivo conocido, aunque tengas que fabricarlo e inyectarlo.

La ROM es una ROM comercial de Mega Drive y no la redistribuimos: se descarga del propio reto y se deja junto a los scripts, que reproducen todos los números de este writeup.

El material — la VM de Brainfuck, el descompilador, la resolución estática del puntero y la búsqueda por mitades están en euskal34/hack-it/5.