Captain's Keygen: The Cursed Treasure Lock

Reverse Engineering, Hard, 500 pts

flag{th3_cur53d_m3r1d14n_y13ld5_1t5_g0ld_t0_th0rn3}

vault_lock is a stripped Linux x86-64 PIE ELF taking two inputs: a name and a 32-hex-char (16-byte) master key. Unusually for this kind of challenge, compass_chart.txt hands over almost the entire algorithm in plain prose — the work is pinning down the exact constants and running the math, not fighting obfuscation.

The 16-byte key splits into four "watches" of four bytes each. Watch 0 is four unknown "master glyphs" k0,k1,k2,k3; watches 1–3 are the same four bytes XORed with 0x5A, 0xA5, 0x3C respectively. So the whole 16-byte key has only 4 unknown bytes.

A 256-entry permutation S[] (the "tide chamber") is generated from a name-derived seed using a PCG-style generator (MULT = 0x5851F42D4C957F2D, INC = 0x14057B7EF767814F, seed state initialized from "BLACKTID" and then updated once per input character) — 256 raw draws to fill S[], then a Fisher-Yates shuffle using 255 more draws. The accumulator is a Horner-style running sum over the 16 expanded key bytes:

acc = 0
for i in 0..15: acc = (acc * 0x1000193 + S[key[i]] * W[i]) % (2**61 - 1)

with W[] a 16-entry weight table read from .rodata and lightly masked by two more constants. The target is 0x024a6bae61713629, cross-checked by a CRC-16/CCITT-FALSE seal 0x0B97 over the 16-byte key.

Since only k0..k3 are free, this is a meet-in-the-middle problem: each k_j contributes to exactly 4 of the 16 Horner terms (once per watch), so the 16-term weighted sum splits cleanly into two independent halves, {k0,k1} and {k2,k3}. Precomputing all 256×256 partial sums for one half into a hash table keyed by "value needed from the other half" turns a 256⁴ ≈ 4.3×10⁹ brute force into about 2×65536 operations.

The name isn't given directly, so a short list of in-lore candidates ("Edward Thorne", "Captain Thorne", "Black-Tide", "The Black Meridian", …) was tried as the seed. "Edward Thorne" is the one that produces a solution at all: k0,k1,k2,k3 = 0x5e,0xa2,0x1d,0x8c, full key 5ea21d8c04f847d6fb07b829629e21b0. It satisfies both the Horner checksum and the CRC-16 independently, which is a strong consistency check for a 4-unknown-byte search.

The flag itself is a separate small stream cipher keyed off the solved state: flagkey = PCG-mix(acc XOR namehash, each key byte), then a keystream byte per output position is (state >> 40) & 0xFF from repeated PCG advances of that flagkey, XORed against a 51-byte ciphertext blob in .rodata. Running that with the verified acc, namehash, and key bytes decrypts cleanly to the flag above.