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

CreTAKE (kex-03)

kex-03-1: Bits-versus-bytes error reduces the ephemeral secret to 64 bits

Follow-up source: CreTAKE team's 2026-10-10 reply

The responder requests 64 bytes (512 bits) of fresh randomness:

get_random_number(&drng_algorithm, buf, SEED_BYTES * 8ULL)

It then expands that value with:

pseudoXOF((MSG_LEN_BYTES + SEED_BYTES) * 8, buf, SEED_BYTES, buf2)

The third pseudoXOF argument is a bit count, but SEED_BYTES is 64. Only the first eight bytes of the 64-byte buffer are absorbed. The correct SEED_BYTES * 8 form appears commented out immediately above related call sites. The erroneous pattern occurs in 23 reference source files and is preserved by every submitted test vector.

In the six S2S instances, this 64-bit value is the only secret input to the session-key computation. A passive eavesdropper enumerates the 2^64 possible inputs, regenerates the deterministic encryption coins and candidate plaintext, and matches the observed ciphertext. This recovers the session key offline at every claimed 128-, 256-, and 512-bit level.

Reproducing

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

This is a source and key-space review; a 2^64 search is not run. Fetch the official archive and inspect the responder call in, for example, CreTAKE128/CreTAKE-S2S-BiT128-eZEN128/KEX_AlgorithmInstance.c line 156. The second pseudoXOF length argument is 64 bits, not the intended 64 bytes.

IDS=kex-03 ./download.sh
./extract.sh kex-03
rg -n -F 'buf, SEED_BYTES, buf2' kex-03/Implementations/Reference_Implementation

The same defect reduces the claimed weak forward secrecy of K2S and S2K instances to 2^64 after compromise of the complementary long-term KEM key. This is an implementation error, not a cryptanalytic attack on the specified primitives.

Extended on 2026-10-17: five of the 23 files are the generic K2K double-key encapsulation twokem_enc (CreTAKE128/CreTAKE-K2K-PLAC128/twokem.c:87–90, CreTAKE256/CreTAKE-K2K-PLAC256/twokem.c:84–87, CreTAKE128/CreTAKE-K2K-ZEN128/twokem.c:85–88, CreTAKE256/CreTAKE-K2K-ZEN256/twokem.c:81–84, CreTAKE512/CreTAKE-K2K-ZEN512/twokem.c:81–84). There, the 64 absorbed bits determine the second-component message m and its encryption coins under the initiator's ephemeral p̃k, and m enters the double-key KEM secret k_i = H(pk_i‖K1‖m) (ZEN128 twokem.c:96–100). K2K claims weak forward secrecy (Figure 3, Theorem 3 and §4.2; physical pp. 10, 25 and 18). Consider an honestly matched K2K session whose two long-term keys are corrupted afterwards. The attacker decapsulates c1 with sk_i to obtain K1 and decapsulates c_j with sk_j to obtain k_j. It then enumerates the 2^64 inputs, identifies the correct one by re-encrypting the second component under the public p̃k, and computes the session key without the ephemeral secret key. K2K weak forward secrecy is therefore 2^64 at every claimed level. The K2K-PLAC512 and K2K-PLAC512Star encapsulations do not contain this call.

sh kex-03/reproduce_k2k_wpfs.sh

The K2K reproducer checks the five twokem.c call sites. It then builds unmodified K2K-ZEN128 and K2K-ZEN512 objects in a temporary copy and shows that changing bytes 8–63 of the 64-byte draw leaves the transcript and the key unchanged. After both long-term keys are corrupted, a reduced 2^16 search recovers the session key, with the other 48 of the 64 bits supplied as a hint. Flipping one hinted bit gives no match. It runs in about 25 seconds and does not perform the full 2^64 search.

Proposed fixes

The CreTAKE team's 2026-10-10 reply says it corrected the affected hash/XOF bit-length arguments in a revision to be released at the next permitted update. This is recorded without evaluating the revision.

kex-03-2: Omitting signatures from the KDF breaks transcript matching

