Paper 2022/259

Partial Key Exposure Attacks on BIKE, Rainbow and NTRU

Andre Esser, Technology Innovation Institute
Alexander May, Ruhr University Bochum
Javier Verbel, Technology Innovation Institute
Weiqiang Wen, Laboratoire Traitement et Communication de l’Information
Abstract

In a so-called partial key exposure attack one obtains some information about the secret key, e.g. via some side-channel leakage. This information might be a certain fraction of the secret key bits (erasure model) or some erroneous version of the secret key (error model). The goal is to recover the secret key from the leaked information. There is a common belief that, as opposed to e.g. the RSA cryptosystem, most post-quantum cryptosystems are usually resistant against partial key exposure attacks. We strongly question this belief by constructing partial key exposure attacks on code-based, multivariate, and lattice-based schemes (BIKE, Rainbow and NTRU). Our attacks exploit the redundancy that modern PQ cryptosystems inherently use for efficiency reasons. The application and development of techniques from information set decoding plays a crucial role for achieving our results. On the theoretical side, we show non-trivial information leakage bounds that allow for a polynomial time key recovery attack. As an example, for all schemes the knowledge of a constant fraction of the secret key bits suffices to reconstruct the full key in polynomial time. Even if we no longer insist on polynomial time attacks, most of our attacks extend well and remain feasible up to large erasure and error rates. In the case of BIKE for example we obtain attack complexities around 60 bits when half of the secret key bits are erased, or a quarter of the secret key bits are faulty. Our results show that even highly error-prone key leakage of modern PQ cryptosystems may lead to full secret key recoveries.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
Erasure Error Model Asymptotics Cold Boot Key Recovery
Contact author(s)
andre r esser @ gmail com
alex may @ rub de
javier verbel @ tii ae
weiqiang wen @ telecom-paris fr
History
2022-06-24: revised
2022-03-02: received
See all versions
Short URL
https://ia.cr/2022/259
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/259,
      author = {Andre Esser and Alexander May and Javier Verbel and Weiqiang Wen},
      title = {Partial Key Exposure Attacks on BIKE, Rainbow and NTRU},
      howpublished = {Cryptology ePrint Archive, Paper 2022/259},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/259}},
      url = {https://eprint.iacr.org/2022/259}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.