Security › kex-02 · Constant-time review · Performance: x86_1 · arm_1

AFS-KEX (kex-02)

kex-02-1: The ephemeral key is generated once as long-term state

The specification requires fresh AFS ephemeral key material for each session and claims completed-session forward secrecy after later compromise of long-term keys.

The uniform wrapper instead generates seed_e and calls the ephemeral key generator inside kex_init_self. It embeds the resulting pk_e/sk_e into the composite public and secret keys returned as the party's long-term material and stores seed_e in the persistent state. Later pass functions reuse that material and never generate a fresh per-session ephemeral key.

This gives a direct completed-session key-recovery attack. A passive attacker records m1 = ct_B and the ct_A prefix of m2. After the session completes, compromise of the two API long-term secret keys exposes csk_B and csk_A in their first halves. The attacker decapsulates the recorded ciphertexts to recover K_B and K_A, then computes the public session KDF XOF(K_B || K_A). The result is the exact erased session key. No cryptanalysis or search is required.

Ephemeral AFS keys must be generated for each protocol execution, kept outside long-term key serialization, and erased when the session completes.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C kex-02 exploit
kex-02/reproduce_pfs_break
kex-02/reproduce_pfs_break_c256
kex-02/reproduce_pfs_break_c512

The three drivers complete honest C128, C256, and C512 exchanges, erase both session-state buffers, and recover each session key using only the recorded first two flights and the subsequently compromised API long-term keys. They also check that the true static-key halves alone do not recover the key.

ATTACK kex-pfs-recovery AFS_KEX_C128 CONFIRMED recorded m1/m2 plus later API long-term-key compromise recovered erased session key 1218217aea48c0aee27983653641600a (static-only control differs)
ATTACK kex-pfs-recovery AFS_KEX_C256 CONFIRMED recorded m1/m2 plus later API long-term-key compromise recovered erased session key 40076703841413297c9105f888a439d48f6015ab23774c9539b3ce6e19eeff5e (static-only control differs)
ATTACK kex-pfs-recovery AFS_KEX_C512 CONFIRMED recorded m1/m2 plus later API long-term-key compromise recovered erased session key 12033302a024a20f0d4498daafdc87c3c91d7c9b7479be51280d1cacf286a0b9eab8d3593771c3260f60eaf02cdc4101b3828a0e4d9ebc3bbe742aee77830a1f (static-only control differs)

kex-02-2: Secret-derived decryption coefficients take a sign branch

The C128 KEM decapsulator decrypts the ciphertext using the secret polynomial, forming mp = v - skpv*b (indcpa.c:354-364). Message conversion then branches on the sign of each secret-derived centered coefficient (poly.c:174-193). This exposes a key- and ciphertext-dependent branch pattern on repeated decapsulation. C256/C512 use different conversion code and are not included in this finding. A KyberSlash-style full-key attack would also need an observable per-coefficient oracle and a chosen-ciphertext recovery argument; neither has been demonstrated here, so this is not rated Critical. See constant_time.md for the data-flow trace.

Constant-time fix (easy, hence Low): derive each message bit from the coefficient with arithmetic masks, as in Kyber's poly_tomsg, instead of branching on its sign.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

The reference Makefile uses -O2. On x86-64 GCC, the following prints the conditional jns in the compiled C128 poly_tomsg path:

cd 'kex-02/Implementations and Test_Vectors/Implementations/Reference_Implementation/AFS_KEX_C128'
gcc -O2 -std=c99 -I. -DBWKEM128_INTERNAL_COMPAT -DBWKEM_C128_USE_ICCS_AUXFUNC -S -o - poly.c | sed -n '/bwkem128_poly_tomsg:/,/\.size[[:space:]]*bwkem128_poly_tomsg/p' | grep -E '\bjns\b'

The source-level secret dependency is the indcpa_dec → poly_tomsg chain above; the assembly check confirms that this particular compiler/build does not erase the branch. No timing-based key recovery is claimed.

kex-02-3: Leaking one in-session encapsulated key permits initiator impersonation

Original source: Xiong and Wang's PKC Forum post Follow-up source: AFS-KEX team's initial statement, response, and further response

Figure 3 authenticates an initiator by extracting pk'_A = cpk_A - t_e(seed_A) and checking CAVerf(id_A,pk'_A). Given Alice's public key, an attacker can choose its own seed* and publish cpk* = pk_A + t_e(seed*); extraction then returns Alice's certified public key. If the in-session encapsulated key K_A is exposed, the attacker completes the remaining exchange, derives K_SESSION = PRF(K_A,K_B), and is accepted by Bob as Alice. Alice does not participate, and no secret of hers other than the assumed K_A exposure is used.

This demonstrates the consequence of exposing an in-session encapsulated key, but it does not contradict the formal proof. Section 9.1 limits RevealEph to ephemeral material that can be precomputed offline, assumes encapsulation randomness is erased, and Remark 9.1 discusses retained precomputed keys rather than the in-session K_A used here. The same exposure defeats the authentication role of the KEM contribution in many KEM-authenticated AKEs. The confirmed protocol behavior is therefore a Medium model-boundary finding, not a break of AFS-KEX's stated primary game.

The spec-faithful protocol witness built from each submitted reference primitive succeeds in 200 of 200 trials, derives Bob's exact session key, and is rejected in 200 of 200 controls without the K_A exposure.

Follow-up Analysis

The AFS-KEX team states that its intended model excludes arbitrary exposure of in-session ephemeral state and characterizes the protocol as ephemeral KEX. That position is consistent with the report's model-boundary classification; it does not change the reproduced impersonation behavior under the stated exposure.

Proposed fixes

