small-guy

TL;DR

The visible machine code does nothing. All 256 rounds of the checker live inside .eh_frame — the DWARF Call Frame Information tables that the C++ exception unwinder interprets. The program recurses 256 times, throws an int, and the unwinder executes the cipher as a side effect of restoring callee-saved registers frame by frame.

The one subtlety that breaks a naive static model: the round key register (rcx, DWARF r2) is consumed one frame later than the frame that pushes it.

1. Surface behaviour

$ ./small-guy AAAA...
Wrong.
$ ./small-guy 'NNS{unw1nd_m3_1f_y0u_c4n_sm4ll_guy!!}'
Correct!

main is at 0x400450. It accepts either a bare 32-character string or the wrapped form NNS{ …32 chars… }, and then:

4004aa:  movdqu (%rbx),%xmm0
4004ae:  movups %xmm0,0xcfb4b(%rip)   # 0x4d0000  <- payload[0:16]
4004b5:  movdqu 0x10(%rbx),%xmm0
4004ba:  movzwl 0xcfb3f(%rip),%eax    # 0x4d0000  <- first 2 bytes
4004c1:  movups %xmm0,0xcfb48(%rip)   # 0x4d0010  <- payload[16:32]
4004c8:  mov    %rax,0xcfb51(%rip)    # 0x4d0020  <- V (zero-extended u16)
4004cf:  call   400600                # wrapper
4004d4:  mov    $0x20,%edx
4004d9:  mov    $0x401dd0,%esi        # 32-byte target
4004de:  mov    $0x404080,%edi        # 32-byte result
4004e3:  call   memcmp

Two globals matter:

