International Association
for Cryptologic Research

Hamming Quasi-Cyclic (HQC) has recently been selected by NIST, after the Round 4 submission, as a postquantum key encapsulation mechanism (KEM) standard and will soon be widely deployed. Therefore, it is important to ensure its implementation is constant-time, i.e., resistant to side-channel attacks. Existing timing attacks on HQC exploit non-constant-time source code and the decryption that is vulnerable to chosen-ciphertext attacks. These active attacks require constructing thousands of invalid ciphertexts, and thus, they can be easily detected. The latest HQC implementation has mitigated all these attacks by making its source code constant-time.

In this work, we provide a new perspective on reviewing the implementation of HQC and exploiting timing leakages. For the first time, we show that an attacker can recover the secret key of HQC without targeting the CCA-insecure decryption and internal states of message decryption. Specifically, an attacker can exploit the timing leakages that occur when processing sparse vectors, which are ciphertext-independent, to recover the secret key by measuring the leakages only once. We find two such timing leakages in the latest stable HQC implementation, supposedly constant-time, and practically extract the leakages even when the process is protected by AMD Secure Encryption Virtualization. We also show that a power side-channel can extract similar leakages on embedded devices.

Our findings apply to all code-based KEMs that are submitted to the NIST Round 4 PQC submission. We show that an attacker can also perform similar passive attacks to recover the session key of BIKE and Classic McEliece. To help write constant-time code, we propose and test a workflow that uses CT-grind when developing the code. We find that CT-grind can effectively find all timing leakages in various implementations of HQC. Therefore, we suggest that cryptographic developers constantly use constant-time analysis tools when developing code.