Original source: ManojG's PKC Forum post Follow-up source: CreTAKE team's response

CreTAKE says its KDF binds the complete public transcript and claims IND-AA or IND-StAA security for the four frameworks (§4.1). However, Figures 1, 2, and 4 include signature bytes in the exchanged messages while their KDF inputs omit those signatures. The reference implementation does the same in every signature-bearing instance.

An adversary corrupts the signature-credential holder and replaces its valid signature with a distinct valid signature on the same authenticated string. It chooses that holder's session as the test session, without revealing its state; this is not excluded by the adopted IND-(St)AA game. The peer accepts, but the two sessions are non-matching because their complete wire transcripts differ. Their KDF inputs and session keys are nevertheless identical. Revealing the non-matching peer session therefore supplies the test session's real key and distinguishes it from random. This is a polynomial-time break of the claimed AKE security, hence Critical; it requires no signature forgery.

The submitted BiT signer is randomized. Two calls with the same key and message readily produce distinct signatures that both verify, so the condition needed by the attack holds in the concrete instances rather than only for a contrived EUF-CMA scheme.

Proposed fixes

The CreTAKE authors' revised KDFs, as quoted in the original post, include the signature bytes in the transcript hash. This section records the proposal without evaluating it.

The later team response says its revised reductions carry the complete signed messages through the games and announces separate framework-and-role tags when credentials are shared. These proposals are recorded without evaluating them.

Reproducing

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

make -C kex-03 lib/libCreTAKE-K2S-PLAC128-BiT128.so
python3 kex-03/reproduce_binding_attacks.py

The witness checks all 18 KDF implementations, generates two distinct valid BiT signatures on one string, and shows the resulting distinct transcripts retain the same KDF input and key.

kex-03-3: The generic double-key KEM fails its claimed first-key CCA game

Original source: ManojG's PKC Forum post Follow-up source: CreTAKE team's response

Figure 7 derives the double-key KEM output as h(pk1,K1,m'), omitting the second public key and both ciphertext components. The five generic twokem.c implementations reproduce this construction. It is not [IND-CCA,IND-CPA] secure under Definition 8.

The first-key CCA game lets the adversary obtain two generated second-key pairs. For the challenge (c1*,c2*) under pk2*, it decrypts c2* with the leaked sk2*, re-encrypts the recovered m' under the other leaked pk2', and asks the permitted CCA query (pk2',(c1*,c2')). Decapsulation recovers the unchanged K1 and m', so it returns exactly the challenge key. The adversary distinguishes with overwhelming probability without learning the first secret key.

This breaks an explicitly claimed component property. The outer K2K framework hashes the complete AKE transcript, so the post does not establish a session-key attack on CreTAKE-K2K itself; the finding is therefore High rather than Critical.

Proposed fixes

The original post proposes deriving the key from a domain-separation tag, both public keys, both ciphertexts, K1, and m'. It does not supply a proof. This section records the proposal without evaluating it.

The team separately proposes K = h(pk', K1, m', c) with the complete two-part ciphertext and says it will revise Figure 7 and the component proof. This proposal is recorded without evaluating it.

Reproducing

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

python3 kex-03/reproduce_binding_attacks.py

The witness checks the five submitted generic implementations and executes the cross-key query algebra with a correctness-preserving PKE model. The attack depends only on PKE correctness and on the displayed KDF inputs.

kex-03-4: Initiator length-unit error removes the NAXOS long-term-key binding

Original source: Xiong and Wang's PKC Forum post and pinned verification package

The initiator hashes r || sk_i with a byte count passed to a bit-length API (for example reference CreTAKE-S2S-BiT128-eZEN128/KEX_AlgorithmInstance.c:117,187 and CreTAKE-S2K-BiT128-PLAC128/KEX_AlgorithmInstance.c:124,204, against auxfunc.c:460; the other S2K and S2S instances make the same calls at nearby lines). It absorbs all 64 bytes of r but only 177, 464, or 1,072 bytes of the BiT secret key. Those bytes are exactly a public-key prefix. A permitted initiator StateReveal therefore supplies the only nonpublic input: the attacker regenerates the ephemeral wKEM key, decrypts the transcript, and derives the session key without search.

