Nullcon HackIM CTF 2013 – Reverse Engineering 300 Write up

Reverse Engineering 300

This Reverse Engineering challenge was a virtual machine implemented in Javascript:

/*
	+---------------------------+
	| Custom Javascript Crackme |
	+---------------------------+

[+] Tested on : Safari, Google-Chrome, Opera, Firefox. (IE ?? O..puhleez!)
[+] No obfuscation, nothing. Just plain code. 🙂
[?] Should be an easy one, eh? 😉
[+] Best of luck!
(c) HackIM2013

*/

var key=[];
var code=[901, 340, 505, 140, 305, 461, 901, 722, 340, 539, 723, 241, 339, 540, 238, 142, 342, 901, 722, 901, 722, 606, 000, 542, 243, 243, 244, 340, 830, 653, 553, 140, 145, 353, 546, 140, 653, 000, 17, 10, 000, 001, 000, 400, 60, 459, 41, 22, 76, 76, 75, 75, 37, 417, 560, 140, 145, 360, 547, 140, 417, 567, 140, 145, 367, 548, 140, 417, 574, 140, 145, 374, 549, 140, 417, 581, 140, 145, 381, 550, 140, 417, 588, 140, 145, 388, 551, 140, 417, 595, 140, 145, 395, 552, 140, 417, 423];
var output=[];

function msg()
{
var message=output.toString().replace(/\,/gi,"");;
document.getElementById("key").value=message;
}

function LMC()
{
	var accumulator=0;
	var inp_counter=0;
	var code_counter=0;
	var pc=code[code_counter];
	while(code[code_counter]>0)
	{
		pc=code[code_counter];
		var mailbox=parseInt(pc%100);
		var opcode=parseInt(pc/100);
		switch(opcode)
		{
			case 1:
  						accumulator=accumulator+code[mailbox];
  						code_counter++;
  						break;
			case 2:
  						accumulator=accumulator-code[mailbox];
  						code_counter++;
  						break;
			case 3:
  						code[mailbox]=accumulator;
  						code_counter++;
  						break;
			case 5:
  						accumulator=code[mailbox];
  						code_counter++;
  						break;
			case 6:
  						code_counter=mailbox;
  						break;
			case 7:
  						if(accumulator==0)
  							{code_counter=mailbox;}
  						else{code_counter++;}
  						break;
			case 8:
  						if(accumulator>=0)
  							{code_counter=mailbox;}
  						else{code_counter++;}
  						break;
			case 9:
  						if(pc==901)
  						{
  							if(inp_counter<key.length)
  							{
  								accumulator=key[inp_counter];
  							 	inp_counter++;
  							 }
  							 else
  							 {
  							 	accumulator=0;
  							 }
  						}
  						else if(pc== 902)
  						{
  							output.push(String.fromCharCode(accumulator));
   						}
  						code_counter++;
  						break;
  		case 0:
  						code[0]=0;
  						code_counter=0;
  						break;
    	default:
  						code[0]=0;
              code_counter=0;
              break;
		}
	}
}

function setup()
{
	 var temp=document.getElementById("key").value;
	 for(var i=0; i<temp.length; ++i)
	 {
	 	key.push(temp.charCodeAt(i));
	 }
	 LMC();
	 msg();
}

