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

BRA (kem-06)

kem-06-1: Malformed inputs drive the BRA decoder out of bounds

Original source: ngcc-dev/ngcc-harness PR #6

After an honest BRA-128 key generation, encapsulation, and decapsulation, changing secret-key byte 0 and decapsulating the otherwise honest ciphertext reaches an unchecked bound in the augmented-Gabidulin decoder. rbc_qpoly_left_div2 initializes a signed counter to k-1, decrements it once per division iteration without checking for exhaustion, and passes it as the unsigned p2_degree argument to rbc_qpoly_mul2. The latter checks the polynomials' stored degrees, not the explicit iteration bounds it actually uses.

AddressSanitizer consequently reports a heap-buffer-overflow when rbc_qpoly_mul2 reads p2->values[j] past the four-coefficient allocation at qpoly.c:458. The same defective control flow exists in all three submitted parameter-set sources.

The original deterministic witness reaches the bug after one-byte secret-key corruption. Xiong and Wang, ePrint 2026/2232, 2026-09-28 revision, §6.5 further show that an ordinary remote adversary can reach the same decoder failure with ciphertext input alone: 30/30 random malformed ciphertexts crashed each of BRA-128 and BRA-256, while BRA-512 and all BRQC controls did not crash. We reproduced the quick ciphertext-only experiment. This upgrades the issue from a corrupted-key robustness defect to remotely reachable unsafe decapsulation. It demonstrates reliable denial of service and an attacker-influenced out-of-bounds read, but not memory disclosure, key recovery, confidentiality loss, or control-flow exploitation. Under the classification policy, that demonstrated termination-only impact is Low.

The decoder must reject an exhausted or negative division bound and validate the explicit multiplication degrees against both input and output allocations.

Reproducing

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

make -C kem-06 exploit
sh kem-06/reproduce_ciphertext_crash.sh

The first target completes an honest round trip, then repeats decapsulation after changing only secret-key byte 0 and requires ASan to identify the unchecked q-polynomial access. Its narrow sanitizer ignore-list excludes a separate pre-decoder stack-redzone access in the submitted field multiplier so that the decoder witness can be reached; no decoder code is modified. The second command fetches the pinned public artifact and runs short random-ciphertext trials against all three unmodified BRA reference sets, with BRA-512 as the non-crashing control.

kem-06-2: Reference field multiplication touches one limb past its output

Original source: ngcc-dev/ngcc-harness PR #6

Further extension to Dariia Porechna's analysis: the reference rbc_elt_ur_mul loop iterates j through ELT_SIZE inclusive and writes o[j+offset]. For the 67- and 83-bit fields, ELT_SIZE is 2, offset becomes 1, but rbc_elt_ur contains only three limbs. The j = 2 iteration therefore reads and writes limb 3, one limb past the declared output. This is a real C out-of-bounds access rather than an ASan layout artifact: placing an exact-size output at a guard-page boundary makes the submitted function fault for both fields.

The access occurs in normal operation. rbc_elt_mul allocates an exact-size rbc_elt_ur on its stack and calls this routine; the polynomial multiplication used by honest key generation, encapsulation, and decapsulation calls rbc_elt_mul. A full ASan build stops during honest BRA-128 key generation at this access. The guard-page witness also provides two useful controls: multiplication returns when the following page is writable, and the 127-bit BRA-512 reference routine stays within its four-limb output when the following page is inaccessible. The optimized BRA-128 and BRA-256 sources likewise allocate four limbs and do not have this exact bound mismatch.

For canonical 67- and 83-bit operands, the fourth-limb contribution is mathematically zero, so ordinary layouts usually rewrite the adjacent word without changing its value. This limits the demonstrated impact to undefined behavior and possible faults on a hard allocation boundary; the audit has not shown attacker-controlled nonzero corruption, key recovery, or a remote KEM break. The reference loop should stop when j + offset == ELT_UR_SIZE, or the output representation should explicitly include the padding limb.

Reproducing

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

make -C kem-06 exploit-field

The ordinary, unsanitized guard-page test confirms faults for GF(2^67) and GF(2^83), then confirms GF(2^127) as an in-bounds negative control.

kem-06-3: The decoder address trace gives a candidate-specific key-recovery route

Follow-up source: Sun Shuzhou's PKC Forum post of 2026-10-04

BRA decryption computes v-u*y using private y and the public ciphertext (src/bra.c:277-288). The augmented-Gabidulin decoder derives pivot next from discrepancies in that word and uses next directly to load and store u0 and u1 (src/augmented_gabidulin.c:184-205). Its memory-address trace is therefore a rank oracle on a secret-key-dependent word. The final KEM ciphertext comparison and fallback selection are masked, but occur after the decoder.

