CreTAKE

BiT-512's digest collision does not transfer into CreTAKE: every signer adds at least 512 fresh bits to what it signs

Holds · Argued · Cause: parameter size

Property: authentication of the signing party

Cost against claim: no chosen-message collision at 2²⁵⁶; a generic multi-target second preimage at 2^512−t for 2^t signed sessions, 2⁴³² at the call's 2⁸⁰

BiT-512 reduces what it signs to a 512-bit digest, and a chosen-message collision on that digest transfers a signature at about 2²⁵⁶ hash calls (listed on BiT's page). Inside CreTAKE the signing party signs values it has just generated with at least 512 bits of fresh randomness (its encapsulation in K2S and S2S, its ephemeral public key in S2K and S2S), and the sender of the first message controls at most a prefix of what is signed, so no message can be chosen and collided before the signing query. What remains is a second preimage over the 2^t digests of honestly signed sessions, 2^512−t hash calls, 2⁴³² at the 2⁸⁰ sessions the call allows: the multi-target degradation that every 512-bit value suffers, not a break of the 512-bit claim.

What causes it

Figures 1, 2 and 4 (Section 3.1): the K2S responder signs pk̃, c̃ and c_i, with c̃ and c_i freshly encapsulated; the S2K initiator signs pk̃ and c_j, with pk̃ derived from a fresh r̃ and c_j freshly encapsulated; the S2S initiator signs pk̃, and the S2S responder signs pk̃ and c̃, with c̃ fresh. Only pk̃, in the two responder roles, is chosen by the sender of the first message. Section 5.2 gives the level of an instance as the minimum over its components.

Evidence

A second member of PQC-X traced the four signing roles in the specification and in the reference code of the level-512 instances, where signing and verification cover the same fields, and computed the residual costs: 2^512−t hash calls classically against 2^t signed sessions; on the quantum side 2^256−t/2 oracle calls only if the membership test costs nothing, at least 2²⁵⁶ in a plain circuit.

Cause in the specification, traced to the specification text.

Limits

The transfer returns if the same BiT key also signs adversary-chosen messages outside CreTAKE, which the designers' model excludes, and, in the submitted code, in the S2S responder role at level 512, where finding cretake-i1 leaves only 64 random bits in the signed transcript (about 2²⁵⁶ hash calls plus 2⁶⁴ sessions, dominated by that finding's own 2⁶⁴ search). Not run: the residual costs are computed, not measured.

Credit

Found by PQC-X.

The initiator's ephemeral key is derived from its state and public bytes only: revealing the state gives the S2S and S2K session key

Minor break · Demonstrated · Cause: code

Property: session-key secrecy under state reveal (the claimed IND-AA and IND-StAA)

Cost against claim: one derivation from the revealed state, against 128, 256 and 512 claimed under state reveal

Scope: The reference and optimised implementations of the S2K and S2S instances; the specification is unaffected.

In S2K and S2S the specification derives the ephemeral key pair from G(sk_i, r̃), so that neither the long-term signing key nor the session state r̃ alone reveals it. The submitted code hashes r̃ followed by the signing key, but passes the length of that buffer in bytes where the hash expects bits, so only 64 + 177, 464 or 1072 bytes are absorbed at levels 128, 256 and 512, and BiT's secret key begins with its 1048, 2144 or 5056-byte public key: not one secret byte is hashed. Whoever learns the state (r̃ in S2S; r̃, c_j and k_j in S2K) recomputes the ephemeral secret key from public data, decrypts c̃ and derives the session key, which the claimed models forbid.

What causes it

KEX_AlgorithmInstance.c of the S2K and S2S instances calls pseudohash(SEED_BYTES * 8, buf, SEED_BYTES + SKI_LEN, seed_kg) in the initiator's first pass (line 117 in S2S-BiT512-eZEN512) and again in its key derivation (line 187), where buf holds the 64-byte r̃ followed by the SKI_LEN-byte signing key; pseudohash (auxfunc.h) reads its third argument in bits. BiT packs its secret key as seed_A and b1, together the public key, then the secret seed and the secret polynomials (packing.c, pack_sk), so every byte absorbed after r̃ is public. Sections 4.2.1 and 4.2.2 make the derivation G(sk_i, r̃) the device that protects the session key against a state reveal (IND-StAA for S2K, IND-AA for S2S). The K2K instances have the same call, but their KEM secret keys begin with secret material, so they are not affected.

Evidence

On the unmodified reference build of S2S-BiT512-eZEN512, after reproducing the official test vectors byte for byte, PQC-X ran the initiator's key derivation with a copy of its secret key in which every byte after the public-key prefix is zero: it returns the same session key as the real key. As a control, flipping one byte of the public prefix makes the derivation fail, since the ephemeral public key changes and the responder's signature no longer verifies. The state is 64 bytes, r̃ alone. A second member of PQC-X re-read the initiator's call in S2K-BiT512-ZEN512 and confirmed the byte count passed as a bit count.

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

