Breaking Optimized HQC: The First Cache-Timing Full Decryption Oracle Key-Recovery... (Crypto 2026)

Hi everyone. How are you doing? I'll present joint work with Chen Gu on a new cache timing for decryption key recovery attack on optimized HQC. HQC has been selected by NIST as a code-based alternative to ML-KEM and is moving towards standardization as FIPS 207. Before its deployment, understanding its implementation security is very important. We already know from previous work on ML-KEM that compiler optimizations can undermine source-level constant-time guarantees. For example, Kyber/Slash exposed the variable-time division instructions and other cases involved the compiler-generated secret-dependent control flows. For HQC, much of the recent work has focused on reference implementations using power or electromagnetic measurements that typically require physical access or close proximity or controlled channel attackers with privileged capabilities. This leaves an important question. How resilient is the high-performance AVX2 optimized implementation against the standard unprivileged adversary? Our focus is the optimized HQC implementation running on a commodity CPU with a co-located unprivileged user space attacker. Under this threat model, we demonstrate an end-to-end key recovery attack on the AVX2 optimized implementation. This work has three main contributions. First, we identify a compiler-induced vulnerability in a find peaks function of the inner Reed-Muller decoder. The source code uses constant time mask selection. However, certain versions of the clan compiler transform this logic into secret dependent conditional branches in the compiled binary. Second, we exploit the resulting control flow using flush and reload on the shared HQC library to build an full decryption style oracle. With carefully chosen ciphertext, the cache trace reveals one bit information of the decoded byte for individual Reed-Muller blocks. Lastly, we develop a GPU accelerated soft information set decoding implementation. Using oracle predictions from the side channel and offline templates, we obtain reliability information about the secret key bits. The soft IAS implementation then uses this information to recover the secret key vector. For HQC 1, the online trace collection takes less than 10 seconds followed by less than 30 minutes of post-processing. Here is the overview of the presentation. I will start with the relevant HQC background. The HQC PKE core has three components: key generation, encryption, and decryption. During key generation, two sparse secret vectors X and Y are sampled together with a uniformly random vector H. The public key consists of H and S, and S is computed from X, Y, and H. To encrypt a message, the scheme derives three sparse vectors R1, R2, and E. It then computes ciphertext components U and V using these values, the message M, and the public key components. During decryption, the receiver first uses the ciphertext and his secret key to compute the received vector V. The decoder now attempts to recover a message M prime from this received vector. The CAM wraps this PKE using an F4 transform. The encapsulation first decrypts the ciphertext, derives new encryption randomness from the recovered message, and re-encrypts to validate the ciphertext. More details of the decryption process that our attack targets. HQC uses a concatenated code consisting of an outer Reed-Solomon code and an inner duplicated Reed-Muller code. Received vector V is divided into N1 independent blocks. Each block is processed by Reed-Muller decoder. The block decodings are independent, so they can be parallelized. However, in software, they're typically processed uh sequentially in a loop. Three main operations are performed. First, expand and assume combines the duplicated components. Next, the Hadamard transform computes the relevant correlations. Finally, find peaks identifies the largest correlation output of the Reed-Muller decoding byte for that block, denoted as MI hat. The collection of these bytes is then passed to the outer Reed-Solomon decoder to produce the final message M prime. Full decryption oracle attack on HQC has been proposed in previous work. The attack exploits the decoding of the N1 Reed-Muller blocks. Our work builds on this FD attack. A full decryption oracle is defined as one that returns the N1 Reed-Muller decoding results in a single query with perfect accuracy. Each result is exactly the decoded byte for that The attacker constructs chosen ciphertext to probe the secret key part X or Y separately. For example, by setting R1 to 0 and R2 to 1, the received vector in the decryption process consists of the secret part X, the encoded message, and a chosen error vector E. The error vector E is constructed by repeating the same optimized error pattern epsilon across all N1 blocks. The offline template method is used to obtain soft information about secret key bits. Given a message M and the carefully chosen error pattern epsilon, one can build offline templates that maps each attainable decoding result to the empirical probability that each position in a secret key block is one. In this way, side channel leakage on the Reed-Muller decoding result can be turned into soft information about a secret key bits. Our attack is based on this FD attack framework. In our setting, Alice is the CCA attacker and Bob is the victim. Alice is collocated with Bob and operates entirely in user space without administrative privileges. Their processes share the last level cache, and the HQ implementation is loaded as a shared library. At the core of the attack is a compiler-induced conditional branching during Reed-Muller coding. As a result, a particular cache line is accessed only for certain Reed-Muller decoding results. This creates a cache timing leakage channel that Alice can exploit using flush and reload. To launch the attack, Alice constructs malformed ciphertext using Bob's public key and specific values of R1, R2, and E, and then submits them to Bob for decapsulation. When Bob is decapsulating, Alice monitors the vulnerable cache line. She flashes the line from the cache with briefly and then reloads it while measuring the reload time. A faster reload tells Alice that Bob accessed the line during decapsulation. While a slow reload indicates that Bob did not access the line. Each cache hit or miss derive or reviews the category of the Reed-Muller decoding result. Pre-built offline templates translate these observations into soft information about the secret key bits. Finally, our new soft S-D implementation combines this information with the public key to recover the full secret key. We now look at how the vulnerability is introduced. On the left is the relevant source code from the find pics function. The loop selects one of the 16 values according to the lower four bits of the Reed-Muller decoding result. The selection uses a mask together with bitwise operations. All 16 iterations are intended to follow the same control flow. On the right is the binary generated for the AVX2 implementation by clang 14 with optimization level O3. Here, the lower four bits of the Reed-Muller decoding result are stored in the register RDI. Instead of preserving the mask selection, the compiler transforms it into sequence of conditional jumps. It compares RDI with values from 0 to 15 and branches to different code blocks depending on whether the comparison evaluates to true or false. The figure on the left illustrates this conditional branching in a binary. RDI is first tested against 0 and execution branches to one of two basic blocks depending on whether RDI is 0. In both of these blocks, RDI is then compared with one. If RDI equals to one, execution moves to the same compare true block in a blue region, regardless of uh which preceding block it came from. Otherwise, execution moves to the same compare false block in a red region. In both destination blocks, RDI is next compared with two, and this pattern of comparison and branching continues. Take the first block in a blue region as an example. It is executed only when RDI equals one. Its counterpart in a red region is executed otherwise. The execution of each basic block therefore identifies a subset of Reed-Muller decoding results. For nonzero RDI, exactly one blue block is executed. In our build, the cache line B600 contains the blue blocks for RDI values 3, 4, 5, and 6. So, it is accessed exactly when M hat modulo 16 lies in this set. By monitoring whether this cache line is accessed, we construct a hit-miss oracle that tells whether an Reed-Muller decoding result belongs to this category. Knowing that a cache line hit or miss reveals the category of an Reed-Muller decoding result, we want to see whether this category is related to the reliabilities of the secret key bits as in the offline template method. We optimize the error pattern epsilon so that when it is combined with the random secret key block, the decoding result falls into the hit category with approximately 50% probability. We then build an offline template for this error pattern and plot the empirical probability that a bit at each position in a secret key block is one conditional on a hit or miss. The figure clearly shows that these probabilities deviate from the a priori probability. This confirms that a hit-or-miss leaks information about secret key bits. To realize this hit-miss algorithm practice, we first calibrate the cache timing channel. To distinguish a hit from a miss, we measure load times from the L1 cache and main memory and select a threshold of 110 clock cycles. In a flush and reload traces, a reload time below this value is classified as a hit, while one above this value is a miss. To determine the temporal resolution of the channel, we measure the number of clock cycles per Reed-Muller block decoding. We find per block decoding short relative to the interval required for reliable flush and reload probe. System jitter and prefetching also make it difficult to associate each hit-or-miss with the corresponding iteration of the Reed-Muller decoding loop. We therefore design a several texts to space out the target blocks, so that each several text targets only one or a few blocks rather than all and one blocks at once. Here are the two several text constructions we use. R1 and R2 are chosen as in the standard FD attack. The difference lies in how the error vector is configured. In method one to target block B of the secret key vector, we place the optimized error pattern epsilon in the corresponding block of the error vector and set all other blocks to zero. In this way, the observed the hit-or-miss is determined entirely by the Reed-Muller decoding result of the target block. In method two, an always hit pattern is put in block zero as a synchronization marker, followed by six zero blocks. From block seven onward, epsilon is placed in three blocks spaced 13 blocks apart. In this way, with each ciphertext, we target three blocks in a key vector, but we lose information about the first seven blocks. We validate our tag with 30 random HQC-1 key pairs using a MacBook Pro with an Intel i7 processor and the Musique toolkit for flush and reload. For method one, each ciphertext is repeated 50 times. We classify the target block as a hit only if the hit count exceeds 40. For method two, each ciphertext is repeated 11 times. The always hit block block zero is used to align the traces. We divide the aligned trace into consecutive regions. Each region is assigned to one of the three target blocks. We then determine which blocks' oracle output by majority voting over the 11 traces. The oracle predictions are mapped into key bit reliabilities using the offline templates and then aggregated across towel error patterns. We rank the secret key positions from most likely to be zero to most likely to be one. As more error patterns are used, the average number of actual ones in the first M positions decreases. This shows that the reliability ranking improves while more error patterns are used and this provides useful input to uh the soft um information set decoding. The remaining task is recover the sparse secret vector from the public syndrome equation. An SD attempt is more likely to succeed when the information set contains only the few non-zero secret bits. From the side channel, we gain soft information LJ for each secret key position J. We use this information to favor positions that are more likely to be zero when selecting the information set. We developed a new soft ISD implementation for Apple Silicon building on the weighted sampling approach of prior work. Each attempt uses a two-list meet-in-the-middle search with multiple re-randomized runs. The Apple GPU accelerates the parallel hash join step. On a Mac Studio M3 Ultra, 28 parallel workers together achieve around 2.3 to 2.5 attempts per second. Each worker uses roughly 7 GB of memory for about 200 GB in total. This figure summarizes the full key recovery results across 30 randomly generated keys. Each run is capped at 2 to the power of 12 attempts. The percentages show the success rate for each configuration, and the box plots show the number of attempts for successful recoveries. To conclude, certain clang versions transform the masked selection in find peaks into secret-dependent branches in a emitted binary for the optimized HQC implementation. The resulting cache line access leaks information about the inner Reed-Muller decoding output. We show that this enables an FD-style oracle attack using unprivileged flash and reload against a shared HQC library. We develop a GPU-accelerated soft ISD implementation to turn this leakage into full key recovery. We also find that similar compiler-induced vulnerabilities appear in other clang versions. Static linking removes the shared library condition for this particular attack, but not the underlying leakage, which may still be exploited using prime and probe or interested execution environments. So, constant time claims must always be verified on the emitted binary. This concludes my presentation. Thank you for your attention.