GreHack 2013 – New assembly (400)

Hello 🙂

In this post I will explain how I solved “New Assembly”, a reverse-engineering challenge, designed for the GreHack 2013 CTF. If you want to play with this crack-me, it is available here.

The binary is a 32-bit PE, which implements a small virtual machine, used to execute a custom bytecode that performs operations on the input password.

1 – VM Control Flow Graph

Usually, in order to emulate a CPU, VMs implement a well-known pattern known as “fetch, decode, execute”. Briefly, this consists of reading from the memory the next instruction to execute, extracting the opcode and its operand(s), and according to the opcode value, dispatching the instruction to a dedicated handler. This leads to a typical control flow graph where a lot of basic blocks are coming from the opcode dispatch function, and returning to the fetch next instruction function:

2 – Instructions fetching and decoding

In order to understand how the VM is implemented, I think that a good start is to analyze the part that fetchs and decodes the bytecode.

After analyzing this part and executing dynamically few instructions from the VM, it can be drawn that:

  • The VM uses a 16 bits value as the instruction pointer (stored at 0x401625)
  • The base address of the VM’s bytecode is 0x401357
  • The fetch instruction reads only 1 byte before decoding and dispatching
  • An instruction is composed of 4 highers bits that define an opcode, thus the VM supports up to 16 opcodes
  • An instruction is composed of 4 lower bits that define 2 registers identifiers
  • Each register id is composed of 2 bits, thus the VM is composed of up to 4 registers (hereby named reg0, reg1, reg2, and reg3)
  • The current destination register id is stored at 0x40162A
  • The current source register id is stored at 0x40162B
  • The 4 registers are encoded on 1 byte, thus representing together a single 32 bit integer stored at 0x401621

Here is the assembly code that performs these step:

In order to dispatch an opcode to its instruction handler, a set of bit test is performed on bits 7,6,5,4. Each test is followed by a conditional jump, which allows reaching an instruction handler after only 4 comparaisons.

3 – Analyzing instructions

Once the VM logical algorithm is identified, the next step is to analyze each opcode instruction handler. For instance, here is the instruction handler associated with the opcode 0x01, used to assign a 8 bits value to a register:

After showing a little patience, I wrote down a table composed of the format and meaning of each opcode:

Opcode Description Size Example
0x00 Moves a 8 bits value from a source register to a destination register 1 mov reg0, reg1
0x01 Moves a 8 bits value (2nd byte of the instruction) to a destination register 2 mov reg0, 0x42
0x02 Moves a 8 bits value from a memory address (stored in a source register) to a destination register 1 mov reg0, byte ptr data[reg1]
0x03 Moves a 8 bits value from a source register to a memory address (stored in a destination register) 1 mov byte ptr data[reg0], reg1
0x04 Does nothing, just return to the dispatcher 1 nop
0x05 Does nothing, just return to the dispatcher 1 nop
0x06 Performs a bitwise exclusive OR (XOR) operation on the destination register and the source register 1 xor reg0, reg1
0x07 Performs a comparison operation between the destination register and the source register. The comparison is performed by a (signed) subtraction which updates the zero-flag register accordingly. 1 cmp reg0, reg1
0x08 Performs an absolute conditional jump if the zero-flag register is set. The address is encoded on 16 bits (2nd and 3rd byte of the instruction) 3 jz 0x00AB
0x09 Performs an absolute conditional jump if the zero-flag register is not set. The address is encoded on 16 bits (2nd and 3rd byte of the instruction) 3 jnz 0x00AB
0x0A Performs an absolute unconditional jump. The address is encoded on 16 bits (2nd and 3rd byte of the instruction) 3 jmp 0x00AB
0x0B Stores one byte from the destination register into an memory area referenced by a dedicated register, hereby call regstr. This register is then incremented 1 stosb reg0
0x0C Reads one byte from the regstr register, and stores it within the destination register. The regstr is then decremented, thus this is used to read a string in reverse order 1 scasb reg0
0x0D Increments the destination register 1 inc reg0
0x0E Decrements the destination register 1 dec reg0
0x0F Computes a 32 bits integer using reg0,reg1,reg2 and reg3 where reg0 is the least significant byte and reg3 is the most significant byte. This integer is then check against the value 0x01030307. The string “Win!” or “Nop!” is then displayed according to the result of the previous check. 1 check_magic

4 – VM bytecode disassembly

The table presented above, allowed me to write a small linear disassembler, used to understand the VM bytecode:

5 – VM bytecode analysis

After compiling and executing the disassembler, I was able to understand the VM bytecode which is actually composed of only 39 instructions. Here is the output of the disassembler, with comments helping understanding what the bytecode does.

6 – Retrieving the flag!

The only remaining step is to extract the obfuscated flag, and to unobfuscate it, doing the reverse xor operation. This can be done using the simple following python script:

The execution of the script gives the following output:

Flag is: N3W_4SM_0PC0D3_R0X

Well, let’s try it:

If you want to play with another challenge that implements a simple VM, I would recommend this challenge from Root-Me: https://www.root-me.org/fr/Challenges/Cracking/ELF-VM/

Rémi

remi

Security Engineer / Malware Analyst, interested in reverse engineering, vulnerability exploitation, OS architecture & software developpement.

Leave a Reply

Your email address will not be published. Required fields are marked *