Let’s dissect this virtual machine!

  • The VM has an accumulator which is used to:
    • hold temporary values
    •  read from memory
    •  write to memory
    •  decide whether jumps are taken or not
    •  read characters from the input (the key we’re entering)
    •  output characters (probably the flag for this challenge)

  •  The VM has a single block of memory with read + write + execute permissions.

  •  The VM has just 9 valid instructions. Each instruction (except for the EXIT one) has exactly 1 argument.
  •  Opcode 1 adds its argument to the accumulator. Let’s call this instruction ADD_ACC.
  •  Opcode 2 substracts its argument from the accumulator. Let’s call this instruction SUB_ACC.
  •  Opcode 3 stores the accumulator in the memory address indicated by its argument. Let’s call this instruction STOR_ACC.
  •  Opcode 5 loads a value in the accumulator from the memory address indicated by its argument. Let’s call it LOAD_ACC.
  •  Opcode 6 makes an unconditional jump to the memory address specified by its argument. Let’s call it JMP.
  •  Opcode 7 is a conditional jump; it jumps to the memory address specified by its argument if accumulator == 0. Let’s call this instruction JZ.
  • Opcode 8 is also a conditional jump; it jumps to the memory address specified by its argument if the value of the accumulator is >= 0. Let’s call it JGE.
  • Opcode 9 is a bit different than the other ones:
    • If its argument is 1, it will load the next character from our entered key an store its ordinal in the accumulator. So let’s call this instruction LOAD_ACC_FROM_KEY. Note that once a character from our key is read by the LOAD_ACC_FROM_KEY instruction, it will be no longer available to be read by this instruction. Also, If this instruction is executed when there are no more remaining chars in the key, it will set the accumulator to 0, as a way to signal that there are no more characters left to be processed.
    •  If its argument is 2, it will output the char corresponding to the value of the accumulator. Let’s call it OUTPUT_ACC.
  • Opode 0 just halts the virtual machine. Let’s call this instruction EXIT.
  • When the VM tries to execute an unknown instruction, it halts.

 

Having all of these in mind, I have instrumented the virtual machine in a way that should output useful information and provide a helpful runtime trace log.

This instrumented version will spit, for each executed instruction: program counter, instruction name, argument for the instruction, whether a jump is taken or not, original value and new value of the accumulator/memory address when any of them gets modified, character read from the key and character printed to the output.

var key=[];
var code=[901, 340, 505, 140, 305, 461, 901, 722, 340, 539, 723, 241, 339, 540, 238, 142, 342, 901, 722, 901, 722, 606, 000, 542, 243, 243, 244, 340, 830, 653, 553, 140, 145, 353, 546, 140, 653, 000, 17, 10, 000, 001, 000, 400, 60, 459, 41, 22, 76, 76, 75, 75, 37, 417, 560, 140, 145, 360, 547, 140, 417, 567, 140, 145, 367, 548, 140, 417, 574, 140, 145, 374, 549, 140, 417, 581, 140, 145, 381, 550, 140, 417, 588, 140, 145, 388, 551, 140, 417, 595, 140, 145, 395, 552, 140, 417, 423];
var output=[];

function msg()
{
var message=output.toString().replace(/\,/gi,"");;
document.getElementById("key").value=message;
}

function log(pc, msg){
	if (window.console && window.console.log){
		console.log("[" + pc + "] " + msg);
	}
}

