CSAW 2018 Quals - "kvm" Reversing 500 Writeup

Hello,

In this challenge we're given an x64 ELF binary. The program acts as a userspace host for KVM virtualization. Among other things, it sets up the VM's address space, initializes the necessary VM registers, copies the code from the ".payload" section to it, then finally runs it.


Additionally, the userspace host expects the VM to trap when executing the three illegal instructions : IN, OUT, and HLT as shown below. The host will do some processing and then fix the VM's state so it can graciously continue executing.

 

And here is an instance of a HLT instruction within the VM's code.

 

Let's now describe the behavior of the host for each illegal instruction.

IN (port 0xE9) : Reads a single character from STDIN and returns it to the VM (The first thing that the VM does is read user input from STDIN).

OUT (port 0xE9) : Outputs a single character to STDOUT.

HLT :  Before the VM executes a HLT instruction, it moves a special value into EAX. After it traps, our host reads this value and uses it as a key in an array. Each key corresponds to a handler routine within the VM's address space.

Here is a list of all present handlers :

Handler 0
Key : 0xc50b6060 => Handler : 0x454
===================
Handler 1
Key : 0x9d1fe433 => Handler : 0x3ed
===================
Handler 2
Key : 0x54a15b03 => Handler : 0x376
===================
Handler 3
Key : 0x8f6e2804 => Handler : 0x422
===================
Handler 4
Key : 0x8aeef509 => Handler : 0x389
===================
Handler 5
Key : 0x3493310d => Handler : 0x32c
===================
Handler 6
Key : 0x59c33d0f => Handler : 0x3e1
===================
Handler 7
Key : 0x968630d0 => Handler : 0x400
===================
Handler 8
Key : 0xef5bdd13 => Handler : 0x435
===================
Handler 9
Key : 0x64d8a529 => Handler : 0x3b8
===================
Handler 10
Key : 0x5f291a64 => Handler : 0x441
===================
Handler 11
Key : 0x5de72dd => Handler : 0x347
===================
Handler 12
Code : 0xfc2ff49f => Handler : 0x3ce
===================

What the host does then is set VM's RIP register to the corresponding handler.

And by examining the handlers, we see that they invoke each other using the HLT instruction.

 

Now, let's try to examine what the VM does and figure out what these handlers are used for.

Briefly, 0x2800 bytes are read from STDIN and for each of these bytes sub_1E0 is called. The first time it's called, this function takes the user-supplied character and the address 0x1300 which points to some data.

 

sub_1E0 initializes local variables and then branches to the handler at 0x32c.

This one examines the dereferenced value, if it is 0xFF it branches to the handler at 0x347, if not it branches to a handler that compares the dereferenced value with the user-supplied character.

 

Now, examining the handler at  0x347 and the handlers it invokes (see the screenshot below : renamed sub_1E0 to traverse_tree), we see that the address 0x1300 is a root node of a binary tree.

In the tree at 0x1300, parent nodes have 0xFF as a value and contain two pointers for the left & right children. A leaf node, contains an ASCII character as a value which we suspect constitutes our flag. Recall that when a leaf is encountered a comparison is made with the user-supplied character and a boolean value is returned (RET instruction).

In the screenshot below, we see that the tree is recursively traversed and when a leaf is encountered and the comparison is successful sub_172 is called as we return from the functions recursively called. 

  

 

When we traverse a left node, sub_172 is called with 0 whereas when we traverse a right node 1 is passed.

What this function does is build an array of bits starting at 0x1320 in the following manner :

BYTE* bits = 0x1320;
BYTE count = 0;

void sub_172( BYTE bit )
{
       *bits |= bit << count++;
       if ( count == 8 )
      {
            count = 0;
            bits++;
      }
}  

This way, the bit array will represent the path traversed from the leaves to the root for all characters.

When this is done for all input characters, the resulting bit array is compared against the bit array for the correct input at 0x580. So, what we have to do is this :

1. Extract the correct bit array from 0x580 as bytes.
2.  Reverse the order of the bytes and then convert them to binary representation. We reverse the order because we want to traverse the tree from root to leaf, doing the opposite would be impossible since all bits are concatenated. Also, when doing this, we'll start by extracting the last character and so on until we reach the first.

Below is the IDA Python script that you should run on the extracted ".payload" section to get the flag :

	from idc import *
	root = 0x1300
	flag = ''
	def tobits(s):
	result = []
	for c in s:
	bits = bin(ord(c))[2:]
	bits = '00000000'[len(bits):] + bits
	result.extend([[int(b) for b in bits]])
	return result
	def traverse_to_leaf(element) :
	global bits
	if Byte(element) == 0xFF :
	bit = bits.pop(0)
	if element == root and bit == 1 :
	#skip null byte
	return
	if bit == 0 :
	#left
	traverse_to_leaf(Qword(element + 8))
	else :
	#right
	traverse_to_leaf(Qword(element + 16))
	else :
	global flag
	flag += chr(Byte(element))
	bl = tobits(GetManyBytes(0x580, 0x54A))
	bl.reverse() #Reverse so we can start exploring from the root
	#Flatten the list
	bits = []
	for byte in bl :
	for bit in byte :
	bits.append(bit)
	while bits :
	traverse_to_leaf(root)
	print flag[::-1] #reverse

view raw kvm_solve.py hosted with ❤ by GitHub

   
As a result, we get the flag and we see that the VM was expecting a tar file as input:

flag.txt0000664000175000017500000000007113346340766011602 0ustar toshitoshiflag{who would win? 100 ctf teams or 1 obfuscat3d boi?}


Thank you for reading :)

You can follow me on Twitter : here