Procesador desconocido ingeniería inversa en un solo programa

TL; DR: realizamos ingeniería inversa de un programa escrito para una arquitectura de CPU completamente desconocida sin ninguna documentación en la CPU (sin un emulador, sin ISA, sin todo) en solo diez horas. Del artículo aprenderás cómo lo hicimos ...

El fin de semana pasado, el equipo CMU PPP y yo participamos en el equipo Dragon Sector Teaser CTF 2019 para relajarnos y alejarnos de la dura fecha límite de CHI 2020 . Dragon Sector es un equipo polaco respetado con una historia de CTF interesantes, por lo que me preguntaba qué tienen en stock.

Después de resolver “ummmfpu”, una tarea que incluía ingeniería inversa de bytecode para el coprocesador de punto flotante uM-FPU de Micromega, decidí participar en una competencia para resolver el problema de CPU Adventure, que en ese momento no fue resuelto por ninguno de los equipos (como resultado fuimos los únicos que completamos la tarea).

Aquí hay una descripción de la tarea CPU Adventure:

Mi abuelo en los años 60 se dedicó al desarrollo de computadoras. Al poner las cosas en orden en su ático, encontré un auto extraño. Al lado de la máquina había una pila de tarjetas perforadas marcadas como "Dragon Adventure Game". Después de un tiempo, logré conectarlo a equipos modernos, pero el juego es demasiado complicado y no puedo llegar al final sin hacer trampa. Me puedes ayudar Adjunto una transcripción de tarjetas perforadas utilizadas en la máquina. Se afirma que la máquina tiene 4 registros de propósito general, 1 kibibyte de memoria de datos y 32 kibibyte de memoria de comando. Para jugar, conéctese al servidor de la siguiente manera: socat tcp4-connect:cpuadventure.hackable.software:1234 fd:0,rawer Sugerencia: el procesador de la máquina es único, no intente buscar información de Google en él.

game.bin

Después de conectarnos al servidor, recibimos la siguiente información:

THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.

SELECT AN OPTION:

- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY

YOUR CHOICE:

Genial Este es un juego de aventuras de la vieja escuela. Después de jugar un poco, nos dimos cuenta de que puedes luchar contra los enemigos y obtener una bandera de este personaje Valis si lo complacemos:

YOUR CHOICE: T

YOU ENTER THE TAVERN AND APPROACH VALIS.

- HEY, I WAS WONDERING IF YOU COULD HELP ME FIND THE FLAG?
- THE FLAG? MAYBE, BUT FIRST, I NEED A REDBULL.
- I... I DON'T HAVE A REDBULL.
- WELL THEN, MAKE YOURSELF USEFUL AND FIND ONE.

THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.

SELECT AN OPTION:

- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY

YOUR CHOICE:

Primeros pasos

No game.bin el juego por mucho tiempo, dándome cuenta de que lo más probable es que sea más importante realizar ingeniería inversa en el archivo game.bin . Lo abrí en un editor hexadecimal, esperando ver valores binarios. Imagina mi sorpresa cuando vi esto:

  110011111101000000111100110010001110000011001101000000000000110010011101010000001101001111100001111111001100111000000011 ... 

Este es literalmente un archivo binario: un archivo de texto que no contiene nada más que caracteres ASCII 1 y 0. Sabemos que es muy probable que sea el código de máquina del procesador, pero además de tener 4 registros, 1 kbyte de memoria de datos y 32 kibibyte de memoria de instrucciones, no se sabe nada al respecto. Por lo tanto, nuestra primera tarea seria será determinar el tamaño de la unidad de este archivo binario (por ejemplo, ¿tiene una dimensión de 8 bits? ¿O, tal vez, tiene una dimensión de 12 bits o 18 bits, como en algunas arquitecturas antiguas ?)

Para averiguar el tamaño de un archivo desconocido, utilicé un viejo truco: cambié el tamaño del cuadro de texto hasta que la longitud del salto de línea correspondiera a la alineación. Este método es ideal para cosas como texto cifrado XOR múltiple, formatos de archivo desconocidos (sin comprimir) y código de una CPU desconocida:


