Reports › kem-06 · Constant-time review

BRA (kem-06)

kem-06-1: A malformed secret key drives 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 first reads p2->values[j] past the four-coefficient allocation at qpoly.c:458; its following output access at line 460 would likewise become out of bounds if execution continued. The same defective control flow exists in all three submitted parameter-set sources, although the deterministic runtime witness below confirms BRA-128 only.

The standard KEM threat model gives a remote peer the ciphertext, not the recipient's secret key. This witness therefore does not establish a remote chosen-ciphertext attack, key recovery, or loss of confidentiality. It does establish unsafe handling of a corrupted, faulted, imported, or maliciously provisioned secret key, with process termination and memory corruption as possible consequences. The decoder should reject an exhausted/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

The target first completes the 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.

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: Secret-derived decoder pivots select memory addresses

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). A cache observer can therefore learn a secret-key-dependent intermediate. The final KEM ciphertext comparison and fallback selection are masked, but occur after the decoder. No complete key recovery or remote timing channel is demonstrated.

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 fuller trace.