**Description**
> We found a mysterious program that none of our most talented hackers could even begin to figure out.> > Author: toshi
**Files provided**
 - [`challenge`](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-14-CSAW-CTF-Quals/files/kvm-challenge)
**Solution** (by [Mem2019](https://github.com/Mem2019))
The OS is obsfucated by using `hlt` instruction to implement the conditional or unconditional `jmp`, so we can patch it first
```pythonhlt_tab = {0xc50b6060 : 0x454,0x9d1fe433 : 0x3ed,0x54a15b03 : 0x376,0x8f6e2804 : 0x422,0x8aeef509 : 0x389,0x3493310d : 0x32c,0x59c33d0f : 0x3e1,0x968630d0 : 0x400,0xef5bdd13 : 0x435,0x64d8a529 : 0x3b8,0x5f291a64 : 0x441,0x5de72dd : 0x347,0xfc2ff49f : 0x3ce}text_end = 0x611def replace_jmps(start,end):	for p in xrange(start,end):		if Byte(p) == 0xB8 and Byte(p + 5) == 0xF4 and Dword(p + 1) in hlt_tab:			jmp_addr = hlt_tab[Dword(p + 1)]			PatchByte(p, 0xE9)			PatchDword(p + 1, (jmp_addr - (p + 5)) & 0xffffffff)			PatchByte(p + 5, 0x90)		#Patch to hlt to jmp```
There are only 4 conditional `jmp`, so analyze them by hand. Also, edit the function to extend it, so that the analysis in IDA will be easier.
After some reversing, we found that the program is a Huffman Tree. It will encode the input into the path going from root node to the corresponding leaf node, but in reversed order(which makes decoding very hard, since the ambiguity exists).
I got stucked in the algorithm for 3 hours, will add more details later if I have time.
```pythonROOT_OFF = 0x1300def MyQword(addr):	ret = Qword(addr)	if ret == 0xFFFFFFFFFFFFFFFF:		return 0	else:		return retdef MyByte(addr):	ret = Byte(addr)	if ret == 0xFF:		return 0	else:		return ret
#dfs to get the mappingdef get_path_to_char(node):	if MyQword(node) != 0xFF:		return [([],chr(MyQword(node)))]	right = MyQword(node + 0x10)	left = MyQword(node + 8)	ret = []	lmap = get_path_to_char(left)	for (p, c) in lmap:		ret.append((p + [0], c))	rmap = get_path_to_char(right)	for (p, c) in rmap:		ret.append((p + [1], c))	return ret
def begin_with(l, sl):	if len(sl) > len(l):		return False	for i in xrange(0, len(sl)):		if l[i] != sl[i]:			return False	return True# recursion too long!!!# #return lsit of strings of possibilities# def get_all_poss(bits, mapping, pad):# 	poss = []# 	for (p,c) in mapping:# 		if begin_with(bits, p):# 			poss.append((len(p), c))# 	ret = []# 	for x in poss:# 		#print poss# 		print pad * ' ' + x[1]# 		ret += map(lambda st : x[1] + st, get_all_poss(bits[x[0]:], mapping, pad + 1))# 	#print ret# 	return ret
#return lsit of strings of possibilitiesdef get_all_poss(obits, mapping, pad):	live_bits = [("",obits)]	while len(live_bits) != 1 or len(live_bits[0][1]) != 0:		(parsed,bits) = live_bits.pop()		poss = []		for (p,c) in mapping:			if begin_with(bits, p):				poss.append((len(p), c))		#get all poss		for x in poss:			#print x			live_bits.append((parsed + x[1],bits[x[0]:]))		#if len(live_bits) == 1:		print live_bits	return live_bits
def recover(data):	ret = []	bits = []	for x in data:		for i in range(0,8):			if x & (1 << i) != 0:				bits.append(1)			else:				bits.append(0)	print bits	mapping = get_path_to_char(ROOT_OFF)	#while len(bits) > 0: loop does not work well for ambiguoutyt	ret = get_all_poss(bits, mapping, 0)	return ret
# fails because it is in reverse order# def recover(data):# 	ret = []# 	cur_node = ROOT_OFF# 	for x in data:# 		for i in range(0,8)[::-1]:# 			print hex(cur_node)# 			if x & (1 << i) != 0: #r# 				cur_node = MyQword(cur_node + 0x10)# 			else:# 				cur_node = MyQword(cur_node + 8)# 			if MyQword(cur_node) != 0xff:# 				ret.append(MyQword(cur_node))# 				cur_node = ROOT_OFF# 	return ret```
Even in the end I did not get the original input, but I've already got the flag, which is part of the input.