Cambiar el tamaño del cuadro de texto

En esta comprobación rápida, descubrí que el tamaño de la unidad de este archivo debería ser un divisor de 20 (el ancho de la ventana alineada). Para averiguar el tamaño exacto, rápidamente escribí un script buscando largas líneas repetidas (suponiendo que cualquier código tiene secuencias estereotipadas repetidas). La línea de repetición más larga fue el siguiente bloque de 425 bits, encontrado en 43625 y 44510:

  10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100 

Como la distancia entre las repeticiones es de 885, llegamos a la conclusión de que la dimensión debe ser de 5 bits, es decir. una CPU desconocida debe tener bytes de 5 bits. Progreso!

Buscamos codificaciones de tarjetas perforadas de 5 bits y rápidamente nos decidimos por la codificación anterior con el código Baudot . Y, de hecho, cuando utilizamos el decodificador en línea para decodificar algunos fragmentos, ¡obtuvimos texto legible!

⇩DRAGON⇩AQUÍ⇧; ⇧⇧⇩SHE⇩ APARECE⇩TO⇩BE⇩GUARDANDO⇩ ALGUNOS⇩KIND⇩OF⇩A⇩BOTTLE⇧; &. &. ⇩THERE⇩IS⇩A⇩B

Código LSB Baudot ITA mejorado de 425 bits

Luego intentamos decodificar todo el archivo usando el código Bodo, pero en los primeros 20 mil bits obtuvimos basura, después de lo cual había un texto perfectamente legible. Esto nos dejó en claro que la primera parte del archivo pertenece a la sección "código", seguida de la sección "datos", que contiene líneas constantes. Asumimos que la máquina probablemente usa código Bodo para E / S y, por lo tanto, también almacena líneas constantes en la codificación Bodo en la memoria. Para hacer que el segmento de código sea más legible, decidí codificarlo usando una codificación de base 32, similar a la codificación hexadecimal, pero expandiéndola con el alfabeto 0-9a-v. Así es como se ve el archivo game.bin con la primera parte codificada por base-32 y la segunda parte decodificada por Bodo (el archivo completo se publica aquí: game.b32 ):

pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf1sf24p5f3r9c11qad0f0sf1df26p5f39c21qad0f05f1ff26p5f39c41qad0f08f1df26p5f39c81qad0f0hf1ef26p5f3r1c00qaq15c20qcl0f01f1of27p5f3p3g3psf35c10qal0f02f1nf27p5f3p3g3psf3rf0hf1nf27p5f3f05f16f27p5f3rf84f95101311fl0f510f84907qa40b518447qa40b514f84f95k9m0k9m0k9m0907qa40b511447qa40b512ruougf10f20g0i9g0i910931b320u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1onp0o9f0o9f0o9f0o9f0onf0ot82odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df24p5f3r9c11qa835548755
[...]
93e9n59ka8fo87r85g8ui8ml8ed87b9h89u291u82333333333456789abcdb01234567892)%c3BOTTLE OF SOPLICA PIGWOWAENEMY HEALTH:

YOU ATTACK

YOU APPROACH REDFORD.



YOU ENTER THE TAVERN AND APPROACH VALIS.
[...]

Para simplificar, llamaré a las unidades de cinco bits "bytes" a continuación. Entre nosotros en el equipo, se nos ocurrieron otros nombres para ellos, los llamé croquetas y Zak, hacks.

Arquitectura de procesador desconocida ingeniería inversa

Ahora llegamos a la parte difícil: ingeniería inversa de 4000 bytes de código que se ejecuta en una arquitectura de CPU única completamente desconocida. Según el código, es bastante obvio que esto debería ser un conjunto de instrucciones de longitud variable , porque es imposible encontrar un patrón repetitivo estable notable en él. Pasé unas horas en esto, luego el miembro de mi equipo Zachary Wade (@ zwad3) comenzó a ayudarme. En primer lugar, comencé a buscar piezas de código duplicadas, sugiriendo que a menudo usarían una pequeña cantidad de instrucciones. Comencé a dividir el código en secuencias repetidas más cortas que eran más convenientes para el análisis. Me gustaría decir que fue un proceso riguroso, pero de hecho, se utilizó principalmente el siguiente algoritmo vago:

