Undercliffe Session Gateway

Undercliffe Terminal runs its berth telemetry through a Veilkey VK-100, a session gateway between the quay equipment and the operations network. A unit pulled from the berth 3 rack is still powered and still answering on the management VLAN, with its support bundles still on it. The task: get the token out of the sealed one.

It looks like a lot of post-quantum machinery — a Kyber-style KEM, an AES-GCM device export, a Fujisaki–Okamoto transform. It reduces to a single mistake: the gateway tells you why a decapsulation failed, and that one bit of politeness is enough to peel its private key apart one coefficient at a time.

1 Reconnaissance

The management console is a small Flask app; the SDK that ships with the unit (sdk/veilkey.py, sdk/vk_restore.py) documents the crypto, so this is a white-box challenge. The relevant surface:

The sealed artefact is vk100-session-record.json: a device-bound export whose inner session record carries the token. The support bundles on the unit are config and CSV only — a deliberate red herring. Nothing in a file gives you the key.

2 The Scheme — and What It Reduces To

Veilkey-1 is a Kyber-512 clone: module-LWE over the ring R_q = Z_q[x]/(x^256 + 1) with

# /spec
n  = 256      # polynomial degree
q  = 3329     # modulus
k  = 2        # module rank  ->  s has 2 polynomials of 256 coeffs = 512 secret ints
eta = 2      # secret/error coefficients live in [-2, 2]
du, dv = 11, 5   # compression bits for u and v

Key generation is the textbook t = A·s + e with s, e small. A ciphertext is the usual compressed pair — u (a length-k vector) and v (one polynomial) — and decryption recovers the message from v − sTu. Decapsulation wraps that in a Fujisaki–Okamoto transform, whose whole job is to make the KEM safe against chosen-ciphertext attacks:

The sealed export never involves a password. Its key is derived straight from the private key:

K_dev = SHAKE256("VK1-dev-export" || SK || salt)     # SK = pack12(s), 768 bytes
export = salt(16) || nonce(12) || AES-256-GCM(K_dev, session_record)

3 The Flaw: A Gateway That Explains Itself

The FO re-encryption step is meant to reject a tampered ciphertext indistinguishably — you should never learn why it was rejected. Undercliffe's /decap does not respect that. It returns three different outcomes:

The distinction between the first outcome and the other two is a direct read of whether the first four decrypted bytes equal the tag. In other words, /decap is a partial plaintext-checking oracle: for any ciphertext we submit, it tells us whether

DecodeMessage(v − sTu)[0:32 bits] == tag_bits

That is exactly the primitive a Guo–Johansson–Nilsson style key-recovery needs. A single distinguishable error message has undone the CCA protection.

4 From Error String to Plaintext-Checking Oracle

Because we hand /decap the compressed ciphertext directly, we control u and v as raw coefficient vectors — we are not obliged to produce a "real" encryption. Each recovered message bit j is

bit_j = 1  iff  w_j := (v − sTu)[j]  lands in the "1" region  (832, 2497)   # q/4 .. 3q/4

So if we can force 31 of the 32 checked bits to fixed, known values regardless of s, and make the 32nd bit depend on exactly one secret coefficient, the oracle's yes/no answer becomes a 1-bit measurement of that coefficient.

Fixing the 31 "carrier" bits

For every checked bit j ≥ 1 we set v[j] deep inside the target region: v[j] = 1665 (compressed y = 16) for a tag-1 bit, v[j] = 0 for a tag-0 bit. Our probe (below) perturbs each bit by at most 2·C0 = 602, comfortably less than the ~832 decode margin, so those 31 bits stay correct for any value of s.

5 Isolating One Secret Coefficient

A monomial u isolates a single coefficient of s. Negacyclic multiplication in Z_q[x]/(x^256+1) means one non-zero term in u touches one term of sTu:

# target coefficient a of the t-th secret polynomial: s[t][a]
u = [[0]*256 for _ in range(k)]
u[t][p] = 185                 # Decompress11(185) = C0 = 301
# p = 0        -> (s^T u)[0] = +C0 * s[t][0]
# p = 256 - a  -> (s^T u)[0] = -C0 * s[t][a]   (negacyclic sign flip)

Now bit 0 of the recovered message is w0 = v[0] − (±C0·s[t][a]). Sweep v[0] across the 5-bit compression grid and watch the oracle flip from "tag valid" to "tag invalid": the flip threshold pins s[t][a] to one of its five possible values.

6 Recovering All 512 Coefficients

Two polynomials of 256 coefficients each: 512 × 4 = 2048 queries, about a minute over the wire. The loop is mechanical once the probe table is fixed:

def recover_coeff(t, a):
    p = 0 if a == 0 else 256 - a          # sign of the isolated term
    sig = []
    for v0 in (3, 6, 9, 11):                # the minimal monotone probe set
        c = build_ct(t, p, v0)                # monomial u + carrier-padded v
        sig.append(oracle(c) == "payload_tag_invalid")
    return SIGNATURE_TABLE[tuple(sig)]         # -> value in {-2,-1,0,1,2}

s = [[recover_coeff(t, a) for a in range(256)] for t in range(2)]

7 Verifying the Key & Unsealing the Export

Sanity-check s before trusting it: recompute the error from the published public key. If max|e| = 2 = eta, the key is exact. Then the vendor's own restore tool derives K_dev, opens the AES-GCM device export, and decrypts the archived session:

$ python3 vk_restore.py \
    --secret-hex <recovered s> \
    --public-key-hex </pubkey> \
    --bundle vk100-session-record.json
[restore] K_dev ok, GCM tag verified, session opened
token: CF26{und3rcl1ff3_d3v_3xp0rt_0p3n3d_jayspvy57167cd6c}

8 Pitfalls

• Margin arithmetic. If the carrier padding is too weak, a large-magnitude secret coefficient can flip one of the 31 fixed bits and the oracle answer becomes noise. Keep the total per-bit perturbation (2·C0) well under the decode margin.
• Negacyclic sign. Targeting a ≥ 1 uses p = 256 − a and flips the sign of the isolated term; get that wrong and every non-zero coefficient reads negated.
• The "support bundles" trap. Time spent grepping the CSV/config bundles for a key is wasted — reading the seal construction (K_dev = … || SK || …) tells you the key must be recovered, not found.

9 Key Lessons

• Monomial ciphertexts isolate one coefficient. u = C0·x^p plus big-margin carrier padding turns a 32-bit tag oracle into a clean one-coefficient threshold read.
• Pick a minimal, monotone probe set. Four v[0] indices distinguish all five secret values — an 8× cut over sweeping the whole compression grid.
• Validate offline first. The shipped bench-key fixture let us build and verify the oracle and the coefficient mapping before spending a single network query, so the live run was 2048 deterministic requests, not a search.

Tools: veilkey.py SDK (compress/decompress, decrypt for the local oracle model), vk_restore.py, requests.