Advanced

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

Guo, Qian LU ; Johansson, Thomas LU and Nilsson, Alexander LU (2020) 40th Annual International Cryptology Conference, CRYPTO 2020 In Lecture Notes in Computer Science 12171. p.359-386
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... (More)
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. (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
Advances in Cryptology – CRYPTO 2020 : 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II
series title
Lecture Notes in Computer Science
volume
12171
pages
359 - 386
publisher
Springer
conference name
40th Annual International Cryptology Conference, CRYPTO 2020
conference location
Santa Barbara, United States
conference dates
2020-08-17 - 2020-08-21
external identifiers
  • scopus:85089719168
ISSN
0302-9743
1611-3349
ISBN
978-3-030-56880-1
978-3-030-56879-5
DOI
10.1007/978-3-030-56880-1_13
project
Side channels on software implementations of post-quantum cryptographic algorithms
language
English
LU publication?
yes
id
65d795f6-1a59-45c0-aa6e-45467fe15e03
alternative location
https://eprint.iacr.org/2020/743
date added to LUP
2020-06-25 10:45:58
date last changed
2020-11-24 03:16:21
@inproceedings{65d795f6-1a59-45c0-aa6e-45467fe15e03,
  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.},
  author       = {Guo, Qian and Johansson, Thomas and Nilsson, Alexander},
  booktitle    = {Advances in Cryptology – CRYPTO 2020 : 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II},
  isbn         = {978-3-030-56880-1},
  issn         = {0302-9743},
  language     = {eng},
  month        = {08},
  pages        = {359--386},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science},
  title        = {A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM},
  url          = {http://dx.doi.org/10.1007/978-3-030-56880-1_13},
  doi          = {10.1007/978-3-030-56880-1_13},
  volume       = {12171},
  year         = {2020},
}