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

Lore (kem-19)

kem-19-1: Lore-512's reducible ring admits smaller quotient attacks

Original source: NGCC PKC Forum post

Lore-512 uses Z_1028[x]/(x^768+1), where 1028 = t·q with the specification's headline modulus q = 257 and t = 4. Here x^768+1 = (x^256+1)(x^512-x^256+1). The factors are coprime modulo 1028: writing y=x^256, their Bézout difference is 3, which is invertible modulo 1028. Public ring equations therefore project into degree-256 and degree-512 quotient rings, and the two recovered secret projections would reconstruct the full secret by CRT. A secret with coefficients in {-2,-1,0,1,2} projects to coefficients bounded by 6 and 4 respectively, so the smaller instances do not lose the small-secret structure.

The forum estimates approximately 451 classical and 391 quantum bits for full recovery, below the claimed 512-bit classical level. Those figures depend on an independent-coefficient/GSA lattice model that has not been reproduced here and does not fully model Lore's fixed-composition secret, rounding correlations, or concrete reduction costs. This is a structurally verified parameter-selection lead, not a demonstrated full-size key recovery or a confirmed 451-bit attack.

Follow-up Analysis

The Lore team's first response and revised-parameter post concern a revised parameter set. This report continues to describe the archived Round 1 submission identified above and does not apply its factorization claim to a later set.

Proposed fixes

The Lore team's revised-parameter post proposes changing Lore-512 to n=1024, k=2, and x^1024+1, while retaining q=257 and t=4, together with revised fixed-composition and BCH parameters. This section records the proposal without evaluating it.

Reproducing

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

python3 kem-19/reproduce_ring_projection.py

The preflight checks exact quotient multiplication and CRT reconstruction modulo 1028 using small-secret polynomials. It does not run lattice reduction; inspect Lore-L4/params.h and poly.c in the official archive's Lore-SHAKE or Lore-SM3 reference backend for the modulus, degree, and negacyclic multiplication. These sources are not needed to run the preflight.

kem-19-2: Lore-384 and -512 emit 256-bit keys from 256-bit keygen seeds

The submitted §3.5 (physical p. 22) openly uses 256-bit SHAKE/SM3 constructions as temporary references for the 384- and 512-bit sets. All twelve higher-level source trees fix LORE_SYMBYTES=32 for hashes, seeds and shared secrets (for example Implementations and Test_Vectors/Implementations/Reference_Implementation/Lore-SM3/Lore-L4/params.h:18); encapsulation outputs only that many bytes (the same tree's kem.c:118–139, with matching paths in the other trees). The NGCC Submission Requirements §2(2) require the encapsulated key to be at least as long as its security level. Thus both submitted high-level KEM outputs miss a direct call requirement, independent of the lattice estimates.

There is also an offline secret-key ceiling. crypto_kem_keypair_derand passes only the first 32 bytes of its 64-byte coins to indcpa_keypair_derand (that tree's kem.c:61–71); the second half is rejection state. The PKE key generator expands that first half deterministically into the secret and public key (indcpa.c:363–378). Enumerating at most 2^256 first-half values and comparing generated public keys recovers a decapsulation secret for a target key. This is a concrete bound, not a completed 2^256 computation. The spec's disclosure of the temporary 256-bit instantiation is noted, but does not change the frozen candidate's targets.

Reproducing

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

python3 kem-19/reproduce_seed_ceiling.py

The certificate checks the twelve affected source trees and both independent 256-bit ceilings; it does not run the exhaustive search.

kem-19-3: BCH decoding timing leaks Lore secret coefficients

Original source: Jinnuo Li's PKC Forum report

The PKC Forum report describes three timing signals in the submitted BCH decoder. In the Lore-SM3/Lore-L2 reference tree, compute_syndromes branches on each received-word bit and conditionally performs 2t syndrome updates (bch_codec.c:403–418); Berlekamp–Massey returns when the locator degree exceeds t (:476–478); and the locator search stops once it finds the required roots (:511–519). decode_bch also exits early for zero syndromes (:544–554). The word is derived from the secret-dependent decryption result (poly.c:540–578), and the decoder runs within decapsulation (kem.c:198). The reporter measured whole-decapsulation differences of about ±13,208 cycles when changing a received-word bit and its error count, 305,780 cycles between decoding success and failure at the correction limit, and 31,704 cycles between zero syndromes and one error at position 507. The latter comparison includes the zero-syndrome early exit; it is not a measurement of root-search termination alone.

The post reports complete recovery of all 1,024 secret coefficients on an STM32F4 using the unmodified Lore-L2 SM3 reference implementation, with 2,936.5, 2,212.5, and 2,218 average queries for its three attacks. It also reports complete recovery on ten x86-host keys using the second signal. These results are not independently reproduced in this report, so the status is Probable. The source-level secret-dependent paths are present in the frozen code; no dependence on the ICCS placeholder hash/XOF is part of this timing mechanism. The reference and AVX bch_codec.c files are byte-identical across SHAKE and SM3 at L2–L4. NEON retains the early exits but replaces the per-bit syndrome branch with a secret-indexed nibble-table lookup, a different potential channel. Other levels and optimized implementations are included only by source inspection, not by measured end-to-end recovery.

Proposed fixes

The reporter recommends implementing the syndrome, error-location, and correction steps in constant time across the affected versions. This recommendation is recorded without evaluation; the forum post does not provide a measured constant-time replacement or a Lore team response.

Reproducing

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

Run sh kem-19/reproduce_bch_work.sh from the repository root. This exercises the frozen Lore-L2 SM3 decoder on a clean codeword, a one-error word, and a word beyond its correction radius. It checks the decoder outcomes and differing execution paths, not the reported whole-decapsulation timing deltas or key recovery. The original forum post gives the platforms, query counts, and measurements; it includes no reproducer or trace data.