TL;DR
This paper presents the first power side-channel attack on the Hamming Quasi-Cyclic (HQC) Key Encapsulation Mechanism (KEM), a candidate for post-quantum cryptography. By analyzing power consumption during decryption, the authors can extract a significant portion of the secret key, demonstrating a practical threat to HQC's security.
What Problem Does This Paper Address?
The advent of quantum computers poses a significant threat to current public-key cryptography. To counter 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, notable for its security not relying on hiding the underlying code structure. While HQC is designed to be secure against classical and quantum attacks (IND-CCA2 secure), this paper investigates a different threat vector: side-channel attacks. Specifically, they target power side-channel attacks, which exploit variations in power consumption during cryptographic operations to infer secret information. Previous attacks on HQC variants have used timing side-channels, but the authors aim to demonstrate the effectiveness of power analysis, even against constant-time implementations of its internal components.
Methods
The core of the attack relies on building a "decoding oracle" that can determine if the internal BCH decoder in HQC's decryption process 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.
Here's a breakdown of their approach:
- Power Side-Channel Analysis: They measure the power consumption of the HQC implementation running on an ARM Cortex-M4 microcontroller.
- Decoding Oracle Construction:
- They first identify "points of interest" (POIs) in the power traces using Welch's t-test, which helps distinguish between different execution paths.
- They then create "templates" representing the typical power consumption for two scenarios: when the BCH decoder corrects an error and when it doesn't. This initialization does not require knowledge of the secret key.
- By capturing a power trace for a specific decryption operation and comparing it to the templates, the oracle can predict whether an error correction occurred.
- Key Retrieval:
- The oracle is then used to query specific crafted ciphertexts. By observing the oracle's output (whether an error was corrected), they can deduce information about the secret key, particularly the support (non-zero positions) of the secret key vector
y.
- The oracle is then used to query specific crafted ciphertexts. By observing the oracle's output (whether an error was corrected), they can deduce information about the secret key, particularly the support (non-zero positions) of the secret key vector
- They first focus on retrieving
y(0), a significant part of the secret key, by systematically probing different parts of the key space. - For the remaining part of the key,
y(1), they employ a linear algebra approach. - In rare cases where the initial attack doesn't fully recover the key, they propose a modification of information set decoding to complete the retrieval.
Datasets
Not discussed in the paper. The evaluation uses a custom setup with an STM32F415RGT6 ARM Cortex-M4 microcontroller and a PicoScope 6402D USB-oscilloscope.
Key Insights and Ideas
- Power Consumption Reveals Error Correction: The most crucial insight is that the power consumption of the HQC's BCH decoder exhibits a distinguishable pattern depending on whether it needs to correct an error. This is a critical vulnerability, even in constant-time implementations.
- Oracle-Based Attack: The attack cleverly transforms the side-channel leakage into a functional oracle that reveals information about the internal state of the decryption process, specifically error correction events.
- Key Structure Exploitation: The attack leverages the sparse nature of the HQC secret key. By targeting specific parts of the key and analyzing the oracle's responses, they can efficiently narrow down the possibilities.
- Practicality Demonstrated: The attack is shown to be practical, requiring a relatively small number of measurements (less than 10,000 for the core attack) on a common microcontroller.
Key Results
- The authors successfully demonstrate a power side-channel attack on the HQC KEM.
- They show that less than 10,000 measurements are sufficient to mount the attack on the HQC reference implementation running on an ARM Cortex-M4.
- The attack can retrieve a large part of the secret key, and a linear algebra solution is provided to recover the remainder.
- The attack is effective against 93.2% of possible keys for HQC-128 with the demonstrated measurement count.
- The oracle initialization requires a very small number of traces (as few as four for initialization and two per class for classification).
Limitations and Future Work
- Key Distribution Dependency: The success rate of the attack is highly dependent on the distribution of ones in the secret key. While they achieve high success rates for common key types, there are rare cases where the attack might not fully succeed without further effort.
- Rare Case Mitigation: For the rare cases where the initial attack doesn't fully recover the key, they propose a modified information set decoding algorithm, but this might require more measurements.
- Future Work: The paper highlights the need for side-channel countermeasures for the HQC KEM, suggesting this is a high-priority research area. Further work could explore optimizing the attack for different parameter sets or developing more robust defenses against such power analysis techniques.
Summary updated