function LMC()
{
	var accumulator=0;
	var inp_counter=0;
	var code_counter=0;
	var jump_string = "";
	var pc=code[code_counter];
	while(code[code_counter]>0)
	{
		pc=code[code_counter];
		var mailbox=parseInt(pc%100);
		var opcode=parseInt(pc/100);
		switch(opcode)
		{
			//Add argument to accumulator
			case 1:
						log(code_counter, "ADD_ACC " + mailbox + " (" + code[mailbox] + ") :  accumulator = " + accumulator + " -> accumulator = " + (accumulator+code[mailbox]));
  						accumulator=accumulator+code[mailbox];
  						code_counter++;
  						break;
			//Substract argument from accumulator
			case 2:
						log(code_counter, "SUB_ACC " + mailbox + " (" + code[mailbox] + ") : accumulator = " + accumulator + " -> accumulator = " + (accumulator - code[mailbox]));
  						accumulator=accumulator-code[mailbox];
  						code_counter++;
  						break;
			//Store accumulator in memory[argument]
			case 3:
						log(code_counter, "STOR_ACC " + mailbox + " : code[" + mailbox + "] = " + code[mailbox] + " -> code[" + mailbox + "] = " + accumulator);
  						code[mailbox]=accumulator;
  						code_counter++;
  						break;
			//Load accumulator from memory[argument]
			case 5:
						log(code_counter, "LOAD_ACC " + mailbox + " : accumulator = " + accumulator + " -> accumulator = " + code[mailbox]);
  						accumulator=code[mailbox];
  						code_counter++;
  						break;
			//JUMP to  memory address
			case 6:
						log(code_counter, "JMP " + mailbox + " : code_counter = " + code_counter + " -> code_counter = " + mailbox);
  						code_counter=mailbox;
  						break;
			//JZ: conditional jump, taken if accumulator == 0
			case 7:
						old_pc = code_counter;
						jump_string = "JZ " + mailbox + " : (accumulator = " + accumulator + "), code_counter = " + code_counter + " -> code_counter = " + mailbox;
  						if(accumulator==0)
  							{code_counter=mailbox;}
  						else{code_counter++; jump_string = "[NOT TAKEN] " + jump_string;}
						log(old_pc, jump_string);
  						break;
			//JGE: conditional jump, taken if accumulator >= 0
			case 8:
						old_pc = code_counter;
						jump_string = "JGE " + mailbox + " : (accumulator = " + accumulator + "), code_counter = " + code_counter + " -> code_counter = " + mailbox;
  						if(accumulator>=0)
  							{code_counter=mailbox;}
  						else{code_counter++; jump_string = "[NOT TAKEN] " + jump_string;}
						log(old_pc, jump_string);
  						break;
			case 9:
						//Load accumulator from key char
  						if(pc==901)
  						{

  							if(inp_counter<key.length)   							{ 								log(code_counter, "LOAD_ACC_FROM_KEY " + inp_counter + " : accumulator = " + accumulator + " -> accumulator = " + key[inp_counter] + "('" + String.fromCharCode(key[inp_counter]) + "')");
  								accumulator=key[inp_counter];
  							 	inp_counter++;
  							 }
  							 else
  							 {
								log(code_counter, "LOAD_ACC_FROM_KEY " + inp_counter + " (no more chars in key) : accumulator = " + accumulator + " -> accumulator = 0");
  							 	accumulator=0;
  							 }
  						}
						//Print char from accumulator
  						else if(pc== 902)
  						{
							log(code_counter, "OUTPUT_ACC " + accumulator + " : character " + String.fromCharCode(accumulator));
  							output.push(String.fromCharCode(accumulator));
   						}
  						code_counter++;
  						break;
		//Exit
  		case 0:
						log(code_counter, "EXIT.");
  						code[0]=0;
  						code_counter=0;
  						break;
		//Unknown opcode: Exit
    	default:
						log(code_counter, "UNKNOWN_OP : " + pc);
  						code[0]=0;
              code_counter=0;
              break;
		}
	}
}

function setup()
{
	 var temp=document.getElementById("key").value;
	 for(var i=0; i<temp.length; ++i) 	 { 	 	key.push(temp.charCodeAt(i)); 	 } 	 LMC(); 	 msg(); } 

Let’s see the output of the instrumented VM when entering the key “abcdefghijklmnopqrstuvwxyz1234567890“:

 [0] LOAD_ACC_FROM_KEY 0 : accumulator = 0 -> accumulator = 97('a')

[1] STOR_ACC 40 : code[40] = 0 -> code[40] = 97

[2] LOAD_ACC 5 : accumulator = 97 -> accumulator = 461

[3] ADD_ACC 40 (97) :  accumulator = 461 -> accumulator = 558

[4] STOR_ACC 5 : code[5] = 461 -> code[5] = 558

[5] LOAD_ACC 58 : accumulator = 558 -> accumulator = 547

[6] LOAD_ACC_FROM_KEY 1 : accumulator = 547 -> accumulator = 98('b')

[7] [NOT TAKEN] JZ 22 : (accumulator = 98), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 97 -> code[40] = 98

[9] LOAD_ACC 39 : accumulator = 98 -> accumulator = 10

[10] [NOT TAKEN] JZ 23 : (accumulator = 10), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 10 -> accumulator = 9

[12] STOR_ACC 39 : code[39] = 10 -> code[39] = 9

[13] LOAD_ACC 40 : accumulator = 9 -> accumulator = 98

[14] SUB_ACC 38 (17) : accumulator = 98 -> accumulator = 81

[15] ADD_ACC 42 (0) :  accumulator = 81 -> accumulator = 81

[16] STOR_ACC 42 : code[42] = 0 -> code[42] = 81

[17] LOAD_ACC_FROM_KEY 2 : accumulator = 81 -> accumulator = 99('c')

