eVMoji - localo

Category: Reverse Engineering
Difficulty: Hard
Author: 0x4d5a

Description

EMOJI HYPE 🔥💯

Summery

A virtual machine was given that can run code created in a custom instruction set based on emoji. If you have ever written an emulator or a similar virtual machine, you get known to the structure of the code quite easily. code.bin is a simple program that asks for a password as input and prints the flag as output if the password is correct.

Solution

I had multiple ideas how the challenge could be solved, one could write a disassembler and work through that, or use symbolic execution with tools like angr. But I don't know angr! (even though it would be a good opportunity to learn it) Maybe another day/challenge. And I am lazy. Therefore writing a disassembler and doing the hard work to go through the disassembly was also not what I wanted. This is a ctf challenge, therefore I wanted a quick and maybe not so clean solution, that just works.

I decided to write a tracer. A tracer has the advantage that we get runtime information instead of just static instructions. Using the great decompiler from ghidra and some analysis based renaming/retyping, the whole VM could be decompiled using the to C code export function of ghidra. The output has still to be cleaned up, but after some minutes the C code could be compiled and the generated program was able to interpret the provided code.bin. After that I made some patches to the VM to debug the code, printf, I was able to create some traces.

I won't go too much into the internals of the vm, but it has some 1kB rwm, 1kB stack, 64kB code and some sort of register. It has 11 opcodes and implementing, or, xor, lsb, write to stdout, read from stdin, dup, shr,exit, test and jeq, push from code and 2x push from rwm (int and ptr?).

code.bin reads 27 chars from stdin, performs xor operations on the first 23 chars of the input or it together and checks if the result matches 0x00. Using just null bytes as the input, the first part of the flag is quite obvious. As we can ignore the xor and use the or operands.
Here is the trace of xor and or with 27x A as input.

read: 27
41 ^ f2 = b3
9c ^ b3 = 2f
2f | 0 = 2f 
41 ^ ea = ab
d9 ^ ab = 72
72 | 2f = 7f 
[...]
41 ^ f5 = b4
9b ^ b4 = 2f
2f | 7f = 7f 
41 ^ a2 = e3
fd ^ e3 = 1e
1e | 7f = 7f 
0 == 7f

And the trace with just or and null bytes as input.

read: 27
6e | 0 = 6e 
33 | 6e = 7f 
77 | 7f = 7f 
5f | 7f = 7f 
61 | 7f = 7f 
67 | 7f = 7f 
33 | 7f = 7f 
5f | 7f = 7f 
76 | 7f = 7f 
31 | 7f = 7f 
72 | 7f = 7f 
74 | 7f = 7f 
75 | 7f = 7f 
34 | 7f = 7f 
6c | 7f = 7f 
69 | 7f = 7f 
7a | 7f = 7f 
34 | 7f = 7f 
74 | 7f = 7f 
31 | 7f = 7f 
6f | 7f = 7f 
6e | 7f = 7f 
5f | 7f = 7f 
0 == 7f

The first operand of the or is the char for the flag:

n3w_ag3_v1rtu4liz4t1on_

Using this as the input for the program we get:
Gotta go cyclic ♻️
We are missing 4 bytes of the flag.
The trace shows this:

ffffffff >> 1 = 7fffffff
edb88320 ^ 7fffffff = 92477cdf
0 == 0
0 >> 1 = 0
0 == 1
92477cdf >> 1 = 4923be6f
edb88320 ^ 4923be6f = a49b3d4f
0 == 0
0 >> 2 = 0
0 == 1
a49b3d4f >> 1 = 524d9ea7
edb88320 ^ 524d9ea7 = bff51d87
[...]
cc0e8f0e >> 1 = 66074787
0 >> 31 = 0
0 == 1
66074787 >> 1 = 3303a3c3
edb88320 ^ 3303a3c3 = debb20e3
0 == 0
f40e845e ^ debb20e3 = 2ab5a4bd
0 == 2ab5a4bd

Some bit shifts, and xor operations. Using the trace operations and the input and output I wrote the algorithm in python to get a better understanding.

o = 0xFFFFFFFF
p = 0
while p<32:
    if (n>>p) & 1 != o & 1:
        o = 0xedb88320 ^ (o>>1)
    else:
        o = o>>1
    p+=1
if o ^ 0xf40e845e == 0:
    print("[*] success")
else:
    print("[*] fail")

I was not able to work out a way to reverse that function, but 4 bytes is brute-force-able and the limited charset should make it feasible for a crude script in python. I wrote a script that runs the algorithm for the lower-case ascii and digits range and the chars _, \n,\x00 but without a result. After some rubber ducky debugging I did what you should always do if you are stuck, google the constants, in this case 0xedb88320 and google says crc32, but the output of the algorithm does not match any output of online crc32 generators. But after taking a look at the source code of a crc32 code for C I realized that the output is just negated. But in the program it is not. I just have to negate 0xf40e845e to 0x0bf17ba1 and find 4 byte input for that crc32. Now I can use highly optimized software to brute-force the input. I used hashcat.

$ hashcat -m 11500 -a 3 --force 0bf17ba1:00000000 ?b?b?b?b
[...]
0bf17ba1:00000000:l0l?
[...]

The flag includes a question mark.

$ python -c "print('n3w_ag3_v1rtu4liz4t1on_l0l?')" | ./eVMoji code.bin
Welcome to eVMoji 😎
🤝 me the 🏳🏳️
Thats the flag: CSCG{n3w_ag3_v1rtu4liz4t1on_l0l?}

Code

eVMoji.c

#include "eVMoji.h"

context con;

ulong read_operands(char *param_1)

{
  undefined8 uVar1;
  uint local_c;
  
  if (*param_1 < '\0') {
    local_c = 2;
    while ((int)local_c < 5) {
      if ((0x80 >> ((byte)local_c & 0x1f) & (int)*param_1) == 0) {
        return (ulong)local_c;
      }
      local_c = local_c + 1;
    }
    uVar1 = 0xffffffff;
  }
  else {
    uVar1 = 1;
  }
  return uVar1;
}



ulong read_opcode(char *param_1)

{
  uint uVar1;
  uint local_18;
  uint local_14;
  
  uVar1 = read_operands(param_1);
  local_18 = 0;
  local_14 = 0;
  while (local_14 < uVar1) {
    local_18 = local_18 |
               0xff << ((byte)(local_14 << 3) & 0x1f) &
               (int)param_1[(int)local_14] << ((byte)(local_14 << 3) & 0x1f);
    local_14 = local_14 + 1;
  }
  return (ulong)local_18;
}



ulong FUN_00100a26(char *code,char *param_2)

{
  char cVar1;
  int iVar2;
  int iVar3;
  
  cVar1 = read_opcode(code);
  *param_2 = cVar1 + -0x30;
  iVar2 = read_operands(code + 1);
  iVar3 = read_operands(code + (iVar2 + 1));
  return (ulong)(uint)(iVar2 + 1 + iVar3);
}



ulong read_registers(char *code,uint *param_2)

{
  char cVar1;
  double dVar2;
  char local_1a;
  char local_19;
  uint local_18;
  int local_14;
  long local_10;
  
  *param_2 = 0;
  local_18 = 0;
  local_14 = 0;
  while (local_14 < 3) {
    cVar1 = FUN_00100a26(code + (int)local_18,&local_1a);
    local_18 = local_18 + (int)cVar1;
    cVar1 = FUN_00100a26(code + (int)local_18,&local_19);
    local_18 = local_18 + (int)cVar1;
    dVar2 = pow((double)(int)local_19,(double)(int)local_1a);
    *param_2 = (uint)(long)((double)(ulong)*param_2 + dVar2);
    local_14 = local_14 + 1;
  }
  return (ulong)local_18;
}



ulong pop(context *con)

{
  con->sp = con->sp - 1;
  return (ulong)*(uint *)(con->stack + (long)(int)con->sp * 4);
}



void vm_main(context *con)

{
  char cVar1;
  char *pcVar2;
  int op_length;
  int iVar3;
  uint uVar4;
  uint uVar5;
  uint uVar6;
  uint local_2c;
  uint local_28;
  uint opcode;
  int should_log;
  should_log=0;
  local_2c = 0;
  local_28 = 0;
LAB_00100bf0:
  opcode = read_opcode(con->code + (int)con->pc);
  op_length = read_operands(con->code + (int)con->pc);
  con->pc = op_length + con->pc;
  if (opcode == 0x80929ff0) {
                    // WARNING: Subroutine does not return
    exit(-1);
  }
  if (opcode < 0x80929ff1) {
    if (opcode == 0x959ee2) {
      local_2c = pop(con);
      //printf("lsb %x = %x\n",local_2c,local_2c & 1);
      //printf("lsb %x = %x\n",local_2c,local_2c & 1);
      local_2c = local_2c & 1;
      uVar5 = con->sp;
      con->sp = uVar5 + 1;
      *(uint *)(con->stack + (long)(int)uVar5 * 4) = local_2c;
      goto LAB_00100bf0;
    }
    if (opcode < 0x959ee3) {
      if (opcode == 0x859ce2) {
        uVar6 = pop(con);
        uVar4 = pop(con);
        uVar5 = con->sp;
        con->sp = uVar5 + 1;
        if(should_log || 1){
            //printf("%x | %x = %x \n",uVar6 , uVar4,uVar6 | uVar4);
            printf("%c",uVar6);
        }
        *(uint *)(con->stack + (long)(int)uVar5 * 4) = uVar6 | uVar4;
        goto LAB_00100bf0;
      }
      if (opcode == 0x8f9ce2) {
        uVar5 = pop(con);
        pcVar2 = con->mem;
        uVar6 = pop(con);
        //write(1,pcVar2 + uVar6,(ulong)uVar5);
        op_length = read_operands(con->code + (int)con->pc);
        con->pc = op_length + con->pc;
        goto LAB_00100bf0;
      }
    }
    else {
      if (opcode == 0xa19ee2) {
        op_length = read_operands(con->code + (int)con->pc);
        con->pc = op_length + con->pc;
        op_length = read_registers(con->code + (int)con->pc,&local_2c);
        con->pc = op_length + con->pc;
        local_28 = pop(con);
        if(should_log){
          printf("%x >> %d = %x\n", local_28,(byte)local_2c & 0x1f,local_28 >> ((byte)local_2c & 0x1f));
        }
        local_28 = local_28 >> ((byte)local_2c & 0x1f);
        uVar5 = con->sp;
        con->sp = uVar5 + 1;
        *(uint *)(con->stack + (long)(int)uVar5 * 4) = local_28;
        goto LAB_00100bf0;
      }
      if (opcode == 0xbc80e2) {
        op_length = read_operands(con->code + (int)con->pc);
        con->pc = op_length + con->pc;
        local_2c = pop(con);
        if(should_log){
            //printf("dup %x\n",local_2c);
        }
        uVar5 = con->sp;
        con->sp = uVar5 + 1;
        *(uint *)(con->stack + (long)(int)uVar5 * 4) = local_2c;
        uVar5 = con->sp;
        con->sp = uVar5 + 1;
        *(uint *)(con->stack + (long)(int)uVar5 * 4) = local_2c;
        goto LAB_00100bf0;
      }
    }
  }
  else {
    if (opcode == 0x96939ff0) {
      uVar5 = pop(con);
      pcVar2 = con->mem;
      uVar6 = pop(con);
      printf("read: %d\n",uVar5);
      read(0,pcVar2 + uVar6,(ulong)uVar5);
      goto LAB_00100bf0;
    }
    if (opcode < 0x96939ff1) {
      if (opcode == 0x80949ff0) {
        uVar6 = pop(con);
        uVar4 = pop(con);
        uVar5 = con->sp;
        if(should_log){
            printf("%x ^ %x = %x\n", uVar6 , uVar4, uVar6 ^ uVar4);
        }
        con->sp = uVar5 + 1;
        *(uint *)(con->stack + (long)(int)uVar5 * 4) = uVar6 ^ uVar4;
      }
      else {
        if (opcode != 0x94a49ff0) goto LAB_00101147;
        op_length = read_registers(con->code + (int)con->pc,&local_2c);
        con->pc = op_length + con->pc;
        op_length = pop(con);
        iVar3 = pop(con);
        should_log=1;

        if(should_log){
            printf("%x == %x\n",op_length,iVar3);
            //printf("%x\n",op_length==iVar3);
        }
        if (op_length == iVar3) {
          con->pc = local_2c + con->pc;
        }
      }
      goto LAB_00100bf0;
    }
    if (opcode == 0xaa929ff0) {
      op_length = read_registers(con->code + (int)con->pc,&local_2c);
      con->pc = op_length + con->pc;
      uVar5 = con->sp;
      con->sp = uVar5 + 1;
      //printf("copy to stack: %x\n", local_2c);
      *(uint *)(con->stack + (long)(int)uVar5 * 4) = local_2c;
      goto LAB_00100bf0;
    }
    if (opcode == 0xbea69ff0) {
      op_length = read_registers(con->code + (int)con->pc,&local_2c);
      con->pc = op_length + con->pc;
      cVar1 = con->mem[local_2c];
      uVar5 = con->sp;
      con->sp = uVar5 + 1;
      if(should_log){
        //printf("copy to stack: %x\n",cVar1);
      }
      *(int *)(con->stack + (long)(int)uVar5 * 4) = (int)cVar1;
      goto LAB_00100bf0;
    }
    if (opcode == 0xa08c9ff0) {
      op_length = read_registers(con->code + (int)con->pc,&local_2c);
      con->pc = op_length + con->pc;
      uVar5 = con->sp;
      con->sp = uVar5 + 1;
      if(should_log){
        //printf("copy to stack: %x\n", *(undefined4 *)(con->mem + local_2c));
      }
      *(undefined4 *)(con->stack + (long)(int)uVar5 * 4) = *(undefined4 *)(con->mem + local_2c);
      goto LAB_00100bf0;
    }
  }
LAB_00101147:
  printf("Unknown opcode: %x",(ulong)opcode);
  goto LAB_00100bf0;
}



int main(int argc,char **argv)

{
  FILE *__stream;
  
  if (argc < 2) {
    puts("Usage: ./eVMoji <code.bin>");
  }
  con.pc = 0;
  con.sp = 0;
  con.mem = (char *)malloc(0x400);
  con.stack = (char *)malloc(0x400);
  con.code = (char *)malloc(0x10000);
  __stream = fopen(argv[1],"rb");
  if (__stream == (FILE *)0x0) {
    printf("File not found: %s",argv[1]);
  }
  fread(con.mem,0x200,1,__stream);
  fread(con.code,0x10000,1,__stream);
  fclose(__stream);
  vm_main(&con);
  return 0;
}


eVMoji.h

#include <stdio.h>
#include <math.h>
#include <unistd.h>
#include <stdlib.h>

typedef unsigned char   undefined;

typedef unsigned char    byte;
typedef unsigned char    dwfenc;
typedef unsigned int    dword;
typedef unsigned long    qword;
typedef unsigned int    uint;
typedef unsigned long    ulong;
typedef unsigned char    undefined1;
typedef unsigned int    undefined4;
typedef unsigned long    undefined8;
typedef unsigned short    ushort;
typedef unsigned short    word;

typedef ulong uint64_t;

typedef struct context context;

struct context {
    uint pc;
    undefined field_0x4;
    undefined field_0x5;
    undefined field_0x6;
    undefined field_0x7;
    char * mem;
    char * stack;
    uint sp;
    undefined field_0x1c;
    undefined field_0x1d;
    undefined field_0x1e;
    undefined field_0x1f;
    char * code;
};
ulong read_operands(char *param_1);
ulong read_opcode(char *param_1);
ulong FUN_00100a26(char *code,char *param_2);
ulong read_registers(char *code,uint *param_2);
ulong pop(context *con);
void vm_main(context *con);
int main(int param_1,char ** param_2);

Mitigation

In my opinion it is quite hard to say mitigation for a re challenge, because it kind of always results in some kind of obfuscation, but for password checking stuff you can always use hashing and decryption of the program using the original input. But that would result in a bad ctf challenge, I guess.

Flag

CSCG{n3w_ag3_v1rtu4liz4t1on_l0l?}