TL; DR: nous avons procédé à une ingénierie inverse d'un programme écrit pour une architecture de CPU complètement inconnue sans aucune documentation sur le CPU (sans émulateur, sans ISA, sans tout) en seulement dix heures. À partir de l'article, vous apprendrez comment nous l'avons fait ...
Le week-end dernier, l'équipe CMU PPP et moi avons participé à l'équipe Dragon Sector Teaser CTF 2019 pour se détendre et s'éloigner de la dure échéance du
CHI 2020 . Dragon Sector est une équipe polonaise respectée avec une histoire de
FFC intéressants, donc je me demandais ce qu'ils avaient en stock.
Après avoir résolu «ummmfpu», une tâche qui comprenait la rétro-ingénierie du bytecode pour le coprocesseur à virgule flottante Micromega uM-FPU, j'ai décidé de participer à un concours pour résoudre le problème CPU Adventure, qui à l'époque n'était résolu par aucune des équipes (en conséquence nous étions les seuls à avoir accompli la tâche).
Voici une description de la tâche CPU Adventure:
Mon grand-père dans les années 60 était engagé dans le développement d'ordinateurs. Remettant les choses en ordre dans son grenier, j'ai trouvé une étrange voiture. À côté de la machine se trouvait une pile de cartes perforées marquées «Dragon Adventure Game». Après un certain temps, j'ai réussi à le connecter à un équipement moderne, mais le jeu est trop compliqué et je ne peux pas arriver au bout sans tricher. Pouvez-vous m'aider? Je joins une transcription des cartes perforées utilisées dans la machine. On prétend que la machine possède 4 registres à usage général, 1 kibioctet de mémoire de données et 32 kibioctet de mémoire de commande. Pour jouer au jeu, connectez-vous au serveur comme suit: socat tcp4-connect:cpuadventure.hackable.software:1234 fd:0,rawer Astuce: le processeur de la machine est unique, n'essayez pas de rechercher des informations sur Google.
game.bin
Une fois connecté au serveur, nous avons reçu les informations suivantes:
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:
Super. Ceci est un jeu d'aventure à l'ancienne. Après avoir joué un peu, nous avons réalisé que vous pouvez combattre des ennemis et obtenir un drapeau de ce personnage Valis si nous lui plaisons:
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:
Premiers pas
Je n'ai pas joué au jeu pendant très longtemps, réalisant qu'il est probablement plus important de
game.bin à une rétro-ingénierie du fichier
game.bin . Je l'ai ouvert dans un éditeur hexadécimal, en espérant voir des valeurs binaires. Imaginez ma surprise quand j'ai vu ceci:
110011111101000000111100110010001110000011001101000000000000110010011101010000001101001111100001111111001100111000000011 ...
Il
s'agit littéralement d'un fichier binaire - un fichier texte qui ne contient rien d'autre que les caractères ASCII 1 et 0. Nous savons que c'est très probablement le code machine du processeur, mais en plus d'avoir 4 registres, 1 Ko de mémoire de données et 32 kibioctets de mémoire d'instructions, on
ne sait
rien à ce sujet. Par conséquent, notre première tâche sérieuse sera de déterminer la taille unitaire de ce fichier binaire (par exemple, a-t-il une dimension 8 bits? Ou, peut-être, a-t-il une dimension 12 bits ou 18 bits, comme dans certaines
architectures anciennes ?)
Pour connaître la taille d'un fichier inconnu, j'ai utilisé une vieille astuce - j'ai redimensionné la zone de texte jusqu'à ce que la longueur du saut de ligne corresponde à l'alignement. Cette méthode est idéale pour des éléments comme le texte chiffré XOR multiple, les formats de fichiers inconnus (non compressés) et le code provenant d'un processeur inconnu:
Modifier la taille de la zone de texteÀ partir de cette vérification rapide, j'ai découvert que la taille unitaire de ce fichier devait être un diviseur de 20 (la largeur de la fenêtre alignée). Pour connaître la taille exacte, j'ai rapidement écrit un script à la recherche de longues lignes répétitives (en supposant que tout code ait des séquences stéréotypées répétitives). La ligne de répétition la plus longue était le bloc de 425 bits suivant, trouvé à 43625 et 44510:
10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100
Comme la distance entre les répétitions est de 885, nous sommes arrivés à la conclusion que la dimension devrait être de 5 bits, c'est-à-dire un processeur inconnu doit avoir 5 octets. Progrès!
Nous avons recherché des encodages de cartes perforées 5 bits et nous nous sommes rapidement installés sur l'ancien encodage
avec le code Baudot . Et en fait - lorsque nous avons utilisé le décodeur en ligne pour décoder certains fragments, nous avons obtenu du texte lisible!
⇩DRAGON⇩HERE⇧; ⇩SHE⇩APPEARS⇩TO⇩BE⇩GUARDING⇩ SOME⇩KIND⇩OF⇩A⇩ BOTTLE⇧; &. &. ⇩␀THERE⇩IS⇩A⇩B
Code LSB Baudot ITA amélioré de 425 bits
Ensuite, nous avons essayé de décoder l'intégralité du fichier en utilisant le code Bodo, mais dans les 20 000 premiers bits environ, nous avons obtenu des ordures, après quoi il y avait un texte parfaitement lisible. Cela nous a montré clairement que la première partie du fichier appartient à la section «code», suivie de la section «données», qui contient des lignes constantes. Nous avons supposé que la machine utilise probablement le code Bodo pour les E / S, et stocke donc également des lignes constantes dans le codage Bodo en mémoire. Pour rendre le segment de code plus lisible, j'ai décidé de le coder en utilisant le codage base-32, similaire au codage hexadécimal, mais en l'étendant avec l'alphabet 0-9a-v. Voici à quoi ressemble le fichier game.bin avec la première partie encodée en base-32 et la seconde partie décodée par Bodo (le fichier complet est affiché ici:
game.b32 ):
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf1sf24p5f3r9c11qad0f0sf1df26p5f39c21qad0f05f1ff26p5f39c41qad0f08f1df26p5f39c81qad0f0hf1ef26p5f3r1c00qaq15c20qcl0f01f1of27p5f3p3g3psf35c10qal0f02f1nf27p5f3p3g3psf3rf0hf1nf27p5f3f05f16f27p5f3rf84f95101311fl0f510f84907qa40b518447qa40b514f84f95k9m0k9m0k9m0907qa40b511447qa40b512ruougf10f20g0i9g0i910931b320u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1onp0o9f0o9f0o9f0o9f0onf0ot82odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df24p5f3r9c11qa835548755
[...]
93e9n59ka8fo87r85g8ui8ml8ed87b9h89u291u82333333333456789abcdb01234567892)%c3BOTTLE OF SOPLICA PIGWOWAENEMY HEALTH:
YOU ATTACK
YOU APPROACH REDFORD.
YOU ENTER THE TAVERN AND APPROACH VALIS.
[...]
Par souci de simplicité, j'appellerai les unités à cinq bits «octets» ci-dessous. Entre eux dans l'équipe, nous avons trouvé d'autres noms pour eux - je les ai appelés croquettes et Zak - hacks.
Ingénierie inverse du processeur inconnue
Nous passons maintenant à la partie difficile - l'ingénierie inverse de 4000 octets de code qui s'exécute sur une architecture de processeur unique complètement inconnue. D'après le code, il est assez évident qu'il devrait s'agir d'un ensemble d'instructions de
longueur variable , car il est impossible d'y trouver un motif de répétition stable notable. J'ai passé quelques heures là-dessus, plus tard, mon membre de l'équipe Zachary Wade (@ zwad3) a commencé à m'aider. Tout d'abord, j'ai commencé à chercher des morceaux de code en double, suggérant qu'ils utiliseraient souvent un petit nombre d'instructions. J'ai commencé à diviser le code en séquences répétitives plus courtes qui étaient plus pratiques pour l'analyse. Je voudrais dire que c'était un processus rigoureux, mais en fait, l'algorithme vague suivant a été principalement utilisé:
- Nous regardons à travers le code et cherchons si quelque chose se répète très souvent
- Effectuez la procédure de recherche et remplacement pour insérer une nouvelle ligne à côté de cette répétition
- Explorez les similitudes / différences entre les lignes de séparation résultantes.
- Répétez ce processus pendant environ une heure ...
Par exemple, l'un des motifs que j'ai découverts était «0f0.f», où «.» indique un caractère inconnu. J'ai cassé la chaîne sur ce modèle et j'ai obtenu ce qui suit:
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf
1sf24p5f3r9c11qad0f0sf
1df26p5f39c21qad0f05f
1ff26p5f39c41qad0f08f
1df26p5f39c81qad0f0hf
1ef26p5f3r1c00qaq15c20qcl0f01f
1of27p5f3p3g3psf35c10qal0f02f
Très utile! Des deuxième et troisième lignes, nous voyons qu'il y a "... p5f3r9c ..." et "... p5f39c ...", et cela nous indique que "r" est un opcode à un octet, c'est-à-dire, "... 5f3" est la fin d'un opcode, et " 9c .. »est le début d'un autre. Dans les deux dernières lignes, nous voyons "p5f3r1c ..." et cela signifie que "1c .." est un autre opcode, et "p3 ..." est également un autre opcode.
J'ai continué à diviser les instructions encore et encore d'une manière similaire, en utilisant les similitudes et les différences de blocs similaires pour trouver des instructions probables. En fin de compte, j'ai obtenu quelque chose comme ça:
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
J'ai supposé que «p» et «q» étaient des instructions avec trois octets d'opérandes, «f0», «f1» et «f2» étaient des instructions avec un opérande et «9c» était une instruction avec deux opérandes. Cependant, je ne savais pas ce que chacune de ces instructions est.
Je me suis donc tourné vers le répertoire de toutes les instructions «p» que j'ai mises en évidence, et j'ai constaté qu'en ce moment, les instructions les plus fréquentes avec «p» étaient «p5f3». De plus, en regardant les endroits où elle se produit, j'ai constaté qu'elle est toujours précédée des instructions «f0», «f1» et «f2». En regardant tous les opérandes "f0", "f1" et "f2", j'ai remarqué que les opérandes f2 sont toujours dans la plage 4-8. En se rappelant que le CPU a 32 ko de mémoire de programme pour l'adressage qui nécessite 15 bits, j'ai supposé que «f0», «f1» et «f2» chargeaient une adresse avec f2 comme octet de poids fort. Lorsque j'ai connecté certaines de ces adresses entre elles, j'ai constaté qu'elles pointaient toutes exactement vers le début des lignes constantes dans la section des données. J'ai trouvé la fonction d'
print ! Il s'ensuit immédiatement que «p5f3» est en fait une sorte d'instruction pour imprimer une ligne ou un appel; si vous prenez en compte l'opérande de trois octets, il s'agit très probablement d'un «appel». Encore une fois, en regardant les instructions «p», j'ai réalisé que les trois octets de l'opérande indiquent l'adresse en
ordre direct (petit-boutien) , c'est-à-dire que le dernier octet de l'opérande est l'octet le plus élevé de l'adresse.
Ce fut une énorme percée! Nous avons identifié notre première instruction. Ayant vu que «f0» et «f1» sont utilisés à d'autres endroits, j'ai supposé qu'ils chargeaient non pas les adresses, mais l'un des quatre registres (par exemple, f0 charge le registre 0) avec des constantes de 5 bits avec adressage direct. C'est logique pour p5f3 - il charge trois arguments de registre pour la fonction 3f5 ("print_string").
J'ai commencé à écrire un désassembleur qui reconnaît l'idiome «print» (f0x, f1x, f2x, p5f3), en plaçant la substitution de la ligne imprimée dans le code désassemblé. En raison du grand nombre de lignes dans le programme, le code désassemblé est rapidement devenu très lisible, et il est devenu plus facile de trouver l'emplacement des blocs fonctionnels (le code désassemblé complet est
ici ):
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
À partir de ce petit extrait de code, j'ai réussi à comprendre plusieurs aspects: l'instruction «q0» devrait indiquer une ramification conditionnelle (car elle est utilisée pour ignorer l'impression de directions inutiles dans la fonction 1v), et les instructions «9c11», «9c21», «9c41», « 9c81 "devrait indiquer une sorte d'instruction ET - ils vérifient les bits définis pour voir si ces directions sont autorisées (cela est clairement indiqué par l'utilisation de" 1 "," 2 "," 4 "et" 8 "dans ces instructions).
Au cours des deux heures suivantes, Zachary Wade (@ zwad3) et moi avons trié les différentes instructions, en faisant et en affinant nos hypothèses sur ce qu'elles faisaient. Avoir de nombreuses déclarations imprimables lisibles a rendu notre travail beaucoup plus facile. Nous avons décidé que chacun de nous rédigerait individuellement son propre démonteur afin que nous puissions examiner les instructions à notre propre rythme et partager nos résultats.
Ingénierie inverse du code
Après quelques heures, j'ai commencé à faire de grands progrès dans le démontage. Après avoir examiné le code qui fonctionnait avec l'inventaire de l'utilisateur (plus précisément, la fonction «boisson» et chaque gestionnaire qui lui est associé), nous avons trouvé des instructions pour sauvegarder et charger à partir de la mémoire (n'oubliez pas que le CPU a 1 kibio de mémoire de données). Ensuite, nous avons découvert que certaines instructions arithmétiques / logiques (ALU) prennent des opérandes de mémoire (par exemple, "9c41" signifie "exécuter AND avec une valeur à l'adresse de données 1 avec une valeur 4"). À partir de cela, nous avons pu recréer les variables dans la mémoire de données, par exemple, dans [0] l'identifiant NPC est stocké à l'emplacement actuel, et dans [6,7] la santé actuelle du joueur est stockée (les 5 bits inférieurs dans [6], les 5 plus anciens dans [7] ]). À ce stade, je suis passé des instructions de rétro-ingénierie à l'annotation de mon code désassemblé et à la rétro-ingénierie du programme lui-même. Voici ma drôle de notation pour les valeurs 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
Nous avons encore de nombreux opcodes inconnus, par exemple, bien que nous ayons découvert que "qa" est une ramification conditionnelle sur zéro (branch-on-zero, brz), nous n'avons pas pu comprendre ce qu'est "qc" (indiqué ci-dessus comme br <c>). Mais cela a suffi pour commencer à comprendre la logique du programme.
En fait, le jeu permet au joueur de se déplacer sur une carte 8 × 8 sur laquelle des PNJ (dragons, taureaux rouges et humains) sont placés au hasard. Vous pouvez vous battre avec n'importe quel PNJ (même Valis, malgré l'absence d'un élément de menu correspondant). Pendant la bataille, vous pouvez attaquer l'ennemi, provoquant une quantité aléatoire de dégâts ou de manque, après quoi l'ennemi attaque le joueur, provoquant également une quantité aléatoire de dégâts ou de manque. Vous pouvez également choisir un verrou de bouclier, grâce auquel l'ennemi manque ou frappe le bouclier sans causer de dégâts. Enfin, vous pouvez tricher en augmentant votre santé à 1000, mais dans ce cas, la variable cachée ("triché", adresse 10) est définie sur 1. Si le joueur tue avec succès l'ennemi, un objet tombe de lui, généralement une bouteille d'alcool (évidemment, ce jeu n'est pas pour les enfants).
Le NPC Valis principal, dont le joueur doit recevoir le drapeau, a une machine d'état dans laquelle il demande au joueur plusieurs articles - un tas de boissons de taureau rouge (évidemment obtenues en battant des ennemis de taureau rouge), diverses boissons mélangées (par exemple, gin et tonic - pour les obtenir, vous devez vaincre le dragon bleu et le dragon gris, puis mélanger les objets qui en sont sortis), et la bande de puissance, qui peut être obtenue si vous battez une autre personne PNJ dans le jeu (Redford) ou si vous l'aidez. Si vous remplissez toute cette longue série de demandes, il vous donnera le drapeau, mais
seulement si la variable «triché» n'est pas égal à 1. Autrement dit, notre tâche est de gagner le jeu sans tricher. Comme nous commençons avec seulement 100 HP, comme tous les ennemis, avec le passage habituel, il sera impossible de vaincre tous les ennemis (pour obtenir tout ce dont vous avez besoin pour vaincre environ 20 adversaires). Il est nécessaire de modifier le RNG d'une manière ou d'une autre, afin que l'ennemi manque toujours.
Les nombres aléatoires sont générés par une fonction similaire à une sorte de PRNG (adresse 37a), mais elle utilise des instructions uniques qui ne sont utilisées nulle part ailleurs, nous ne pouvons donc pas les inverser. Cependant, nous avons remarqué qu'il charge son vecteur d'état à partir de trois adresses en mémoire ([11], [12] et [13]), c'est-à-dire que son état complet ne prend que 15 bits. Cela signifie que le RNG doit avoir une courte période - pas plus de 2 ^ 15 = 32768 de longueur.
Alors que nous (en vain) essayions d'inverser la mise en œuvre du RNG, Jay Bosamia (@ jay_f0xtr0t) et Matthew Savage (@thebluepichu) ont implémenté un exploit. En envoyant simplement la commande «bouclier» 100 000 fois de suite, nous avons pu obtenir une séquence de «coups» et de «manques» ennemis correspondant au bit émis par le RNG. Nous nous sommes assurés que cette séquence se répète avec une période de 32767. Grâce à cela, nous avons pu assembler notre exploit principal - lorsque nous combattions avec le premier ennemi que nous avons rencontré, nous avons fermé nos boucliers 40 fois pour recréer la séquence de coups sûrs et manqués, recherché cette séquence dans une grande séquence périodique, puis découvert quand protéger et quand attaquer pour que l'ennemi manque toujours. Ensuite, nous avons fait le tour de la carte en mode assassinhobo, tuant tout le monde et récupérant leur butin. À la fin, nous sommes retournés à Valis et avons poliment demandé notre drapeau, que nous avons reçu:
DrgnS{m4kin9-v4lis-happy-w1th-n4t1ve-b4ud0t-cpu}
Fuh! En effet, une vraie aventure. Je n'arrive toujours pas à croire que nous sommes passés d'une chaîne binaire et d'un manque total de documentation du processeur à deux désassembleurs presque complets et un code propre désassemblé en moins de 10 heures! Tout le code est disponible sur GitHub:
mon désassembleur ,
le désassembleur de Zachary ,
mon code brut désassemblé ,
mon code désassemblé annoté ,
Matt's Exploit client .