Source-linked AI summary
OT-PCA: New Key-Recovery Plaintext-Checking Oracle Based Side-Channel Attacks on HQC with Offline Templates
Haiyue Dong, Qian Guo
TL;DR
HQC key-recovery attacks need fewer PC-oracle calls, which can be a measurement bottleneck. OT-PCA builds decoder-based offline templates and optimizes error patterns to extract soft key information. Simulations report fewer calls than prior methods, including when oracle accuracy is 95%, and power-analysis tests validate the approach on ARM Cortex-M4.
Problem
Reducing PC-oracle calls matters because each call requires one or more side-channel measurements that can bottleneck attacks under real-time and operational constraints.
Source: §1 · p. 2Method
OT-PCA builds offline templates from the public decoder and optimizes error patterns for informative, independent decryption outcomes, then uses soft information for key recovery.
Source: §1 · pp. 2–3Results
OT-PCA reduces perfect-oracle calls 2.4-fold for hqc-128 versus and 87- and 137-fold for hqc-192 and hqc-256 versus; at 95% accuracy, the hqc-128 reduction is 7.6-fold versus.
Source: §1 · p. 3Takeaways & Limitations
Power-trace tests on an ARM Cortex-M4 validated the approach and matched the simulation results.
Source: §6 · p. 20Constant-time implementation, masking, or shuffling can make accurate PC-oracle construction difficult or infeasible, hardening the attack.
Source: §6 · p. 20
Abstract
from arXiv · showhide
In this paper, we introduce OT-PCA, a novel approach for conducting Plaintext-Checking (PC) oracle based side-channel attacks, specifically designed for Hamming Quasi-Cyclic (HQC). By calling the publicly accessible HQC decoder, we build offline templates that enable efficient extraction of soft information for hundreds of secret positions with just a single PC oracle call. Our method addresses critical challenges in optimizing key-related information extraction, including maximizing decryption output entropy and ensuring error pattern independence, through the use of genetic-style algorithms. Extensive simulations demonstrate that our new attack method significantly reduces the required number of oracle calls, achieving a 2.4-fold decrease for hqc-128 and even greater reductions for hqc-192 and hqc-256 compared to current state-of-the-art methods. Notably, the attack shows strong resilience against inaccuracy in the PC oracle-when the oracle accuracy decreases to 95%, the reduction factor in oracle call requirements increases to 7.6 for hqc-128. Lastly, a real-world evaluation conducted using power analysis on a platform with an ARM Cortex-M4 microcontroller validates the practical applicability and effectiveness of our approach.
1 Introduction
OT-PCA uses decoder-derived offline templates and optimized error patterns to reduce the PC-oracle calls needed for HQC key recovery. Simulations and ARM Cortex-M4 power-analysis tests support its efficiency and practical effectiveness.
1 Introduction
- Offline templates use the public decoder to estimate position-wise probabilities that secret-block entries are nonzero, conditional on decryption outcomes.The estimates exploit how adding sampled sparse vectors to predefined error patterns can change decryption success or failure.Source: §1 · p. 3
- Genetic-style algorithms select error patterns for balanced success/failure outcomes and maximize pairwise Hamming distances among the pattern set.Balanced outcomes maximize decryption-output entropy, while larger pairwise distances make patterns as independent as possible.Source: §1 · p. 3
- The process builds templates offline, then combines chosen-ciphertext oracle outputs with template information and soft-information ISD for key recovery.The paper describes post-processing costs as comparable to Gaussian elimination.Source: §1 · p. 3
- 2.4-fold fewer calls for hqc-128 than, and 87- and 137-fold reductions for hqc-192 and hqc-256 versus.These are perfect-oracle simulation comparisons; Table 1 summarizes required PC-oracle calls for key recovery.Source: §1 · p. 3, Table 1 · p. 4
- At 95% oracle accuracy, OT-PCA requires 7.6 times fewer calls for hqc-128 than the previous best approach.The paper presents this as robustness under conditions where constructing a perfect PC oracle is difficult.Source: §1 · p. 3
- Power analysis across 120 newly keyed runs on ARM Cortex-M4 tested PQClean hqc-128, with outcomes matching simulations.The evaluation supports practical effectiveness on that platform and implementation.Source: §1 · p. 4
2 Preliminaries
The preliminaries describe HQC’s code-based KEM construction and decoding pipeline, then establish how PC-oracle side-channel attacks use chosen ciphertexts and decryption outcomes to recover secret-key information.
2.1 Mathematical Notations
- The notation uses the polynomial ring R = F2[X]/(X^n − 1), views polynomials as length-n binary vectors, and defines Hamming weight as the number of nonzero entries.The paper also specifies index-set, sampling, and Bernoulli-distribution notation.Source: §2.1 · p. 4
2.2 Overview of Hamming Quasi-Cyclic (HQC)
- HQC is a code-based KEM relying on the difficulty of decoding random quasi-cyclic codes in the Hamming metric, with an IND-CCA KEM formed from an IND-CPA PKE core using the HHK transformation.The described parameter sets use a first-order [128, 8, 64] Reed Muller code.Source: §2.2 · pp. 4–5, Table 2 · p. 5
2.2.1 The Public Key Encryption (PKE) Core in HQC
- HQC’s PKE key generation samples h and fixed-weight x,y, while encryption samples r1,r2,e and forms u = r1 + h·r2 and v = mG + s·r2 + e.The secret key is (x,y), the public key is (h,s), and G generates the concatenated Reed Muller–Reed Solomon code.Source: §2.2.1 · p. 5
- The decoder processes v − u·y; sufficiently low-weight residual error permits recovery of m, while exceeding its correction capability may cause decryption failure.The code construction combines an outer Reed Solomon code with inner duplicated Reed Muller encoding.Source: §2.2.1 · p. 5
2.2.2 Key Encapsulation Mechanism (KEM) in HQC
- In HQC decapsulation, encryption is de-randomized with a seed derived by hashing m, the public key, and a random 128-bit salt, and re-encryption validates ciphertext authenticity.The construction also incorporates hash functions G and K.Source: §2.2.2 · p. 6
2.3 Overview of PC Oracle Based Side-Channel Attacks on HQC
- PC-oracle attacks choose ciphertext components so decoder outcomes depend on secret vector y and indirectly on x through s = x + h · y.The threat model allows chosen ciphertexts and message vectors, and assumes measurable side-channel leakage can support a PC oracle.Source: §2.3 · p. 7
- Prior PC-oracle strategies assume enough errors have pushed the outer Reed Solomon decoder to its limit, so one additional corrupted Reed Muller block causes decryption failure.The attack seeks to correlate failure information with the hidden keys y and x.Source: §2.3 · p. 7
3 The New Attack
OT-PCA uses the public HQC decoder to build offline templates that turn decryption outcomes into soft information about secret positions. It combines optimized error patterns, online PC-oracle queries, and soft-information-guided ISD for full key recovery.
3 The New Attack
- OT-PCA constructs offline templates with the public decoder, then combines their soft information with online PC-oracle outputs for full key recovery.The attack is designed to reduce the number of oracle calls required against HQC.Source: §3 · p. 7, §3.1 · p. 8
3.1 Novel Idea
- Secret-dependent sparse-vector additions flip selected error-pattern bits, shifting decryption success or failure likelihood and revealing position-wise secret probabilities.A position's conditional probability can rise or fall relative to its prior depending on whether a flip increases or decreases the decoder input's weight.Source: §3.1 · p. 8
- Offline templates estimate each position's probability of being one by grouping sampled secret-distribution vectors according to Reed Muller decoding outcome.The construction samples 1,000,000 low-weight vectors and estimates conditional probabilities for each outcome.Source: §3.1 · p. 8
- Error-pattern selection maximizes decryption-output entropy, while a genetic algorithm selects patterns with large pairwise Hamming distances.The first objective seeks near-uniform success/failure outputs; the second optimization provides only marginal additional gains because the first already yields relatively distant patterns.Source: §3.1 · pp. 9–11
3.2 Online Attack
- The online phase shifts Reed Muller blocks, gathers measurements, and combines template probabilities into soft reliability rankings for secret entries.After n1 shifts, it gathers information for the first n1·n2 entries of each secret polynomial; the stated online query count is 2·t·n1.Source: §3.2 · p. 11
3.3 Full Key Recovery from ISD with Soft Information
- Soft-information ISD selects the n + ℓ positions with the smallest probabilities of being one, then uses T0 and T1 to choose positions assumed zero.The selected T1 positions are removed from eH before the remaining index set is split for collision search.Source: §3.3 · pp. 11–12
- The collision procedure searches two lists of bounded-weight patterns for partial-syndrome matches, then verifies candidate solutions.The method limits w0 to 2 or 3 to keep list-generation cost controlled and chooses ℓ so verification cost is negligible.Source: §3.3 · pp. 12–13
- The ISD cost is dominated by max{CGauss, niter·Clist}; with w0=3, added cost is comparable to Gaussian elimination, and with w0=2, it is significantly lower.Success requires an error-free set of T1 assumed-zero positions and no more than w0 errors in each collision-list index set during one of niter rounds.Source: §3.3 · p. 13
4 Results
Simulations show OT-PCA reduces required oracle calls across HQC parameter sets and remains effective with imperfect oracles; real-world power-trace results align with simulations.
4.1 Simulation Results
- Simulations tested 10,000 random keys per scenario, varying hqc-128 oracle accuracy from 1 to 0.9 and assuming a perfect oracle for hqc-192 and hqc-256.The study notes no inherent limitation preventing application to hqc-192 and hqc-256 with less accurate oracles.Source: §4.1 · p. 13
4.1.1 Targeting hqc-128
- As measurements per block increase, errors among the first n reordered secret entries decrease for hqc-128, hqc-192, and hqc-256.For hqc-128, a mean of no more than 5 errors corresponded to success probability above 50% when w0 = 3.Source: §4.1.1 · p. 14, Figure 5 · p. 14, §4.1.2 · p. 16
- For hqc-128, a single template built with a perfect oracle retained high success probabilities even with oracle accuracy ρ = 0.9.With ω0 = 3, success probabilities ranged from 65.95% to 87.02% for t = 11 to 14.Source: §4.1.1 · p. 14
- 58.8× fewer calls than SCA-LDPC and up to 7.6× fewer than Zero-Tester were reported as oracle accuracy decreased.The comparison reports calls needed for success probability above 50%.Source: §4.1.1 · p. 15, Table 4 · p. 15
4.1.2 Targeting hqc-192 and hqc-256
- 87-fold and 137-fold reductions in oracle calls for hqc-192 and hqc-256, respectively, compare OT-PCA with Schamberger et al..OT-PCA requires 22×56 calls for hqc-192 and 14×90 for hqc-256, versus 1920×56 and 1920×90, respectively.Source: §4.1.2 · pp. 16–17
4.2 Real-World Validation
- Real-world hqc-128 results aligned with simulations using seven oracle calls per block across 120 newly generated key pairs.The CNN classified all 10,138 test traces correctly before being applied to traces from the 120 key pairs.Source: §4.2 · pp. 18–19, Table 7 · p. 19
5 Discussion
OT-PCA is presented as more robust than Zero-Tester and applicable to hqc-192, where Zero-Tester depends on rare secret-key patterns. The authors also outline a possible extension to multi-value or parallel oracles, which remains to be evaluated.
5.1 More on Comparison with the Zero-Tester Method
- Zero-Tester is effective for only about 15% of hqc-192 keys because it relies on long runs of zero entries in secret polynomials.The likelihood of finding an all-zero block of length n2 within the secret vectors is low.Source: §5.1 · p. 19
- For hqc-192, increasing measurements per Reed Muller block reduces decision errors in the first n positions of reordered z.The cited section provides sample complexity, post-processing complexity, and full-key-recovery probability for a perfect oracle.Source: §5.1 · p. 19, Figure 8 · p. 20
5.2 Extension to Multi-value or Parallel PC oracle
- OT-PCA can extend to multi-value or parallel oracles through templates for more than two decrypted messages, but extensive experiments remain necessary.Preliminary investigations found gains over binary PC oracle attacks.Source: §5.2 · pp. 19–20
6 Concluding Remarks
OT-PCA uses offline templates built from the publicly available Reed Muller decoder to supply soft information for key recovery. Simulations and ARM Cortex-M4 power-trace tests support fewer oracle calls than state-of-the-art attacks, while accurate-oracle countermeasures can harden the attack.
6 Concluding Remarks
- OT-PCA uses offline Reed Muller decoder templates to provide soft information for key recovery, reducing oracle calls and matching simulations in real-world power-trace tests.The authors report more robustness to oracle inaccuracy and significantly better hqc-192 performance than.Source: §6 · p. 20
- Constant-time implementation, masking, or shuffling can make accurate PC oracle construction difficult or infeasible, hardening the attack.The paper identifies evaluating multi-value or parallel oracle attacks and extending OT-PCA to other schemes as future work.Source: §6 · p. 20