VM Opcode for Reverse Engineering: Bytecode to Constraints

VM 기반 문제는 보통 bytecode + dispatcher로 구성된다. 핵심은 opcode 의미를 복원하고, bytecode를 사람이 읽을 수 있는 형태로 끌어내는 것이다.

1. VM Skeleton

아래처럼 스택 기반 VM이 많다. 구조체 안에 pc, sp, flag만 있어도 충분하다.

1
typedef struct {
2
    const uint8_t *code;
3
    const uint8_t *input;
4
    uint32_t pc;
5
    uint8_t sp;
6
    uint8_t flag;
7
    uint8_t stack[64];
8
} VM;
9

10
static uint8_t rol8(uint8_t v, unsigned r) {
11
    return (uint8_t)((v << r) | (v >> (8 - r)));
12
}
13

14
static int vm_run(VM *vm) {
15
    for (;;) {
16
        uint8_t op = vm->code[vm->pc++];
17
        switch (op) {
18
        case 0x01: { // PUSH imm8
19
            vm->stack[vm->sp++] = vm->code[vm->pc++];
20
            break;
21
        }
22
        case 0x02: { // LOAD idx
23
            uint8_t idx = vm->code[vm->pc++];
24
            vm->stack[vm->sp++] = vm->input[idx];
25
            break;
26
        }
27
        case 0x10: { // XOR
28
            uint8_t b = vm->stack[--vm->sp];
29
            uint8_t a = vm->stack[vm->sp - 1];
30
            vm->stack[vm->sp - 1] = a ^ b;
31
            break;
32
        }
33
        case 0x11: { // ADD
34
            uint8_t b = vm->stack[--vm->sp];
35
            uint8_t a = vm->stack[vm->sp - 1];
36
            vm->stack[vm->sp - 1] = (uint8_t)(a + b);
37
            break;
38
        }
39
        case 0x12: { // ROL imm
40
            uint8_t r = vm->code[vm->pc++];
41
            vm->stack[vm->sp - 1] = rol8(vm->stack[vm->sp - 1], r);
42
            break;
43
        }
44
        case 0x20: { // CMP imm
45
            uint8_t v = vm->stack[--vm->sp];
46
            uint8_t imm = vm->code[vm->pc++];
47
            vm->flag = (v == imm);
48
            break;
49
        }
50
        case 0x30: { // JNZ rel8 (flag == 0이면 jump)
51
            int8_t off = (int8_t)vm->code[vm->pc++];
52
            if (!vm->flag) {
53
                vm->pc = (uint32_t)(vm->pc + off);
54
            }
55
            break;
56
        }
57
        case 0xFF: { // HALT imm
58
            uint8_t ret = vm->code[vm->pc++];
59
            return ret;
60
        }
61
        default:
62
            return 0;
63
        }
64
    }
65
}

리버서 입장에서는 아래를 먼저 체크한다.

pc가 opcode/operand를 읽은 뒤 증가하는지 여부
sp가 push/pop 이전인지 이후인지
flag의 의미가 true/false로 그대로 쓰이는지, 반전되는지
JNZ 오프셋이 부호 있는 상대 이동인지, 절대 이동인지

Opcode Table

스택 효과까지 같이 보면 식을 만들기가 쉬워진다. S를 스택이라고 하면,

Opcode	Mnemonic	Stack Effect	Desc
`0x01`	`PUSH imm8`	`S -> S, imm`	즉시값 push
`0x02`	`LOAD idx`	`S -> S, input[idx]`	입력 push
`0x10`	`XOR`	`S, a, b -> S, (a ^ b)`	XOR
`0x11`	`ADD`	`S, a, b -> S, (a + b)`	mod 256
`0x12`	`ROL imm`	`S, a -> S, rol8(a, imm)`	rotate
`0x20`	`CMP imm`	`S, a -> S`	flag = (a == imm)
`0x30`	`JNZ rel8`	`S -> S`	flag == 0이면 PC += off
`0xFF`	`HALT imm`	`S -> S`	즉시값 반환

스택 효과를 먼저 정리하면 식 세우기가 훨씬 깔끔하다. 특히 CMP가 값을 pop하는지, 남겨두는지 파악을 해야한다.

Dispatcher

