Hqc Decryption Enables 99.69% Recovery Via Single-Trace Simple Power Analysis

The security of the Hamming Quasi-Cyclic (HQC) cryptosystem, recently selected for standardisation by the NIST Post-Quantum Cryptography project, faces a new challenge as researchers demonstrate a practical vulnerability. Pavel Velek, Tomáš Rabas, and Jiří Buček, all from the Czech Technical University in Prague, have successfully executed a Simple Power Analysis (SPA) attack targeting the polynomial multiplication stage of HQC decryption. Their work reveals that power consumption leakage during this process can be exploited to compromise the system, achieving a remarkably high 99.69% success rate in their experiments. This discovery is significant as it highlights a potential weakness in a leading post-quantum candidate and prompts consideration of robust countermeasures to ensure its long-term security.

Their work reveals that power consumption leakage during this process can be exploited to compromise the system, achieving a remarkably high 99.69% success rate in their experiments. The team targeted the base-case 64-bit multiplication algorithm within a recursive Karatsuba implementation, focusing on a single ‘limb’ of the private key. This multiplication utilizes a window method and a lookup table to compute the product of two 64-bit values. The innovative aspect of the attack lies in its ability to recover the private key directly from a single power trace, differing from other approaches that aim to recover a shared secret key after the Reed-Solomon decoder.

Researchers meticulously analyzed the base-case multiplication, revealing that the creation and access of the lookup table during the algorithm’s execution leaked crucial information. The algorithm constructs a 16-entry table storing multiples of one operand, masking the four highest bits to prevent overflow. During each iteration, four bits of the other operand are used to index the table, retrieving a value added to intermediate results. The team harnessed this process, demonstrating a 99.69% success rate over 10,000 attack attempts. This method achieves a high success rate without relying on profiling or machine learning, distinguishing it from related work.

The study further investigated potential countermeasures, assessing their time complexity to provide a comprehensive evaluation of the vulnerability and possible mitigations. By focusing on the fundamental polynomial multiplication, the research pioneers a direct attack on the private key, offering valuable insights into the security of code-based cryptography and informing the ongoing standardization process. The authors developed two alternative base_mul functions: base_mul2, which eliminates the lookup table, and base_mul3, which removes the countermeasure against cache timing attacks. Their work focused on a vulnerability within the HQC decryption process, specifically the initial polynomial multiplication stage. This approach bypasses the need for complex profiling or machine learning techniques, presenting a heightened practical threat to implementations of the HQC system.

To conduct the attack, the study employed a ChipWhisperer-Lite board to capture power traces during decryption operations. The team focused on the base-case 64-bit multiplication algorithm within a recursive Karatsuba implementation, targeting a single ‘limb’ of the private key. The algorithm, based on the work of Brent et al. (2008), utilizes a window method and a lookup table to compute the product of two 64-bit values. Data shows that the countermeasure intended to prevent cache timing attacks inadvertently creates a discernible pattern in power consumption, directly correlated to the bits of the private key polynomial.

Researchers meticulously analyzed the base-case multiplication, revealing that the predictable access pattern to the lookup table leaks crucial information. The multiplication algorithm operates by creating a lookup table of multiples of a value, ‘b’, and then accessing this table based on the bits of another value, ‘a’. The implementation masks the four highest bits of ‘b’ to prevent overflow, and then iterates through all 16 entries of the lookup table during each processing step. This consistent access, while intended to thwart timing attacks, provides the necessary signal for the SPA attack. Tests prove that by repeating the attack on different limbs of the private key, an attacker could potentially reconstruct the entire key.

This breakthrough highlights a practical threat to the security of HQC as currently deployed. The target implementation, sourced from the NIST Round 4 submission and integrated into both PQClean and liboqs libraries, was chosen for its accessibility and widespread use. The study further investigated potential countermeasures, assessing their time complexity to provide a comprehensive evaluation of the vulnerability and possible mitigations. Researchers demonstrated the recovery of a significant portion of the private key by analysing power consumption during the base multiplication function within HQC decryption, a function central to the Karatsuba algorithm used in prominent implementations. The attack, executed using a ChipWhisperer-Lite board, achieved a high success rate of 99.69% across ten thousand attempts, highlighting a practical vulnerability in current HQC implementations found within the PQClean and liboqs libraries.

To address this vulnerability, the authors proposed and implemented two modified multiplication functions, base_mul2 and base_mul3, designed to resist the demonstrated SPA attack. Importantly, these new functions not only provide protection against the attack but also offer a substantial performance improvement, achieving speed-ups of 2.3 and 6.9times respectively compared to the original base_mul function. The authors acknowledge that these functions may still be susceptible to other side-channel attacks, such as cache timing attacks, but suggest masking as a potential countermeasure.

Future research will focus on analysing other HQC implementations to assess their resilience against side-channel attacks, continuing the effort to secure this promising post-quantum cryptographic scheme. The research contributes to the ongoing effort to secure post-quantum cryptography against practical side-channel attacks, identifying a security weakness in a specific implementation of HQC, demonstrating a successful attack, and proposing and validating improved implementations that are both more secure and faster.