CH01 – RootersCTF Writeup

Finally, we are going to walkthrough the last reversing challenge in the RootersCTF 2019, I prefered to postpone that one till the end because that was the most fun for me, so let’s ride!

This challenge is a VM, so we should be mainly focusing on locating two things:

  • VM Context Structure: this is a structure mainly describing the state of the virtual processor at any given point of time, i.e registers values, STATUS, etc…
  • VM’s Fetch, Decode and Execute routine

We are given two files in the challenge vm and bytecode:

  • vm is the VM parser
  • bytecode contains the instructions to be executed by VM.

So mainly we will start by vm.

At the start, we can see the program is using fopen to have a file descriptor for an open file with modes rb (read binary).

It then calls a custom routine isValidXVMFile, which is only checking the first double word of the opened file whether it’s XVM2, fails if it’s not.

Afterwards, it prints a prompt to the user (xvm):, and waits for an input. We should notice that it’s using in here scanf to get some input from the user, with a string specifier %ld which is long decimal, that means the program is expecting a number instead of a string.

It then calls initializeStruct routine, which is a custom function that initializes the VM Context Structure we mentioned earlier.

We actually know nothing about any of the VM Context Structure’s fields, however we can tell from above that the VM Context Structure is 128 bytes in size, and has the following fields:

  • VMContextStruct+0x28: Contains a pointer to VMContextStruct+0x04
  • VMContextStruct+0x30: Contains a pointer to VMContextStruct+0x08
  • VMContextStruct+0x38: Contains a pointer to VMContextStruct+0x0C
  • VMContextStruct+0x40: Contains a pointer to VMContextStruct+0x10
  • VMContextStruct+0x48: Contains a pointer to VMContextStruct+0x14
  • VMContextStruct+0x50: Contains a pointer to VMContextStruct+0x18
  • VMContextStruct+0x58: Contains a pointer to VMContextStruct+0x1C
  • VMContextStruct+0x60: Contains a pointer to VMContextStruct+0x20
  • VMContextStruct+0x68: Contains a pointer to VMContextStruct+0x78
  • VMContextStruct+0x70: Contains a pointer to VMContextStruct+0x79
  • Initializes the bytes at VMContextStruct+0x78 and VMContextStruct+0x79 with zero, and VMContextStruct+0x7A with one

So we have 9 4-byte values at the start of the structure, and 3 1-byte values. We can guess that the 9 dwords are registers, and the 3 bytes are maybe STATUS/FLAG register.

After initializing the VM Context Structure, the program reads the first 156 bytes after the 4-byte signature of the XVM file, using the custom subroutine read156Bytes.

Afterwards, the program starts iterating through the 156 read bytes 4 bytes at a time, for the sake of simplicity, we can extract those 156 bytes from the bytecode file into a new file if we wanted to further have a look at (and maybe manually decompile) the VM instructions’ opcode.

After reading the instructions from the file, a call to a final subroutine is done before whether printing the flag or prompting the user with a Wrong Input message.

We can notice two interesting things happening in here:

  • VMContextStruct+0x7A seems to be some “execution continuation” flag, as long as it has non-zero value, the execution keeps parsing and executing instructions, once it’s zero the function returns.
  • VMContextStruct+0x00 is mostly the PC (Program Counter) of the VM, I concluded so because the value is parsed, multiplied by 4 (from this info, we knew that each instruction is 4 bytes long), and reads the corresponding data from the 156 read bytes based on that index.

Then, the 4 read bytes are given to the custom function fetch_decode_execute.

This big function is the VM’s execution flow handler routine (i.e Fetch, Decode, and Execute), after analyzing it, we can conclude that the VM supports the following OPCODE’s:

  • 0x0F:
    • 0 operands
    • Description: Copies userInput into VMContextStruct+0x20
  • 0x00:
    • 0 operands
    • Description: NOP
  • 0x01:
    • 2 operands (op1, op2)
    • Description: XOR’s Reg_op1, Reg_op2, stores the result in Reg1
  • 0x02:
    • 2 operands (op1, op2)
    • Description: AND’s #op1, #op2, stores the result in Reg1
  • 0x03:
    • 2 operands (op1, op2)
    • Description: OR’s #op1, #op2, stores the result in Reg1
  • 0x04:
    • 1 operand (op1)
    • Description: Stores value pointed to by PC+4 into Reg_op1
  • 0x05:
    • 2 operands (op1, op2)
    • Description: Checks if [Reg_op1] < [Reg_op2], if yes STATUS[0] = 0x00, STATUS[1] = 0x01. Then it checks if [Reg_op1] == [Reg_op2], if yes STATUS[0] = 0x01, STATUS[1] = 0x00.
  • 0x06:
    • 0 operands
    • Description: Exits, by setting STATUS[2] = 0x00, and returns STATUS[0]

