WASM, Rocket Navigation

Task description

A rocket on a canvas has to be steered to the centre by entering a 12-digit sequence, digit by digit.

What the game shows

A .wasm module backs the whole game, exposing reset_game, input_digit, get_diff_x, get_diff_y and check_win. Each typed digit updates the rocket’s position on screen, and after exactly 12 digits, check_win decides whether the flag unlocks. Only two coordinates, x and y, are ever shown.

The state machine, from the WAT disassembly

The module actually tracks four values, (x, y, z, w), over a prime field with modulus p = 4294967291. Starting state after reset_game is (0, 0, 0, 1), and the module’s memory holds a fixed target state the input needs to reach exactly: (2782920168, 3459205023, 2841489756, 430009836).

Each digit d you enter first runs through a fixed polynomial, val = (d^3 + 4919*d + 42) mod p, and then updates all four state components at once via a fixed affine transformation:

x_new = (383*x + 359*y + 912*z + 351*w + 340*val) mod p
y_new = (936*x + 967*y + 495*z + 745*w + 232*val) mod p
z_new = (153*x + 248*y + 401*z + 654*w + 836*val) mod p
w_new = (383*x + 969*y + 328*z + 192*w + 926*val) mod p

or, in matrix form, s_{i+1} = M * s_i + f(d_i) * b (mod p). check_win passes only when all four components exactly match the target, not just the two visible ones, which is exactly why watching the rocket’s on-screen position alone can’t reveal the answer: z and w are invisible, and they’re checked just as strictly as x and y are.

Why a direct search doesn’t work

Twelve digits, ten choices each, is 10^12 possible sequences, far too many to try directly. But the state update is linear (an affine map applied the same way at every step), which means it can be run forward from the start or, using the inverse of the same matrix M, backward from the target, and the two directions can be matched in the middle.

Meet in the middle

1. Forward, from the known starting state, enumerate every possible state after the first 6 digits (10^6 possibilities), and store each in a hash table.
2. Backward, from the known target state, invert the transformation (computing M’s modular inverse, using Fermat’s little theorem for the per-entry modular inverse, a^(p-2) mod p) to enumerate every state reachable by some 6-digit suffix that would land exactly on the target (another 10^6 possibilities).
3. Match: any state appearing in both tables gives a working 12-digit sequence, the forward 6 digits followed by the backward 6.

That turns a 10^12 search into two 10^6 searches plus a hash lookup, which a small C solver (using 128-bit intermediate arithmetic, since products of 32-bit field elements overflow 64 bits) ran in about 2 seconds.

A verification pitfall

An early attempt failed because the target state’s values were transcribed by hand from the WAT’s hex literals, and a hex-to-decimal slip crept in. The fix was to decode the actual compiled WASM binary (it ships base64-encoded in the page) and read the target bytes directly out of it, then independently confirm the recovered model against the live module running in Node.js before trusting the solver’s output.

The answer

306807833005

Entered digit by digit, it steers the rocket’s visible x and y to the centre, because all four hidden state components land exactly on target, and the flag reads: CTF2026[306807833005].