바이너리에서 VM을 찾을 때는 다음 순서로 좁혀 들어간다.

opcode fetch 패턴: op = code[pc++] 같은 형태가 반복되는 루프를 찾자
switch/jumptable: switch (op) 또는 jmp [table + op*8] 같은 분기 테이블 체크
operand fetch: 특정 case에서 code[pc++]를 추가로 읽는지 확인한다. 이게 곧 opcode 길이.
stack 업데이트: sp++, --sp의 위치를 보고 push/pop 고정
flag 사용: CMP나 TEST 결과가 JZ/JNZ로 이어지는지 추적

VM이 난독화되어 있으면 opcode를 XOR/ADD로 디코딩하거나, 바이트코드를 런타임에 복호화한다. 이런 경우는 dispatcher 이전에 작은 복호화 루틴이 붙는 경우가 많다.

Bytecode 추출 + 디스어셈블

바이트코드를 덤프했으면 디스어셈블을 만들어야 한다. opcode 길이만 알면 간단히 파싱 가능하다.

1
op_info = {
2
    0x01: ("PUSH", 1),
3
    0x02: ("LOAD", 1),
4
    0x10: ("XOR", 0),
5
    0x11: ("ADD", 0),
6
    0x12: ("ROL", 1),
7
    0x20: ("CMP", 1),
8
    0x30: ("JNZ", 1),
9
    0xFF: ("HALT", 1),
10
}
11

12
def disasm(code):
13
    pc = 0
14
    out = []
15
    while pc < len(code):
16
        op = code[pc]
17
        name, imm_len = op_info.get(op, ("DB", 0))
18
        if name == "DB":
19
            out.append(f"{pc:02X}: DB 0x{op:02X}")
20
            pc += 1
21
            continue
22
        imm = None
23
        if imm_len:
24
            imm = code[pc + 1]
25
        if name == "JNZ":
26
            off = imm if imm < 0x80 else imm - 0x100
27
            tgt = (pc + 2 + off) & 0xFFFFFFFF
28
            out.append(f"{pc:02X}: JNZ {off:+#x} ; -> {tgt:02X}")
29
        elif imm_len:
30
            out.append(f"{pc:02X}: {name} 0x{imm:02X}")
31
        else:
32
            out.append(f"{pc:02X}: {name}")
33
        pc += 1 + imm_len
34
    return out

JNZ rel8는 pc가 operand를 읽은 뒤를 기준으로 상대 이동한다. 이 기준이 틀리면 분기 타겟이 전부 어긋난다.

\text{target} = \text{pc}_{after} + \text{sign\_extend}(off)

2. Bytecode Example

해당 bytecode는 8바이트 입력을 검증한다. 고정 패턴이 반복되므로 디스어셈블만 제대로 되면 바로 식이 나온다.

1
static const uint8_t program[] = {
2
    0x02, 0x00, 0x01, 0x13, 0x10, 0x01, 0x05, 0x11, 0x12, 0x01, 0x20, 0xEE, 0x30, 0x64,
3
    0x02, 0x01, 0x01, 0x57, 0x10, 0x01, 0x11, 0x11, 0x12, 0x01, 0x20, 0x94, 0x30, 0x56,
4
    0x02, 0x02, 0x01, 0x9B, 0x10, 0x01, 0x1F, 0x11, 0x12, 0x01, 0x20, 0x3C, 0x30, 0x48,
5
    0x02, 0x03, 0x01, 0xDF, 0x10, 0x01, 0x2A, 0x11, 0x12, 0x01, 0x20, 0xAD, 0x30, 0x3A,
6
    0x02, 0x04, 0x01, 0x22, 0x10, 0x01, 0x07, 0x11, 0x12, 0x01, 0x20, 0xA8, 0x30, 0x2C,
7
    0x02, 0x05, 0x01, 0x68, 0x10, 0x01, 0x19, 0x11, 0x12, 0x01, 0x20, 0x62, 0x30, 0x1E,
8
    0x02, 0x06, 0x01, 0xA1, 0x10, 0x01, 0x2D, 0x11, 0x12, 0x01, 0x20, 0x06, 0x30, 0x10,
9
    0x02, 0x07, 0x01, 0x3C, 0x10, 0x01, 0x3B, 0x11, 0x12, 0x01, 0x20, 0x1B, 0x30, 0x02,
10
    0xFF, 0x01, 0xFF, 0x00
11
};