[18] [NOT TAKEN] JZ 22 : (accumulator = 99), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 3 : accumulator = 99 -> accumulator = 100('d')

[20] [NOT TAKEN] JZ 22 : (accumulator = 100), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 4 : accumulator = 100 -> accumulator = 101('e')

[7] [NOT TAKEN] JZ 22 : (accumulator = 101), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 98 -> code[40] = 101

[9] LOAD_ACC 39 : accumulator = 101 -> accumulator = 9

[10] [NOT TAKEN] JZ 23 : (accumulator = 9), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 9 -> accumulator = 8

[12] STOR_ACC 39 : code[39] = 9 -> code[39] = 8

[13] LOAD_ACC 40 : accumulator = 8 -> accumulator = 101

[14] SUB_ACC 38 (17) : accumulator = 101 -> accumulator = 84

[15] ADD_ACC 42 (81) :  accumulator = 84 -> accumulator = 165

[16] STOR_ACC 42 : code[42] = 81 -> code[42] = 165

[17] LOAD_ACC_FROM_KEY 5 : accumulator = 165 -> accumulator = 102('f')

[18] [NOT TAKEN] JZ 22 : (accumulator = 102), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 6 : accumulator = 102 -> accumulator = 103('g')

[20] [NOT TAKEN] JZ 22 : (accumulator = 103), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 7 : accumulator = 103 -> accumulator = 104('h')

[7] [NOT TAKEN] JZ 22 : (accumulator = 104), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 101 -> code[40] = 104

[9] LOAD_ACC 39 : accumulator = 104 -> accumulator = 8

[10] [NOT TAKEN] JZ 23 : (accumulator = 8), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 8 -> accumulator = 7

[12] STOR_ACC 39 : code[39] = 8 -> code[39] = 7

[13] LOAD_ACC 40 : accumulator = 7 -> accumulator = 104

[14] SUB_ACC 38 (17) : accumulator = 104 -> accumulator = 87

[15] ADD_ACC 42 (165) :  accumulator = 87 -> accumulator = 252

[16] STOR_ACC 42 : code[42] = 165 -> code[42] = 252

[17] LOAD_ACC_FROM_KEY 8 : accumulator = 252 -> accumulator = 105('i')

[18] [NOT TAKEN] JZ 22 : (accumulator = 105), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 9 : accumulator = 105 -> accumulator = 106('j')

[20] [NOT TAKEN] JZ 22 : (accumulator = 106), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 10 : accumulator = 106 -> accumulator = 107('k')

[7] [NOT TAKEN] JZ 22 : (accumulator = 107), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 104 -> code[40] = 107

[9] LOAD_ACC 39 : accumulator = 107 -> accumulator = 7

[10] [NOT TAKEN] JZ 23 : (accumulator = 7), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 7 -> accumulator = 6

[12] STOR_ACC 39 : code[39] = 7 -> code[39] = 6

[13] LOAD_ACC 40 : accumulator = 6 -> accumulator = 107

[14] SUB_ACC 38 (17) : accumulator = 107 -> accumulator = 90

[15] ADD_ACC 42 (252) :  accumulator = 90 -> accumulator = 342

[16] STOR_ACC 42 : code[42] = 252 -> code[42] = 342

[17] LOAD_ACC_FROM_KEY 11 : accumulator = 342 -> accumulator = 108('l')

[18] [NOT TAKEN] JZ 22 : (accumulator = 108), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 12 : accumulator = 108 -> accumulator = 109('m')

[20] [NOT TAKEN] JZ 22 : (accumulator = 109), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 13 : accumulator = 109 -> accumulator = 110('n')

[7] [NOT TAKEN] JZ 22 : (accumulator = 110), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 107 -> code[40] = 110

[9] LOAD_ACC 39 : accumulator = 110 -> accumulator = 6

[10] [NOT TAKEN] JZ 23 : (accumulator = 6), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 6 -> accumulator = 5

[12] STOR_ACC 39 : code[39] = 6 -> code[39] = 5

[13] LOAD_ACC 40 : accumulator = 5 -> accumulator = 110

[14] SUB_ACC 38 (17) : accumulator = 110 -> accumulator = 93

[15] ADD_ACC 42 (342) :  accumulator = 93 -> accumulator = 435