• Revisamos el código y buscamos si algo se repite con mucha frecuencia.
• Realice el procedimiento de búsqueda y reemplazo para insertar una nueva línea junto a esta repetición
• Explore las similitudes / diferencias entre las líneas divididas resultantes.
• Repita este proceso durante aproximadamente una hora ...

Por ejemplo, uno de los patrones que descubrí fue "0f0.f", donde "." indica un personaje desconocido. Rompí la cadena en este patrón y obtuve lo siguiente:

pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf
1sf24p5f3r9c11qad0f0sf
1df26p5f39c21qad0f05f
1ff26p5f39c41qad0f08f
1df26p5f39c81qad0f0hf
1ef26p5f3r1c00qaq15c20qcl0f01f
1of27p5f3p3g3psf35c10qal0f02f

Muy útil! De la segunda y tercera línea vemos que hay "... p5f3r9c ..." y "... p5f39c ...", y esto nos sugiere que "r" es un código de operación de un solo byte, es decir, "... 5f3" es el final de un código de operación, y " 9c .. "es el comienzo de otro. En las últimas dos líneas vemos "p5f3r1c ..." y esto significa que "1c .." es otro código de operación, y "p3 ..." es también otro código de operación.

Continué dividiendo las instrucciones una y otra vez de manera similar, usando las similitudes y diferencias de bloques similares para encontrar instrucciones probables. Al final, obtuve algo como esto:

pv83
pi70
pk00
p7a0
qfgv
pjg3
f0k
f13
f28
p5f3
pv10
pk40
pn60
f0s
f1s
f24
p5f3
r
9c11
qad0
f0s
f1d
f26
p5f3
9c21
qad0
f05
f1f

Supuse que "p" y "q" eran instrucciones con tres bytes de operandos, "f0", "f1" y "f2" eran instrucciones con un operando, y "9c" era una instrucción con dos operandos. Sin embargo, no sabía qué es cada una de estas instrucciones.

Así que busqué en el directorio de todas las instrucciones "p" que resalté, y descubrí que en este momento las instrucciones más frecuentes con "p" eran "p5f3". Además, al observar los lugares donde ocurre, descubrí que siempre está precedido por las instrucciones "f0", "f1" y "f2". Al observar todos los operandos "f0", "f1" y "f2", noté que los operandos f2 siempre están en el rango 4-8. Recordando que la CPU tiene 32 kb de memoria de programa para direccionamiento que requiere 15 bits, supuse que "f0", "f1" y "f2" cargaron alguna dirección con f2 como el byte alto. Cuando conecté algunas de estas direcciones, descubrí que todas apuntan exactamente al comienzo de las líneas constantes en la sección de datos. ¡Encontré la función de print ! Inmediatamente se dedujo que "p5f3" es en realidad algún tipo de instrucción para imprimir una línea o llamada; si tiene en cuenta el operando de tres bytes, lo más probable es que sea una "llamada". Nuevamente, mirando las instrucciones "p", me di cuenta de que los tres bytes del operando indican la dirección en orden directo (little-endian) , es decir, el último byte del operando es el byte más alto de la dirección.

¡Fue un gran avance! Hemos identificado nuestra primera instrucción. Habiendo visto que "f0" y "f1" se usan en otros lugares, supuse que no cargan las direcciones, sino uno de los cuatro registros (por ejemplo, f0 carga el registro 0) con constantes de 5 bits con direccionamiento directo. Esto es lógico para p5f3: carga tres argumentos de registro para la función 3f5 ("print_string").

Comencé a escribir un desensamblador que reconoce la expresión "imprimir" (f0x, f1x, f2x, p5f3), colocando la sustitución de la línea impresa en el código desensamblado. Debido a la gran cantidad de líneas en el programa, el código desensamblado rápidamente se volvió muy legible, y se hizo más fácil encontrar la ubicación de los bloques de funciones (el código desensamblado completo está aquí ):

