[ 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.
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:
$ ./layerup 'SecurinetsENIT{5ff2inb723nm}'
Correct!1. First look
$ 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:
| offset | meaning |
|---|---|
0x000 | 256-slot operand stack (int) |
0x400 | stack pointer |
0x404 | registers regs[0..7] |
0x428 | bytecode pointer (0x4022e0) |
0x430 | bytecode length (0x75) |
0x434 | program counter |
0x438 | input pointer |
0x440 | input length |
0x444 | keep-running flag |
0x448 | status word A (must end == 0) |
0x44c | status 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)
| op | name | semantics |
|---|---|---|
0x3c | PUSH imm32 | push little-endian u32 |
0x42 | SETREG r | pop → regs[r] |
0xae | GETREG r | push regs[r] |
0x5e | LEN | push input length |
0x9a | LOAD | pop idx; push input[idx] |
0x8f | EQ | pop a,b; push (b == a) |
0xd3 | JZ addr16 | pop v; branch to absolute addr if 0 |
0x1b | JMP addr16 | branch to absolute addr |
0xb8 | XOR | push b ^ a |
0x71 | ADD | push b + a |
0x4d | MUL | push b * a |
0x53 | SHR | push b >> a |
0xe2 | ROL | push rol32(b, a) |
0x7b | HALT | pop 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:
#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
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 74. 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:
// 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:
- Pick a candidate length
nand character set. - Forward half (
Fchars): from the init state, enumerate all prefixes, store the resulting 64-bit mid-state in a hash table. - Backward half (
B = n - Fchars): 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:
inner = 5ff2inb723nm -> flag = SecurinetsENIT{5ff2inb723nm}The binary validates the entire flag string (the inner text alone returns Wrong.).
5. Solver (MITM, C + OpenMP)
// 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
SecurinetsENIT{5ff2inb723nm}$ ./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.txtis 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/JMPtake absolute targets; (2) ther1update's>>16term uses the post-multiplyr0value.