BiT

bit-1

A 512-bit message digest at level 512 caps BiT-512 at 256 bits

Minor break · Tested at small scale · Cause: parameter size

Property: existential unforgeability

Cost against claim: digest collision 2^256.3 and one signing query, against 2⁵¹²

BiT hashes the message together with a digest of the public key into a fixed-length value µ, and verification depends on the message only through µ: the commitment is rebuilt from the public key and the signature, and the last check compares the challenge seed carried by the signature with a hash of µ and that commitment. Two messages with the same µ are therefore indistinguishable to the verifier, so a signature obtained on the first is accepted on the second. At level 512 µ has 512 bits, and no salt enters it, so a generic collision found before any signature is requested costs about 2²⁵⁶ hash evaluations against the 512-bit claim.

Parameter set	Claim	Attack cost	Verdict
BiT-512	512 classical, 465 quantum	2^256.3 hash evaluations and one signing query; quantum collision search 2¹⁷¹ (BHT, with as much quantum memory) to 2²⁰⁵ (CNS), no better than 2²⁵⁶ in an area-time accounting	Minor break
BiT-256	256 classical	2^256.3 (no margin)	Holds
BiT-128	128 classical	2^128.3 (no margin)	Holds
Table 10 sets (levels 80, 192 and 384; no implementation submitted)	80, 192 and 384 classical	not assessed	not computed

What causes it

Fig. 5 (Sign step 4 and Verify step 4) sets µ := H(tr ‖ M) with κ bits, κ being the security parameter (Definition 1), hence 512 bits at level 512; the reference code fixes the same 64 bytes (BIT_MESSAGEBYTES in params.h). The per-signature randomness rnd (Sign step 6) enters only the mask seed, never µ. Verify step 8 compares c̃ with H(µ ‖ w′), where w′ comes from pk and σ = (z1, h, c̃) alone (steps 5 to 7), so nothing else in verification depends on the message. At levels 128 and 256 the code gives µ twice κ bits (32 and 64 bytes), which a literal reading of Fig. 5 does not say.

Evidence

The transfer was run on the reference code, at reduced digest lengths. First on BiT-128 with µ cut to 24 bits in the source (re-run since with identical output): a collision after 6572 messages, and the signature on the first message accepted on the second while a control message was rejected. Then by a second member of PQC-X on the unmodified BiT-512 reference implementation, whose official test vectors were reproduced byte for byte, with µ cut to 16 to 40 bits through a link-time wrapper: 78 trials, 78 transfers accepted, 78 control messages rejected, and 78 rejections once the full 512-bit µ is restored; the mean number of messages to a collision follows the birthday bound (fitted slope 0.485 bits per digest bit against the expected 0.5). The full-size cost, √(π/2·2⁵¹²) ≈ 2^256.3 hash evaluations with negligible memory by parallel collision search, was computed from the bound, not from the fit. The digest lengths were also checked in Fig. 5 and in params.h of the three sets (32, 64 and 64 bytes).

Cause in the specification, traced to the specification text.

Limits

Generic and far from practical, and judged with an ideal hash at the length the specification fixes, so nothing here counts a limit of the placeholder hash; the fix is a µ of at least 1024 bits at level 512, which the call's hash interface allows. BiT-128 and BiT-256 give µ twice their level, so their collision cost equals their claim exactly, with no margin. The quantum side is model-dependent: 2¹⁷¹ queries with as much quantum memory (Brassard, Høyer and Tapp, LATIN 1998) or 2²⁰⁵ queries with 2¹⁰² classical memory (Chailloux, Naya-Plasencia and Schrottenloher, ASIACRYPT 2017), but no better than classical parallel search in an area-time accounting. The 80, 192 and 384 sets of Table 10 have no submitted implementation and were not assessed.

What PQC-X adds

The mechanism run on the unmodified BiT-512 reference code with a shortened digest (78 transfers out of 78 trials, birthday scaling measured from 16 to 40 bits), the expected cost with its memory and quantum accounting, and the remark that the pseudocode gives µ only κ bits at every level while the code doubles it at levels 128 and 256.

Credit