Paper 2026/071

Reed–Muller Encoding Leakage Enables Single-Trace Message Recovery in HQC

Abstract

HQC is a code-based key-encapsulation mechanism standardized by NIST, whose decapsulation follows a Fujisaki--Okamoto (FO) transform and therefore re-executes encryption-side encoding during deterministic re-encryption. In this paper, we show that this design choice exposes a critical leakage point in the \emph{Reed--Muller (RM) encoding} routine: across the NIST-submitted implementations, the HQC team's official codebase, and the PQClean implementations. We demonstrate the practical impact of this leakage on a ChipWhisperer CW308 UFO board with an STM32F303 (Cortex-M4) target. Using a total of 5{,}000 power traces for profiling and evaluation, we recover the full 128-bit encapsulation message from a \emph{single} decapsulation trace with up to 96.9\% success. In comparison, the current state of the art for single-trace HQC message recovery based on \emph{soft-analytical side-channel attacks} (SASCA) reports profiling on the order of 500{,}000 traces; our approach therefore reduces the required profiling budget by two orders of magnitude while achieving comparable single-trace capability. Beyond session-key compromise, we show that direct recovery of the decrypted message can serve as an oracle primitive that substantially lowers the cost of oracle instantiation in prior HQC secret-key recovery frameworks. While prior oracle instantiations typically map leakage to a discrete set of task-specific labels, our approach recovers the decrypted message itself, and thus applies uniformly over the full message space (i.e., arbitrary $m'$ values). Concretely, we reduce the profiling cost required to instantiate a \emph{decryption success/failure} oracle, multi-value plaintext-checking, and full-decryption oracles by approximately 90.3\%, 84.83\%, and 26.7\%, respectively.