Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Schröder, Robin Leander ; Gast, Stefan and Guo, Qian LU (2024) 33rd USENIX Security Symposium, USENIX Security 2024 p.6669-6686
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 compiletime 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... (More)
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 compiletime 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 might 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. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the 33rd USENIX Security Symposium
article number
373
pages
6669 - 6686
conference name
33rd USENIX Security Symposium, USENIX Security 2024
conference location
Philadelphia, United States
conference dates
2024-08-14 - 2024-08-16
external identifiers
  • scopus:85204966340
ISBN
978-1-939133-44-1
language
English
LU publication?
yes
id
64ad1594-55a2-4a3e-b034-8612b99c214c
alternative location
https://www.usenix.org/conference/usenixsecurity24/presentation/schr%C3%B6der
date added to LUP
2025-01-16 14:59:35
date last changed
2025-06-06 15:17:37
@inproceedings{64ad1594-55a2-4a3e-b034-8612b99c214c,
  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 compiletime 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.<br/>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 might 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.<br/>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.}},
  author       = {{Schröder, Robin Leander and Gast, Stefan and Guo, Qian}},
  booktitle    = {{Proceedings of the 33rd USENIX Security Symposium}},
  isbn         = {{978-1-939133-44-1}},
  language     = {{eng}},
  pages        = {{6669--6686}},
  title        = {{Divide and Surrender: Exploiting Variable Division Instruction Timing in HQC Key Recovery Attacks}},
  url          = {{https://www.usenix.org/conference/usenixsecurity24/presentation/schr%C3%B6der}},
  year         = {{2024}},
}