Divide and Surrender: Exploiting Variable Division Instruction Timing in HQC Key Recovery Attacks

Robin Leander Schröder; Stefan Gast; Qian Guo

Paper 2024/299

Divide and Surrender: Exploiting Variable Division Instruction Timing in HQC Key Recovery Attacks

Robin Leander Schröder

, Fraunhofer Institute for Secure Information Technology, Fraunhofer Austria

Stefan Gast, Graz University of Technology

Qian Guo

, Lund University

Abstract

We uncover a critical side-channel vulnerability in the Hamming Quasi-Cyclic (HQC) round 4 optimized implementation arising due to the use of the modulo operator. In some cases, compilers optimize uses of the modulo operator with compile-time known divisors into constant-time Barrett reductions. However, this optimization is not guaranteed: for example, when a modulo operation is used in a loop the compiler may emit division (div) instructions which have variable execution time depending on the numerator. When the numerator depends on secret data, this may yield a timing side-channel. We name vulnerabilities of this kind Divide and Surrender (DaS) vulnerabilities. For processors supporting Simultaneous Multithreading (SMT) we propose a new approach called DIV-SMT which enables precisely measuring small division timing variations using scheduler and/or execution unit contention. We show that using only 100 such side-channel traces we can build a Plaintext-Checking (PC) oracle with above 90% accuracy. Our approach may also prove applicable to other instances of the DaS vulnerability, such as KyberSlash. We stress that exploitation with DIV-SMT requires co-location of the attacker on the same physical core as the victim. We then apply our methodology to HQC and present a novel way to recover HQC secret keys faster, achieving an 8-fold decrease in the number of idealized oracle queries when compared to previous approaches. Our new PC oracle attack uses our newly developed Zero Tester method to quickly determine whether an entire block of bits contains only zero-bits. The Zero Tester method enables the DIV-SMT powered attack on HQC-128 to complete in under 2 minutes on our targeted AMD Zen2 machine.

Note: Updated responsible disclosure section to reflect the newly released patch to the vulnerability. Final version.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: PQC HQC side-channel attack division
Contact author(s): leander schroeder @ sit fraunhofer de
stefan gast @ iaik tugraz at
qian guo @ eit lth se
History: 2024-07-25: last of 2 revisions; 2024-02-21: received; See all versions
Short URL: https://ia.cr/2024/299
License: CC BY

BibTeX

@misc{cryptoeprint:2024/299,
      author = {Robin Leander Schröder and Stefan Gast and Qian Guo},
      title = {Divide and Surrender: Exploiting Variable Division Instruction Timing in {HQC} Key Recovery Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/299},
      year = {2024},
      url = {https://eprint.iacr.org/2024/299}
}