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

PolarLAC (kem-30)

kem-30-1: Re-encryption rejection sampling leaks the decrypted-message class

Follow-up source: PolarLAC team's PKC Forum response

Practical follow-up: Weng et al.'s PKC Forum post, pinned recovery artifact, and the PolarLAC team's confirmation

Reference: Xiong and Wang, ePrint 2026/2232, 2026-09-28 revision, §§3.3 and 3.7–3.8

Decapsulation re-encrypts the decrypted message for its Fujisaki--Okamoto check. The derived seed enters sample_screened_poly, whose spectral rejection loop repeats until a bound is met (pke.c:30–42). Its total rejection count R is therefore a deterministic public function of the secret-derived decrypted message, and execution time reveals that count. The generic statement that polar coding supports constant-time implementation (physical p. 4) is not contradicted; the relevant claim is that this implementation keeps constant-time control flow (§8.4, physical p. 39). The leaking rejection loop is data-dependent control flow.

The first artifact measured adjacent R classes about 9,000–10,600 cycles apart, but its attempted algebraic use of that coarse class recovered 0/512 coefficients. A later physical attack uses differential timing directly. On PolarLAC-Light it made 17,010,803 differential comparisons, each based on seven target/reference pairs (about 238 million decapsulation calls), recovered all 512 secret coefficients in 66.1 minutes, and used the recovered key to decrypt a fresh ciphertext. A second recorded run again recovered 512/512 coefficients.

Follow-up Analysis

The PolarLAC team first confirmed the rejection-count channel while noting the earlier negative recovery result. It subsequently acknowledged the practical timing attack. Complete key recovery contradicts the explicit control-flow claim and is Critical under the classification policy. We validated the pinned source and both recorded recovery transcripts but have not independently rerun the 66-minute physical acquisition, so the status is Probable.

Constant-time fix (moderate): use fixed-work, message-independent sampling in the re-encryption path. The complete decapsulation, including reconstruction of its coins, must have a trace independent of the decrypted message and long-term key. This gives a Medium remediation floor; the demonstrated recovery and contradicted control-flow claim determine the higher Critical severity.

Proposed fixes

The team's response proposes removing data-dependent rejection sampling. This records the proposal without assessing it.

Reproducing

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

sh kem-30/reproduce_full_timing_recovery.sh

The wrapper fetches and hash-checks the pinned artifact, builds it, and validates both recorded complete-recovery runs and their fresh-ciphertext check. Set NGCC_SLOW=1 to repeat the roughly 66-minute physical experiment; timing results depend on the host.

kem-30-2: Secret-indexed LLR tables expose PolarLAC decoding through the cache

Original source: PolarLAC team's PKC Forum acknowledgment

PolarLAC computes each decoder log-likelihood ratio as llr_table[centered + RATIO - 1], where centered comes directly from a decrypted coefficient (poly.c:359–369 in the reference PolarLAC-512 tree). The table address therefore depends on secret-key and ciphertext data during decapsulation. The same lookup occurs in all 20 submitted poly.c copies.

The team confirms the cache leakage. No measured cache trace or candidate-specific recovery is public.

Constant-time fix (moderate, hence Medium): replace each 256-entry secret-indexed lookup with an oblivious lookup or an arithmetic LLR computation. Because this operation is repeated for every decoded coefficient, it is a material rewrite or slowdown rather than a small local mask.

Proposed fixes

The team's response proposes replacing the lookup with an implementation having no secret-dependent memory access. This records the proposal without assessing it.

Reproducing

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

python3 kem-30/reproduce_llr_cache_lookup.py

kem-30-3: Reference and optimized PolarLAC fail cross-decapsulation

Original source: LK-PQC-Hunter's PKC Forum post Follow-up source: PolarLAC team's 2026-10-11 response

The submitted reference and optimized x86 builds reproduce their own KATs but do not interoperate. The post reports failed cross-decapsulation in both directions on four seeds for each of Light, 128, 256, 512 and 512-Star. We independently built the 128-bit pair: each self-decapsulation agreed, while each cross-tree decapsulation returned a different key despite rc=0. Their public keys already diverge after the common 16-byte public seed. The submitted ARM KAT values match the reference values at all five sets, making x86 optimized the outlier; the underlying primitive or encoding discrepancy is not yet isolated. This is a key-agreement availability defect, not a key-recovery claim.

Proposed fixes

The team reports unifying NTT-domain, sampling and serialization conventions and correcting inverse NTT, with cross-implementation tests on revised code. It says the revised and submitted formats must not be mixed. These changes are recorded without evaluation.

Reproducing

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

python3 kem-30/reproduce_interop.py

The certificate compares the reference, x86 optimized and ARM KAT values in the SHA-256-pinned official archive. It does not rerun the cross-decapsulation experiment.