Defeating Nested Virtualization with Miasm - FCSC21 CTF VMV
FCSC was a week long CTF and I usually like these long duration ctfs as I’m not that good of a speedrunner tbh :( Also I’m a bit late for this writeup but anyways it better late than never!
TL;DR
This challenge features a nested virtual machine with 5 levels of nesting and is great for learning the tooling aspect of reverse engineering. I solved it by writing a disassembler for it in miasm and then applying some pattern detection logic on it. The virtual machines are nearly similar but they differ in opcodes and some values used to decode an instruction, so we’ve to deal with that too. At the last level we find the key check algo implementation which is not that difficult and we write a solution script to get the key.
Challenge
Though FCSC had many interesting reversing challenges, I dedicated most of my time to VMV.
The challenge requires a 16 byte string as an argument.
1 | └──╼ $time ./vmv helloworld123456 |
It prints the message :
“[fr] Ne quittez pas, un correspondant va prendre votre appel… [\fr]”
which translates to -
“Do not leave, a correspondent will take your call…”
and seems like this is a waiting message as it checks our key. Yeah its obvious that it’ll take time as it’s a VM(V) but this much… Oh boy!
The Main Function
There is a single function which takes various functions as arguments and random values?
Turns out it is initializing a hashmap with key and functions as its keys and values respectively. There are two base64 encrypted strings which when decoded are used as the bytecode.
But where has our input disappeared?
Our input is concatenated to the second base64 decoded buffer for now. Finally, the Dispatcher consists of a bytecode iterator and the same hashmap.
VM Analysis
After getting a basic idea of the VM Implementation, I figured out the registers and other variables used by the VM.
VM Context Structure
I defined the structure as follows:
1 | 0x0000000 vm_context struc |
Opcodes
This VM consists of 24 opcodes in total.
I defined them as follows :
PUSH_REG, PUSH_IMM, POP
There are two variants of the push instruction : PUSH_REG(pushes a register) and PUSH_IMM(pushes an 32 bit immediate). As it is an ascending stack so the SP is incremented after a PUSH.ADD, XOR, MUL, AND
The above arithmetic operations work by popping two values off the stack and then pushing their result back. The result also suffers a modulo operation with 0x7fffffff, except for XOR.INC, DEC
Increments/Decrements the specified register.JE, JNE
These are used for comparision and jumping at the same time here. They pop two values off the stack and compare them, later jump to the specified destination depending on the result.JMP
Relative Jump where destination = PC + ImmediateCALL, RET
Before CALL, it assigns the value of current PC to LR(Link Register) and then calls a function. For example, in ARM, the BL instruction places the return address in the LR(Link Register). The opposite is done when returning from the function.MEMSTORE, MEMFETCH, MEMSHIFT_REG, MEMSHIFT_IMM
The VM has its own memory which is initialized in the VM_CONTEXT_INIT function as an array of 0x2000000 32-bit values. VM_MEM_PTR register is used as an index to the memory and is used by MEMFETCH and MEMSTORE. MEMSTORE puts the value of a register in memory and MEMFETCH does the opposite. The MEMSHIFT_REG and MEMSHIFT_IMM are both used to save the current value of VM_MEM_NEXT_PTR in VM_MEM_PTR and shifts VM_MEM_NEXT_PTR by a specified value (REG/IMM).ROMFETCH
Fetches 32 bits from the remaining bytecode treated as ROM here. Afterwards it increments the ROM_PTR which acts as an index.PUTCHAR_REG, PUTCHAR_IMM
These are used to display a character and afterwards set the PUT_FLAG which is used to display the waiting message.MOD
Pops and does a modulo operation on the value with the specified immediate. Later it pushes the result onto the stack.EXIT_REG, EXIT_IMM
They set the EXIT_CODE register to a register or an immediate and exits the VM.
LAY(LAYERS)ERS
At this point I wrote a simple disassembler script but whatttt there is a vm inside a vm. Now after analysing it this much there is no going back ryt? I began looking for options and chose miasm for this task as it is a tool I’ve kept my eye on recently.
Also I’ve heard good things about it’s Intermediate Representation, so why not try it ourselves.
Writing a Custom Architecture - Miasm 101
So I needed to start from scratch now. Though this part took most of my time but it was worth it.
I want to thank my friend ArcherCreat for helping me out with miasm. After a little chat with him I got a basic intro to miasm features and how can I use them to solve challenges. Infact he is the one who inspired me at first, you can checkout some of his writeups here.
If you are new to miasm, you can checkout their blog and github for more examples.
Basically we need to create 6 files in order to write a custom architecture in miasm.
1 | /home/user/.local/lib/python3.9/site-packages/miasm/ |
It seems like a lot, but in the end we’ll mainly work with regs.py, arch.py, sem.py as the others are mostly inherited from the base class.
regs.py
We can describe the registers used by our architecture here. By default the registers are 32 bits.
1 | reg_names32 = ["R0","R1","R2","R3","R4","R5","R6","PC","VM_MEM_PTR","LR","R10","R11","SP","R13","R14","R15","R16","R17","R18","R19"] |
I added the General Purpose Registers, Control Status Registers, and other miscellaneous 32 and 64 bit registers used by our VM. As the registers are referenced by their index in the struct we need to define them as shown above.
arch.py
We start off by describing the instructions for the first level, adding their opcodes and argument type. This is done by the addop() function.
Miasm automatically extracts the amount of bits from the bytecode according to the operands specified while defining the instructions and updates the offset.
1 | addop("MEMSHIFT_IMM", [bs32(0xba1116a9), imm32,]) |
Miasm works on binary stream, and offers us bs8() which converts a single byte opcode to binary. Similarly we can just create a bs32() helper in our case.
1 | class bs32(bs): |
This was easy as miasm already provides us with other basic helper functions such as int2bin(), swap32().
We define a global variable nest level to store the current nesting level while trying to disassemble the VM. We also need to initialize the register index and putchar immediate xor lists as these values differ across levels.
1 | nest_level = 0 |
Now we need to describe the operands and map them to their classes.
We’ll mostly use these :
1 | reg_idx = bs(l=32, cls=(vmv_reg_idx, vmv_arg)) |
As the register isn’t specified normally and its index is decoded on the fly using the succeeding 32 bits from bytecode we need to do a workaround for it as follows:
1 | class vmv_reg_idx(vmv_arg): |
In our class we define a custom decode function where we use the nest_level to get the xor value for a particular VM nesting level.
We do the same for PUTCHAR_IMM operation:
1 | class vmv_putchar_imm32(imm_noarg, vmv_arg): |
While building the CFG, miasm needs to know a few things such as :
- When does it need to stop disassembling
- When does it need to break the control flow
1 | conditional_branch = ["JE","JNE"] |
As the branch instructions use relative addressing and depends on PC(offset here) we can do the following to create a label in the expression.
1 | def dstflow2label(self, loc_db): |
sem.py
This is the main mastermind responsible for the Miasm IR.
We just need to describe each instruction and map them to the specific mnemonic defined in the arch.py.
For example, a PUSH_IMM instruction looks like the following :
1 | def push_imm(ir, instr, imm): |
We put the specific immediate to [SP+4] and increase SP by 4 afterwards.
Jumps could be tricky, in our case we need to pop two values off the stack so we assign temporary variables to store them and then use the ExprOp FLAG_EQ_CMP to compare them. Later we can use ExprCond to use it as a condition for changing the IRDst. We also decrease the SP by 8 in the end.
1 | def je(ir, instr, dst): |
Analysing Nested VMs
I began scrolling through the CFG, and found some notable differences.
Now we don’t have the hashmap implementation and there is a simple jump table in every nested vm.
An interesting thing to note here is that a specific instruction has the same offset in every VM.
As the register position differs here we will actually see that disassembly is inconsistent in some places such as at function @ 0xdc0 which acts as a bytecode iterator.
For the first nested VM the VM_CONTEXT structure is stored at R3 and checking out 0xdc0 the first register looks like a program counter. R6 looks like the VM_MEM_PTR comparing the differences between the blocks.
So in a nutshell, it can be described as follows :
1 | 0x00 vm_context struc |
But these register positions change in other levels as well but this is not much of a issue here.
The ROM has the following format :
The size of the next bytecode buffer is read from the first 4 bytes and then those no. of 32 bit values are fetched from the ROM and stored in VM memory. We observe that the sizes of the bytecode are also similar here and our input key is at the end.
Intuition
So overall, the nested VMs are almost similar and we can make use of the same instruction offsets as follows :
- Create a pattern detection helper to check for subsequent PUSH and JE operation and get their values and offsets respectively.
- Map handlers to offsets in a dictionary as
{handler : offset} - Keep on adding new opcodes at each level
Miasm allows us to define a callback function when it diassembles the blocks.
We can implement it as follows :
1 | def get_opcodes(mdis, cur_bloc, offsets_to_dis): |
Pattern 1
As obvious we need to extract the opcode and the offset.
Just adding an if statement does the job, where we look out for a block having 3 instructions PUSH_REG, PUSH_IMM, JE respectively and keep on adding the results to a dictionary.
1 | if (len(cur_bloc.lines) == 3 and |
Later we can just add the opcodes using the same old addop(), neat!
Pattern 2
We need another pattern for extracting the xor values for register indices, and putchar immediate xor values as well.
Here we check the block offset as the values are always initialized in that single block ie. 0xe8 and append those values to a global list.
1 | if(mdis.loc_db.get_location_offset(cur_bloc.loc_key) == 0xe8): |
Drawbacks Of Current Logic
My logic would fail when :
- Some of the opcodes are similar across levels but they map to a different instruction which would cause interference.
- Pattern isn’t found successfully due to obfuscation or different dispatchers.
- Offsets differ in a level
Although I could’ve done some workaround to deal with some of the issues but I didn’t bother doing it at the moment.
IR Simplification - SSA
Finally we get the Key checking algo unfolded, and we can make use of miasm to simplify the IR to SSA Expressions and extract the constraints easily.
1 | ira = machine.ira(loc_db) |
Just keep in mind at this point we only have our input in the ROM left.
The key checking algo isn’t that difficult to solve.
The first constraint checks the first 4 bytes of our input key as:
1 | (@[ROM + ROM_PTR] * 0x117052C0) % 0x7fffffff == 0x1 |
So, we just need to calculate the inverse modulo to get the first four bytes of our input here. The second one is easy as well, it checks the next 4 bytes as follows :
1 | (@[ROM + ROM_PTR + 0x4] % 0x77f3) == 0x4926 |
We can use the Chinese Remainder Theorem to solve it easily.
These operations are also carried out for the other two parts. A variable is set if all of these checks return true, ie. R16 here, and we get the failure or success message printed in the end.
Solution Script
Miasm also comes with features like symbolic execution and provides translators for SMT solvers like z3 but I don’t think it’ll help us here. A solution script using some basic math is enough.
1 | import string |
Finally, we get the flag as :
1 | FCSC{w3NeEdT0gODe3p3r} |
Solution Files
I’ve uploaded the architecture and other solution files along with the dot output files on my github here :
mrT4ntr4/Challenge-Solution-Files/FCSC21_CTF_VMV
Ahh, I still have more to learn about miasm, bye!