0: call 38v
4: call 7i
8: call k
c: call a7
g: q vgf

k: call 3gj
o: print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
15: call 1v
19: call 4k
1d: call 6n
1h: print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
1u: ret

1v: unk 9
20: unk c
21: unk 1
22: unk 1
23: q 0da
27: print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: unk 9
2l: unk c
2m: unk 2
2n: unk 1
2o: q 0da
2s: print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: unk 9
3a: unk c
3b: unk 4
3c: unk 1
3d: q 0da
3h: print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: unk 9
3v: unk c
40: unk 8
41: unk 1
42: q 0da
46: print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret

A partir de este pequeño fragmento de código, logré descubrir varios aspectos: la instrucción "q0" debería indicar alguna ramificación condicional (porque se usa para omitir la impresión de direcciones innecesarias en la función 1v), y las instrucciones "9c11", "9c21", "9c41", " 9c81 "debería indicar algún tipo de instrucción AND: comprueban los bits establecidos para ver si estas direcciones están permitidas (esto se insinúa claramente mediante el uso de" 1 "," 2 "," 4 "y" 8 "en estas instrucciones).

Durante las siguientes dos horas, Zachary Wade (@ zwad3) y yo resolvimos las diversas instrucciones, formulando y refinando nuestras suposiciones sobre lo que estaban haciendo. Tener muchas declaraciones impresas legibles hizo nuestro trabajo mucho más fácil. Decidimos que cada uno de nosotros individualmente escribiría su propio desensamblador para poder examinar las instrucciones a nuestro propio ritmo y compartir nuestros hallazgos.

Código de ingeniería inversa

Después de unas horas, comencé a hacer grandes progresos en el desmontaje. Después de examinar el código que funcionaba con el inventario del usuario (más específicamente, la función "beber" y cada controlador asociado con él), encontramos instrucciones para guardar y cargar desde la memoria (no olvide que la CPU tiene 1 kibibyte de memoria de datos). Luego descubrimos que algunas instrucciones aritméticas / lógicas (ALU) toman operandos de memoria (por ejemplo, "9c41" significa "ejecutar Y con valor en la dirección de datos 1 con valor 4"). A partir de esto, pudimos recrear las variables en la memoria de datos, por ejemplo, en [0] el identificador de NPC se almacena en la ubicación actual, y en [6,7] se almacena la salud actual del jugador (los 5 bits inferiores en [6], los 5 bits más antiguos en [7] ]). En esta etapa, pasé de las instrucciones de ingeniería inversa a anotar mi código desmontado e ingeniería inversa del programa en sí. A continuación se muestra mi notación divertida para valores de 5 bits:

_start:
call init

L4:
call check_moves
call print_menu
call handle_command
br 4

print_menu:
call print_itemname
print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
call print_moves
call print_npcmenu
call print_itemmenu
print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
ret

print_moves:
and 0y1, [1]
brz 2k
print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: and 0y2, [1]
brz 39
print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: and 0y4, [1]
brz 3u
print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: and 0y8, [1]
brz 4j
print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret

print_npcmenu:
add 0y0, [0]
brz 6m
sub 0y2, [0]
br<c> 5p
print 7o1 # '\x0e- (\x0fT\x0e)\x0fALK TO \x00'
call print_npcname
call print_crlf
5p: sub 0y1, [0]
brz 6m
print 7n2 # '\x0e- (\x0fF\x0e)\x0fIGHT \x00'
call print_npcname
call print_crlf
6m: ret

print_itemmenu:
print 7nh # '\x0e- (\x0fD\x0e)\x0fRINK\r\n\x00'
print 765 # '\x0e- \x0fSHOW \x0e(\x0fI\x0e)\x0fNVENTORY\r\n\x00'
ret

Todavía tenemos muchos códigos de operación desconocidos, por ejemplo, aunque descubrimos que "qa" es una ramificación condicional en cero (branch-on-zero, brz), no pudimos entender qué es "qc" (indicado anteriormente como br <c>). Pero eso fue suficiente para comenzar a entender la lógica del programa.