디스어셈블하면 이런 식으로 반복된다.

1
00: LOAD 0
2
02: PUSH 0x13
3
04: XOR
4
05: PUSH 0x05
5
07: ADD
6
08: ROL 1
7
0A: CMP 0xEE
8
0C: JNZ +0x64
9
(반복)
10
70: HALT 1
11
72: HALT 0

이 구조에서 블록 하나의 길이는 14바이트다.

첫 블록 JNZ의 오프셋은 0x72 - 0x0E = 0x64
실패 주소는 HALT 0가 시작되는 0x72
성공 주소는 HALT 1가 시작되는 0x70

수식화

패턴이 똑같으니 한 블록만 보면 된다. 스택의 변화까지 적으면 식이 나온다.

1
LOAD i           -> [x_i]
2
PUSH k[i]        -> [x_i, k_i]
3
XOR              -> [x_i ^ k_i]
4
PUSH c[i]        -> [x_i ^ k_i, c_i]
5
ADD              -> [(x_i ^ k_i) + c_i]
6
ROL 1            -> [rol8((x_i ^ k_i) + c_i, 1)]
7
CMP t[i]         -> flag = (top == t_i), stack pop
8
JNZ fail         -> if flag == 0, jump to fail

y_i = \text{rol}_8((x_i \oplus k_i) + c_i, 1)

y_i = t_i

여기서 $x_i$ 는 입력 바이트, $k_i$ 는 key, $c_i$ 는 add, $t_i$ 는 CMP 상수다. 모든 연산은 mod 256이다.

역연산도 바로 나온다.

x_i = \text{ror}_8(t_i, 1) - c_i \oplus k_i \pmod{256}

아래는 VM 상수

1
k = [13, 57, 9B, DF, 22, 68, A1, 3C]
2
c = [05, 11, 1F, 2A, 07, 19, 2D, 3B]
3
t = [EE, 94, 3C, AD, A8, 62, 06, 1B]

실제 문제는 ROL 대신 ROR이 섞이거나, ADD 위치가 바뀌거나, 스택/레지스터가 꼬여 있다. 어렵지만 패턴을 찾고, 수식화를 차근차근 한다면 당신도 할 수 있다.

3. Solving

Direct

1
def ror8(v, r):
2
    return ((v >> r) | (v << (8 - r))) & 0xFF
3

4
keys = [0x13, 0x57, 0x9B, 0xDF, 0x22, 0x68, 0xA1, 0x3C]
5
adds = [0x05, 0x11, 0x1F, 0x2A, 0x07, 0x19, 0x2D, 0x3B]
6
targets = [0xEE, 0x94, 0x3C, 0xAD, 0xA8, 0x62, 0x06, 0x1B]
7

8
out = []
9
for i in range(8):
10
    v = ror8(targets[i], 1)
11
    v = (v - adds[i]) & 0xFF
12
    v = v ^ keys[i]
13
    out.append(v)
14

15
print(bytes(out))

SMT

오퍼랜드가 꼬여 있거나 제약이 섞이면 SMT도 고려해볼 수 있다.

1
from z3 import *
2

3
def rol8(v, r):
4
    return ((v << r) | LShR(v, 8 - r)) & 0xFF
5

6
keys = [0x13, 0x57, 0x9B, 0xDF, 0x22, 0x68, 0xA1, 0x3C]
7
adds = [0x05, 0x11, 0x1F, 0x2A, 0x07, 0x19, 0x2D, 0x3B]
8
targets = [0xEE, 0x94, 0x3C, 0xAD, 0xA8, 0x62, 0x06, 0x1B]
9

10
x = [BitVec(f"x{i}", 8) for i in range(8)]
11
s = Solver()
12

13
for i in range(8):
14
    expr = rol8((x[i] ^ keys[i]) + adds[i], 1)
15
    s.add(expr == targets[i])
16

17
if s.check() == sat:
18
    m = s.model()
19
    ans = bytes([m[x[i]].as_long() for i in range(8)])
20
    print(ans)

VM 문제는 작은 차이로 풀이 방향이 바뀐다. 아래는 참고하면 좋을 거다.