[16] STOR_ACC 42 : code[42] = 342 -> code[42] = 435

[17] LOAD_ACC_FROM_KEY 14 : accumulator = 435 -> accumulator = 111('o')

[18] [NOT TAKEN] JZ 22 : (accumulator = 111), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 15 : accumulator = 111 -> accumulator = 112('p')

[20] [NOT TAKEN] JZ 22 : (accumulator = 112), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 16 : accumulator = 112 -> accumulator = 113('q')

[7] [NOT TAKEN] JZ 22 : (accumulator = 113), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 110 -> code[40] = 113

[9] LOAD_ACC 39 : accumulator = 113 -> accumulator = 5

[10] [NOT TAKEN] JZ 23 : (accumulator = 5), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 5 -> accumulator = 4

[12] STOR_ACC 39 : code[39] = 5 -> code[39] = 4

[13] LOAD_ACC 40 : accumulator = 4 -> accumulator = 113

[14] SUB_ACC 38 (17) : accumulator = 113 -> accumulator = 96

[15] ADD_ACC 42 (435) :  accumulator = 96 -> accumulator = 531

[16] STOR_ACC 42 : code[42] = 435 -> code[42] = 531

[17] LOAD_ACC_FROM_KEY 17 : accumulator = 531 -> accumulator = 114('r')

[18] [NOT TAKEN] JZ 22 : (accumulator = 114), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 18 : accumulator = 114 -> accumulator = 115('s')

[20] [NOT TAKEN] JZ 22 : (accumulator = 115), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 19 : accumulator = 115 -> accumulator = 116('t')

[7] [NOT TAKEN] JZ 22 : (accumulator = 116), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 113 -> code[40] = 116

[9] LOAD_ACC 39 : accumulator = 116 -> accumulator = 4

[10] [NOT TAKEN] JZ 23 : (accumulator = 4), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 4 -> accumulator = 3

[12] STOR_ACC 39 : code[39] = 4 -> code[39] = 3

[13] LOAD_ACC 40 : accumulator = 3 -> accumulator = 116

[14] SUB_ACC 38 (17) : accumulator = 116 -> accumulator = 99

[15] ADD_ACC 42 (531) :  accumulator = 99 -> accumulator = 630

[16] STOR_ACC 42 : code[42] = 531 -> code[42] = 630

[17] LOAD_ACC_FROM_KEY 20 : accumulator = 630 -> accumulator = 117('u')

[18] [NOT TAKEN] JZ 22 : (accumulator = 117), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 21 : accumulator = 117 -> accumulator = 118('v')

[20] [NOT TAKEN] JZ 22 : (accumulator = 118), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 22 : accumulator = 118 -> accumulator = 119('w')

[7] [NOT TAKEN] JZ 22 : (accumulator = 119), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 116 -> code[40] = 119

[9] LOAD_ACC 39 : accumulator = 119 -> accumulator = 3

[10] [NOT TAKEN] JZ 23 : (accumulator = 3), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 3 -> accumulator = 2

[12] STOR_ACC 39 : code[39] = 3 -> code[39] = 2

[13] LOAD_ACC 40 : accumulator = 2 -> accumulator = 119

[14] SUB_ACC 38 (17) : accumulator = 119 -> accumulator = 102

[15] ADD_ACC 42 (630) :  accumulator = 102 -> accumulator = 732

[16] STOR_ACC 42 : code[42] = 630 -> code[42] = 732

[17] LOAD_ACC_FROM_KEY 23 : accumulator = 732 -> accumulator = 120('x')

[18] [NOT TAKEN] JZ 22 : (accumulator = 120), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 24 : accumulator = 120 -> accumulator = 121('y')

[20] [NOT TAKEN] JZ 22 : (accumulator = 121), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 25 : accumulator = 121 -> accumulator = 122('z')

[7] [NOT TAKEN] JZ 22 : (accumulator = 122), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 119 -> code[40] = 122

[9] LOAD_ACC 39 : accumulator = 122 -> accumulator = 2

[10] [NOT TAKEN] JZ 23 : (accumulator = 2), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 2 -> accumulator = 1

