Deja VM — Reverse Engineering Writeup

Category: Reverse Engineering / VM-Based Crackme Binary: dej4 VM (ELF 64-bit, PIE, not stripped) Flag: Africc{reverse_the_vm_to_win___}

1. Recon

$ file "dej4 VM"
ELF 64-bit LSB pie executable, x86-64, ... not stripped

strings reveals the interesting bits right away:

usage: %s '<flag>'
A1B2-C3D4-E5F6-0079
CRACKME_DEBUG
[debug] crc_legacy(argv[0]) = %08x
4111111111111111
Uggc://rknzcyr.vainyvq
Access granted.
Access denied.

Symbol table (nm) shows the whole game plan:

crc_legacy  luhn_check  rot13_transform  is_prime_trial  xor_fold_hash
fake_license_parse  rol32  ror32  mba_add  mba_xor  vm_run
runtime_env_check  PAYLOAD_BLOB  IV_WORDS  words_from_bytes

So main drives a custom VM interpreter (vm_run) over a bytecode blob (PAYLOAD_BLOB) using 4 "IV" words. Most of the crypto helper functions (crc_legacy, luhn_check, rot13_transform, fake_license_parse, is_prime_trial) are decoy obfuscation that only feed a dummy global g_sink and never influence the check.

2. main() — a state machine

main is a big switch on a state variable (offset -0x9c). Walking it:

State	Action
0	Require `argc == 2`; else usage, exit.
1	`strlen(argv[1])` must equal `0x20` (32 chars). Load `IV_WORDS = 3b1d4a7f c259e081 77a6f3d4 0e4b9c82`.
2–5	Decoys feeding `g_sink`: `fake_license_parse("A1B2-C3D4-E5F6-0079")`, `crc_legacy(argv[0])`, `luhn_check("4111111111111111")`, `rot13_transform("Uggc://rknzcyr.vainyvq")` → `https://example.invalid`.
5	Decoy `is_prime_trial(strlen+0x15fd7)`.
6	Decoy `xor_fold_hash`; the `0xdeadbeef` branch is dead code (requires `argc != 2`, which is impossible).
7	`runtime_env_check()` → `ptrace(PTRACE_TRACEME)` returns 1 if a debugger is attached (anti-debug).
8	The real work — see below.
9	`memcmp(computed_32_bytes, 0x3130, 0x20)` → state 10 = "Access granted.", state 11 = "Access denied."

State 8 — block processing (CBC-like)

// input  = 16 bytes of flag, output  = 16 bytes appended to outbuf
for (block = 0; block*16 < 32; block++) {
    words_from_bytes(flag + block*16, buf);      // 16 bytes -> 4 LE dwords
    for (i = 0; i < 4; i++) buf[i] ^= IV[i];     // XOR with IV
    if (debugged && block == 0) buf[0] ^= 0x5A5A5A5A;  // anti-debug
    vm_run(PAYLOAD_BLOB + 0xc, 0x98, buf);       // VM output overwrites buf
    store buf into outbuf at block*16;
    IV = buf;                                    // chained IV = previous output
}

So we must decrypt two 16-byte blocks, each encrypted as:

out = VM( flag_block ^ IV )   , then IV = out

The 32-byte target at 0x3130:

cc20900f d3970a2e da86c31b 4d9bf521 fa6c76aa 3d6d2d80 ae6351b0 9ff5fa95

3. The VM (`vm_run`)

vm_run(bytecode, len, buf) keeps:

10 dwords reg[0..9] (memset at rbp-0x40),
4 dwords out[0..3] (at rbp-0x50, written back to buf at the end),
a 32-bit state register S (rbp-0x20),
a loop counter (rbp-0x1c),
bytecode pointer pc.

Dispatch is a jump table at 0x3030 (18 entries). Recovered opcodes:

Op	Meaning
0	END
1	`reg[a] = buf32[b]`
2	`out[a] = reg[b]`
3	`reg[a] = reg[b]`
4	`reg[a] = mba_add(reg[a], reg[b])` (= `a+b` mod 2³²)
5	`reg[a] = reg[a] - reg[b]`
6	`reg[a] = mba_xor(reg[a], reg[b])` (= `a^b`)
7	`reg[a] = rol32(reg[a], imm)`
8	`reg[a] = ror32(reg[a], imm)`
9	`reg[a] = S`
10	`S = mba_add(S * 0xd1342543, 0x2545f491)`
11	`reg[a] = imm32`
12	`JMP imm16`
13	`LOOP imm16` (dec counter; jump if != 0)
14	`reg[a] = rol32(S, imm)`
15	`SWAP reg[a], reg[b]`
16	`counter = imm32`
17	`S = imm32`

(Opcode 0 is reached either by falling off the program or by the END byte; the fetch loop breaks when pc >= len and dumps out[0..3] into buf.)

