Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

When Frodo Flips: End-to-End Key Recovery on FrodoKEM via Rowhammer

Published

Author(s)

Michael Fahr Jr., Hunter Kippen, Andrew Kwong, Thinh Dang, Jacob Lichtinger, Dana Dachman-Soled, Daniel Genkin, Alexander Nelson, Ray Perlner, Arkady Yerukhimovich, Daniel Apon

Abstract

In this work, we recover the private key material of the FrodoKEM key exchange mechanism as submitted to the NIST PQC standardization process. The new mechanism that allows for this is a Rowhammer-assisted poisoning of the FrodoKEM KeyGen process. That is, we induce the FrodoKEM software to output a higher-error PK, (A, B = AS + ̃E), where the error ̃E is modified by Rowhammer. Then, we perform a decryption failure attack, using a variety of publicly-accessible supercomputing resources running on the order of only 200,000 core-hours. We delicately attenuate the decryption failure rate to ensure that the adversary's attack succeeds practically, but so honest users cannot easily detect the manipulation. Achieving this public key "poisoning" requires an extreme engineering effort, as FrodoKEM's KeyGen runs on the order of 8 milliseconds. (Prior Rowhammer-assisted attacks against cryptography require as long as 8 hours of persistent access.) In order to handle this real-world timing condition, we require a wide variety of prior and brand new, low-level engineering techniques, including e.g. memory massaging algorithms – i.e. "Feng Shui" – and a precisely-targeted performance degradation attack on SHAKE. Finally, we also investigate the applicability of our attack to other lattice-based KEMs in the NIST PQC Round 3 candidate pool; e.g. Kyber, Saber, etc. To conclude, we discuss various simple countermeasures to protect implementations against this novel attack paradigm.
Proceedings Title
CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
Conference Dates
November 7-11, 2022
Conference Location
Los Angeles, CA, US
Conference Title
ACM Conference on Computer and Communications Security (CCS) (ACM CCS 2022)

Keywords

Postquantum Cryptography, Side Channel, Rowhammer, FrodoKem

Citation

Fahr Jr., M. , Kippen, H. , Kwong, A. , Dang, T. , Lichtinger, J. , Dachman-Soled, D. , Genkin, D. , Nelson, A. , Perlner, R. , Yerukhimovich, A. and Apon, D. (2022), When Frodo Flips: End-to-End Key Recovery on FrodoKEM via Rowhammer, CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security , Los Angeles, CA, US, [online], https://doi.org/10.1145/3548606.3560673, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934918 (Accessed July 22, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created November 7, 2022, Updated February 16, 2023