A Power Side-Channel Attack on the CCA2-Secure HQC KEM

Thomas Schamberger, Julian Renner, Georg Sigl, Antonia Wachter-Zeh

TL;DR

This paper presents the first power side-channel attack against the Hamming Quasi-Cyclic (HQC) Key Encapsulation Mechanism (KEM), a candidate for post-quantum cryptography. The attack exploits power consumption variations during the HQC decryption process to extract the secret key, demonstrating a practical threat to HQC's security with a relatively small number of measurements.

What Problem Does This Paper Address?

The advent of quantum computers poses a significant threat to current public-key cryptography. To address this, the National Institute of Standards and Technology (NIST) is standardizing post-quantum cryptography (PQC) algorithms. Hamming Quasi-Cyclic (HQC) is a promising code-based PQC candidate that offers advantages like small public key sizes and precise decryption failure rate estimation. Unlike some other code-based systems, HQC's security doesn't rely on hiding the underlying code structure. However, like any cryptographic system, HQC is susceptible to side-channel attacks, which exploit physical leakage (like power consumption) to infer secret information. While previous attacks on HQC focused on timing side-channels, this paper tackles the more challenging power side-channel attack vector, specifically targeting the CCA2-secure KEM version of HQC. The challenge lies in the fact that HQC's decryption algorithm is designed to be constant-time, making traditional timing attacks less effective, and the CCA2 security property means decryption failures are signaled, which can be used to thwart naive attacks.

Methods

The core of the attack relies on building a "decoding oracle" that can determine whether the internal BCH decoder in HQC's decryption algorithm had to correct an error. This oracle is constructed using a power side-channel analysis technique based on template matching and a sum of squared differences metric.

  1. Power Side-Channel Analysis: The researchers measure the power consumption of the HQC implementation running on an ARM Cortex-M4 microcontroller during decryption. They observe that the power consumption patterns differ subtly depending on whether the BCH decoder needs to correct an error.
  2. Decoding Oracle Construction:
    • POI Detection: Welch's t-test is used to identify "points of interest" (POIs) in the power traces where the leakage is most significant for distinguishing between error-correction and non-error-correction events.
  3. Template Matching: For each of the two classes (error corrected vs. not corrected), a "template" is created by averaging power traces from a set of known inputs.
  4. Classification: When presented with a new power trace from an unknown input, the oracle compares it to both templates using the sum of squared differences. The class with the lower difference is predicted.
  5. Secret Key Retrieval:
    • Targeting y(0): The attack first focuses on retrieving a significant portion of the secret key, denoted as y(0), which is crucial for decryption. This is achieved by carefully crafting specific ciphertexts and querying the decoding oracle. By observing the oracle's output for these crafted inputs, the researchers can deduce information about the "support" (the positions of non-zero elements) of y(0). This process involves determining a "super support" and then refining it to find the exact support.
  6. Targeting y(1): The remaining part of the secret key, y(1), is then recovered using linear algebra techniques, leveraging the information gained about y(0).
  7. Information Set Decoding (ISD): In rare cases where the side-channel information is noisy or the secret key has a specific structure, a modified information set decoding algorithm is employed to recover the key.

Datasets

Not discussed in the paper. The evaluation uses the reference implementation of HQC-128 running on an STM32F415RGT6 ARM Cortex-M4 microcontroller.

Key Insights and Ideas

  • Power Leakage in Constant-Time Implementations: The paper demonstrates that even constant-time implementations can leak exploitable information through power consumption, challenging the assumption that constant-time execution guarantees side-channel resistance.
  • Decoding Oracle as a Powerful Tool: The ability to build a reliable decoding oracle from power traces is a significant enabler for this attack. This oracle effectively bypasses the CCA2 security by revealing internal decryption behavior.
  • Exploiting BCH Decoder Behavior: The attack cleverly leverages the specific way the BCH decoder in HQC operates, particularly how it handles errors, to create distinguishable power signatures.
  • Key Structure Matters: The success rate of the attack is shown to be highly dependent on the distribution of non-zero elements in the secret key. This highlights the importance of analyzing key structures in side-channel attack resilience.
  • Practicality of the Attack: The attack is shown to be practical, requiring a relatively low number of measurements (less than 10,000 for the decoding step) to retrieve the entire secret key for HQC-128.

Key Results

  • The paper successfully demonstrates the first power side-channel attack on the CCA2-secure HQC KEM.
  • The attack can retrieve the entire secret key for the HQC-128 reference implementation.
  • Initialization: Only four traces are sufficient for initializing the decoding oracle.
  • Attack Efficiency: Less than 10,000 measurements of the decoding step are sufficient to mount the attack.
  • Success Rate: The attack can successfully retrieve the secret key for 93.2% of possible keys in HQC-128 with less than 10,000 traces.
  • The attack methodology is adaptable to different parameter sets of HQC.

Limitations and Future Work

  • Key Distribution Dependency: The attack's success rate is significantly influenced by the Hamming weight and distribution of non-zero elements in the secret key. While the paper provides solutions for specific key types (e.g., using linear algebra or modified ISD), there are rare cases where the entire key cannot be recovered directly.
  • Measurement Noise: Errors during power measurements or specific secret key structures can lead to incomplete support recovery, necessitating the use of modified ISD algorithms.
  • Future Work: The authors suggest that the attack highlights the need for side-channel countermeasures for the BCH decoder used in HQC. Further research could explore more robust defenses against such power-based attacks. The paper also mentions that the attack methodology can be adapted for a larger range of keys, but this would require a significant increase in measurement traces.

Summary updated

BibTeX
@article{schamberger2020power,
  author = {Thomas Schamberger and Julian Renner and Georg Sigl and Antonia Wachter-Zeh},
  title = {{A Power Side-Channel Attack on the CCA2-Secure HQC KEM}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
  url = {https://openreview.net/forum?id=V3Ye2egrnBag},
}

Loading related content...

Figure