[12] STOR_ACC 39 : code[39] = 2 -> code[39] = 1

[13] LOAD_ACC 40 : accumulator = 1 -> accumulator = 122

[14] SUB_ACC 38 (17) : accumulator = 122 -> accumulator = 105

[15] ADD_ACC 42 (732) :  accumulator = 105 -> accumulator = 837

[16] STOR_ACC 42 : code[42] = 732 -> code[42] = 837

[17] LOAD_ACC_FROM_KEY 26 : accumulator = 837 -> accumulator = 49('1')

[18] [NOT TAKEN] JZ 22 : (accumulator = 49), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 27 : accumulator = 49 -> accumulator = 50('2')

[20] [NOT TAKEN] JZ 22 : (accumulator = 50), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 28 : accumulator = 50 -> accumulator = 51('3')

[7] [NOT TAKEN] JZ 22 : (accumulator = 51), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 122 -> code[40] = 51

[9] LOAD_ACC 39 : accumulator = 51 -> accumulator = 1

[10] [NOT TAKEN] JZ 23 : (accumulator = 1), code_counter = 10 -> code_counter = 23

[11] SUB_ACC 41 (1) : accumulator = 1 -> accumulator = 0

[12] STOR_ACC 39 : code[39] = 1 -> code[39] = 0

[13] LOAD_ACC 40 : accumulator = 0 -> accumulator = 51

[14] SUB_ACC 38 (17) : accumulator = 51 -> accumulator = 34

[15] ADD_ACC 42 (837) :  accumulator = 34 -> accumulator = 871

[16] STOR_ACC 42 : code[42] = 837 -> code[42] = 871

[17] LOAD_ACC_FROM_KEY 29 : accumulator = 871 -> accumulator = 52('4')

[18] [NOT TAKEN] JZ 22 : (accumulator = 52), code_counter = 18 -> code_counter = 22

[19] LOAD_ACC_FROM_KEY 30 : accumulator = 52 -> accumulator = 53('5')

[20] [NOT TAKEN] JZ 22 : (accumulator = 53), code_counter = 20 -> code_counter = 22

[21] JMP 6 : code_counter = 21 -> code_counter = 6

[6] LOAD_ACC_FROM_KEY 31 : accumulator = 53 -> accumulator = 54('6')

[7] [NOT TAKEN] JZ 22 : (accumulator = 54), code_counter = 7 -> code_counter = 22

[8] STOR_ACC 40 : code[40] = 51 -> code[40] = 54

[9] LOAD_ACC 39 : accumulator = 54 -> accumulator = 0

[10] JZ 23 : (accumulator = 0), code_counter = 10 -> code_counter = 23

[23] LOAD_ACC 42 : accumulator = 0 -> accumulator = 871

[24] SUB_ACC 43 (400) : accumulator = 871 -> accumulator = 471

[25] SUB_ACC 43 (400) : accumulator = 471 -> accumulator = 71

[26] SUB_ACC 44 (60) : accumulator = 71 -> accumulator = 11

[27] STOR_ACC 40 : code[40] = 54 -> code[40] = 11

[28] JGE 30 : (accumulator = 11), code_counter = 28 -> code_counter = 30

[30] LOAD_ACC 53 : accumulator = 11 -> accumulator = 417

[31] ADD_ACC 40 (11) :  accumulator = 417 -> accumulator = 428

[32] ADD_ACC 45 (459) :  accumulator = 428 -> accumulator = 887

[33] STOR_ACC 53 : code[53] = 417 -> code[53] = 887

[34] LOAD_ACC 46 : accumulator = 887 -> accumulator = 41

[35] ADD_ACC 40 (11) :  accumulator = 41 -> accumulator = 52

[36] JMP 53 : code_counter = 36 -> code_counter = 53

[53] JGE 87 : (accumulator = 52), code_counter = 53 -> code_counter = 87

[87] ADD_ACC 40 (11) :  accumulator = 52 -> accumulator = 63

[88] UNKNOWN_OP : 417

Once we have understood how this virtual machine works, we should focus on understanding what the actual program that runs on top of it does.

In order to understand what the program does I have coded a simple disassembler:

