AFS-KEX

The wrapper draws one ephemeral key at initialisation and reuses it in every session, so completed sessions lose forward secrecy

Minor break · Demonstrated · Cause: code

Property: forward secrecy

Cost against claim: session key recomputed from the recorded transcript and the long-term secret keys, against the perfect forward secrecy claimed

The submitted wrapper draws the ephemeral seed inside kex_init, folds the ephemeral key into the composite key pair that it returns as the party's long-term key, and no message pass ever draws a new one: the composite decapsulation key is the same in every session. A passive adversary records the two ciphertexts of a session; once it later holds the two private keys as the interface outputs them, it decapsulates both ciphertexts and recomputes the session key exactly. The protocol also discloses each party's frozen ephemeral seed to its peer, so an adversary who once completed a session with each of two parties needs only their certified static keys to recover every past session key between them.

What causes it

Fig. 3 and §2.2 sample seed_A in Round 1 and seed_B in Round 2 of every session, and characteristic 9 (§1.3, §2.7) rests on that freshness; the security proofs cover that protocol. §4 then describes the profile submitted under the NGCC interface, in which each party holds the peer's combined public key cpk before the handshake, and the code implements that profile: kex_init_self (KEX_AlgorithmInstance.c, lines 56 to 108) draws seed_e, forms csk = s_s + s_e and cpk = t_s + t_e, exports (cpk, pk_s) as the public key and (csk, cpk, id, z, sk_s) as the private key, and keeps seed_e in the state. The pass functions draw fresh encapsulation coins only, and the EKeyGen calls of passes 3 and 4 merely rebuild the peer's ephemeral key for the binding check. The message sizes of Table 6 (768, 784, 16 and 0 bytes at C128) follow from cpk never being sent. The interface cannot refresh the ephemeral key: a second kex_init also replaces the certified static key, and a fresh seed written into the state makes the peer's binding check fail.

Evidence

Run on the reference AFS-KEX-C128 build, rebuilt from the submission with the official test vectors reproduced byte for byte. Two sessions from one kex_init transmit the same composite public key, and the session key recomputed from the recorded transcript and the two exported private keys equals the true session key (an exact 128-bit match). A second member of PQC-X rebuilt the code, re-ran both programs with identical logs, and ran an independent test: both sessions complete, the seed each party discloses to its peer is the same in both sessions and equals the one stored by kex_init, the composite secret key equals the static secret plus the ephemeral secret derived from that seed, a second kex_init changes the static key too, and a fresh seed placed in the state makes pass 4 fail. The fifteen copies of the wrapper (reference, AVX2 performance and resource variants, Cortex-M4; three sets each) are identical, which carries the finding to AFS-KEX-C256 and AFS-KEX-C512.

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

Limits

The protocol of Fig. 3, which the security proofs cover, is not affected: with an ephemeral key drawn in every session the attack disappears. The behaviour was run on AFS-KEX-C128 only; the C256 and C512 wrappers were checked identical in source.

Designers' response

On the NGCC public-key forum (2026-09-22) the designers acknowledged that the wrapper generated the composite and ephemeral key pairs at initialisation, and announced a revised implementation that draws them inside the message passes, keeps the session secrets in the session state and erases them afterwards. PQC-X has not checked it.

Credit

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

The frozen composite key exposes about 2⁶ decryption failures of AFS-KEX-C128 within the call's query budget

Holds · Argued · Cause: code

Property: resilience to decryption-failure attacks (characteristic 7); key recovery not costed

Cost against claim: about 2⁶ observable failures per 2⁸⁰ decapsulations under one composite key, against at most one per key

The designers accept a failure rate of 2^-67.98 per session at C128 because a fresh ephemeral component changes the composite decapsulation key every session, so that an adversary observes at most one failure per key. In the submitted code the composite key never changes, and a peer holding a certified key of its own, running sessions with the victim, knows the encapsulated keys of each session and can tell from the victim's seed ciphertext whether the victim's decapsulation succeeded, since that ciphertext decrypts to the victim's frozen seed (which every peer learns) exactly then: one bit per session, for a ciphertext of the peer's choice. With the decoder actually implemented, an honest ciphertext fails with probability about 2^-74.2, so about 2⁶ failures are observable within the 2⁸⁰ decapsulations the call allows, and failure boosting would raise the yield; recovering the key from them was not costed, so no claim on the key falls.

What causes it

§3.2 argues that for any fixed combined key the adversary observes at most one decryption failure, because the ephemeral component is drawn afresh in every session (Fig. 3), and Table 1 lists δ_AFS = 2^-67.98 for the base C128 set on that understanding. The wrapper keeps one composite key for good (afs-kex-i1). Decapsulation uses implicit rejection, so a failure is not an abort: it shows in the seed ciphertext, which decrypts to the frozen seed exactly when decapsulation succeeded.

Evidence

A second member of PQC-X recomputed the failure rate at C128 by an exact per-coefficient convolution of the decryption noise (q = 3329, du = 10, dv = 4, composite secret CBD(6) + CBD(6)), taking the eight coefficients of a block as independent, and modelled the implemented decoder as the exact nearest-codeword decoder of the [8,4,4] code (a scaled E8 lattice, 240 relevant vectors). Table 1's 2^-67.98 matches the inscribed-ball criterion of Theorem 7.2 with e1 drawn from CBD(5), as Fig. 1 reads; the code draws e1 from CBD(6) (indcpa.c), and with the implemented decoder the composite-key rate is about 2^-74.2 (2^-62.0 under the ball criterion), hence about 2^5.8 failures expected in 2⁸⁰ honest decapsulations (2¹⁸ under the ball criterion). The oracle rests on the frozen key of afs-kex-i1, run on the C128 build.

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

Limits

No key recovery from the failures was run or costed: the observation records that the designers' argument for characteristic 7 no longer applies to the submitted code at C128. AFS-KEX-C256 and AFS-KEX-C512 (2^-122.24 and 2^-124.13 per session) give no failure within 2⁸⁰ decapsulations and are not affected, nor is the protocol of Fig. 3.

Credit

Found by PQC-X, extending an observation by M.-J. Saarinen (ngcc.dev kex-02-1, 2026-09-21): the ephemeral key generated once and kept as long-term state.