De hecho, el juego permite al jugador moverse alrededor de un mapa de 8 × 8 en el que se colocan al azar NPC (dragones, toros rojos y humanos). Puedes luchar con cualquier NPC (incluso Valis, a pesar de la falta de un elemento de menú correspondiente). Durante la batalla, puedes atacar al enemigo, causando una cantidad aleatoria de daño o falla, después de lo cual el enemigo ataca al jugador, causando también una cantidad aleatoria de daño o falla. También puedes elegir un bloqueo de escudo, gracias al cual el enemigo falla o golpea el escudo sin causar daño. Finalmente, puede hacer trampa al aumentar su salud a 1000, pero en este caso, la variable oculta ("engañado", dirección 10) se establece en 1. Si el jugador mata con éxito al enemigo, un objeto se cae de él, generalmente una botella de algo de alcohol (obviamente, Este juego no es para niños).

El NPC Valis principal, del cual el jugador debe recibir la bandera, tiene una máquina de estado en la que le pide al jugador varios artículos: un montón de bebidas Red Bull (obviamente obtenidas al derrotar a los enemigos Red Bull), varias bebidas mixtas (por ejemplo, gin tonic) para obtenerlos, debes derrotar al dragón azul y al dragón gris, y luego mezclar los objetos que se cayeron de ellos), y la tira de poder, que se puede obtener si derrotas a otra persona NPC en el juego (Redford) o lo ayudas. Si cumple con toda esta larga serie de solicitudes, él le dará la bandera, pero solo si la variable "engañado" no es igual a 1. Es decir, nuestra tarea es ganar el juego sin hacer trampa. Como comenzamos con solo 100 HP, como todos los enemigos, con el paso habitual será imposible derrotar a todos los enemigos (para obtener todas las cosas necesarias que necesita para derrotar a unos 20 oponentes). Es necesario modificar el RNG de alguna manera, para que el enemigo siempre falle.

Los números aleatorios son generados por una función que es similar a algún tipo de PRNG (dirección 37a), pero utiliza instrucciones únicas que no se utilizan en ningún otro lugar, por lo que no podemos realizar ingeniería inversa. Sin embargo, notamos que carga su vector de estado desde tres direcciones en la memoria ([11], [12] y [13]), es decir, su estado completo solo toma 15 bits. Esto significa que el RNG debe tener un período corto, no más de 2 ^ 15 = 32768 de longitud.

Mientras (sin éxito) intentamos revertir la implementación de RNG, Jay Bosamia (@ jay_f0xtr0t) y Matthew Savage (@thebluepichu) implementaron un exploit. Simplemente enviando el comando "escudo" 100,000 veces seguidas, pudimos obtener una secuencia de "golpes" y "fallas" enemigas correspondientes a la salida de bits del RNG. Nos aseguramos de que esta secuencia se repita con un período de 32767. Gracias a esto, pudimos reunir nuestra hazaña principal: cuando luchamos con el primer enemigo que conocimos, cerramos nuestros escudos 40 veces para recrear la secuencia de golpes y fallos, buscamos esta secuencia en una secuencia periódica grande y luego descubrimos cuándo proteger y cuándo atacar para que el enemigo siempre falle. Luego, recorrimos todo el mapa en modo killhobo , matando a todos y recogiendo su botín. Al final, volvimos a Valis y cortésmente pedimos nuestra bandera, que recibimos:

DrgnS{m4kin9-v4lis-happy-w1th-n4t1ve-b4ud0t-cpu}

Fuh! De hecho, una verdadera aventura. ¡Todavía no puedo creer completamente que pasamos de una cadena binaria y una falta total de documentación del procesador a dos desensambladores casi completos y un código desensamblado limpio en menos de 10 horas! Todo el código está disponible en GitHub: mi desensamblador , el desensamblador de Zachary , mi código desmontado sin procesar , mi código desmontado anotado , el cliente de Matt's Exploit .