From Multiplication to Recovery: A Single-trace Side-Channel Attack on HQC

Abstract

Hamming Quasi-Cyclic (HQC) has been selected by NIST as a standard for code-based Post-Quantum Cryptography (PQC) Key Encapsulation Mechanisms (KEMs). While HQC offers robust theoretical security based on the Decisional Quasi- Cyclic Syndrome Decoding problem, its physical implementation is vulnerable to side-channel attacks. Previous research has predominantly focused on vulnerabilities during the decoding stage. However, the Karatsuba polynomial multiplication in the latest HQC specifications has not been thoroughly analyzed. In this work, we present a comprehensive Soft-Analytical Side-Channel Attack (SASCA) targeting the implementation of the iterative Karatsuba algorithm. We present the optimized factor graph and algorithm tailored to the binary values and sparsity of HQC to make the SASCA more practical. Furthermore, we introduce a joint recovery framework that combines the leakage of polynomial multiplication with the leakage of decoder using valid ciphertexts. We demonstrate the efficiency of our attack against the reference implementation and extend our attack to the Liboqs library, achieving a high success rate even in the presence of high noise levels.