The original post proposes correcting the public description of which secret authenticates the exchange. This section records the proposal without evaluating it.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C kex-02 reproduce-protocol-findings

The pinned wrapper runs the protocol experiment at C128, C256, and C512 and requires both exact key agreement and the no-leak rejection controls. It prints ATTACK kex-02-3 ... CONFIRMED.

kex-02-4: A copied certified public key enables an unknown-key-share

Original source: Xiong and Wang's PKC Forum post Follow-up source: AFS-KEX team's response and further response

The protocol derives K_SESSION = PRF(K_A,K_B). Neither party identity enters that KDF or a MAC. An attacker Eve registers a copy of Alice's public key under Eve's identity, relays an Alice–Bob exchange, and changes the cleartext id_A in round 3 to id_E. Alice accepts Bob, Bob's certification check accepts the same public key for Eve, and Bob accepts Eve; both honest parties derive the same key while disagreeing about its peer identity. The defect is specifically that the peer identity is not bound into the derived key.

The witness reproduces this unknown-key-share in 200 of 200 sessions at every parameter set using only public-key copying and message relay. The specification says authentication is obtained through public-key recovery and certification, but the formal Setup generates distinct honest public keys and excludes duplicate-key registration. Because the attack depends on a certification policy outside that model, it is a Medium identity-binding gap rather than a break inside the stated game.

Follow-up Analysis

The team states that its certification model disallows duplicate public-key registration and that, in a deployment permitting it, identities should enter the key derivation. This agrees with the report's stated precondition and does not change the reproduced behavior under that precondition.

Proposed fixes

The original post proposes including id_A, id_B, and a transcript hash in the session-key PRF. This section records the proposal without evaluating it.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C kex-02 reproduce-protocol-findings

The pinned wrapper runs the copied-key relay at C128, C256, and C512 and requires equal keys together with different recorded peer identities. It prints ATTACK kex-02-4 ... CONFIRMED.

kex-02-5: An unauthenticated responder observes decapsulation failures

Original source: Xiong and Wang's PKC Forum post Follow-up source: AFS-KEX team's response and further response

The KEM uses implicit rejection, and the initiator sends round 3 for both valid and invalid ciphertexts. An unauthenticated responder nevertheless knows the valid ciphertext's encapsulated key. It can decrypt the returned protected seed with the key derived for the valid path and check whether that seed reconstructs the initiator's certified public key. After a ciphertext modification triggers implicit rejection, this check fails, revealing the decapsulation-validity bit even though the message flow is unchanged.

At each parameter set, the validity check succeeded for 200 of 200 honest ciphertexts and failed for 200 of 200 deliberately modified ciphertexts. This confirms the observable reaction bit, not a recovery attack. The specification already argues that a fresh composite key permits at most one relevant failure observation per session. Aggregating useful conditions across independently refreshed composite keys has not been validated, and no natural-failure run or long-term-key recovery is claimed.

Follow-up Analysis

The team emphasizes that the composite public key changes each session and argues that the resulting failure observations cannot be accumulated against one key. That is already the limitation stated here; no cross-session recovery is claimed.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C kex-02 reproduce-protocol-findings

The pinned wrapper checks the honest and injected-failure seed-recovery controls at C128, C256, and C512. It prints ATTACK kex-02-5 ... CONFIRMED.

kex-02-6: Failure terms make the stated QROM bounds non-tight

Original source: PKC Forum AFS-KEX evaluation, PROOF-002

Theorem 9.3 (physical p. 61) includes 16 N S² δ in the pMAKE key-secrecy bound. Theorem 10.6 (physical p. 65) includes 5 N S² δ for pUAKE in the QROM. Both require the underlying AFS-KEM to be δ-correct; Table 1 (physical p. 17) supplies its δ_AFS estimates. Even with N=S=1, C128's stated δ_AFS=2^-67.98 leaves at most 63.98 and 65.66 bits of proof-bound margin against the 80-bit quantum target. The corresponding pMAKE/pUAKE margins are 118.24/119.92 at C256, 162.17/163.85 at C384, and 120.13/121.81 at C512, below their 128-, 192-, and 256-bit quantum targets. C128-s and C512-s also miss; C256-s and C384-s do not miss through this term alone. More parties or sessions enlarge the stated terms.

This is an insufficient reduction, not evidence of an efficient attack or a measurement of the true failure rate. The failure-term loss is a generic property of this proof form; no candidate-specific recovery route follows. It is recorded as Info, separately from any observed per-ciphertext failure reaction. The candidate's deliberately high stated DFR merits further analysis, but the bound alone does not establish a vulnerability.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kex-02/reproduce_failure_bound.py

The arithmetic certificate recomputes all eight BW-set bounds from transcribed Table 1 values at N=S=1; check the theorem text and values in the frozen PDF separately. It does not measure failures or execute a protocol attack.

kex-02-7: Incoming message lengths are ignored before fixed-size reads

Original source: NGCC harness issue 32

The receive-side pass-2, pass-3 and pass-4 functions accept m1_len_bytes, m2_len_bytes and m3_len_bytes respectively, then discard them. Passes 2 and 3 feed the caller buffers into fixed-size KEM decapsulation; pass 3 also reads the seed suffix of m2, and pass 4 reads m3[i] for every seed byte (KEX_AlgorithmInstance.c, all three trees). A peer can supply a one-byte buffer with its true length, yet the wrapper proceeds to read the expected full message. The reporter observed AddressSanitizer errors; our certificate confirms the source path, not the precise runtime crash or any disclosure.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kex-02/reproduce_short_messages.py

The source certificate checks all three receive functions in all three submitted parameter sets. It does not execute malformed exchanges.