This contradicts the specification's state-reveal argument (physical pp. 19–20; Theorems 2 and 4 on physical pp. 23–26). All 12 reference instances recovered 20/20 keys. Changing the length to bits gave 0/20, while correcting only the responder's expansion length left recovery intact. Source inspection confirms the same call in all 12 optimized wrappers; four optimized ZEN runs hit an unrelated alignment crash on this host.

Proposed fixes

The CreTAKE team says it corrected the affected hash/XOF input lengths in a revision to be released at the next permitted update. This is recorded without evaluating the revision.

Reproducing

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

./kex-03/reproduce_naxos_and_lengths.sh

kex-03-5: Ignored KEX message lengths cause pre-authentication out-of-bounds reads

Original source: Xiong and Wang's PKC Forum post and pinned verification package

The KEX wrappers parse fixed-size fields while discarding the caller's m1_len_bytes or m2_len_bytes. In K2S, for example, a buffer allocated to the attacker-supplied length is passed to PKE code that reads the fixed TPK_LEN; K2S and K2K reach these paths before authentication.

With buffers sized to the bytes received, AddressSanitizer reported invalid reads for all 150 tested truncations across the 25 reference instances. No out-of-bounds write, memory disclosure, or control-flow consequence was demonstrated, so this is Low.

Proposed fixes

The CreTAKE team says it will check expected message lengths before parsing or invoking the underlying primitives. This proposal is recorded without evaluation.

Reproducing

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

./kex-03/reproduce_naxos_and_lengths.sh

kex-03-6: POLARLAC reference and optimized vectors derive different shared secrets

Original source: LK-PQC-Hunter's PKC Forum post Follow-up source: PolarLAC team's 2026-10-11 response

In the frozen official archive, each of the 13 POLARLAC-based reference and optimized KAT pairs starts with the same 64-byte seed but records a different shared secret. All 12 ZEN-based pairs agree under the same check. For example, K2K-PLAC128's first reference and optimized SS fields begin 8DA4C53F and 35C82311. We independently checked the archive's published SHA-256 and these vector fields. The forum additionally reports that mixed reference/optimized parties complete derive but obtain different keys on 4/4 seeds. That protocol experiment was not rerun here; the archived vectors alone establish inconsistent submitted implementations, not which one is correct. This is a Low interoperability defect.

Proposed fixes

The CreTAKE team said the PolarLAC team would correct the underlying incompatibility. The PolarLAC team now reports revised NTT, sampling and serialization conventions, with cross-implementation tests. These changes are recorded without evaluating the revised candidate.

Reproducing

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

python3 kex-03/reproduce_kat_interop.py

The script downloads the pinned official archive, verifies its SHA-256, and checks first-record seeds and shared secrets for all 25 instance pairs. It exits with SKIP status 77 if the archive is unavailable; --archive /path/to/CreTAKE.zip permits offline replay.

kex-03-7: K2K-PLAC512 encryption coins depend on only 128 message bits

Original source: LK-PQC-Hunter's PKC Forum post

In the reference trees for CreTAKE-K2K-PLAC512 (twokem.c:107,155) and CreTAKE-K2K-PLAC512Star (twokem.c:108,156), sizeof(buf3) = 128 is passed to pseudoXOF as a bit length. The XOF copies only 16 bytes (auxfunc.c:482–507), all from the 64-byte random message m; the remaining message bytes and public-key digest do not affect its output. Thus the two encryption seeds and double-key KEM secret have at most 128 bits of input entropy. The 128/256-bit and ZEN512 K2K variants use the correct * 8 length. The certificate below inspects and executes only the reference tree; the optimized call sites are source-inspected.

The first POLARLAC ciphertext component is generated from an encryption seed and public key, independently of m (POLARLAC-512/pke.c:144–190). An attacker can enumerate the 2^128 message prefixes, derive candidate seeds, and check that component against the observed ciphertext. This recovers the K2K secret k_i; the search is a concrete bound, not a run we performed. The full ciphertext is still compared on decapsulation—this is not a truncated re-encryption check.