JNZ rel8는 부호 있는 오프셋일 가능성이 높다. int8_t 캐스팅을 먼저 의심한다.
pc 기준을 확정하자. 오프셋 계산은 operand 읽은 뒤 pc 기준인 경우가 많다.
스택/레지스터 폭을 확정하자. uint8_t vs uint32_t 차이로 결과가 깨진다.
CMP가 값을 pop하는지 확인하자. pop 유무에 따라 식이 달라진다.
VM은 종종 opcode를 XOR/ADD로 디코딩한다. Dispatcher 이전 복호화 루틴을 찾는다.
반복 패턴이 보이면, 한 블록만 수식화해서 전체에 적용하자.

4. 실습

✨ 챌린지 공짜 다운로드 ✨

1
#include <stdint.h>
2
#include <stdio.h>
3

4
static uint8_t ror8(uint8_t v, unsigned r) {
5
    return (uint8_t)((v >> r) | (v << (8 - r)));
6
}
7

8
static int run_vm(const uint8_t *code, size_t code_len, uint8_t *out, size_t out_cap, size_t *out_len) {
9
    uint8_t stack[64];
10
    size_t sp = 0;
11
    size_t pc = 0;
12
    size_t out_idx = 0;
13

14
    while (pc < code_len) {
15
        uint8_t op = code[pc++];
16
        switch (op) {
17
        case 0xA1: { // PUSH imm8
18
            if (pc >= code_len || sp >= sizeof(stack)) {
19
                return 0;
20
            }
21
            stack[sp++] = code[pc++];
22
            break;
23
        }
24
        case 0xB2: { // ADD imm8
25
            if (pc >= code_len || sp == 0) {
26
                return 0;
27
            }
28
            uint8_t imm = code[pc++];
29
            stack[sp - 1] = (uint8_t)(stack[sp - 1] + imm);
30
            break;
31
        }
32
        case 0xC3: { // XOR imm8
33
            if (pc >= code_len || sp == 0) {
34
                return 0;
35
            }
36
            uint8_t imm = code[pc++];
37
            stack[sp - 1] ^= imm;
38
            break;
39
        }
40
        case 0xD4: { // ROR imm8
41
            if (pc >= code_len || sp == 0) {
42
                return 0;
43
            }
44
            uint8_t imm = code[pc++];
45
            stack[sp - 1] = ror8(stack[sp - 1], imm & 7u);
46
            break;
47
        }
48
        case 0xE5: { // OUT
49
            if (sp == 0 || out_idx >= out_cap) {
50
                return 0;
51
            }
52
            out[out_idx++] = stack[--sp];
53
            break;
54
        }
55
        case 0xF6: { // HALT
56
            *out_len = out_idx;
57
            return 1;
58
        }
59
        default:
60
            return 0;
61
        }
62
    }
63

64
    return 0;
65
}
66