Further extension to the original analysis: Sun shows that ciphertexts (u,v)=(1,t) reveal membership in the secret support E_y, and that intersections with public random subspaces recover the full support adaptively. Instrumented formal BRA-128 decapsulation recovered E_y exactly for 3/3 keys in 3,443, 5,044, and 6,467 queries. Guessing the remaining x support and solving the resulting linear system gives modeled full-key costs of about 2^49.9, 2^57.4, and 2^71.5 at the three levels; a sharper accounting is lower.

No physical cache channel or wall-clock signal was demonstrated, BRA-256's real-decoder support experiment did not converge, and the final algebraic phase was not run at full parameters. The exact address-trace oracle plus a candidate-specific recovery chain warrants High / Lead. Although the specification explicitly claims that running time leaks no sensitive decoder information (physical p. 17), Critical under the side-channel policy requires end-to-end key recovery or forgery, which is not shown here.

Constant-time fix (local-to-moderate; High consequence floor): the decoder already computes the pivot and swap masks without branches. Scanning all positions and selecting u0[next] and u1[next] with masks removes the indexed access. The candidate-specific recovery route keeps the classification at High regardless of that remediation cost.

Reproducing

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

Inspect src/kem.c:214, src/bra.c:277-288, and src/augmented_gabidulin.c:184-205 under Implementations/Reference_Implementation/BRA-128/; the same pivot code is present in BRA-256/512. See constant_time.md for the source trace. The full recovery extension has no public reproducer and remains a Lead.

kem-06-4: Ignored padding bits make ciphertexts malleable without changing the key

The u and v encodings end with 5 unused bits each, which rbc_vec_from_string ignores (rbc_vec.c:789-809). Decapsulation compares the re-serialized decoded vectors rather than the received bytes (kem.c:241-252), and the key hashes those re-serialized vectors (kem.c:265-266). Every honest ciphertext therefore has 1,023 byte-distinct variants that decapsulate to the same key. The submission claims IND-CCA2 security, which is trivially violated.

The specification's Algorithm 9 (§3.4) compares the received (u, v) with the re-encryption as algebraic values; it defines no byte parser or rule for accepting alternative wire encodings. The submitted byte parser discards the padding bits before the check, so the implementation never compares the original ciphertext bytes.

Extended on 2026-10-17: the optimized implementations of BRA-128, BRA-256, and BRA-512 use the same parser and comparison. In Implementations/Optimized_Implementation/BRA-{128,256,512}/src/, kem.c and rbc-*/rbc_vec.c are byte-identical to the reference files (cmp). The only other differences are the carry-less multiplication and squaring code in rbc_elt.c and the matching element-size macros in the rbc_*.h headers. rbc_vec_from_string and the helpers it calls (rbc_elt_set_coefficient_vartime and the zeroing routines) are unchanged. The optimized builds were checked by source only and were not run.

Reproducing

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

python3 kem-06/reproduce_padding_alias.py

kem-06-5: Secret-key expansion depends on the external DRBG

BRA stores a seed and reconstructs its secret supports and polynomials by resetting a local random_source from that seed (parsing.c:56–89). random_source_seed_with_len is a direct call to the external init_random_number (lib/random_source/random_source.c:27–32). Correct decapsulation therefore depends on the particular ICCS DRBG stream, although this operation is deterministic key expansion rather than fresh randomness.

The shipped implementation works with its bundled drng.c; the Low impact is key-format and implementation interoperability. The expansion should use a scheme-defined XOF.

Reproducing

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

python3 security/rbg_protocol_dependency.py --report-id kem-06-5

kem-06-6: Short ciphertexts reach BRA's fixed-offset parser

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

All six kem_dec wrappers discard ct_len_bytes and pass ct to bra_decaps. Its parser reads two fixed-length vectors and the salt at fixed offsets (src/parsing.c:166–169). If the supplied buffer is actually shorter than the ciphertext size, the parser reads beyond it before rejecting the ciphertext. The forum post reports an AddressSanitizer reproduction on reference BRA-128; our certificate checks the same source path in all six trees. An out-of-bounds read is confirmed, but the available evidence does not show secret disclosure or a cryptographic break.

Reproducing

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

python3 kem-06/reproduce_short_ciphertext.py

This source certificate checks the missing length guard and fixed-offset reads. The sanitizer observation is attributed to the forum post, not rerun by this command.