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

ADKEX (Authenticated Ding Key Exchange) (kex-01)

kex-01-1: The stated no-matching-session theorem admits trivial distinguishers

Original source: Sun's PKC Forum post Follow-up source: DKEM / DKEX / ADKEX team's confirmation; Xuanzhi-assisted ADKEX evaluation

The specification defines a fresh session with no matching session and claims key indistinguishability for every such session (pages 31–32). The proof following Theorem 5.1 says that this case "can be proven similarly" to its matching-session wPFS case. This is false for the responder role. An active initiator claims an honest initiator's identity, satisfying the stated freshness condition, then chooses its ephemeral key and encapsulation, decapsulates the responder's reply, and knows the public transcript. It therefore computes the responder's real session key and distinguishes it from random with advantage 1/2 without a Reveal, StateReveal, or Corrupt query.

This does not attack an honestly matched exchange. It shows that the claimed no-matching-session case fails to account for the deliberately unauthenticated initiator: the theorem needs a role-scoped authentication goal rather than the stated all-session claim.

A later forum evaluation gives another counterexample under the literal freshness predicate: Corrupt(B) is an allowed query but is never listed among the exclusions on physical p. 31. With B's static key, an attacker can impersonate B to an honest initiator A and compute both KEM contributions to A's no-matching-session key. This reading depends on the undefined phrase “honest peer”: if it means an uncorrupted peer, the corruption would instead make the session ineligible. The ambiguity concerns the same overly broad no-matching-session claim, not a separate break of an honestly matched exchange.

Reproducing

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

Apply the experiment on physical PDF pages 31–32 to a completed responder session created by an active initiator. The session has no matching honest initiator session and remains fresh under the listed exclusions, while the initiator possesses all three inputs to the responder's KDF.

kex-01-2: ADKEX-512 silently derives different keys in honest sessions

Original source: Sun's PKC Forum post Follow-up source: DKEM/DKEX/ADKEX team's PKC Forum response

ADKEX-512 inherits signed 16-bit arithmetic from its DKEM backend. Rare intermediate overflows make the two parties derive different shared secrets even though every API call reports success. A fresh deterministic run found the first mismatch at trial 148; a separate 3,000-session run found two mismatches. Identical controls over 3,000 ADKEX-128 and ADKEX-256 sessions found none.

This contradicts the specification's correctness condition, which requires matching honest sessions to output the same key except with negligible probability. It is Low because the demonstrated effect is a silent reliability failure, not key recovery or an authentication bypass.

Follow-up Analysis

The team confirms 20 handshake failures in 20,000 ADKEX-512 reference sessions. Its instrumentation found that overflow and failure depend only on the public received ciphertext, not the long-term secret; the submitted AVX2 backend is unaffected, while NEON and Cortex-M4 share the defect.

Proposed fixes

The team's fix commit proposes additional forward-NTT reductions in the scalar, NEON, and Cortex-M4 paths. 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-01 reproduce-correctness

The witness uses the submitted API and prints CONFIRMED kex-01-2 at the first honest ADKEX-512 mismatch.

kex-01-3: Incoming message lengths are ignored before fixed-size reads

Original source: Sun's PKC Forum post Follow-up source: DKEM / DKEX / ADKEX team's confirmation

kex_generate_pass2_msg_b discards m1_len_bytes, and kex_derive_ss_a discards mb_len_bytes, before parsing the supplied pointer as a complete fixed-size protocol message (KEX_AlgorithmInstance.c:79–101 and 121–134). A one-byte pass-1 allocation reaches a 32-byte read 767 bytes beyond that allocation at dkecca.c:60; AddressSanitizer traces it through ADKEX_pass2_msg_b_derand and the public pass-2 API.

Without a protected allocator boundary, adjacent heap bytes are consumed by encapsulation, transcript hashing, and key derivation while the API still returns success. The out-of-bounds ct_S is also passed to decapsulation at adkex_derand.c:78. The returned message contains a KEM ciphertext and derived transcript values rather than the adjacent bytes themselves, and no recovery channel has been demonstrated. The confirmed impact is therefore an attacker-triggered out-of-bounds read, with no demonstrated memory disclosure or control-flow impact, hence Low.

The team independently reproduced the AddressSanitizer finding and reports that the same missing-length pattern was present in DKEX and DKEM.

Reproducing

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

make -C kex-01 reproduce-truncated
make -C kex-01 clean-reproducers

The first command builds the submitted ADKEX-128 source with AddressSanitizer, supplies a one-byte message with length one, checks for the heap-buffer-overflow trace, and prints CONFIRMED kex-01-3.

kex-01-4: A copied certified responder key permits identity misbinding

Original source: Xuanzhi-assisted ADKEX evaluation

ADKEX says its transcript hash binds identities and prevents unknown-key shares (specification physical pp. 5, 7). But its specified T = H(LABEL || pk_B || m1 || m2) (Algorithm 20, physical p. 23) and all three byte-identical reference binders (adkex_derand.c:10–25) contain no identity. If Eve registers Bob's certified public key under Eve's name, an initiator accepting that registration can complete an exchange with Bob while naming Eve as the peer; both derive the same key. This requires duplicate-key certification, outside the specification's distinct-key formal setup, so it is an identity-binding gap rather than an in-model key-recovery attack.

Reproducing

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

make -C kex-01
python3 kex-01/reproduce_identity_alias.py

The native witness checks all three levels: a duplicated-key alias agrees with the real responder, while an independently generated responder key used as a control does not produce an equal key.