67
int main(int argc, char **argv) {
68
    (void)argc;
69
    (void)argv;
70
    static const uint8_t program[] = {
71
        0xA1, 0xA7, 0xB2, 0x3A, 0xC3, 0x05, 0xD4, 0x01, 0xE5,
72
        0xA1, 0x02, 0xB2, 0x7F, 0xC3, 0x2D, 0xD4, 0x05, 0xE5,
73
        0xA1, 0xB0, 0xB2, 0x12, 0xC3, 0x71, 0xD4, 0x03, 0xE5,
74
        0xA1, 0x3D, 0xB2, 0xC6, 0xC3, 0x13, 0xD4, 0x07, 0xE5,
75
        0xA1, 0xDB, 0xB2, 0x9D, 0xC3, 0xA9, 0xD4, 0x02, 0xE5,
76
        0xA1, 0x96, 0xB2, 0x21, 0xC3, 0x6C, 0xD4, 0x06, 0xE5,
77
        0xA1, 0x55, 0xB2, 0xB8, 0xC3, 0x0F, 0xD4, 0x04, 0xE5,
78
        0xA1, 0xE8, 0xB2, 0x4E, 0xC3, 0xD2, 0xD4, 0x01, 0xE5,
79
        0xA1, 0x95, 0xB2, 0x3A, 0xC3, 0x05, 0xD4, 0x01, 0xE5,
80
        0xA1, 0xC2, 0xB2, 0x7F, 0xC3, 0x2D, 0xD4, 0x05, 0xE5,
81
        0xA1, 0xF8, 0xB2, 0x12, 0xC3, 0x71, 0xD4, 0x03, 0xE5,
82
        0xA1, 0x62, 0xB2, 0xC6, 0xC3, 0x13, 0xD4, 0x07, 0xE5,
83
        0xA1, 0x9F, 0xB2, 0x9D, 0xC3, 0xA9, 0xD4, 0x02, 0xE5,
84
        0xA1, 0xCF, 0xB2, 0x21, 0xC3, 0x6C, 0xD4, 0x06, 0xE5,
85
        0xA1, 0x55, 0xB2, 0xB8, 0xC3, 0x0F, 0xD4, 0x04, 0xE5,
86
        0xA1, 0xD0, 0xB2, 0x4E, 0xC3, 0xD2, 0xD4, 0x01, 0xE5,
87
        0xA1, 0xA3, 0xB2, 0x3A, 0xC3, 0x05, 0xD4, 0x01, 0xE5,
88
        0xA1, 0x82, 0xB2, 0x7F, 0xC3, 0x2D, 0xD4, 0x05, 0xE5,
89
        0xA1, 0x38, 0xB2, 0x12, 0xC3, 0x71, 0xD4, 0x03, 0xE5,
90
        0xA1, 0xBD, 0xB2, 0xC6, 0xC3, 0x13, 0xD4, 0x07, 0xE5,
91
        0xF6
92
    };
93

94
    uint8_t out[256];
95
    size_t out_len = 0;
96
    int ok = run_vm(program, sizeof(program), out, sizeof(out), &out_len);
97

98
    if (!ok) {
99
        return 1;
100
    }
101

102
    fwrite(out, 1, out_len, stdout);
103
    fputc('\n', stdout);
104
    return 0;
105
}

이 VM의 opcode는 아래처럼 단순하다.

Opcode	Mnemonic	Stack Effect	Desc
`0xA1`	`PUSH imm8`	`S -> S, imm`	즉시값 push
`0xB2`	`ADD imm8`	`S, a -> S, (a + imm)`	mod 256
`0xC3`	`XOR imm8`	`S, a -> S, (a ^ imm)`	XOR
`0xD4`	`ROR imm8`	`S, a -> S, ror8(a, imm)`	rotate
`0xE5`	`OUT`	`S, a -> S`	출력 버퍼에 append
`0xF6`	`HALT`	`S -> S`	종료

bytecode는 다음 패턴을 반복한다.

1
PUSH e_i
2
ADD k_i
3
XOR a_i
4
ROR r_i
5
OUT

y_i = \text{ror}_8(((e_i + k_i) \bmod 256) \oplus a_i, r_i)

$y_i$ 가 힌트 문자열이 되도록 $e_i$ 를 미리 만들어 둔 형태다. 역으로 계산하면

e_i = (\text{rol}_8(y_i, r_i) \oplus a_i) - k_i \pmod{256}

flag 파일에는 이 $e_i$ 들이 opcode와 같이 들어간 bytecode가 있다.