4. Bytecode disassembly

Program = bytes at 0x308c, length 0x98:

01000001010101020201030311dec0ed5e10b80b
000003040107040703050207050d060405030503070503060405090506040504
000403040007040b0305020705110404050e050506040504
01040304010704170e050904040503050007051306040504
020403040007041d03050107051f0404050305020705020404050e050d060405
0403040a0d160002000002010102020202030300

Disassembly:

  0: reg[0] = buf32[0]      # input words
  3: reg[1] = buf32[1]
  6: reg[2] = buf32[2]
  9: reg[3] = buf32[3]
 12: S = 0x5eedc0de         # round constant / seed
 17: counter = 3000         # 3000 rounds
 22: ... round body ...     # 22..135
135: S = S*0xd1342543 + 0x2545f491
136: LOOP 22
139: OUT[0]=reg[0]  OUT[1]=reg[1]  OUT[2]=reg[2]  OUT[3]=reg[3]
151: END

So this is a 3000-round custom block cipher on 4 words (a,b,c,d), with a round key S that evolves linearly:

S_{r+1} = S_r * 0xd1342543 + 0x2545f491   (mod 2^32),  S_0 = 0x5eedc0de

5. The round function

Tracing the body with registers a=reg0, b=reg1, c=reg2, d=reg3:

def cipher_round(a, b, c, d, s):
    a1 = a + (rol(b,7) ^ rol(c,13) ^ rol(d,3) ^ s)                    & M32
    b1 = b + ((rol(a1,11) + rol(c,17)) & M32 ^ rol(s,5))              & M32
    c1 = c + (((rol(b1,23) + rol(s,9)) & M32) ^ rol(a1,19))           & M32
    d1 = d + (((rol(a1,29) + rol(b1,31) + rol(c1,2)) & M32) ^ rol(s,13)) & M32
    return a1, b1, c1, d1

M32 = 0xffffffff, all arithmetic mod 2³². Note rol(s,9) then later rol(s,13) use the same round s; S is updated only after the round.

Inverting a round

Each of the four updates is a simple substitution, so a round is trivially reversible:

def cipher_inverse_single(fwd, s):
    a1, b1, c1, d1 = fwd
    d = d1 - ((((rol(a1,29) + rol(b1,31) + rol(c1,2)) & M32) ^ rol(s,13)) & M32)
    c = c1 - ((((rol(b1,23) + rol(s,9)) & M32) ^ rol(a1,19)) & M32)
    b = b1 - ((((rol(a1,11) + rol(c,17)) & M32) ^ rol(s,5)) & M32)
    a = a1 - (rol(b,7) ^ rol(c,13) ^ rol(d,3) ^ s)
    return a, b, c, d

Because S only depends on the round number, we can precompute S_0..S_2999 and run the inverse rounds in reverse.

6. Verification

An emulator written from the disassembly produces byte-identical output to the real VM (checked under gdb by dumping the buffer before/after vm_run).
For A×32 under gdb, simulated and actual computed buffers matched exactly, confirming both the bytecode decode and the anti-debug 0x5a5a5a5a behavior.

7. Solving for the flag

Split the 32-byte target into two blocks and decrypt backwards through the chained IVs:

target = bytes.fromhex(class="hljs-string">"cc20900f d3970a2e da86c31b 4d9bf521 "
                       class="hljs-string">"fa6c76aa 3d6d2d80 ae6351b0 9ff5fa95")
out0, out1 = target[:16], target[16:]
IV0 = [0x3b1d4a7f, 0xc259e081, 0x77a6f3d4, 0x0e4b9c82]

buf0 = cipher_inverse(unpack(class="hljs-string">"<4I", out0))          # flag[0:16] ^ IV0
flag0 = pack(class="hljs-string">"<4I", *[buf0[i] ^ IV0[i] for i in range(4)])

IV1 = unpack(class="hljs-string">"<4I", out0)                           # chained IV
buf1 = cipher_inverse(unpack(class="hljs-string">"<4I", out1))          # flag[16:32] ^ IV1
flag1 = pack(class="hljs-string">"<4I", *[buf1[i] ^ IV1[i] for i in range(4)])

flag = flag0 + flag1

Result:

Africc{reverse_the_vm_to_win___}

$ ./dej4\ VM 'Africc{reverse_the_vm_to_win___}'
Access granted.

8. Takeaways

The "deja vu" hint + future quote is a clue that you must run the cipher backwards in time (invert the 3000-round schedule).
ptrace anti-debug (fixed by set disable-randomization on + running under gdb and accounting for the 0x5a5a5a5a XOR, or simply by solving algebraically).
The fake helpers (crc_legacy, luhn_check, etc.) are pure noise writing to g_sink; always check whether a function's output actually influences the acceptance branch.

AFRICC Qualifiers 2027 - Deja VM writeup