PQC-XXJTLU · cryptanalysis

Home › Public-key schemes › Loom

Key exchange · lattice

Loom

Implementation

Bugs in the submitted code; the specification is sound on these points.

loom-i1

The initiator's ephemeral decapsulation key survives a rejected response, so pass 3 can be retried on the same state

Minor break · Argued · Cause: code

Property: key recovery

Cost against claim: on the order of 103 retries on one reused initiator state recover dk and that session's key (costed, not run)

In the reference Loom-AKE, a failed decapsulation leaves the initiator's ephemeral KEM key dk in place: the native context stays in its waiting state and the NGCC API leaves the caller's pass-1 state blob byte for byte unchanged, so one dk can process any number of responder messages. A caller that retries on that state hands an active attacker a plaintext-checking oracle, at most one bit per attempt, from which dk follows after on the order of 103 attempts, and with it the key of the session whose honest ciphertext was withheld. dk is not erased after a successful decapsulation either.

Parameter setClaimAttack costVerdict
LoomKEX-128IND-CCA of the session, 128 classicalabout 103 retries on one state (s carries about 1.5 x 103 bits); costed, not runMinor break
LoomKEX-256IND-CCA of the session, 256 classicalon the order of 103 retries on one state; costed, not runMinor break
LoomKEX-512IND-CCA of the session, 512 classicalseveral 103 retries on one state (s carries about 6.6 x 103 bits); costed, not runMinor break

What causes it

Section 4.1.5 (p. 33) and section 4.4 (p. 48) require dk to process at most one KEM ciphertext and to be erased after it, whether decapsulation succeeds or returns failure, enforced by the implementation's state machine; the simulation in Theorem 4.13 (pp. 36 to 37) relies on it. The reference enforces none of it, identically at the three levels: crypto_loom_auth_init (loom/loom.c) returns an error on a failed decapsulation with its state and skkem untouched, destroy_ctx frees without wiping, the NGCC adapter kex_generate_pass3_msg_a wipes only its own copy and leaves the caller's PASS1 blob, and loom_kex_ctx_pack serialises skkem at every stage. The signed transcript covers only the accepted ciphertext, so rejected attempts leave no trace, and the specification's own advice of a simple protocol-level retry after decryption failures (p. 5) invites the reuse.

Evidence

Behavioural test on the unmodified reference at the 128 and 512 levels: one initiator context processed 1000 distinct tampered responder messages under the same dk, all rejected with state and dk unchanged, then accepted the honest message and completed the handshake with equal shared secrets. Through the NGCC API, the caller's pass-1 blob stayed identical over 20 failed pass-3 calls and then completed with the honest message, and the pass-3 blob after success still carries dk. The key recovery itself was costed, not run. A second member of PQC-X rebuilt the reference from a checked copy, reproduced the official KATs byte for byte, wrote and ran these tests and re-ran the attacker's state check.

Cause in the submitted code; the specification is not affected.

Limits

The submitted KAT harness aborts on the first error. Exposure needs a caller that waits for another responder message on the same state, which the API permits and the retry advice suggests but section 4.4 forbids; a small retry cap removes it. The payoff is one session's key, not a long-term key.

Credit

First public report: M.-J. Saarinen (ngcc.dev kex-05-2, 2026-09-21). Found independently by PQC-X.

loom-i2

The reference draws the ephemeral secret r from PRF streams the public-key lifting also reads

Holds · Demonstrated · Cause: code

Property: IND-CCA security

Cost against claim: conformance defect carried by the KATs; noise variance unchanged within 0.04%, DFR moved by about 0.01 bit

During encapsulation, the randomized lifting of the public key should use PRF nonce 0 and r nonces 1 to k; in the reference the lifting runs through nonces 0, 1, 2 and on, so most r polynomials are sampled from bytes the lifting also reads: 4 of 5 at level 128, 3 of 4 at 256, all 4 at 512. The official KATs carry the deviation. No security consequence was found: the shared bytes are fresh per-encapsulation coins, never output, and exploiting the correlation requires r itself.

Parameter setClaimAttack costVerdict
LoomKEX-128disjoint PRF streams, 128 classical4 of 5 r polynomials share PRF bytes with the lifting; no measurable effectHolds
LoomKEX-256disjoint PRF streams, 256 classical3 of 4 r polynomials share PRF bytes with the lifting; no measurable effectHolds
LoomKEX-512disjoint PRF streams, 512 classical4 of 4 r polynomials share PRF bytes with the lifting; no measurable effectHolds

What causes it

Algorithms 11 and 12 (pp. 10 to 11) give the lifting nonce 0 and r nonces 1 to k, and Game 2 of Theorem 4.4 (pp. 24 to 25) needs them distinct so that the lifting is independent of r. In kem/indcpa.c the lifting receives nonce 0, but polyvec_invq (kem/poly_invq.c) takes it by value and increments its own copy per polynomial and inside its rejection loop, while the caller goes on to 1 to k for r. The SM3 counter-mode PRF does not bind the output length, so the shorter stream is a prefix of the longer. The same core code is shared with Weaver.

Evidence

gdb traces of every PRF call in the unmodified official KAT executables at the three levels showed identical prefixes of 64, 136 and 272 bytes between lifting and r streams. A paired experiment on one key, the unmodified code against a control whose lifting reads independent nonces, over 12.8 to 25.6 million coefficients per level: decryption noise variance agrees within 0.04%, tails within counting error, and no per-position bias appears. Run by a second member of PQC-X, who also found the overlap wider at level 512 than first reported.

Cause in the submitted code; the specification is not affected.

Limits

Theorem 4.4 as written does not cover the implemented sampling, and an implementation following Algorithms 11 and 12 would not reproduce the KATs; no distinguisher, bias or change in failure rate was found.

Credit

Found by PQC-X.