<- cd ../ (back to ~/writeups on the homepage)

[ writeup · case #032 ]

LayerUp

A stripped x86-64 ELF implements a custom stack-machine VM running 117 bytes of bytecode that folds your input into two 32-bit registers, printing Correct! only on a single 64-bit equality. The check is not hand-invertible, so I recover the flag with a meet-in-the-middle search.

date
2026-10-11
read
5 min
tags
#ctf #reversing #vm #mitm
event
Securinets ENIT — Cat the Flag v3
category
rev
points
370
placement
1st place

CTF: Securinets ENIT Category: Reverse Engineering Flag: SecurinetsENIT{5ff2inb723nm}


TL;DR

layerup is a stripped x86-64 ELF that implements a small custom stack-machine VM. The VM runs a 117-byte (0x75) bytecode program that folds your input into two 32-bit registers and prints Correct! only if both registers equal fixed constants. The register update is a per-character mix of xor / rotate / multiply / add.

Because the accept condition is a single 64-bit equality, the check is not invertible by hand and not collision-resistant — so the password is recovered with a meet-in-the-middle (MITM) search over candidate inputs.

The accepted input is the full flag string itself:

text
$ ./layerup 'SecurinetsENIT{5ff2inb723nm}'
Correct!

1. First look

text
$ file layerup
ELF 64-bit LSB executable, x86-64, dynamically linked, stripped

$ strings layerup | grep -E 'Correct|Wrong'
Correct!
Wrong.

main is at 0x4003c0. Input is taken from argv[1] (via strlen + memcpy, capped at 0x1000 bytes) or, if no argument is given, from stdin via fread. A VM context (~0x450 bytes) is built on the stack and the bytecode is interpreted.


2. The VM

A context struct (handler receives rdi = context base) holds:

offsetmeaning
0x000256-slot operand stack (int)
0x400stack pointer
0x404registers regs[0..7]
0x428bytecode pointer (0x4022e0)
0x430bytecode length (0x75)
0x434program counter
0x438input pointer
0x440input length
0x444keep-running flag
0x448status word A (must end == 0)
0x44cstatus word B (must end != 0)

Main loop (0x400560): fetch op = bytecode[pc], dispatch through a handler table at 0x404060 (call *0x404060(,rax,8)). The loop continues while the keep-running flag is set; HALT clears it, and the success check at 0x4005b8 prints Correct! (0x4022d0) iff status A == 0 and status B != 0, otherwise Wrong. (0x4022d9).

Opcode map (verified from the handler table)

opnamesemantics
0x3cPUSH imm32push little-endian u32
0x42SETREG rpop → regs[r]
0xaeGETREG rpush regs[r]
0x5eLENpush input length
0x9aLOADpop idx; push input[idx]
0x8fEQpop a,b; push (b == a)
0xd3JZ addr16pop v; branch to absolute addr if 0
0x1bJMP addr16branch to absolute addr
0xb8XORpush b ^ a
0x71ADDpush b + a
0x4dMULpush b * a
0x53SHRpush b >> a
0xe2ROLpush rol32(b, a)
0x7bHALTpop v; set status words; stop

Key gotcha: the JZ / JMP operands are absolute bytecode offsets, not relative. With that, the control flow is a clean while (i != len) loop (JMP 21 = loop condition, JZ 31 = loop body, JMP 99 = exit/final check).


3. The check (decoded from the bytecode)

Disassembling the 117 bytes of bytecode yields exactly this per-character mixing function:

c
#include <stdint.h>
typedef uint32_t u32;
#define M1 0xA3C59AC3u
#define M2 0xCF1BBCDDu
static inline u32 rol(u32 x, int r){ r &= 31; return (x << r) | (x >> ((32 - r) & 31)); }

int accepts(const unsigned char *s, int len) {
    u32 r0 = 0x7e4a1c3b, r1 = 0x2d5f8e11;      // register init constants
    for (int i = 0; i < len; i++) {
        u32 c = s[i];
        u32 t = rol(r0 ^ c, 11);
        t  = t * M1 + (u32)i;   r0 = t;        // r0 update (independent of r1)
        u32 u = (t >> 16) * M2 + r1;
        u  = rol(u, 7) ^ c;     r1 = u;        // r1 update
    }
    return r0 == 0xA5219537 && r1 == 0xC19B6387; // accept condition
}

All arithmetic is mod 2³². Note r0 evolves independently of r1; r1 depends on r0's intermediate value.

Verification against the live binary

Running the real binary on "AAAA" and reading regs[0]/regs[1] at the success check gives r0=0x16b165b5, r1=0x35a94097 — which matches the emulator byte-for-byte, confirming the decode is correct (and that the "broken binary" notes are a red herring).

Constants reference

text
r0 init  = 0x7e4a1c3b      r1 init  = 0x2d5f8e11
r0 final = 0xA5219537      r1 final = 0xC19B6387
MUL1 = 0xA3C59AC3   (inverse mod 2^32 = 0x0d8465eb)
MUL2 = 0xCF1BBCDD
rotations: r0 uses rol 11, r1 uses rol 7

4. Recovering the password (meet-in-the-middle)

Each step is a bijection on (r0, r1) given the character c and index i, so it inverts cleanly:

c
// backward step: given state AFTER the step, the char c, and index i -> state BEFORE
static inline void bwd(u32 *r0, u32 *r1, int c, int i) {
    u32 r0new = *r0;
    u32 t   = (r0new - (u32)i) * 0x0d8465eb;   // (r0new - i) * MUL1^-1
    u32 r0p = rol(t, 21) ^ (u32)c;             // ror 11 == rol 21
    u32 u   = rol(*r1 ^ (u32)c, 25);           // ror 7  == rol 25
    u32 r1p = u - (r0new >> 16) * M2;          // NB: uses r0new>>16, not t>>16
    *r0 = r0p; *r1 = r1p;
}

Because the state is 64 bits and each step is invertible, the search is a standard MITM:

  1. Pick a candidate length n and character set.
  2. Forward half (F chars): from the init state, enumerate all prefixes, store the resulting 64-bit mid-state in a hash table.
  3. Backward half (B = n - F chars): from the final state, invert all suffixes and look up the meet-state in the table. A collision reconstructs a full accepting string.

Cost ≈ charset^max(F,B); memory ≈ charset^F. On a 16-core box this recovers the password for the relevant lengths in minutes.

Why a search is needed and how the length/charset were found

The accept condition is a 64-bit target, so:

  • No input ≤ 9 chars can satisfy it (search space < 2^64 → effectively no preimage). Confirmed empty by exhaustive MITM.
  • A readable preimage first appears around the length where charset^length ≈ 2^64.

Sweeping length/charset combinations, the solver hit a solution at inner length 12 over [a-z0-9_], and it is the unique solution in that space:

text
inner = 5ff2inb723nm   ->   flag = SecurinetsENIT{5ff2inb723nm}

The binary validates the entire flag string (the inner text alone returns Wrong.).


5. Solver (MITM, C + OpenMP)

c
// build: gcc -O3 -march=native -fopenmp -o mitm mitm.c
// run:   ./mitm "SecurinetsENIT{" "}" "abcdefghijklmnopqrstuvwxyz0123456789_" 12 5
// args:  <prefix> <suffix> <charset> <mid-length m> <forward-split f>

The full solver forward-enumerates f middle characters into an open-addressing hash of the 64-bit mid-state, then streams the backward m-f characters (inverting the suffix } and the back half) and probes the table. It was validated with a self-test that recovers a known plaintext before being pointed at the real targets.


6. Final answer

text
SecurinetsENIT{5ff2inb723nm}
text
$ ./layerup 'SecurinetsENIT{5ff2inb723nm}'
Correct!

7. Notes & lessons

  • The accept condition is a 64-bit hash equality, which is not collision-resistant: multiple distinct inputs make the binary print Correct!. The intended flag is the specific designed string; a well-chosen short length keeps it effectively unique in the natural search space.
  • The provided notes_about_layeryp.txt is deliberate misdirection — it argues the binary is broken. The "stack-depth guard" it mistakes for an "operand zero-check" is just an underflow/arity check (sp <= 0 / sp == 1), not a value test. The binary is fully functional.
  • The two correctness-critical details when reimplementing: (1) JZ/JMP take absolute targets; (2) the r1 update's >>16 term uses the post-multiply r0 value.