def disassemble(code):
    disasm = []
    address = 0
    for instr in code:
        opcode = instr / 100
        args   = instr % 100

        if opcode == 1:
            disasm.append('[%s] ADD_ACC\t%s' % (address, args))
        elif opcode == 2:
            disasm.append('[%s] SUB_ACC\t%s' % (address, args))
        elif opcode == 3:
            disasm.append('[%s] STOR_ACC\t%s' % (address, args))
        elif opcode == 5:
            disasm.append('[%s] LOAD_ACC\t%s' % (address, args))
        elif opcode == 6:
            disasm.append('[%s] JMP\t%s' % (address, args))
        elif opcode == 7:
            disasm.append('[%s] JZ\t%s' % (address, args))
        elif opcode == 8:
            disasm.append('[%s] JGE\t%s' % (address, args))
        elif opcode == 9:
            if args == 1:
                disasm.append('[%s] LOAD_ACC_KEY\t' % address)
            elif args == 2:
                disasm.append('[%s] PRINT_ACC' % address)
            else:
                disasm.append('[%s] UNKNOWN_INSTR\t%s' % (address, instr))
        elif opcode == 0:
            disasm.append('[%s] HALT' % address)
        else:
            disasm.append('[%s] UNKNOWN_INSTR\t%s' % (address, instr))

        address += 1

    return disasm

code=[901,340,505,140,305,461,901,722,340,539,723,241,339,
      540,238,142,342,901,722,901,722,606,000,542,243,243,
      244,340,830,653,553,140,145,353,546,140,653,000,17,
      10,000,001,000,400,60,459,41,22,76,76,75,75,37,417,
      560,140,145,360,547,140,417,567,140,145,367,548,140,
      417,574,140,145,374,549,140,417,581,140,145,381,550,
      140,417,588,140,145,388,551,140,417,595,140,145,395,
      552,140,417,423]

print '\n'.join(disassemble(code))

And this is the output of the disassembler, along with a very few comments I have added:

[0] LOAD_ACC_KEY
[1] STOR_ACC	40
[2] LOAD_ACC	5
[3] ADD_ACC	40
[4] STOR_ACC	5
[5] UNKNOWN_INSTR	461
[6] LOAD_ACC_KEY
[7] JZ	22
[8] STOR_ACC	40
[9] LOAD_ACC	39
[10] JZ	23
[11] SUB_ACC	41
[12] STOR_ACC	39
[13] LOAD_ACC	40
[14] SUB_ACC	38
[15] ADD_ACC	42		// key_sum
[16] STOR_ACC	42		// key_sum
[17] LOAD_ACC_KEY
[18] JZ	22
[19] LOAD_ACC_KEY
[20] JZ	22
[21] JMP	6
[22] HALT
[23] LOAD_ACC	42		// key_sum
[24] SUB_ACC	43		// key_sum -= 400
[25] SUB_ACC	43		// key_sum -= 400
[26] SUB_ACC	44		// key_sum -= 60
[27] STOR_ACC	40		// save key_sum
[28] JGE	30
[29] JMP	53
[30] LOAD_ACC	53
[31] ADD_ACC	40
[32] ADD_ACC	45
[33] STOR_ACC	53
[34] LOAD_ACC	46
[35] ADD_ACC	40
[36] JMP	53
[37] HALT
[38] HALT
[39] HALT
[40] HALT
[41] HALT
[42] HALT
[43] UNKNOWN_INSTR	400
[44] HALT
[45] UNKNOWN_INSTR	459
[46] HALT
[47] HALT
[48] HALT
[49] HALT
[50] HALT
[51] HALT
[52] HALT
[53] UNKNOWN_INSTR	417
[54] LOAD_ACC	60
[55] ADD_ACC	40
[56] ADD_ACC	45
[57] STOR_ACC	60
[58] LOAD_ACC	47
[59] ADD_ACC	40
[60] UNKNOWN_INSTR	417
[61] LOAD_ACC	67
[62] ADD_ACC	40
[63] ADD_ACC	45
[64] STOR_ACC	67
[65] LOAD_ACC	48
[66] ADD_ACC	40
[67] UNKNOWN_INSTR	417
[68] LOAD_ACC	74
[69] ADD_ACC	40
[70] ADD_ACC	45
[71] STOR_ACC	74
[72] LOAD_ACC	49
[73] ADD_ACC	40
[74] UNKNOWN_INSTR	417
[75] LOAD_ACC	81
[76] ADD_ACC	40
[77] ADD_ACC	45
[78] STOR_ACC	81
[79] LOAD_ACC	50
[80] ADD_ACC	40
[81] UNKNOWN_INSTR	417
[82] LOAD_ACC	88
[83] ADD_ACC	40
[84] ADD_ACC	45
[85] STOR_ACC	88
[86] LOAD_ACC	51
[87] ADD_ACC	40
[88] UNKNOWN_INSTR	417
[89] LOAD_ACC	95
[90] ADD_ACC	40
[91] ADD_ACC	45
[92] STOR_ACC	95
[93] LOAD_ACC	52
[94] ADD_ACC	40
[95] UNKNOWN_INSTR	417
[96] UNKNOWN_INSTR	423