Limits

Run on S2S-BiT512-eZEN512; the other S2S sets and the S2K sets follow from the same code lines and the lengths in their headers (the bytes absorbed never reach the end of BiT's public key), not from a run. The attack needs the initiator's state, which the designers' models let the adversary reveal; without it the finding changes nothing. Fixing the length argument hashes the whole signing key, as the specification intends.

Designers' response

The designers confirmed that some hash and XOF calls pass byte counts where bit counts are expected, and announced corrected length arguments with regenerated test vectors, with no change to the protocol or its parameters (PKC forum, 2026-09-22). PQC-X has not checked it.

Credit

Found by PQC-X, extending an observation by M.-J. Saarinen (ngcc.dev kex-03-1, 2026-09-21): the same initiator-side call is noted there as a second units error that still absorbs all 64 random bytes; what it leaves out is the signing key.

The responder feeds 8 of its 64 random bytes to the XOF: the ephemeral share, and every S2S session key, falls to a 2⁶⁴ search

Minor break · Argued · Cause: code

Property: session-key secrecy against a passive eavesdropper

Cost against claim: 2⁶⁴ re-encryptions against 128, 256 and 512: any S2S session key, passively; the ephemeral share of K2S, S2K and K2K at the same cost

Scope: The reference and optimised implementations; the specification is unaffected.

In every responder of the submitted code, the 64 random bytes drawn for the ephemeral encapsulation are handed to the XOF with their length in bytes where it expects bits, so only the first eight bytes reach the ephemeral message k̃ and the encryption coins. In the six S2S instances k̃ is the only secret in the session key: an eavesdropper who enumerates the 2⁶⁴ possible inputs, re-encrypts and compares with the ciphertext c̃ recovers the session key, and Grover brings the count to 2³². In K2S, S2K and the generic K2K instances the same search recovers the ephemeral share, so the session key rests on the long-term KEM key alone: weak forward secrecy, and the long-term-key reveal the designers' models allow, fall at 2⁶⁴.

What causes it

KEX_AlgorithmInstance.c of every K2S, S2K and S2S instance (line 156 in S2S-BiT512-eZEN512, line 154 in K2S-PLAC128-BiT128) and twokem.c of the generic double-key KEM (K2K-PolarLAC-128, K2K-PolarLAC-256 and K2K-ZEN at every level) draw SEED_BYTES = 64 random bytes, then call pseudoXOF with SEED_BYTES as the input length. pseudoXOF (auxfunc.h) takes that argument in bits and absorbs (bits + 7)/8 bytes, eight here; the random-number call just above passes SEED_BYTES * 8 correctly. 23 reference source files carry the call, and the same 23 in the optimised implementation; the submitted test vectors were produced by this code. Figures 1 to 4 (Section 3.1) have the responder encapsulate with fresh randomness, and the specification fixes no shorter length: the defect is in the code alone.

Evidence

PQC-X reproduced the official test vectors of S2S-BiT512-eZEN512 and K2S-PLAC128-BiT128 byte for byte on the unmodified reference code, then fixed the responder's 64 random bytes through a linker wrapper around the random-number function. On S2S-BiT512-eZEN512, two runs that differ in 56 of the 64 bytes give the same c̃ and the same session key, and a run that differs in one bit of the first eight bytes gives different ones. On K2S-PLAC128-BiT128, c̃ is likewise unchanged, while c_i and the session key still change with the KEM's own randomness. A second member of PQC-X re-read the responder's call in S2K-BiT512-ZEN512 and confirmed the byte count passed as a bit count. The 2⁶⁴ enumeration itself was not run.

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

Limits

The generic K2K instances carry the same call in twokem.c; this was read, not run. The compact double-key KEM of K2K-PolarLAC-512 and K2K-PolarLAC-512* is a different code path, not covered here. Because the S2S responder's signed transcript pk̃, c̃ now depends on 64 random bits, the collision on BiT-512's message digest listed on BiT's page also becomes usable against S2S-BiT-ePolarLAC-512 and S2S-BiT-eZEN-512 (about 2²⁵⁶ hash calls plus 2⁶⁴ sessions); the 2⁶⁴ search above dominates it. Fixing the length argument restores the 512 bits of randomness the specification intends.

Designers' response

The designers confirmed that some hash and XOF calls pass byte counts where bit counts are expected, and announced corrected length arguments with regenerated test vectors, with no change to the protocol or its parameters (PKC forum, 2026-09-22). PQC-X has not checked it.

Credit

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