A New Key Recovery Side-Channel Attack on HQC with Chosen Ciphertext
Abstract
Hamming Quasi-Cyclic (HQC) is a code-based candidate of NIST post-quantum standardization procedure. The decoding steps of code-based cryptosystems are known to be vulnerable to side-channel attacks and HQC is no exception to this rule. In this paper, we present a new key recovery side-channel attack on HQC with chosen ciphertext. Our attack takes advantage of the reuse of a static secret key on a micro-controller with a physical access. The goal is to retrieve the static secret key by targeting the Reed-Muller decoding step of the decapsulation and more precisely the Hadamard transform. This function is known for its diffusion property, a property that we exploit through side-channel analysis. The side-channel information is used to build an Oracle that distinguishes between several decoding patterns of the Reed-Muller codes. We show how to query the Oracle such that the responses give a full information about the static secret key. Experiments show that less than $20.000$ electromagnetic attack traces are sufficient to retrieve the whole static secret key used for the decapsulation. Finally, we present a masking-based countermeasure to thwart our attack.