CreTAKE claims IND-StAA for K2K (§4.2.2 and Theorem 3). In the adopted model, an initiator StateReveal of an honestly matched test session is permitted without corrupting that party's long-term key (Figure 14, physical pp. 23–24). The revealed initiator state contains the independent k_j (KEX_AlgorithmInstance.c:131–145). Alternatively, corruption of the responder's static KEM key permits decapsulation of the public ct_j to obtain k_j. With both k_i and k_j, the attacker computes the transcript-bound session key. This below-target attack is conditional on one of those preconditions; a passive attack on every session is not claimed.

Proposed fixes

The CreTAKE team says it corrected the affected XOF length argument in a revision to be released at the next permitted update. This is recorded without evaluating the revision.

Reproducing

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

python3 kex-03/reproduce_k2k_prefix.py

The certificate checks both 512-bit PLAC source variants, the bit-length conversion, and the session-state layout. It also tests that changing bytes after the first 16 does not alter the submitted XOF's effective input. It does not perform the 2^128 search.

kex-03-8: Generic QROM reduction terms give loose one-query bounds

Original source: PKC Forum evaluation attachment, PROOF-001/002

Theorems 1, 2 and 4 of the submitted specification (physical pp. 21, 23 and 25) contain additive QROM terms proportional to 1/sqrt(|K|). With S=N=q=1 (one session, two parties and one oracle query), and setting component advantages and collision terms to zero, their coefficients are respectively 6, 10 and 8. The submitted key widths are 128, 256 and 512 bits. The resulting proof-error exponents are about 61/125/253 bits for K2S and S2S and 60/124/252 bits for S2K, all below the corresponding 80-, 128-, and 256-bit quantum targets even at this minimal positive-query budget. Larger session or query budgets only weaken these stated bounds.

This is a generic reduction loss, not a demonstrated attack or evidence that the underlying KEM and signature components are weak. It gives no candidate-specific recovery route and is recorded as Info rather than a vulnerability. A tighter reduction would be needed to certify the targets from these particular theorems.

Reproducing

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

python3 kex-03/reproduce_proof_bound.py

The arithmetic certificate checks the minimal positive-query terms; the theorem text and key-width instantiations must be checked in the frozen specification and implementation.

kex-03-9: The embedded BiT-128 signing oracle enables credential recovery and impersonation

CreTAKE instantiates its signature credentials with BiT (§3.2.2 and Figure 12, physical pp. 14–15), and its K2S, S2K and S2S security theorems assume that BiT is EUF-CMA (Theorems 1, 2 and 4, physical pp. 21, 23 and 26). The embedded BiT-128 signer draws one bit b per signature and negates the whole challenge with it. It then adds the same ±c·s to every response row, while rejection sampling is applied coefficient by coefficient (Common/primitives/sig/BiT-128/sign.c:132–149). The z0 row has the constant secret 1, so it reveals the shared sign statistically. Weighting the other rows by that posterior and regressing on c converges to the secret s. Martin Feussner's public attack applies this to recover an equivalent BiT-128 signing key from about 200,000 to 250,000 signatures.

CreTAKE supplies those signatures. The K2S responder kex_generate_pass2_msg_b (CreTAKE128/CreTAKE-K2S-PLAC128-BiT128/KEX_AlgorithmInstance.c:129–177) accepts any first message as the ephemeral key p̃k, even random bytes, and accepts any claimed initiator key. It encrypts to them and signs p̃k‖c̃‖c_i with its long-term BiT key (:169; ZEN variant :161). No step authenticates the initiator, and the responder keeps no replay state, so every query returns a fresh signature. The other BiT-128 frameworks expose the same signer in different ways. S2S responders re-sign p̃k‖c̃ each time an observed first message is replayed (CreTAKE-S2S-BiT128-eZEN128/KEX_AlgorithmInstance.c:163). S2K initiators sign p̃k‖c_j in every session (CreTAKE-S2K-BiT128-ZEN128/KEX_AlgorithmInstance.c:131), so their signatures can be collected passively.

