Security › kem-05 · Constant-time review · Performance: x86_1 · arm_1

BIKE-MLThre (kem-05)

kem-05-1: The default library deterministically generates a public secret key

Original source: Xiong and Wang's PKC Forum post

The submitted default make all builds libbike_v2.a with -DNIST_RAND=1 and FromNIST/rng.c (Makefile:4–5,24–26,32–46). That file's global AES-CTR DRBG state starts at zero, but the public library exposes only the KEM API and no library path calls randombytes_init. Key generation immediately draws both secret seeds from this state (kem.c:100–130). Only the separate KAT wrapper initializes the DRBG (kat/KEM_AlgorithmInstance.c:18).

Consequently, the first key pair in every fresh process is fixed and publicly reproducible. For BIKE-MLThre-128 its public key begins b505bc3a4fd4de9a86991932daad9337bf3343b2ea3697bd11443da3e1388027, exactly as reported. The same source path is selected for the 192-, 256-, and 512-bit builds. Reproducing the secret key gives immediate decapsulation and violates every claimed security level, hence Critical.

Reproducing

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

python3 kem-05/reproduce_unseeded_drbg.py

The witness compiles the archived 128-bit sources with the submitted default flags, compares key generation in two fresh processes, and checks the reported public-key prefix. Initializing the same DRBG with two distinct seeds produces distinct keys as a control.

kem-05-2: Same-key multi-instance decoding misses BIKE-MLThre-128 and -256 targets

Additional reference: May and Sá Diogo, Multi-Instance Security Degradation of Code-Based KEMs, ePrint 2026/517, pinned 2026-06-12 version

Each encapsulation under one public key gives a new syndrome for an independently sampled weight-t error. May and Sá Diogo's same-key DS-DOOM attack searches all such targets together and returns the error for one observed ciphertext. In BIKE-MLThre, that error recovers the masked seed m and hence the shared key KDF(m,c0,c1).

Applying the authors' pinned estimator to the submitted dimensions gives the first below-target crossings:

The crossings use fewer than the evaluation ceiling of 2^80 ciphertexts under one public key and no decapsulation oracle. The NGCC call gives signatures a 2^64 per-key message requirement but gives KEMs no corresponding session cap. BIKE-MLThre explicitly discusses static-key deployments and key-reuse exposure (specification §3.4, physical pages 30–31). A hypothetical 2^64-ciphertext limit would avoid these two crossings, but it is neither specified nor enforced. The attacks therefore fall just below the 128- and 256-bit targets under the pinned estimator and are Critical under the classification policy.

The margins are only 0.110 and 0.220 bits, and the estimator reports large memory costs of 2^96.189 and 2^103.648 bits. One fewer session exponent puts each estimate back above its target. The classification is consequently sensitive to estimator precision, time-memory accounting, and alternative ISD cost models; the report does not claim a robust multi-bit shortfall.

Reproducing

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

Install numpy and scipy, then run:

python3 kem-05/reproduce_multi_instance.py

The witness downloads the official estimator at commit 39b78dcc077793cfa3ccdce8d032ece76825ca55, verifies both its archive and doom.py hashes, reproduces each crossing and its preceding above-target point, and checks the 512-bit control.