I have translated that disassembled code to a pseudo-C representation:

code[5] = key[0] + 461;
int key_index = 1;
exec_automodified_code5();

int counter = 10;
int key_sum = 0;

//ab..e..h..k..n..q..t..w..z..3.. = 871
//aq..e..h..k..n..q..t..w..z..3..6 = 902 => flag: C0ffee?

while(1){
	if (!key[key_index]){
		halt();
	}

	if (!counter){
		break;
	}

	counter--;
	key_sum += key[key_index] - 17;

	//These two chars from the key are just ignored in every loop.
	//The program just checks that they are not null.
	if ((!key[key_index + 1]) || (!key[key_index + 2])){
		halt();
	}
	key_index += 3;

}

key_sum -= 860;

if (key_sum >= 0){
	code[53] = key_sum + 417 + 459;
}

The program reads the first character from the entered key, adds 461 to it and stores it at code[5], and then executes code[5]. So by entering an ‘a’ (ordinal 97), we get 461+97=558 stored at code[5]. It gets executed as a LOAD_ACC 58 instruction, which loads a value into the accumulator from code[58], which, in turn, is a valid memory address. And since the next instruction at code[6] is a LOAD_ACC_FROM_KEY which will immediately overwrite the value of the accumulator, the instruction generated from the first character of our key + 461 is pretty harmless.

After that, the program loops 10 times; for every time the loop is taken, it takes the value of a char from our key, substracts 17 from it, and adds it to a variable; then it just checks that the following 2 chars are not null, but it does nothing else with these two chars.

After looping 10 times, the program substracts 860 from the variable that is holding the sum of [every third char – 17]; if the result is >=0, it will add 417 + 459 to the result of the substraction, and it will store the result of this addition to code[53].
So once again our input is used to generate code that will be executed; since the “9 02” (OUTPUT_ACC) instruction is not present in the original code and it should somehow be present in order to spit the flag for this challenge, I suspected that, as a first step, I should generate a “9 02” instruction in order to be stored and executed at code[53].

When providing “abcdefghijklmnopqrstuvwxyz01234567890” as the input key I got the following chars added up:

"b", "e", "h", "k", "n", "q", "t", "w", "z", 3"

Let’s do the addition:

>>> sum([ord(c)-17 for c in 'behknqtwz3'])
871
>>> 871 - 860 + 417 + 459
887

So by replacing the “b” with a “q” (that is, “b” + 15) we get the expected 902 value:

>>> sum([ord(c)-17 for c in 'qehknqtwz3'])
886
>>> 886 - 860 + 417 + 459
902

So, by providing as the input key the following string: “aq..e..h..k..n..q..t..w..z..3..6” (note that I had to add “..6” -but other alphanumeric chars seem to work as well- at the end of the analyzed chars in order for the program to show the flag; the program seems to consume 3 more characters after the loop) it shows the flag for this challenge: C0ffee?.

Hope you liked this (long) write up; feel free to leave a comment! 🙂

Advertisements

2 thoughts on “Nullcon HackIM CTF 2013 – Reverse Engineering 300 Write up

  1. Pingback: Nullcon HackIM CTF 2013 – Reverse Engineering 300 Write up | Ragnarok Connection

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s