Timing side channels in HQC implementations

Short answer: Three papers report timing side-channel attacks on implementations of HQC, a code-based key encapsulation scheme: a 2019 attack on BCH decoding time, a 2023 cache-timing attack on the reference implementation, and a 2024 USENIX Security paper on division instruction timing. The authors report key recovery in each case. These are implementation attacks on specific software, not breaks of the underlying scheme.

How does the BCH decoding timing attack work?

A practicable chosen ciphertext timing attack retrieves the HQC secret key by exploiting a correlation between the weight of the error to be decoded and the running time of the BCH decoding algorithm. For 128-bit security parameters, this attack runs in less than a minute on a desktop computer. It requires 5,441 decoding requests and achieves a success probability of approximately 93 percent.

To prevent this specific attack, the authors propose a constant time algorithm for the decoding of BCH codes. Their implementation achieves constant time execution of the decoding process without a significant performance penalty. This countermeasure addresses the variable execution time inherent in standard decoding routines.

What is the cache-timing attack mechanism?

The 2023 authors say they present the first chosen-ciphertext cache-timing attacks on the reference implementation of HQC, using a plaintext-checking (PC) oracle. This oracle uses side-channel information to check if a given ciphertext decrypts to a given message. With access to the public key, an attacker can encrypt messages. Together with the PC oracle, this setup is sufficient to perform a key-recovery attack.

The attack distinguishes implementations by identifying a vulnerability during the randomness generation process of two vectors in the reference implementation. The authors formally introduce a concept called the cache line indicator to describe the timing behavior in the HQC implementation. Deducing this indicator provides the basis for the cache-timing based distinguisher.

How does division instruction timing affect security?

A critical side-channel vulnerability exists in the HQC round 4 optimized implementation due to the use of the modulo operator. Compilers may optimize modulo operations with compile-time known divisors into constant-time Barrett reductions, but this optimization is not guaranteed. When a modulo operation is used in a loop, the compiler may emit division instructions with variable execution time depending on the numerator.

When the numerator depends on secret data, this yields a timing side-channel named Divide and Surrender (DaS). For processors supporting Simultaneous Multithreading (SMT), a new approach called DIV-SMT enables precisely measuring small division timing variations. The 2024 authors report that using only 100 such side-channel traces they can build a PC oracle with above 90% accuracy. Exploitation with DIV-SMT requires co-location of the attacker on the same physical core as the victim.

What are the practical implications for key recovery?

The 2024 authors apply DIV-SMT to HQC and report a faster way to recover secret keys, with an 8-fold decrease in the number of idealized oracle queries compared to previous approaches. The new PC oracle attack uses a Zero Tester method to quickly determine whether an entire block of bits contains only zero-bits.

They report that the Zero Tester method lets the DIV-SMT attack on HQC-128 complete in under 2 minutes on their targeted AMD Zen2 machine.

FAQ

Is the BCH timing attack practical?

The 2019 authors call it practicable. For 128-bit security parameters, it runs in less than a minute on a desktop computer. It utilizes 5,441 decoding requests and maintains a success probability of approximately 93 percent, as reported by the authors.

Does the constant time countermeasure have performance costs?

The 2019 authors report that their constant-time BCH decoding implementation achieves constant-time execution without a significant performance penalty.

What hardware is required for the DIV-SMT attack?

The DIV-SMT approach requires processors supporting Simultaneous Multithreading (SMT). Additionally, exploitation requires the attacker to be co-located on the same physical core as the victim to measure small division timing variations accurately.

Can the Zero Tester method be applied elsewhere?

The 2024 authors say their approach might prove applicable to other instances of the DaS vulnerability, such as KyberSlash. However, the specific application discussed here targets HQC-128, achieving completion in under 2 minutes on an AMD Zen2 machine.