Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Don’t Reject This: Key-Recovery Timing Attacks Due to Rejection-Sampling in HQC and BIKE

Guo, Qian LU ; Hlauschek, Clemens ; Johansson, Thomas LU orcid ; Lahr, Norman ; Nilsson, Alexander LU orcid and Schröder, Robin Leander (2022) In IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) 2022(3). p.223-263
Abstract
Well before large-scale quantum computers will be available, traditional cryptosystems must be transitioned to post-quantum (PQ) secure schemes. The NIST PQC competition aims to standardize suitable cryptographic schemes. Candidates are evaluated not only on their formal security strengths, but are also judged based on the security with regard to resistance against side-channel attacks. Although round 3 candidates have already been intensively vetted with regard to such attacks, one important attack vector has hitherto been missed: PQ schemes often rely on rejection sampling techniques to obtain pseudorandomness from a specific distribution. In this paper, we reveal that rejection sampling routines that are seeded with secretdependent... (More)
Well before large-scale quantum computers will be available, traditional cryptosystems must be transitioned to post-quantum (PQ) secure schemes. The NIST PQC competition aims to standardize suitable cryptographic schemes. Candidates are evaluated not only on their formal security strengths, but are also judged based on the security with regard to resistance against side-channel attacks. Although round 3 candidates have already been intensively vetted with regard to such attacks, one important attack vector has hitherto been missed: PQ schemes often rely on rejection sampling techniques to obtain pseudorandomness from a specific distribution. In this paper, we reveal that rejection sampling routines that are seeded with secretdependent information and leak timing information result in practical key recovery attacks in the code-based key encapsulation mechanisms HQC and BIKE.
Both HQC and BIKE have been selected as alternate candidates in the third round of the NIST competition, which puts them on track for getting standardized separately o the finalists. They have already been specifically hardened with constant-time decoders to avoid side-channel attacks. However, in this paper, we show novel timing vulnerabilities in both schemes: (1) Our secret key recovery attack on HQC requiresonly approx. 866,000 idealized decapsulation timing oracle queries in the 128-bit security setting. It is structurally different from previously identified attacks on the scheme: Previously, exploitable side-channel leakages have been identified in the BCH decoder of a previously submitted HQC version, in the ciphertext check as well as in the pseudorandom function of the Fujisaki-Okamoto transformation. In contrast, our attack uses the fact that the rejection sampling routine invoked during the deterministic re-encryption of the decapsulation leaks secret-dependent timing information, which can be efficiently exploited to recover the secret key when HQC is instantiated with the (now constant-time) BCH decoder, as well as with the RMRS decoder of the current submission. (2) From the timing information of the constant weight word sampler in the BIKE decapsulation, we demonstrate how to distinguish whether the decoding step is successful or not, and how this distinguisher is then used in the framework of the GJS attack to derive the distance spectrum of the secret key, using 5.8 x 107 idealized timing oracle queries. We provide details and analyses of the fully implemented attacks, as well as a discussion on possible countermeasures and their limits. (Less)
Please use this url to cite or link to this publication:
author
; ; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)
volume
2022
issue
3
pages
41 pages
publisher
Ruhr-University of Bochum
external identifiers
  • scopus:85136557123
ISSN
2569-2925
DOI
10.46586/tches.v2022.i3.223-263
project
Side channels on software implementations of post-quantum cryptographic algorithms
Securing Quantum-Safe Signatures
Lightweight Cryptography for Autonomous Vehicles
language
English
LU publication?
yes
id
c3a77d10-bdd6-4dac-a7a9-50a284b922e1
date added to LUP
2022-08-30 11:50:58
date last changed
2023-11-21 06:25:27
@article{c3a77d10-bdd6-4dac-a7a9-50a284b922e1,
  abstract     = {{Well before large-scale quantum computers will be available, traditional cryptosystems must be transitioned to post-quantum (PQ) secure schemes. The NIST PQC competition aims to standardize suitable cryptographic schemes. Candidates are evaluated not only on their formal security strengths, but are also judged based on the security with regard to resistance against side-channel attacks. Although round 3 candidates have already been intensively vetted with regard to such attacks, one important attack vector has hitherto been missed: PQ schemes often rely on rejection sampling techniques to obtain pseudorandomness from a specific distribution. In this paper, we reveal that rejection sampling routines that are seeded with secretdependent information and leak timing information result in practical key recovery attacks in the code-based key encapsulation mechanisms HQC and BIKE.<br/>Both HQC and BIKE have been selected as alternate candidates in the third round of the NIST competition, which puts them on track for getting standardized separately o the finalists. They have already been specifically hardened with constant-time decoders to avoid side-channel attacks. However, in this paper, we show novel timing vulnerabilities in both schemes: (1) Our secret key recovery attack on HQC requiresonly approx. 866,000 idealized decapsulation timing oracle queries in the 128-bit security setting. It is structurally different from previously identified attacks on the scheme: Previously, exploitable side-channel leakages have been identified in the BCH decoder of a previously submitted HQC version, in the ciphertext check as well as in the pseudorandom function of the Fujisaki-Okamoto transformation. In contrast, our attack uses the fact that the rejection sampling routine invoked during the deterministic re-encryption of the decapsulation leaks secret-dependent timing information, which can be efficiently exploited to recover the secret key when HQC is instantiated with the (now constant-time) BCH decoder, as well as with the RMRS decoder of the current submission. (2) From the timing information of the constant weight word sampler in the BIKE decapsulation, we demonstrate how to distinguish whether the decoding step is successful or not, and how this distinguisher is then used in the framework of the GJS attack to derive the distance spectrum of the secret key, using 5.8 x 107 idealized timing oracle queries. We provide details and analyses of the fully implemented attacks, as well as a discussion on possible countermeasures and their limits.}},
  author       = {{Guo, Qian and Hlauschek, Clemens and Johansson, Thomas and Lahr, Norman and Nilsson, Alexander and Schröder, Robin Leander}},
  issn         = {{2569-2925}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{223--263}},
  publisher    = {{Ruhr-University of Bochum}},
  series       = {{IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)}},
  title        = {{Don’t Reject This: Key-Recovery Timing Attacks Due to Rejection-Sampling in HQC and BIKE}},
  url          = {{http://dx.doi.org/10.46586/tches.v2022.i3.223-263}},
  doi          = {{10.46586/tches.v2022.i3.223-263}},
  volume       = {{2022}},
  year         = {{2022}},
}