Paper 2020/743

A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM

Qian Guo, Thomas Johansson, and Alexander Nilsson

Abstract

In the implementation of post-quantum primitives, it is well known that all computations that handle secret information need to be implemented to run in constant time. Using the Fujisaki-Okamoto transformation or any of its different variants, a CPA-secure primitive can be converted into an IND-CCA secure KEM. In this paper we show that although the transformation does not handle secret information apart from calls to the CPA-secure primitive, it has to be implemented in constant time. Namely, if the ciphertext comparison step in the transformation is leaking side-channel information, we can launch a key-recovery attack. Several proposed schemes in round 2 of the NIST post-quantum standardization project are susceptible to the proposed attack and we develop and show the details of the attack on one of them, being FrodoKEM. It is implemented on the reference implementation of FrodoKEM, which is claimed to be secure against all timing attacks. Experiments show that the attack code is able to extract the secret key for all security levels using about \(2^{30}\) decapsulation calls.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in CRYPTO 2020
Keywords
Lattice-based cryptographyNIST post-quantum standardizationLWEtiming attacksside-channel attacks
Contact author(s)
alexander nilsson @ eit lth se
qian guo @ eit lth se
thomas johansson @ eit lth se
History
2020-06-18: received
Short URL
https://ia.cr/2020/743
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/743,
      author = {Qian Guo and Thomas Johansson and Alexander Nilsson},
      title = {A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on {FrodoKEM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/743},
      year = {2020},
      url = {https://eprint.iacr.org/2020/743}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.