Voila, we now have a full picture of how the VM works, the only remaining thing is writing a parser that reads the first 156 bytes from bytecode file (excluding the first 4 bytes), and starts execution in order to get us to the flag value.

Here is my Python3 implementation of the parser.

#!/usr/bin/env python3

# read the first 156 bytes of the "bytecode" file
with open("bytecode", "rb") as f:
    f.seek(4)
    data = f.read(156)


# Initialize VM Context Structure
VMContextStruct = {
    "RegisterFile" : [0, 0, 0, 0, 0, 0, 0, 0, 0],
    "STATUS" : [0, 0, 1]
}

# Initialize required variables for parsing each instruction
pc, opcode, op1, op2 = 0, 0, 0, 0
while VMContextStruct["STATUS"][2] == 1:
    pc      = VMContextStruct["RegisterFile"][0]
    # Read [pc+3] first, little endianness
    opcode  = data[pc+3]
    op1     = data[pc+2]+1
    op2     = data[pc+1]+1

    # Debug statements start here
    print("[DEBUG]\nOPCODE: {0}\nOP1: {1}\nOP2: {2}\n".format(hex(opcode), hex(op1), hex(op2)))
    print("[VMContextStructure]\nPC: {0}\nReg1: {1}\nReg2: {2}\nReg3:{3}\nReg4: {4}\nReg5: {5}\nReg6: {6}\nReg7: {7}\nReg8: {8}\n".format(hex(VMContextStruct["RegisterFile"][0]), hex(VMContextStruct["RegisterFile"][1]), hex(VMContextStruct["RegisterFile"][2]), hex(VMContextStruct["RegisterFile"][3]), hex(VMContextStruct["RegisterFile"][4]), hex(VMContextStruct["RegisterFile"][5]), hex(VMContextStruct["RegisterFile"][6]), hex(VMContextStruct["RegisterFile"][7]), hex(VMContextStruct["RegisterFile"][8])))
    input()
    # Debug statements end here

    # NOP instruction
    if opcode == 0x00:
        VMContextStruct["RegisterFile"][0] += 4
        continue
    # Reg1 = Regop1 ^ Regop2
    elif opcode == 0x01:
        VMContextStruct["RegisterFile"][1] = VMContextStruct["RegisterFile"][op1] ^ VMContextStruct["RegisterFile"][op2] 
    # Reg1 = #op1 & #op2
    elif opcode == 0x02:
        VMContextStruct["RegisterFile"][1] = op1 & op2
    # Reg1 = #op1 | #op2
    elif opcode == 0x03:
        VMContextStruct["RegisterFile"][1] = op1 | op2
    # Load PC+4 into Reg_op1
    elif opcode == 0x04:
        VMContextStruct["RegisterFile"][0] += 4
        pc = VMContextStruct["RegisterFile"][0]
        temp = data[pc+3] << 24
        temp |= data[pc+2] << 16
        temp |= data[pc+1] << 8
        temp |= data[pc]
        VMContextStruct["RegisterFile"][op1] = temp
    # Regop1 < Regop2, if yes Regop1 == Regop2, if yes STATUS[0] = 1, STATUS[1] = 0, else STATUS[0] = 0, STATUS[1] = 1
    elif opcode == 0x05:
        if VMContextStruct["RegisterFile"][op1] < VMContextStruct["RegisterFile"][op2]:
            if VMContextStruct["RegisterFile"][op1] == VMContextStruct["RegisterFile"][op2]:
                VMContextStruct["STATUS"][0] = 0x01
                VMContextStruct["STATUS"][1] = 0x00
            else:
                VMContextStruct["STATUS"][0] = 0x00
                VMContextStruct["STATUS"][1] = 0x01
    # Exit, STATUS[2] = 0
    elif opcode == 0x06:
        VMContextStruct["STATUS"][2] = 0

    VMContextStruct["RegisterFile"][0] += 4

After executing the script, we can see at PC = 0x24, Reg1 which is the first Register in the VM has the value 0xf00dbab3, which is the value compared with our input, the equivalent decimal of that value is 4027431603, let’s try it out.

Leave a comment