[FR] Write-up FCSC 2021 : VMV
2021-05-03 18:00 +0200I - Intro
VMV se compose d’un simple executable ELF pour Linux x86-64. Il demande une chaine de 16 caractères de long en entrée et est censé nous indiquer s’il s’aggit du bon flag.
On peut essayer de l’executer pour voir :
$ ./vmv 0123456789ABCDEF
[fr] Ne quittez pas, un correspondant va prendre votre appel... [\fr]
* bruit de ventilateur de PC qui accélère *
[fr] Ne quittez pas, un correspondant va prendre votre appel... [\fr]
* htop indique 100% d'usage du CPU *
[fr] Ne quittez pas, un correspondant va prendre votre appel... [\fr]
Bon il semble que comprendre ce qui se passe dynamiquement soit plutôt compromis.
II - Reverse engineering du binaire
Comme le nom du challenge nous l’a déjà suggéré, il s’aggit probablement d’une VM. Après avoir importé l’executable dans Ghidra, on peut observer plusieurs parties intéressantes dans main:
FUNCTION_TABLE = (function_table_entry **)calloc(8,0x20000);
push_function_to_table(0x00adc52d,ADD_weird);
push_function_to_table(0x0560729d,MUL_weird);
push_function_to_table(0x48c5ccc6,XOR);
push_function_to_table(0x542010a0,AND_weird);
push_function_to_table(0xbdecfe55,RET);
push_function_to_table(0x41f93b4b,HALT_1);
push_function_to_table(0x5e64bb6c,PUSH_imm);
push_function_to_table(0xed4e2cfb,JMP);
push_function_to_table(0x180bc12d,JE);
push_function_to_table(0x5a0f38fc,JNE);
push_function_to_table(0x27497906,HALT_2);
push_function_to_table(0xba1116a9,ADD_imm);
push_function_to_table(0xfa83fa5e,CALL);
push_function_to_table(0x818cd6b5,HALT_with_exitcode);
push_function_to_table(0x8d67bae1,READ_rom);
push_function_to_table(0xd1450d67,WRITE_stdout);
push_function_to_table(0x8ea45b38,DEC);
push_function_to_table(0xf00bb6c1,INC);
push_function_to_table(0x5991ba22,PUSH_reg);
push_function_to_table(0x43ae1f53,MODULO);
push_function_to_table(0x8960888a,POP_reg);
push_function_to_table(0x1f0a8e6f,ADD_reg);
push_function_to_table(0x466a54d9,HALT_3);
push_function_to_table(0xfb521a9c,WRITE_ram);
push_function_to_table(0xc650f15d,READ_ram);
Une table de fonctions semble être créée et chaque entrée de celle-ci est accompagnée d’un opcode. Les fonctions correspondent donc à des instructions de la VM. Celles-ci sont plutôt faciles à identifier marlgré certaines, comme MUL, qui introduisent des maths bizares dans lesquelles je ne me suis pas aventuré.
En regardant attentivement ces fonctions, on remarque que lorsqu’une instruction a besoin d’un numéro de registre en opérande, celui-ci est xoré par 0xd77947b. On en profitera pour construire la liste des instructions accompagnées de leurs paramètres
Plus loin on observe le chargement des 2 blocs de mémoires. Je les ai simplement appelées ROM et RAM, car l’une d’entre elles ne possède pas d’instruction pour être écrite.
ram_code = b64decode(RAM_CODE_B64,0x3f10);
input_len = strlen(argv[1]);
ram_code_and_input = calloc(1,input_len + 0x2f4c);
rom_code = b64decode(ROM_CODE_B64,0x1328);
memcpy(ram_code_and_input,ram_code,0x2f4c);
input_len = strlen(argv[1]);
memcpy(ram_code_and_input + 0x2f4c,argv[1],input_len);
vm = vm_init(rom_code,ram_code_and_input);
On remarque qu’avant d’être passées à vm_init, la RAM et la ROM passent dans une fonction. En regardant la manière dont elles sont stockées dans le binaire, on se rend vite compte qu’il s’aggit d’un simple encodage base64. Cela peut être confirmé en regardant les tailles passées en paramètre de chaque fonction. En effet, un groupe de 4 caractères base64 forment 3 octets une fois décodés : (0x3f10 / 4) * 3 = 0x2f4c.
Notre chaine d’entrée est ajoutée à la fin de la RAM.
III - Premier deassemblage
Pour effectuer notre deassemblage de la ROM, j’ai écrit un simple script Python (assez moche) :
import sys
import struct
rom_pool = b""
rom_index = 0
labels = {}
labels_index = 1
assembly = []
def r32():
global rom_index
if len(rom_pool[rom_index:rom_index+4]) != 4:
rom_index += 4
return 0
x = struct.unpack("<I", rom_pool[rom_index:rom_index+4])
rom_index += 4
return x[0]
def get_imm():
return "0x%08X" % (r32(),)
def get_rel():
global rom_index, labels, labels_index
x = struct.unpack("<i", rom_pool[rom_index:rom_index+4])[0]
rom_index += 4
new_pc = rom_index + (x * 4)
if new_pc not in labels:
labels[new_pc] = ".l%d" % labels_index
labels_index += 1
return "%d %s @ 0x%08X" % (x, labels[new_pc], new_pc)
def get_reg():
specials = {
7: "pc",
8: "pwi",
9: "lr",
12: "sp",
22: "acc",
25: "pri"
}
r = (r32() ^ 0xd77947b) & 0x3f
if r in specials:
return "%s_%d" % (specials[r], r)
return "r_%d" % r
def ADD_weird():
return ("ADD_weird s,s")
def MUL_weird():
return ("MUL_weird s,s")
def XOR():
return ("XOR s,s")
def AND_weird():
return ("AND_weird s,s")
def RET():
return ("RET")
def HALT_1():
return ("HALT_1")
def PUSH_imm():
return ("PUSH", get_imm())
def JMP():
return ("JMP", get_rel())
def JE():
return ("JE s,s", get_rel())
def JNE():
return ("JNE s,s", get_rel())
def HALT_2():
return ("HALT_2", get_imm())
def ADD_imm():
return ("pwi = acc & ADD acc,", get_imm())
def CALL():
return ("CALL", get_rel())
def HALT_with_exitcode():
return ("HALT", get_reg())
def READ_rom():
return ("READ rom @pri(+4)", get_reg())
def WRITE_stdout():
return ("PRINT", get_reg())
def DEC():
return ("DEC", get_reg())
def INC():
return ("INC", get_reg())
def PUSH_reg():
return ("PUSH", get_reg())
def MODULO():
return ("MODULO s,", get_reg())
def POP_reg():
return ("POP", get_reg())
def ADD_reg():
return ("pwi = acc & ADD acc,", get_reg())
def HALT_3():
return ("HALT_3")
def WRITE_ram():
return ("WRITE mem @pwi", get_reg())
def READ_ram():
return ("READ mem @pwi", get_reg())
instructions = {
0x00adc52d: ADD_weird,
0x0560729d: MUL_weird,
0x48c5ccc6: XOR,
0x542010a0: AND_weird,
0xbdecfe55: RET,
0x41f93b4b: HALT_1,
0x5e64bb6c: PUSH_imm,
0xed4e2cfb: JMP,
0x180bc12d: JE,
0x5a0f38fc: JNE,
0x27497906: HALT_2,
0xba1116a9: ADD_imm,
0xfa83fa5e: CALL,
0x818cd6b5: HALT_with_exitcode,
0x8d67bae1: READ_rom,
0xd1450d67: WRITE_stdout,
0x8ea45b38: DEC,
0xf00bb6c1: INC,
0x5991ba22: PUSH_reg,
0x43ae1f53: MODULO,
0x8960888a: POP_reg,
0x1f0a8e6f: ADD_reg,
0x466a54d9: HALT_3,
0xfb521a9c: WRITE_ram,
0xc650f15d: READ_ram,
}
with open(sys.argv[1], "rb") as f:
rom_pool = f.read()
while rom_index < len(rom_pool):
pc = rom_index
op_code = r32()
try:
assembly += [(pc, instructions[op_code]())]
except KeyError:
assembly += [(pc, ".word %08X" % op_code)]
for i in assembly:
if i[0] in labels:
print(" " + labels[i[0]])
if isinstance(i[1], str):
d = i[1]
else:
d = " ".join(i[1])
print("%08X : %s" % (i[0], d))
On lance alors notre magnifique script en passant en argument un fichier qui contient notre ROM décodée.
C’est alors qu’on se rend compte de la réelle difficulté du challenge.
C’est une autre VM.
En effet, on reconnait facilement le gros switch au milieu responsable de sauter à l’endroit du code qui correspond à la bonne instruction :
00000110 : PUSH r_0
00000118 : PUSH 0x952DB75F
00000120 : JE s,s 740 .l4 @ 0x00000CB8
00000128 : PUSH r_0
00000130 : PUSH 0x140C2CF8
00000138 : JE s,s 675 .l5 @ 0x00000BCC
00000140 : PUSH r_0
00000148 : PUSH 0x4517CC48
00000150 : JE s,s 774 .l6 @ 0x00000D70
00000158 : PUSH r_0
00000160 : PUSH 0xE80C7BE2
00000168 : JE s,s 350 .l7 @ 0x000006E8
// ...
Et on reconnait aussi la partie responsable de lire un registre ou de lire un opcode :
.read_at_pc
00000DC0 : PUSH r_3
00000DC8 : PUSH 0x00000000
00000DD0 : ADD_weird s,s
00000DD4 : POP pwi_8
00000DDC : PUSH pwi_8
00000DE4 : READ mem @pwi pwi_8
00000DEC : PUSH pwi_8
00000DF4 : READ mem @pwi r_0
00000DFC : PUSH 0x00000001
00000E04 : ADD_weird s,s
00000E08 : POP r_5
00000E10 : POP pwi_8
00000E18 : WRITE mem @pwi r_5
00000E20 : RET
.read_reg
00000E24 : PUSH 0x39EE8310
00000E2C : XOR s,s
00000E30 : PUSH 0x0000003F
00000E38 : AND_weird s,s
00000E3C : PUSH r_3
00000E44 : ADD_weird s,s
00000E48 : POP pwi_8
00000E50 : READ mem @pwi r_0
00000E58 : RET
On remarquera que les registres de la VM sont stockés dans la RAM et non dans des registres de l’hote.
Une difference notable est la présence d’une seconde clé pour l’instruction PRINT. En effet, l’immédiat présent après l’instruction est xoré de la même manière que les numéros de registres.
J’ai rapidement identifié les differentes instructions, qui sont les mêmes que la VM précedente, et j’ai modifié le script avec les nouveaux opcodes et la nouvelle clé pour les registres.
En déassemblant ce qu’on trouve au début de la RAM, on obtient encore une autre VM. Il semble que le problème doit être traité de manière plus automatique.
IV - Deassembleur recurssif
La première chose importante que j’ai remarquée, c’est que les codes des deux VMs étaient plutôt identiques. Les seules différences sont les opcodes et les clés de registres et de print. Il devrait être plutôt trivial d’extraire ceux-ci à coup de manipulations moches de strings en Python.
La RAM étant plutôt conséquante (environ 12KB), j’ai simplement supposé que les VMs sont les unes à la suite des autres et font la même taille que la première.
On peut alors écrire ce script Python (toujours d’une aussi grande qualité):
import sys
import struct
class Dissassembly:
def __init__(self, rom, reg_key, print_key, opcodes):
self.rom_pool = rom
self.reg_key = reg_key
self.print_key = print_key
self.opcodes = opcodes
self.rom_index = 0
self.labels = {}
self.labels_index = 1
self.assembly = []
self.specials = {}
def r32(self):
x = struct.unpack("<I", self.rom_pool[self.rom_index:self.rom_index+4])
self.rom_index += 4
return x[0]
def get_imm(self):
return "0x%08X" % (self.r32(),)
def get_rel(self):
x = struct.unpack("<i", self.rom_pool[self.rom_index:self.rom_index+4])[0]
self.rom_index += 4
new_pc = self.rom_index + (x * 4)
if new_pc not in self.labels:
self.labels[new_pc] = ".l%d" % self.labels_index
self.labels_index += 1
return "%d %s @ 0x%08X" % (x, self.labels[new_pc], new_pc)
def get_reg(self):
r = (self.r32() ^ self.reg_key) & 0x3f
if r in self.specials:
return "%s_%d" % (self.specials[r], r)
return "r_%d" % r
def ADD(self):
return ("ADD s,s")
def MUL(self):
return ("MUL s,s")
def XOR(self):
return ("XOR s,s")
def AND(self):
return ("AND s,s")
def RET(self):
return ("RET")
def PUSH_imm(self):
return ("PUSH", self.get_imm())
def JMP(self):
return ("JMP", self.get_rel())
def JE(self):
return ("JE s,s", self.get_rel())
def JNE(self):
return ("JNE s,s", self.get_rel())
def ADD_imm(self):
return ("pwi = acc & ADD acc,", self.get_imm())
def CALL(self):
return ("CALL", self.get_rel())
def HALT_reg(self):
return ("HALT", self.get_reg())
def HALT_imm(self):
return ("HALT", self.get_imm())
def READ_rom_reg(self):
return ("READ rom @pri(+4)", self.get_reg())
def PRINT_reg(self):
return ("PRINT", self.get_reg())
def PRINT_imm(self):
return ("PRINT", chr((self.r32() ^ self.print_key) & 0xFF))
def DEC(self):
return ("DEC", self.get_reg())
def INC(self):
return ("INC", self.get_reg())
def PUSH_reg(self):
return ("PUSH", self.get_reg())
def MODULO(self):
return ("MODULO s,", self.get_reg())
def POP_reg(self):
return ("POP", self.get_reg())
def ADD_reg(self):
return ("pwi = acc & ADD acc,", self.get_reg())
def WRITE_imm(self):
return ("WRITE mem @pwi", self.get_imm())
def WRITE_reg(self):
return ("WRITE mem @pwi", self.get_reg())
def READ_reg(self):
return ("READ mem @pwi", self.get_reg())
def get_instructions(self):
instructions = []
while self.rom_index < len(self.rom_pool):
pc = self.rom_index
opcode = self.r32()
try:
instructions += [(pc, self.opcodes[opcode](self))]
except KeyError:
instructions += [(pc, ".word %08X" % opcode)]
return instructions
def get_dissassembly(self):
instructions = self.get_instructions()
dissassembly = ""
for i in instructions:
if i[0] in self.labels:
dissassembly += " " + self.labels[i[0]] + "\n"
if isinstance(i[1], str):
d = i[1]
else:
d = " ".join(i[1])
dissassembly += "%08X : %s\n" % (i[0], d)
return dissassembly
OPCODES_LIST = [
Dissassembly.HALT_reg,
Dissassembly.DEC,
Dissassembly.RET,
Dissassembly.READ_reg,
Dissassembly.CALL,
Dissassembly.PRINT_reg,
Dissassembly.JMP,
Dissassembly.XOR,
Dissassembly.MUL,
Dissassembly.AND,
Dissassembly.INC,
Dissassembly.JE,
Dissassembly.WRITE_reg,
Dissassembly.ADD,
Dissassembly.PUSH_imm,
Dissassembly.READ_rom_reg,
Dissassembly.PUSH_reg,
Dissassembly.JNE,
Dissassembly.PRINT_imm,
Dissassembly.HALT_imm,
Dissassembly.ADD_imm,
Dissassembly.ADD_reg,
Dissassembly.POP_reg,
Dissassembly.MODULO,
]
def build_opcodes_dict(opcodes):
d = {}
for i in range(len(opcodes)):
d[opcodes[i]] = OPCODES_LIST[i]
return d
class Parser:
def __init__(self, dissassembly):
self.dissassembly = dissassembly.split("\n")
def get_reg_key(self):
line = self.dissassembly[507]
if not line.startswith("00000E24 : PUSH "):
raise Exception("Invalid dissassembly : Unable to get reg_key")
return int(line[16:], 16)
def get_print_key(self):
line = self.dissassembly[32]
if not line.startswith("000000E8 : PUSH "):
raise Exception("Invalid dissassembly : Unable to get print_key")
return int(line[16:], 16)
def get_opcodes(self):
opcodes = []
for i in range(39, 109, 3):
line = self.dissassembly[i]
if " : PUSH " not in line:
raise Exception("Invalid dissassembly : Unable to get opcodes at line %d" % i)
opcodes += [int(line[16:], 16)]
return opcodes
opcodes = [
0x952DB75F,
0x140C2CF8,
0x4517CC48,
0xE80C7BE2,
0x950885B3,
0xF85712C3,
0xD708325C,
0x01688047,
0x54D4C1E6,
0xA9475B13,
0x29CC50C7,
0xBF5E62BA,
0x81761C59,
0x2445BAFC,
0x37D5991B,
0xEEF14B6E,
0x3BD7549B,
0x56AE0803,
0x0B46465F,
0x8032F32E,
0x87AB3B02,
0xFB0A90EC,
0xEE68C600,
0x5DCC45A4,
]
reg_key = 0x39EE8310
print_key = 0x08929D1E
with open(sys.argv[1], "rb") as f:
while True:
f.read(4)
rom_pool = f.read(3676)
d = Dissassembly(rom_pool, reg_key, print_key, build_opcodes_dict(opcodes))
dis = d.get_dissassembly()
p = Parser(dis)
try:
reg_key = p.get_reg_key()
opcodes = p.get_opcodes()
print_key = p.get_print_key()
except Exception:
print(dis)
break
print("New VM : reg :", hex(reg_key))
J’ai remarqué qu’entre chaque VMs il y avait un entier dont j’ignorais compeltement l’utilité. En me repenchant dessus, je me suis rendu compte qu’il s’aggissait simplement de la taille de la VM à venir. Comme toutes les VMs sont de la même taille, je l’ai simplement ignoré.
En utilisant donc ce script, on obtient le code de la dernière VM qui implémente la vérification finale :
00000000 : PUSH 0x00000000
00000008 : POP r_16
00000010 : READ rom @pri(+4) r_14
00000018 : PUSH 0x00000001
00000020 : PUSH r_14
00000028 : PUSH 0x117052C0
00000030 : MUL s,s
00000034 : JNE s,s 2 .l1 @ 0x00000044
0000003C : INC r_16
.l1
00000044 : READ rom @pri(+4) r_14
0000004C : PUSH r_14
00000054 : PUSH 0x000077F3
0000005C : POP r_15
00000064 : MODULO s, r_15
0000006C : PUSH 0x00004926
00000074 : JE s,s 4 .l2 @ 0x0000008C
0000007C : PUSH 0x00000000
00000084 : POP r_16
.l2
0000008C : PUSH r_14
00000094 : PUSH 0x00007C49
0000009C : POP r_15
000000A4 : MODULO s, r_15
000000AC : PUSH 0x00003159
000000B4 : JE s,s 4 .l3 @ 0x000000CC
000000BC : PUSH 0x00000000
000000C4 : POP r_16
.l3
000000CC : READ rom @pri(+4) r_14
000000D4 : PUSH 0x00000001
000000DC : PUSH r_14
000000E4 : PUSH 0x278BCE9D
000000EC : MUL s,s
000000F0 : JNE s,s 2 .l4 @ 0x00000100
000000F8 : INC r_16
.l4
00000100 : READ rom @pri(+4) r_14
00000108 : PUSH r_14
00000110 : PUSH 0x000077F3
00000118 : POP r_15
00000120 : MODULO s, r_15
00000128 : PUSH 0x000028B2
00000130 : JE s,s 4 .l5 @ 0x00000148
00000138 : PUSH 0x00000000
00000140 : POP r_16
.l5
00000148 : PUSH r_14
00000150 : PUSH 0x00007C49
00000158 : POP r_15
00000160 : MODULO s, r_15
00000168 : PUSH 0x000044A9
00000170 : JE s,s 4 .l6 @ 0x00000188
00000178 : PUSH 0x00000000
00000180 : POP r_16
.l6
00000188 : PUSH r_16
00000190 : PUSH 0x00000002
00000198 : JE s,s 2 .l7 @ 0x000001A8
000001A0 : JMP 110 .l8 @ 0x00000360
.l7
000001A8 : PRINT "Congratulations, you won. Validate with FCSC{<input>}\n"
00000358 : HALT 0x00000000
.l8
00000360 : PRINT "Noooooo, damn you lost!\n"
00000420 : HALT 0x00000001
Il y a 4 READ rom @pri(+4), or notre entrée fait 16 octets de long et chaque READ en lis 4. On peut donc supposer que notre entrée est lue régulièrement dans r14.
Oui, l’entrée est supposée avoir été concaténée avec la RAM et non la ROM, mais on va mettre ca sur le dos du fait que je ne suis pas allé dans le détail lors de l’analyse de la première sous-VM.
Il faut donc que les 4 groupes de 4 octets qui composent notre flag respectent les conditions suivantes :
FLAG[0] * 0x117052C0 = 1
FLAG[1] % 0x000077F3 = 0x00004926
FLAG[1] % 0x00007C49 = 0x00003159
FLAG[2] * 0x278BCE9D = 1
FLAG[3] % 0x000077F3 = 0x000028B2
FLAG[3] % 0x00007C49 = 0x000044A9
V - Conclusion
Cela ne semble pas très complexe à brute-force, mais j’ai rencontré quelques problèmes, notament sur la multiplication. En effet la VM n’implemente pas une “vraie” multiplication. J’ai essayé de reimplémenter la chose en me basant sur la decompilation de Ghidra mais cela n’a pas fonctionné : il n’y avait aucune solution.
J’ai donc fini par opter pour une solution plus radicale, j’ai simplement et bêtement copié l’assembleur x86 du binaire dans mon programme de brute-force :
#include <stdint.h>
#include <stdio.h>
uint32_t mul_weird(uint64_t a, uint64_t b);
int main() {
for (uint32_t i = 0x20202020; i < 0x7F7F7F7F; i++) {
uint32_t m = mul_weird(i, 0x117052C0);
if (m == 1)
printf("%08X\n", i);
}
printf("==\n");
for (uint32_t i = 0x20202020; i < 0x7F7F7F7F; i++) {
unsigned long long m = i % 0x000077F3;
unsigned long long n = i % 0x00007C49;
if (m == 0x00004926 && n == 0x00003159)
printf("%08X\n", i);
}
printf("==\n");
for (uint32_t i = 0x20202020; i < 0x7F7F7F7F; i++) {
uint32_t m = mul_weird(i, 0x278BCE9D);
if (m == 1)
printf("%08X\n", i);
}
printf("==\n");
for (uint32_t i = 0x20202020; i < 0x7F7F7F7F; i++) {
unsigned long long m = i % 0x000077F3;
unsigned long long n = i % 0x00007C49;
if (m == 0x000028B2 && n == 0x000044A9)
printf("%08X\n", i);
}
}
bits 64
global mul_weird
mul_weird:
mov rdx, rsi
mov rax, rdi
; Partie copiée du binaire d'origine
MOV RCX,RDX
IMUL RCX,RAX
MOV RDX,0x200000005
MOV RAX,RCX
MUL RDX
MOV RAX,RCX
SUB RAX,RDX
SHR RAX,1
ADD RAX,RDX
SHR RAX,0x1e
MOV RDX,RAX
SHL RDX,0x1f
SUB RDX,RAX
MOV RAX,RCX
SUB RAX,RDX
; MOV RDX,qword ptr [RBP + local_20]
; MOV RCX,qword ptr [RDX]
; MOV RDX,qword ptr [RBP + local_20]
; MOV EDX,dword ptr [RDX + 0x38]
MOVSXD RDX,EDX
SHL RDX,0x2
ADD RDX,RCX
; MOV dword ptr [RDX],EAX
; NOP
; POP RBP
RET
Cela prend environ une dizaine de secondes sur ma machine. On obtient alors les 4 ints qui composent le flag :
654E3377
==
30546445
6A904C90
==
65444F67
==
37F787E8
72337033
En éliminant les résultats qui possèdent des caractères non imprimables et en rétablissant l’endianness, on obtient :
FCSC{w3NeEdT0gODe3p3r}