Address	Meaning
`0x4d0000`	`.vmin` section — the raw 32-byte payload
`0x4d0020`	`V` = `payload[0]
`0x401dd0`	32-byte comparison target
`0x404080`	32-byte result written by the exception landing pad

2. The decoy: a 256-deep recursion

The wrapper at 0x400600 calls check(0) at 0x400618:

400618:  push   %rbp
400619:  mov    %rsp,%rbp
40061c:  mov    %rdi,%rax            ; i
40061f:  cmp    $0x100,%eax
400624:  je     400786               ; base case at i == 256
40062a:  movzbl 0x4014d0(%rax),%r8d  ; table1[i]         (256 bytes)
400632:  mov    %rax,%rcx
400635:  and    $0x7,%ecx
400638:  mov    0xcf9e1(%rip),%r10   ; V
40063f:  shr    %cl,%r10             ; V >> (i & 7)
400642:  add    %r10d,%r8d
400645:  and    $0x1f,%r8d           ; D = (table1[i] + (V >> (i&7))) & 0x1f
400649:  mov    0x4015d0(,%rax,8),%r9 ; table2[i]        (256 * u64)
400651:  mov    0xcf9c8(%rip),%r10   ; V
400658:  movabs $0x9e3779b97f4a7c15,%r11
400662:  imul   %r11,%r10
400666:  xor    %r10,%r9             ; r9 = table2[i] ^ (V * GOLDEN)
400669:  push   %r9
40066b:  push   %r9                  ; pushed twice
40066d:  lea    0x1(%rax),%rdi
400671:  jmp    *0x401df0(,%r8,8)    ; 32-entry jump table

Every one of the 32 jump-table targets is byte-for-byte identical in effect:

400740:  call   400618               ; check(i+1)
400745:  jmp    400791               ; leave; ret

So at the instruction level the 32 branches are pure theatre. What actually differs between them is the address of the call, and therefore which .eh_frame row describes that frame.

At i == 256 the base case throws:

400786:  sub    $0x10,%rsp
40078a:  call   400422               ; __cxa_allocate_exception + __cxa_throw(int)

The handler is the wrapper’s landing pad (0x400610 → 0x4003f0), which does nothing but snapshot four callee-saved registers:

4003fb:  mov %rbx,0x3c7e(%rip)   # 0x404080
400402:  mov %r12,0x3c7f(%rip)   # 0x404088
400409:  mov %r13,0x3c80(%rip)   # 0x404090
400410:  mov %r14,0x3c81(%rip)   # 0x404098

rbx/r12/r13/r14 = 32 bytes of state. Nothing in the executable code ever writes them. The unwinder does.

3. The real VM: `DW_CFA_val_expression`

readelf --debug-dump=frames on the FDE for 0x400618 shows, at each of the 32 call-site addresses, a row of the form:

DW_CFA_advance_loc: 5 to 0000000000400740
DW_CFA_restore_state
DW_CFA_remember_state
DW_CFA_offset_extended: r2 (rcx) at cfa-24
DW_CFA_val_expression: r13 (r13) (DW_OP_breg13: 0; DW_OP_breg2: 0;
                                  DW_OP_constu: 9650029242287828579;
                                  DW_OP_mul; DW_OP_plus)

DW_CFA_val_expression tells the unwinder: the caller’s value of this register is the result of this DWARF expression, evaluated in the current frame’s context. That is a full stack machine — mul, xor, shl, shr, and, and even DW_OP_bra for loops. The obfuscator uses it as an ALU.

The 32 branches decode into 8 perfectly symmetric families:

D	Operation
0–3	`reg += C` (variant A) — rbx, r12, r13, r14
4–7	`reg += C` (variant B)
8–11	`reg ^= rotl(next_reg, k)` (k = 7, 17, 29, 41)
12–15	`reg *= C`
16–19	`reg ^= rcx`
20–23	`reg += rcx * C`
24–27	`reg ^= rotl(other_reg, k)` (k = 11, 23, 37, 53)
28–29	`swap(rbx, r13)`, `swap(r12, r14)`
30	rbx: LCG `x = x*1812433253 + 2567483615`, repeated `(rcx & 3) + 1` times
31	r13: LCG `x = x*1103515245 + 12345`, repeated `(rcx & 3) + 1` times

D=30/31 are implemented with DW_OP_dup … DW_OP_bra: -19 — an actual counted loop inside a DWARF expression.

The seed is loaded by the throwing frame’s row:

DW_CFA_advance_loc: 4 to 000000000040078a
DW_CFA_remember_state
DW_CFA_val_expression: r2  (rcx) (DW_OP_lit0)
DW_CFA_val_expression: r3  (rbx) (DW_OP_addr: 4d0000; DW_OP_deref)
DW_CFA_val_expression: r12 (r12) (DW_OP_addr: 4d0008; DW_OP_deref)
DW_CFA_val_expression: r13 (r13) (DW_OP_addr: 4d0010; DW_OP_deref)
DW_CFA_val_expression: r14 (r14) (DW_OP_addr: 4d0018; DW_OP_deref)

So unwinding out of the innermost (throwing) frame loads the payload straight into the state, and every frame above it applies one round. Unwinding runs inner → outer, so the round order is i = 255 down to 0, 256 rounds total, ending when the wrapper’s handler frame is reached.

Row selection

Two traps here.

A frame’s row is looked up at return_address - 1, not at the return address. For the 5-byte call at 0x400740 the return address is 0x400745, and 0x400744 falls inside the row [0x400740, 0x400745) — the call’s own row.
Each 2-byte jmp following a call also carries a val_expression row. Those rows are decoys: no frame’s RA-1 can ever land in them. If you enumerate rows linearly instead of resolving through the jump table at 0x401df0, you pick up 32 phantom operations.

4. The bug that cost the most time

Every arithmetic row contains both:

DW_CFA_offset_extended: r2 (rcx) at cfa-24     <- rule that RESTORES rcx
DW_CFA_val_expression:  rN ( … DW_OP_breg2 … ) <- expression that READS rcx

All rules in a CFI row are evaluated simultaneously against the current frame’s register context (this is exactly what libgcc’s uw_update_context_1 does — it snapshots orig_context first, then computes every new register from that snapshot). Therefore:

Unwinding frame i produces rcx = [frame_i.CFA - 24]. Since check(i) does push %rbp; mov %rsp,%rbp; push %r9; push %r9, CFA = rbp+16 and CFA-24 = rbp-8, so that slot holds r9(i).
But the expression evaluated in frame i reads frame i’s own rcx, which was produced one step earlier, by frame i+1. That value is r9(i+1).

Round i therefore consumes r9(i+1), not r9(i).

The author left a smoking gun for this: the seed row explicitly sets r2 (rcx) = DW_OP_lit0. That line is only meaningful if rcx is read one frame after it is written — it seeds round 255 with zero.

rcx = 0                       # from the seed row's DW_OP_lit0
for i in range(255, -1, -1):
    apply(op[D(i, V)], state, rcx)   # frame i's own rcx
    rcx = r9_of(i, V)                # what frame i hands to frame i-1

The naive model (round i uses r9(i)) is self-consistent, so:

forward-simulator → inverter round-trip tests pass 100 % on random inputs;
Unicorn cross-checks pass, because they verify “is the value at CFA-24 equal to table2[i] ^ K?” — a question about the formula, not about which frame’s slot gets consumed;

…and yet the full 65536-way brute force over V yields zero self-consistent candidates. Both halves of the model share the same wrong assumption, so no internal test can see it.

5. Getting ground truth

The decisive step was dynamic verification against the real libgcc unwinder — no reimplementation, no emulator:

break *0x4004d4                       # right after the wrapper returns
run 0123456789abcdefghijklmnopqrstuv
printf "%016lx %016lx %016lx %016lx\n", \
    *(unsigned long*)0x404080, *(unsigned long*)0x404088, \
    *(unsigned long*)0x404090, *(unsigned long*)0x404098

real   : 4e3d7f80f1b613b2 dbc4887d40da4fe1 7827ac63bfe01ef8 9aa7dc6ee2b3c2e8
shift=1: 4e3d7f80f1b613b2 dbc4887d40da4fe1 7827ac63bfe01ef8 9aa7dc6ee2b3c2e8   <- match
shift=0: 8e99b54ce2a87627 e5fc1e61354dc65a 8c4762118be57e62 769ae6cd4fd40171   <- naive

All four words matched bit-for-bit on the first try with the corrected schedule.

6. Solving

Every round is a bijection on 64-bit words, and the schedule depends only on the 16-bit V:

Forward	Inverse
`r += C`	`r -= C`
`r ^= rotl(o, k)`	same (`o` unchanged by the round)
`r *= C`	`r *= C⁻¹ mod 2⁶⁴` (all constants odd)
`r ^= rcx`	same
`r += rcx*C`	`r -= rcx*C`
`swap`	`swap`
`x = x*A + B`, n times	`x = (x - B)*A⁻¹`, n times

So no SMT solver is needed. For each of the 65536 values of V, run all 256 rounds backwards from the target at 0x401dd0 and test the self-consistency condition — the recovered payload’s first two bytes must equal the V used:

for V in range(0x10000):
    p = invert(V)
    if p[0] | (p[1] << 8) == V:
        print(V, p)

13 seconds of pure Python, two hits:

HIT V=6e75  b'unw1nd_m3_1f_y0u_c4n_sm4ll_guy!!'
HIT V=7c41  b"A|\x10fV\xa5\xdc)\xdc\xd8\xb1\x92:'\xf1\x8b…"   (coincidental)

$ ./small-guy 'NNS{unw1nd_m3_1f_y0u_c4n_sm4ll_guy!!}'
Correct!

7. Files

File	Purpose
`core.py`	ELF/CFI extraction, DWARF expression interpreter, forward simulator (`shift=1` correct, `shift=0` reproduces the bug)
`inv.py`	Round inverses, round-trip self-test, 65536-way brute force over `V`

$ python3 inv.py
roundtrip ok
HIT V=6e75  b'unw1nd_m3_1f_y0u_c4n_sm4ll_guy!!'

8. Lessons

.eh_frame is executable. DW_CFA_val_expression is a Turing-ish stack machine that runs during unwinding, in a region no disassembler shows you as code. readelf --debug-dump=frames is the disassembler for it.
A CFI row applies simultaneously. Registers restored by the row are for the caller; expressions in the same row read the callee’s values. Any register used both as an operand and as a restore target is off by one frame by construction.
Round-trip tests cannot validate a model, only its internal consistency. A forward simulator and its own inverse will agree perfectly on a wrong model. Same for per-formula emulation: it validates the arithmetic, not the composition semantics.
One real execution beats any amount of static reasoning. A single breakpoint and four printfs settled a question that three independent static cross-checks could not.