OT-PCA: New Key-Recovery Plaintext-Checking Oracle Based Side-Channel Attacks on HQC with Offline Templates

What it is

OT-PCA is a plaintext-checking (PC) oracle side-channel attack framework targeting HQC key encapsulation, from Haiyue Dong and Qian Guo (Lund University). Its core novelty: "offline templates" (OTs) built purely from the public HQC decoder, before ever touching the oracle, which then extract soft information on hundreds of secret-key positions per oracle call.

How it works

During an offline phase, the attacker samples sparse vectors from HQC's secret-key distribution, adds them to chosen error patterns, and runs them through the public decoder (no oracle calls needed) to empirically estimate position-wise probabilities — the likelihood each secret bit is non-zero, conditioned on decryption success/failure. Two optimization problems drive error-pattern selection, solved via genetic-style algorithms: (1) maximize decryption-outcome entropy (success/failure ~50/50) to maximize information per call, and (2) maximize pairwise Hamming distance across a set of error patterns so they contribute independent information. Online, the attacker issues chosen ciphertexts, gets real oracle decryption results, and combines them with the precomputed templates via a new Information Set Decoding (ISD) algorithm that exploits the soft information for full key recovery.

Preconditions / Affected

Applies to all three HQC parameter sets (hqc-128, hqc-192, hqc-256), per NIST PQC round-4 concatenated Reed-Solomon/Reed-Muller code construction (post-October 2020 spec). Requires a constructible PC oracle via decapsulation side-channel leakage (timing, power/EM, microarchitectural) — the threat model assumes attacker-chosen ciphertext and message fed into decapsulation on a target device.

What to do

The concrete numbers the summary omits — oracle-call counts by parameter set, from Table 1 (perfect oracle, accuracy=1):

That's roughly a 2.4x reduction for hqc-128 vs. Zero-Tester, and 87x/137x reductions for hqc-192/256 vs. SHRWS22 — notably, Zero-Tester reportedly "struggles with hqc-192" while OT-PCA scales. The attack was practically validated with power analysis on PQClean's hqc-128 on an ARM Cortex-M4 (120 independent runs, fresh key each time), matching simulation. Source code: https://github.com/ot-pca/ot-pca.

Caveats

The 95%-accuracy, 7.6x-improvement figure is simulation-only (reported for hqc-128); the hardware validation used a presumably near-perfect oracle. The paper notes potential extension to misuse and fault-injection attacks, but does not demonstrate those.