With an equivalent key, the attacker impersonates the K2S responder to an honest initiator. It answers with its own c̃ under the initiator's p̃k, an encapsulation c_i to the initiator's long-term KEM key, and a valid signature, so it knows k̃ and k_i and hence the session key. This breaks a fresh initiator session in the IND-AA game without a Corrupt query on the responder, contrary to Theorem 1. In the executed run, 250,000 signatures were harvested through the unmodified K2S-PLAC128-BiT128 library. The rounded candidate failed the compressed public-key relation, and Feussner's public low-confidence search over 24 bits completed an equivalent key that differs from the real one. The initiator then accepted all five impersonated sessions with the attacker's key. A fresh, unrelated BiT key in the same position was rejected.

One key was run end to end. Feussner reports that three of four keys succeed at 200,000 signatures and the fourth at 250,000. The other five BiT-128 instances use the same signer, but their impersonations (S2S in either role, S2K initiator) were not executed. The BiT-256 and BiT-512 signers have the same shared-sign structure, but no recovery cost is established for them, so they are not listed as affected.

Reproducing

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

sh kex-03/reproduce_bit_oracle_recovery.sh
NGCC_LONG=1 sh kex-03/reproduce_bit_oracle_recovery.sh

Both modes fetch Feussner's bit_global_sign.c at commit 91f2ddf and hash-check it. The file is not redistributed, and the script exits with 77 when it cannot be fetched. Both modes then compile it, with only main renamed, against CreTAKE's own BiT-128 source in a temporary directory. All signatures come from kex_generate_pass2_msg_b in the prebuilt library. The default run takes about 35 seconds. It checks that 20 random first messages are signed with valid and distinct signatures, while changed messages reject. It then harvests 30,000 signatures and measures the shared-sign leak against the true key, used only for evaluation. As controls, it repeats the measurement with an unrelated key and with each signature's sign posterior replaced by the previous signature's. NGCC_LONG=1 harvests 250,000 signatures and recovers the key from public data only. It then requires 5/5 impersonated sessions and rejection of the unrelated-key control, in about 4.5 minutes.

kex-03-10: A copied certified key causes identity misbinding

CreTAKE states that each framework must bind its hidden contribution "to the identities and complete public transcript", and that the session key "is derived from the identities, public transcript, and all KEM-derived secrets" (§4.2, physical p. 18). In the code, the only identity material is the pair of long-term public keys. For example, derive_session_key hashes p̃k‖pk_I‖pk_R‖c̃‖c_i‖k̃‖k_i (CreTAKE128/CreTAKE-K2S-PLAC128-BiT128/KEX_AlgorithmInstance.c:27–48), and the other frameworks follow the same pattern. No signed string and no KDF input contains a party name. Definition 1 (physical p. 5) has KG take a party identity, but that identity never reaches Init or Der.

Suppose a registration authority certifies Bob's public key under the name Eve as well. An initiator that addresses Eve then runs the exchange on Bob's key, Bob answers, and both parties accept with equal session keys. The initiator's session names Eve as the peer, while the key is actually shared with Bob. Eve needs no secret and sends no message. Bob's authenticated traffic can therefore be attributed to Eve, which is an unknown-key-share.

The attack needs duplicate-key certification, which lies outside the distinct-key setting of CreTAKE's IND-AA and IND-StAA proofs. It is an identity-binding gap, not a key-recovery attack inside the model. Binding the certified identity strings into the session-key derivation removes it, and so does a registration authority that enforces key uniqueness.

Reproducing

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

python3 kex-03/reproduce_copied_key_alias.py

The script uses the prebuilt kex-03/lib/libCreTAKE-*.so on all 25 instances. On each one it checks three things: an honest exchange agrees, the exchange addressed to the duplicate "Eve" certificate agrees with Bob, and a control that substitutes an independently generated responder key fails to agree. It runs in under a second.