1
A1 8D B2 3A C3 05 D4 01 E5 A1 61 B2 7F C3 2D D4
2
05 E5 A1 40 B2 12 C3 71 D4 03 E5 A1 E4 B2 C6 C3
3
13 D4 07 E5 A1 77 B2 9D C3 A9 D4 02 E5 A1 91 B2
4
21 C3 6C D4 06 E5 A1 11 B2 B8 C3 0F D4 04 E5 A1
5
C2 B2 4E C3 D2 D4 01 E5 A1 89 B2 3A C3 05 D4 01
6
E5 A1 E4 B2 7F C3 2D D4 05 E5 A1 F8 B2 12 C3 71
7
D4 03 E5 A1 E1 B2 C6 C3 13 D4 07 E5 A1 AB B2 9D
8
C3 A9 D4 02 E5 A1 9A B2 21 C3 6C D4 06 E5 A1 B1
9
B2 B8 C3 0F D4 04 E5 A1 6C B2 4E C3 D2 D4 01 E5
10
A1 2D B2 3A C3 05 D4 01 E5 A1 8C B2 7F C3 2D D4
11
05 E5 A1 C6 B2 12 C3 71 D4 03 E5 A1 F6 B2 C6 C3
12
13 D4 07 E5 A1 DC B2 9D C3 A9 D4 02 E5 A1 8F B2
13
21 C3 6C D4 06 E5 A1 11 B2 B8 C3 0F D4 04 E5 A1
14
66 B2 4E C3 D2 D4 01 E5 A1 29 B2 3A C3 05 D4 01
15
E5 A1 A4 B2 7F C3 2D D4 05 E5 A1 79 B2 12 C3 71
16
D4 03 E5 A1 E2 B2 C6 C3 13 D4 07 E5 A1 D0 B2 9D
17
C3 A9 D4 02 E5 A1 80 B2 21 C3 6C D4 06 E5 A1 D1
18
B2 B8 C3 0F D4 04 E5 A1 1E B2 4E C3 D2 D4 01 E5
19
A1 3D B2 3A C3 05 D4 01 E5 A1 A1 B2 7F C3 2D D4
20
05 E5 A1 DE B2 12 C3 71 D4 03 E5 A1 E4 B2 C6 C3
21
13 D4 07 E5 A1 DB B2 9D C3 A9 D4 02 E5 A1 9A B2
22
21 C3 6C D4 06 E5 A1 C0 B2 B8 C3 0F D4 04 E5 A1
23
B4 B2 4E C3 D2 D4 01 E5 A1 2D B2 3A C3 05 D4 01
24
E5 A1 0C B2 7F C3 2D D4 05 E5 A1 E0 B2 12 C3 71
25
D4 03 E5 A1 C4 B2 C6 C3 13 D4 07 E5 A1 9F B2 9D
26
C3 A9 D4 02 E5 A1 CF B2 21 C3 6C D4 06 E5 A1 42
27
B2 B8 C3 0F D4 04 E5 A1 F0 B2 4E C3 D2 D4 01 E5
28
A1 A5 B2 3A C3 05 D4 01 E5 A1 03 B2 7F C3 2D D4
29
05 E5 F6

bytecode가 고정 패턴으로 반복된다는 점을 이용해 $e_i, k_i, a_i, r_i$ 를 직접 뽑아내자.

y_i = \text{ror}_8(((e_i + k_i) \bmod 256) \oplus a_i, r_i)

1
from pathlib import Path
2

3
def ror8(v, r):
4
    return ((v >> r) | (v << (8 - r))) & 0xFF
5

6

7
def load_bytecode(path):
8
    data = path.read_text().strip().split()
9
    if not data:
10
        return []
11
    return [int(tok, 16) for tok in data]
12

13

14
def parse_blocks(code):
15
    blocks = []
16
    pc = 0
17

18
    while pc < len(code):
19
        op = code[pc]
20
        if op == 0xF6:
21
            return blocks
22

23
        if pc + 8 >= len(code):
24
            raise ValueError("truncated block")
25

26
        if code[pc] != 0xA1 or code[pc + 2] != 0xB2 or code[pc + 4] != 0xC3:
27
            raise ValueError(f"unexpected opcode sequence at {pc:04X}")
28
        if code[pc + 6] != 0xD4 or code[pc + 8] != 0xE5:
29
            raise ValueError(f"unexpected opcode sequence at {pc:04X}")
30

31
        e = code[pc + 1]
32
        k = code[pc + 3]
33
        a = code[pc + 5]
34
        r = code[pc + 7]
35
        blocks.append((e, k, a, r))
36
        pc += 9
37

38
    raise ValueError("missing HALT")
39

40

41
def recover_output(blocks):
42
    out = []
43
    for e, k, a, r in blocks:
44
        v = (e + k) & 0xFF
45
        v ^= a
46
        v = ror8(v, r)
47
        out.append(v)
48
    return bytes(out)
49

50

51
def main():
52
    bytecode_path = Path(__file__).with_name("flag")
53
    code = load_bytecode(bytecode_path)
54
    blocks = parse_blocks(code)
55
    output = recover_output(blocks)
56
    print(output.decode("ascii"))
57

58

59
if __name__ == "__main__":
60
    main()

Top 3 Solver (Discord @badabodaa)

1
@lacroix RubiyaLab 2025.12.31
2
@Gunter RubiyaLab 2025.12.31
3
@minzu RubiyaLab 2025.12.31