Article

A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM

Authors:

Thomas Johansson,

Alexander NilssonAuthors Info & Claims

Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II

Pages 359 - 386

https://doi.org/10.1007/978-3-030-56880-1_13

Published: 17 August 2020 Publication History

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 decapsulation calls.

References

[1]

NIST post-quantum cryptography standardization. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization. Accessed 24 Sept 2018

[2]

NTRU Open Source Project. https://github.com/NTRUOpenSourceProject. Accessed 10 Feb 2020

[3]

Open quantum safe. https://openquantumsafe.org. Accessed 21 Jan 2020

[4]

Aguilar Melchor, C., et al.: HQC. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[5]

Aguilar Melchor, C., et al.: RQC. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[6]

Aragon, N., et al.: BIKE. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[7]

Aragon, N., et al.: ROLLO. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[8]

Băetu C, Durak FB, Huguenin-Dumittan L, Talayhan A, and Vaudenay S Ishai Y and Rijmen V Misuse attacks on post-quantum cryptosystems Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 747-776

[9]

Bauer A, Gilbert H, Renault G, and Rossi M Matsui M Assessment of the key-reuse resilience of NewHope Topics in Cryptology – CT-RSA 2019 2019 Cham Springer 272-292

[10]

Bernstein, D.J., Bruinderink, L.G., Lange, T., Panny, L.: HILA5 pindakaas: on the CCA security of lattice-based encryption with error correction. Cryptology ePrint Archive, Report 2017/1214 (2017). https://eprint.iacr.org/2017/1214

[11]

Bernstein, D.J., et al.: Classic McEliece. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[12]

Bos, J.W., et al.: Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016: 23rd Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 1006–1018. ACM Press (2016).

[13]

Bruinderink LG, Hülsing A, Lange T, and Yarom Y Gierlichs B and Poschmann AY Flush, gauss, and reload – a cache attack on the BLISS lattice-based signature scheme Cryptographic Hardware and Embedded Systems – CHES 2016 2016 Heidelberg Springer 323-345

[14]

Brumley, D., Boneh, D.: Remote timing attacks are practical. In: USENIX Security 2003: 12th USENIX Security Symposium, Washington, DC, USA, 4–8 August 2003. USENIX Association (2003)

[15]

D’Anvers J-P, Guo Q, Johansson T, Nilsson A, Vercauteren F, and Verbauwhede I Lin D and Sako K Decryption failure attacks on IND-CCA secure lattice-based schemes Public-Key Cryptography – PKC 2019 2019 Cham Springer 565-598

[16]

D’Anvers, J.P., Tiepelt, M., Vercauteren, F., Verbauwhede, I.: Timing attacks on error correcting codes in post-quantum secure schemes. IACR Cryptology ePrint Archive 2019, 292 (2019)

[17]

Facon, A., Guilley, S., Lec’Hvien, M., Schaub, A., Souissi, Y.: Detecting cache-timing vulnerabilities in post-quantum cryptography algorithms. In: 2018 IEEE 3rd International Verification and Security Workshop (IVSW), pp. 7–12. IEEE (2018)

[18]

Fluhrer, S.: Cryptanalysis of ring-LWE based key exchange with key share reuse. Cryptology ePrint Archive, Report 2016/085 (2016). http://eprint.iacr.org/2016/085

[19]

Fujisaki E and Okamoto T Wiener MJ Secure integration of asymmetric and symmetric encryption schemes Advances in Cryptology — CRYPTO 1999 1999 Heidelberg Springer 537-554

[20]

Guo Q, Johansson T, and Yang J Galbraith SD and Moriai S A novel CCA attack using decryption errors against LAC Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 82-111

[21]

Hofheinz D, Hövelmanns K, and Kiltz E Kalai Y and Reyzin L A modular analysis of the Fujisaki-Okamoto transformation Theory of Cryptography 2017 Cham Springer 341-371

[22]

Howgrave-Graham N et al. Boneh D et al. The impact of decryption failures on the security of NTRU encryption Advances in Cryptology - CRYPTO 2003 2003 Heidelberg Springer 226-246

[23]

Howgrave-Graham, N., Silverman, J.H., Singer, A., Whyte, W.: NAEP: provable security in the presence of decryption failures. Cryptology ePrint Archive, Report 2003/172 (2003). http://eprint.iacr.org/2003/172

[24]

Kocher PC Koblitz N Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems Advances in Cryptology — CRYPTO 1996 1996 Heidelberg Springer 104-113

[25]

Lu, X., et al.: LAC. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[26]

McEliece RJ A public-key cryptosystem based on algebraic Coding Thv 1978 4244 114-116

[27]

Naehrig, M., et al.: FrodoKEM. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[28]

Poppelmann, T., et al.: NewHope. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[29]

Schwabe, P., et al.: CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

[30]

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20–22 November 1994, pp. 124–134. IEEE Computer Society Press (1994).

[31]

