Key Recovery from Side-Channel Power Analysis Attacks on Non-SIMD HQC Decryption

HQC is a code-based cryptosystem that has recently been announced for standardization after the fourth round of the NIST postquantum cryptography standardization process. During this process, the NIST specifically required submitters to provide two kinds of implementation: a reference one, meant to serve lisibility and compliance with the specifications; and an optimized one, aimed at showing the performance of the scheme alongside other desirable properties such as resilience against implementation misuse or side-channel analysis. While most side-channel attacks regarding PQC candidates running in this process were mounted over reference implementations, very few consider the optimized, allegedly side-channel resistant (at least, constant-time), implementations. Unfortunately, HQC optimized version only targets x86-64 with Single Instruction Multiple Data (SIMD) support, which reduces the code portability, especially for non-generalist computers. In this work, we present two power side-channel attacks on the optimized HQC implementation with just the SIMD support deactivated. We show that the power leaks enough information to recover the private key, assuming the adversary can ask the target to replay a legitimate decryption with the same inputs. Under this assumption, we first present a keyrecovery attack targeting standard Instruction Set Architectures (ARM T32, RISC-V, x86-64) and compiler optimization levels. It is based on the well known Hamming Distance model of power consumption leakage, and exposes the key from a single oracle call. During execution on a real target, we show that a different leakage, stemming from to the micro-architecture, simplifies the recovery of the private key. This more direct second attack, succeeds with a 99% chance from 83 executions of the same legitimate decryption. While the weakness leveraged in this work seems quite devastating, we discuss simple yet effective and efficient countermeasures to prevent such a key-recovery.

The first code-based cryptosystem dates back to 1978, with the seminal work of Robert J. McEliece [28]. He suggested to use binary Goppa codes, for which a