TL; DR: desenvolvemos engenharia reversa de um programa criado para uma arquitetura de CPU completamente desconhecida, sem nenhuma documentação na CPU (sem um emulador, sem ISA, sem tudo) em apenas dez horas. A partir do artigo, você aprenderá como fizemos isso ...
No final de semana passado, a equipe da CMU PPP e eu participamos da equipe CTF 2019 do Dragon Sector Teaser para relaxar e nos afastar do prazo final do
CHI 2020 . O Dragon Sector é uma equipe polonesa respeitada, com uma história de
CTFs interessantes, então eu queria saber o que eles têm em estoque.
Tendo resolvido o “ummmfpu”, uma tarefa que incluía a engenharia reversa de bytecode para o coprocessador de ponto flutuante Micromega uM-FPU, decidi participar de uma competição para resolver o problema de CPU Adventure, que na época não era resolvido por nenhuma das equipes (como resultado fomos os únicos que concluíram a tarefa).
Aqui está uma descrição da tarefa CPU Adventure:
Meu avô nos anos 60 estava envolvido no desenvolvimento de computadores. Colocando as coisas em ordem no sótão, encontrei um carro estranho. Ao lado da máquina havia uma pilha de cartões perfurados marcados com "Dragon Adventure Game". Depois de algum tempo, consegui conectá-lo a equipamentos modernos, mas o jogo é muito complicado e não consigo chegar ao fim sem trapacear. Você pode me ajudar? Estou anexando uma transcrição de cartões perfurados usados na máquina. Alega-se que a máquina possui 4 registros de uso geral, 1 kibibyte de memória de dados e 32 kibibyte de memória de comando. Para jogar, conecte-se ao servidor da seguinte maneira: socat tcp4-connect:cpuadventure.hackable.software:1234 fd:0,rawer Dica: o processador da máquina é único, não tente pesquisar informações nele.
game.bin
Após conectar-se ao servidor, recebemos as seguintes informações:
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:
Ótimo. Este é um jogo de aventura da velha escola. Depois de jogar um pouco, percebemos que você pode lutar contra inimigos e obter uma bandeira desse personagem Valis, se quisermos:
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:
Primeiros passos
Não joguei o jogo por muito tempo, percebendo que provavelmente é mais importante fazer a engenharia reversa do arquivo
game.bin . Abri-o em um editor hexadecimal, esperando ver valores binários. Imagine minha surpresa quando vi isso:
110011111101000000111100110010001110000011001101000000000000110010011101010000001101001111100001111111001100111000000011 ...
Este
é literalmente um arquivo binário - um arquivo de texto que não contém nada além dos caracteres ASCII 1 e 0. Sabemos que esse provavelmente é o código de máquina do processador, mas além de ter 4 registros, 1 kbyte de memória de dados e 32 kibibyte de memória de instruções,
nada se sabe sobre ele. Portanto, nossa primeira tarefa séria será determinar o tamanho da unidade desse arquivo binário (por exemplo, possui uma dimensão de 8 bits? Ou, talvez, uma dimensão de 12 ou 18 bits, como em algumas
arquiteturas antigas ?)
Para descobrir o tamanho de um arquivo desconhecido, usei um truque antigo - redimensionei a caixa de texto até que o comprimento da quebra de linha correspondesse ao alinhamento. Esse método é ótimo para coisas como vários textos criptografados em XOR, formatos de arquivo desconhecidos (não compactados) e código de uma CPU desconhecida:
Alterar o tamanho da caixa de textoNessa verificação rápida, descobri que o tamanho da unidade desse arquivo deve ser um divisor de 20 (a largura da janela alinhada). Para descobrir o tamanho exato, escrevi rapidamente um script procurando longas linhas de repetição (supondo que qualquer código tenha seqüências repetidas estereotipadas). A linha de repetição mais longa foi o seguinte bloco de 425 bits, encontrado em 43625 e 44510:
10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100
Como a distância entre as repetições é 885, chegamos à conclusão de que a dimensão deve ser de 5 bits, ou seja, uma CPU desconhecida deve ter bytes de 5 bits. Progresso!
Pesquisamos codificações de cartões perfurados de 5 bits e rapidamente instalamos a codificação antiga
com o código Baudot . E, de fato - quando usamos o decodificador on-line para decodificar alguns fragmentos, obtivemos texto legível!
⇩DRAGON⇩HERE⇧; ⇩SHE⇩APPEARS⇩TO⇩BE⇩GUARDING⇩ ALGUM⇩KIND⇩OF⇩A⇩BOTTLE⇧; &. &.
Código LSB Baudot aprimorado de 425 bits
Em seguida, tentamos decodificar o arquivo inteiro usando o código Bodo, mas nos primeiros 20 mil bits conseguimos lixo, após o qual havia um texto perfeitamente legível. Isso deixou claro para nós que a primeira parte do arquivo pertence à seção "código", seguida pela seção "dados", que contém linhas constantes. Assumimos que a máquina provavelmente usa o código Bodo para E / S e, portanto, armazena linhas constantes na codificação Bodo na memória. Para tornar o segmento de código mais legível, decidi codificá-lo usando a codificação base-32, semelhante à codificação hexadecimal, mas expandindo-o com o alfabeto 0-9a-v. Aqui está como o arquivo game.bin se parece com a primeira parte codificada pela base-32 e a segunda parte decodificada pelo Bodo (o arquivo completo é postado aqui:
game.b32 ):
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf1sf24p5f3r9c11qad0f0sf1df26p5f39c21qad0f05f1ff26p5f39c41qad0f08f1df26p5f39c81qad0f0hf1ef26p5f3r1c00qaq15c20qcl0f01f1of27p5f3p3g3psf35c10qal0f02f1nf27p5f3p3g3psf3rf0hf1nf27p5f3f05f16f27p5f3rf84f95101311fl0f510f84907qa40b518447qa40b514f84f95k9m0k9m0k9m0907qa40b511447qa40b512ruougf10f20g0i9g0i910931b320u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1onp0o9f0o9f0o9f0o9f0onf0ot82odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df24p5f3r9c11qa835548755
[...]
93e9n59ka8fo87r85g8ui8ml8ed87b9h89u291u82333333333456789abcdb01234567892)%c3BOTTLE OF SOPLICA PIGWOWAENEMY HEALTH:
YOU ATTACK
YOU APPROACH REDFORD.
YOU ENTER THE TAVERN AND APPROACH VALIS.
[...]
Para simplificar, chamarei as unidades de cinco bits de "bytes" abaixo. Entre os membros da equipe, criamos outros nomes para eles - eu os chamei de croquetes e Zak - hacks.
Engenharia reversa da arquitetura do processador desconhecido
Agora, chegamos à parte difícil - a engenharia reversa de 4000 bytes de código que roda em uma arquitetura de CPU exclusiva e completamente desconhecida. A partir do código, é óbvio o suficiente para que este seja um conjunto de instruções de
comprimento variável , porque é impossível encontrar nele um padrão de repetição estável e perceptível. Passei algumas horas nisso, mais tarde meu membro da equipe, Zachary Wade (@ zwad3) começou a me ajudar. Primeiro, comecei a procurar por partes duplicadas do código, sugerindo que elas usariam frequentemente um pequeno número de instruções. Comecei a dividir o código em sequências repetidas mais curtas, mais convenientes para análise. Eu gostaria de dizer que foi um processo rigoroso, mas, de fato, o seguinte algoritmo vago foi usado principalmente:
- Examinamos o código e verificamos se algo se repete com muita frequência.
- Execute o procedimento de pesquisa e substituição para inserir uma nova linha ao lado desta repetição
- Explore as semelhanças / diferenças entre as linhas de divisão resultantes.
- Repita esse processo por cerca de uma hora ...
Por exemplo, um dos padrões que descobri foi "0f0.f", onde "." indica um caractere desconhecido. Eu quebrei a corda nesse padrão e obtive o seguinte:
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf
1sf24p5f3r9c11qad0f0sf
1df26p5f39c21qad0f05f
1ff26p5f39c41qad0f08f
1df26p5f39c81qad0f0hf
1ef26p5f3r1c00qaq15c20qcl0f01f
1of27p5f3p3g3psf35c10qal0f02f
Muito útil! A partir da segunda e terceira linhas, vemos que existem "... p5f3r9c ..." e "... p5f39c ...", e isso sugere que "r" é um código de operação de byte único, ou seja, "... 5f3" é o fim de um código de operação e " 9c .. ”é o começo de outro. Nas duas últimas linhas, vemos "p5f3r1c ..." e isso significa que "1c .." é outro código de operação e "p3 ..." também é outro código de operação.
Continuei dividindo as instruções repetidamente de maneira semelhante, usando as semelhanças e diferenças de blocos semelhantes para encontrar instruções prováveis. No final, consegui algo parecido com isto:
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
Eu assumi que "p" e "q" eram instruções com três bytes de operandos, "f0", "f1" e "f2" eram instruções com um operando e "9c" era uma instrução com dois operandos. No entanto, eu não sabia o que cada uma dessas instruções é.
Então, virei para o diretório de todas as instruções “p” que destaquei e descobri que, no momento, as instruções mais frequentes com “p” eram “p5f3”. Além disso, olhando para os locais onde ocorre, descobri que é sempre precedido pelas instruções “f0”, “f1” e “f2”. Observando todos os operandos “f0”, “f1” e “f2”, notei que os operandos f2 estão sempre no intervalo 4-8. Lembrando que a CPU possui 32 kb de memória de programa para endereçamento que requer 15 bits, presumi que "f0", "f1" e "f2" carregavam algum endereço com f2 como o byte alto. Quando conectei alguns desses endereços, descobri que todos eles apontam exatamente para o início das linhas constantes na seção de dados. Eu encontrei a função de
print ! Imediatamente se seguiu que “p5f3” é realmente algum tipo de instrução para imprimir uma linha ou chamada; se você levar em conta o operando de três bytes, provavelmente é uma "chamada". Mais uma vez, observando as instruções “p”, percebi que os três bytes do operando indicam o endereço em
ordem direta (little-endian) , ou seja, o último byte do operando é o byte mais alto do endereço.
Foi um grande avanço! Identificamos nossa primeira instrução. Tendo visto que “f0” e “f1” são usados em outros lugares, presumi que eles carregassem não os endereços, mas um dos quatro registros (por exemplo, f0 carrega o registro 0) com constantes de 5 bits com endereçamento direto. Isso é lógico para p5f3 - ele carrega três argumentos de registro para a função 3f5 (“print_string”).
Comecei a escrever um desmontador que reconhece o idioma "print" (f0x, f1x, f2x, p5f3), colocando a substituição da linha impressa no código desmontado. Devido ao grande número de linhas no programa, o código desmontado rapidamente se tornou muito legível e ficou mais fácil descobrir a localização dos blocos de funções (o código desmontado completo está
aqui ):
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 deste pequeno pedaço de código, consegui descobrir vários aspectos: a instrução "q0" deve indicar alguma ramificação condicional (porque é usada para ignorar a impressão de direções desnecessárias na função 1v) e as instruções "9c11", "9c21", "9c41", " 9c81 ”deve indicar algum tipo de instrução AND - eles verificam os bits definidos para ver se essas instruções são permitidas (isso é claramente sugerido pelo uso de“ 1 ”,“ 2 ”,“ 4 ”e“ 8 ”nestas instruções).
Nas duas horas seguintes, Zachary Wade (@ zwad3) e eu resolvemos as várias instruções, fazendo e refinando nossas suposições sobre o que estavam fazendo. Ter muitas instruções de impressão legíveis tornou nosso trabalho muito mais fácil. Decidimos que cada um de nós escreveria seu próprio desmontador para que pudéssemos examinar as instruções em nosso próprio ritmo e compartilhar nossas descobertas.
Engenharia reversa de código
Depois de algumas horas, comecei a fazer grandes progressos na desmontagem. Após examinar o código que funcionava com o inventário do usuário (mais especificamente, a função "drink" e cada manipulador associado a ele), encontramos instruções para salvar e carregar da memória (não esqueça que a CPU possui 1 kibibyte de memória de dados). Em seguida, descobrimos que algumas instruções aritméticas / lógicas (ALU) usam operandos de memória (por exemplo, “9c41” significa “execute AND com valor no endereço de dados 1 com valor 4”). A partir disso, fomos capazes de recriar as variáveis na memória de dados, por exemplo, em [0] o identificador NPC é armazenado no local atual e em [6,7] a saúde atual do jogador é armazenada (os 5 bits inferiores em [6], os 5 bits mais antigos em [7 ]). Nesse estágio, mudei de instruções de engenharia reversa para anotar meu código desmontado e fazer engenharia reversa no próprio programa. Abaixo está minha notação engraçada 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
Ainda temos muitos códigos de operação desconhecidos, por exemplo, embora tenhamos descoberto que "qa" é uma ramificação condicional no zero (ramificação no zero, brz), não conseguimos entender o que é "qc" (indicado acima como br <c>). Mas isso foi suficiente para começar a entender a lógica do programa.
De fato, o jogo permite que o jogador se mova em torno de um mapa 8 × 8 no qual NPCs (dragões, touros vermelhos e humanos) são colocados aleatoriamente. Você pode lutar com qualquer NPC (mesmo Valis, apesar da falta de um item de menu correspondente). Durante a batalha, você pode atacar o inimigo, causando uma quantidade aleatória de dano ou falha, após o que o inimigo ataca o jogador, causando também uma quantidade aleatória de dano ou falha. Você também pode escolher um bloqueio de escudo, graças ao qual o inimigo erra ou atinge o escudo sem causar danos. Finalmente, você pode trapacear aumentando sua saúde para 1000, mas, neste caso, a variável oculta ("trapaceado", endereço 10) é definida como 1. Se o jogador matar o inimigo com sucesso, um objeto cairá dele, geralmente uma garrafa de álcool (obviamente, este jogo não é para crianças).
O NPC principal Valis, do qual o jogador deve receber a bandeira, tem uma máquina de estado na qual ele pede ao jogador vários itens - um monte de bebidas Red Bull (obviamente obtidas ao derrotar inimigos Red Bull), várias bebidas mistas (por exemplo, gim e tônica) Para obtê-los, você precisa derrotar o dragão azul e o dragão cinza e, em seguida, misturar os objetos que caíram deles) e a régua de energia, que pode ser obtida se você derrotar outra pessoa do NPC no jogo (Redford) ou ajudá-lo. Se você atender a toda essa longa série de solicitações, ele lhe dará a bandeira, mas
somente se a variável "trapaceado" não for igual a 1. Ou seja, nossa tarefa é vencer o jogo sem trapacear. Como começamos com apenas 100 HP, como todos os inimigos, na passagem usual, será impossível derrotar todos os inimigos (para obter todas as coisas necessárias para derrotar cerca de 20 oponentes). É necessário modificar o RNG de alguma forma, para que o inimigo sempre erre.
Os números aleatórios são gerados por uma função que é semelhante a algum tipo de PRNG (endereço 37a), mas usa instruções exclusivas que não são usadas em nenhum outro lugar, portanto, não podemos fazer engenharia reversa. No entanto, notamos que ele carrega seu vetor de estado de três endereços na memória ([11], [12] e [13]), ou seja, seu estado completo leva apenas 15 bits. Isso significa que o RNG deve ter um período curto - não mais que 2 ^ 15 = 32768 de comprimento.
Enquanto nós (sem sucesso) tentamos reverter a implementação da RNG, Jay Bosamia (@ jay_f0xtr0t) e Matthew Savage (@thebluepichu) implementaram uma exploração. Simplesmente enviando o comando "shield" 100.000 vezes seguidas, conseguimos uma sequência de "acertos" e "erros" inimigos correspondentes à saída de bits do RNG. Garantimos que essa sequência se repita com um período de 32767. Graças a isso, conseguimos montar nossa principal façanha - em uma luta com o primeiro inimigo que encontramos, fechamos nossos escudos 40 vezes para recriar a sequência de acertos e faltas, procuramos por essa sequência em uma grande sequência periódica e descobrimos quando proteger e quando atacar para que o inimigo sempre erre. Depois, percorremos todo o mapa no modo assassinato, matando todos e recolhendo seus itens. No final, retornamos a Valis e pedimos educadamente nossa bandeira, que recebemos:
DrgnS{m4kin9-v4lis-happy-w1th-n4t1ve-b4ud0t-cpu}
Fuh! De fato, uma verdadeira aventura. Ainda não acredito que viemos de uma sequência binária e de uma completa falta de documentação do processador para dois desmontadores quase completos e um código desmontado em menos de 10 horas! Todo o código está disponível no GitHub:
meu desmontador ,
desmontador de Zachary ,
meu código desmontado bruto ,
meu código desmontado anotado ,
cliente Exploit de Matt .