Smart NP Cryptography Made Simple 2016 Heidelberg Springer

[32]

Strenzke F Sendrier N A timing attack against the secret permutation in the McEliece PKC Post-Quantum Cryptography 2010 Heidelberg Springer 95-107

[33]

Strenzke F Gaborit P Timing attacks against the syndrome inversion in code-based cryptosystems Post-Quantum Cryptography 2013 Heidelberg Springer 217-230

Cited By

Ravi PChattopadhyay AD’Anvers JBaksi A(2024)Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New ResultsACM Transactions on Embedded Computing Systems10.1145/360317023:2(1-54)Online publication date: 28-Mar-2024
https://dl.acm.org/doi/10.1145/3603170
Almeida JArranz Olmos SBarbosa MBarthe GDupressoir FGrégoire BLaporte VLéchenet JLow COliveira TPacheco HQuaresma MSchwabe PStrub P(2024)Formally Verifying KyberAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_12(384-421)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_12
Mondal PKundu SBhattacharya SKarmakar AVerbauwhede I(2024)A Practical Key-Recovery Attack on LWE-Based Key-Encapsulation Mechanism Schemes Using RowhammerApplied Cryptography and Network Security10.1007/978-3-031-54776-8_11(271-300)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54776-8_11
Show More Cited By

Recommendations

Lattice-based certificateless encryption scheme

Certificateless public key cryptography (CL-PKC) can solve the problems of certificate management in a public key infrastructure (PKI) and of key escrows in identity-based public key cryptography (ID-PKC). In CL-PKC, the key generation center (KGC) does ...
Decryption Failure Attacks on IND-CCA Secure Lattice-Based Schemes
Public-Key Cryptography – PKC 2019
Abstract
In this paper we investigate the impact of decryption failures on the chosen-ciphertext security of lattice-based primitives. We discuss a generic framework for secret key recovery based on decryption failures and present an attack on the NIST ...
A Novel CCA Attack Using Decryption Errors Against LAC
Advances in Cryptology – ASIACRYPT 2019
Abstract
Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II

Aug 2020

864 pages

ISBN:978-3-030-56879-5

DOI:10.1007/978-3-030-56880-1

Editors:
Daniele Micciancio
UC San Diego, La Jolla, CA, USA
,
Thomas Ristenpart
Cornell Tech, New York, NY, USA

© International Association for Cryptologic Research 2020.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2020

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ravi PChattopadhyay AD’Anvers JBaksi A(2024)Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New ResultsACM Transactions on Embedded Computing Systems10.1145/360317023:2(1-54)Online publication date: 28-Mar-2024
https://dl.acm.org/doi/10.1145/3603170
Almeida JArranz Olmos SBarbosa MBarthe GDupressoir FGrégoire BLaporte VLéchenet JLow COliveira TPacheco HQuaresma MSchwabe PStrub P(2024)Formally Verifying KyberAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_12(384-421)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_12
Mondal PKundu SBhattacharya SKarmakar AVerbauwhede I(2024)A Practical Key-Recovery Attack on LWE-Based Key-Encapsulation Mechanism Schemes Using RowhammerApplied Cryptography and Network Security10.1007/978-3-031-54776-8_11(271-300)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54776-8_11
Guo QNabokov DNilsson AJohansson T(2023)SCA-LDPC: A Code-Based Framework for Key-Recovery Side-Channel Attacks on Post-quantum Encryption SchemesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8730-6_7(203-236)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8730-6_7
Ma YYang XWang AWei CChen TXu H(2023)Side-Channel Analysis on Lattice-Based KEM Using Multi-feature Recognition - The Case Study of KyberInformation Security and Cryptology – ICISC 202310.1007/978-981-97-1235-9_12(221-239)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-97-1235-9_12
Shi WHan JJiang HMa Z(2023)Improved Key-Recovery Attacks Under Imperfect SCA Oracle for Lattice-Based KEMsProvable and Practical Security10.1007/978-3-031-45513-1_4(67-82)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45513-1_4
Guo QMårtensson E(2023)Do Not Bound to a Single Position: Near-Optimal Multi-positional Mismatch Attacks Against Kyber and SaberPost-Quantum Cryptography10.1007/978-3-031-40003-2_11(291-320)Online publication date: 16-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-40003-2_11
D’Anvers J(2023)One-Hot Conversion: Towards Faster Table-Based A2B ConversionAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30634-1_21(628-657)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30634-1_21
Heinz DDreo Rodosek G(2023)Fast First-Order Masked NTTRUConstructive Side-Channel Analysis and Secure Design10.1007/978-3-031-29497-6_7(127-148)Online publication date: 3-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-29497-6_7
Wang RNgo KDubrova E(2022)A Message Recovery Attack on LWE/LWR-Based PKE/KEMs Using Amplitude-Modulated EM EmanationsInformation Security and Cryptology – ICISC 202210.1007/978-3-031-29371-9_22(450-471)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-29371-9_22
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents