Write-up for CODEGATE 2022 Finals Reversing challenge VM

_vm.md

CODEGATE 2022 Finals VM

Analysis

We are given a virtual machine binary called run, and a custom binary for it called VM. It has 16 registers and a flat memory. Below is the opcodes of this VM.

Then, we should disassemble the given program to see what's going on. disasm.py disassembles the custom binary VM into disassembly.S. Take a look at it.

Goal

The binary VM, gets some itput, checks it, and prints out Correct! if it was correct. The flag is the correct itput itself.

Solution

Reversing the entire check routine would be a big pain. Therefore, we should try brute-forcing the flag by checking the program status.

0059: eq r3 == r1 + 0h ? ZF
005a: jne if(!ZF) ip += r0 + 6h --> 0x61(Fail)
005b: add r4 += r0 + 2h
005c: add r6 += r0 + 2h
005d: eq r4 == r0 + 3ch ? ZF
005e: jne if(!ZF) ip += r0 + -25h --> 0x40(Loop Top)
005f: mov r1 = r0 + 1h

Here, r4 is used to index mem[0xfac] which holds the user input. As you can see, we can suspect that there is a loop which evaluates the flag on halfword basis. To check whether each halfword is correct or not, we can check the register states. Please take a look at solver.py for more detailed solution.

disasm.py

import struct



def disasm(asm:bytes) -> str:
    length = int.from_bytes(asm[:4], 'little')
    assert length == len(asm) - 4
    disasm = list()
    for ip in range(length // 8):
        inst = asm[4 + ip * 8: 4 + (ip + 1) * 8]
        op, Rd, Rm, _, imm = struct.unpack("<BBBBi", inst)
        match op:
            case 0:
                disasm += [f"mov r{Rd} = r{Rm} + {imm:x}h"]
            case 1:
                disasm += [f"st mem[r{Rm} + {imm:x}h] = r{Rd}"]
            case 2:
                disasm += [f"ld r{Rd} = mem[r{Rm} + {imm:x}h]"]
            case 3:
                disasm += [f"add r{Rd} += r{Rm} + {imm:x}h"]
            case 4:
                disasm += [f"sub r{Rd} -= r{Rm} + {imm:x}h"]
            case 5:
                disasm += [f"xor r{Rd} ^= r{Rm} + {imm:x}h"]
            case 6:
                disasm += [f"and r{Rd} &= r{Rm} + {imm:x}h"]
            case 7:
                disasm += [f"eq r{Rd} == r{Rm} + {imm:x}h ? ZF"]
            case 8:
                disasm += [f"je if(ZF) ip += r{Rm}+ {imm:x}h"]
            case 9:
                disasm += [f"jne if(!ZF) ip += r{Rm} + {imm:x}h"]
            case 10:
                disasm += [f"jmp ip += r{Rm} + {imm:x}h"]
            case 11:
                disasm += [f"lsh r{Rd} <<= r{Rm} + {imm:x}h"]
            case 12:
                disasm += [f"rsh r{Rd} >>= r{Rm} + {imm:x}h"]
            case 13:
                if imm == 0:
                    disasm += [f"read"]
                elif imm == 1:
                    disasm += [f"write"]
                else:
                    disasm += [f"bad"]
            case 14:
                disasm += [f"hlt"]

    return disasm

if __name__ == '__main__':
    with open("VM", "rb") as f:
        prog = f.read()
        disas = disasm(prog)
    
    for i, j in enumerate(disas):
        print(f"{i:04x}: {j}")

disassembly.S

0000: xor r1 ^= r1 + 0h 
0001: mov r3 = r0 + fh
0002: mov r2 = r7 + -54h 
0003: mov r5 = r2 + 0h
0004: mov r8 = r0 + 55504e49h //INPU
0005: st mem[r7 + -80h] = r8
0006: mov r8 = r0 + 203a54h  //T: 
0007: st mem[r7 + -7ch] = r8
0008: st mem[r5 + 0h] = r1 
0009: add r5 += r0 + 4h
000a: sub r3 -= r0 + 1h
000b: eq r3 == r0 + 0h ? ZF
000c: jne if(!ZF) ip += r0 + -5h
000d: mov r1 = r7 + -80h
000e: mov r4 = r0 + 7h
000f: mov r6 = r1 + 0h
0010: mov r5 = r0 + 1h
0011: write
0012: mov r4 = r0 + 3ch
0013: mov r6 = r2 + 0h  
0014: mov r5 = r0 + 0h 
0015: read
0016: mov r6 = r7 + -54h 
0017: add r6 += r1 + 0h
0018: sub r6 -= r0 + 1h 
0019: st mem[r6 + 0h] = r0 
001a: xor r4 ^= r4 + 0h 
001b: mov r8 = r0 + 42ca32dah 
001c: st mem[r7 + -94h] = r8
001d: mov r8 = r0 + 7f09207fh
001e: st mem[r7 + -90h] = r8
001f: mov r8 = r0 + 7b291908h
0020: st mem[r7 + -8ch] = r8
0021: mov r8 = r0 + -1fef28bh
0022: st mem[r7 + -88h] = r8
0023: mov r8 = r0 + -6d5114e1h
0024: st mem[r7 + -84h] = r8
0025: mov r8 = r0 + -6aa8a2a5h
0026: st mem[r7 + -80h] = r8
0027: mov r8 = r0 + 4d4fe62h
0028: st mem[r7 + -7ch] = r8
0029: mov r8 = r0 + -1fe5784h
002a: st mem[r7 + -78h] = r8
002b: mov r8 = r0 + -87ed21fh
002c: st mem[r7 + -74h] = r8
002d: mov r8 = r0 + -427548fbh
002e: st mem[r7 + -70h] = r8
002f: mov r8 = r0 + 42cadd6dh
0030: st mem[r7 + -6ch] = r8
0031: mov r8 = r0 + 12fb883eh
0032: st mem[r7 + -68h] = r8
0033: mov r8 = r0 + 343c8ebbh
0034: st mem[r7 + -64h] = r8
0035: mov r8 = r0 + 1d0fa7c5h
0036: st mem[r7 + -60h] = r8
0037: mov r8 = r0 + 1d0f1d0fh
0038: st mem[r7 + -5ch] = r8
0039: mov r6 = r7 + -94h 
003a: mov r5 = r2 + 0h 
003b: add r5 += r4 + 0h 
003c: xor r3 ^= r3 + 0h 

003d: mov r1 = r0 + ffffh 
003e: st mem[r7 + -9ch] = r5 
003f: mov r8 = r0 + 8h 
0040: st mem[r7 + -98h] = r8 
0041: ld r5 = mem[r7 + -9ch] 
0042: mov r8 = r5 + 0h
0043: add r8 += r3 + 0h 
0044: ld r5 = mem[r8 + 0h]
0045: and r5 &= r0 + ffh 
0046: lsh r5 <<= r0 + 8h  
0047: xor r1 ^= r5 + 0h
0048: mov r8 = r1 + 0h
0049: add r1 += r1 + 0h
004a: and r1 &= r0 + ffffh
004b: rsh r8 >>= r0 + fh
004c: eq r8 == r0 + 1h ? ZF
004d: jne if(!ZF) ip += r0 + 1h --> 0x4f
004e: xor r1 ^= r0 + 1021h

004f: ld r5 = mem[r7 + -98h]
0050: sub r5 -= r0 + 1h
0051: st mem[r7 + -98h] = r5
0052: eq r5 == r0 + 0h ? ZF
0053: jne if(!ZF) ip += r0 + -ch --> 0x48

0054: add r3 += r0 + 1h
0055: eq r3 == r0 + 2h ? ZF
0056: jne if(!ZF) ip += r0 + -18h --> 0x3f
0057: ld r3 = mem[r6 + 0h]
0058: and r3 &= r0 + ffffh
0059: eq r3 == r1 + 0h ? ZF
005a: jne if(!ZF) ip += r0 + 6h --> 0x61(Fail)
005b: add r4 += r0 + 2h
005c: add r6 += r0 + 2h
005d: eq r4 == r0 + 3ch ? ZF
005e: jne if(!ZF) ip += r0 + -25h --> 0x40
005f: mov r1 = r0 + 1h
0060: jmp ip += r0 + 1h //Success
0061: xor r1 ^= r1 + 0h //Fail
0062: hlt

solver.py

import gdb
import string
bp = gdb.Breakpoint("*0x00005555555551e1")
bp.condition = "*0x5555555580c4==0x59"

flag = ""

def blocks():
    for i in "_"+string.ascii_letters:
        for j in "_"+string.ascii_letters:
            yield i+j


for i in range(len(flag), 60, 2):
    for piece in blocks():
        with open("triads", "wt") as f:
            f.write(flag + piece + "\n")
        gdb.execute("ignore 1 {}".format(i//2))
        gdb.execute("run VM < triads")
        trial = gdb.parse_and_eval("*(0x5555555580a0+0x4)")
        refer = gdb.parse_and_eval("*(0x5555555580a0+0xc)")
        if trial == refer:
            flag += piece
            print("SET:", flag)
            break
        else:
            print("FAIL:", flag + piece, hex(trial), "!=", hex(refer))