On the Timing Leakage of the Deterministic Re-encryption in HQC KEM

Well before large-scale quantum computers will be available, traditional cryptosystems must be transitioned to post-quantum secure schemes. The NIST PQC competition aims to standardize suitable cryptographic schemes. Candidates are evaluated not only on their formal security strengths, but are also judged based on the security of the optimized implementation, for example, with regard to resistance against side-channel attacks. HQC is a promising code-based key encapsulation scheme and selected as an alternate candidate in the third round of the competition, which puts it on track for getting standardized separately to the finalists, in a fourth round. Despite having already received heavy scrutiny with regard to side channel attacks, in this paper, we show a novel timing vulnerability in the optimized implementations of HQC, leading to a full secret key recovery. The attack is both practical, requiring only approx. 866,000 idealized decapsulation timing oracle queries in the 128-bit security setting, and structurally different from previously identified attacks on HQC: Previously, exploitable side-channel leakages have been identified in the BCH decoder of a previously submitted version, in the ciphertext check as well as in the PRF of the Fujisaki-Okamoto (FO) transformation employed by several NIST PQC KEM candidates. In contrast, our attack uses the fact that the rejection sampling routine invoked during the deterministic re-encryption of the KEM decapsulation leaks secret-dependent timing information. These timing leaks can be efficiently exploited to recover the secret key when HQC is instantiated with the (now constant-time) BCH decoder, as well as with the RMRS decoder of the current submission. Besides a detailed analysis of the new attack, we discuss possible countermeasures and their limits.