Paper 2022/952

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

Michael Fahr Jr., University of Arkansas
Hunter Kippen, University of Maryland, College Park
Andrew Kwong, University of Michigan–Ann Arbor
Thinh Dang, George Washington University, National Institute of Standards and Technology
Jacob Lichtinger, National Institute of Standards and Technology
Dana Dachman-Soled, University of Maryland, College Park
Daniel Genkin, Georgia Institute of Technology
Alexander Nelson, University of Arkansas
Ray Perlner, National Institute of Standards and Technology
Arkady Yerukhimovich, George Washington University
Daniel Apon, Mitre (United States)
Abstract

In this work, we recover the private key material of the FrodoKEM key exchange mechanism as submitted to the NIST Post Quantum Cryptography (PQC) standardization process. The new mechanism that allows for this is a Rowhammer-assisted \emph{poisoning} of the FrodoKEM Key Generation (KeyGen) process. The Rowhammer side-channel is a hardware-based security exploit that allows flipping bits in DRAM by “hammering” rows of memory adjacent to some target-victim memory location by repeated memory accesses. Using Rowhammer, we induce the FrodoKEM software to output a higher-error Public Key (PK), $(\mathbf{A}, \mathbf{B} = \mathbf{A}\mathbf{S}+\mathbf{\widetilde{E}}),$ where the error $\widetilde{\mathbf{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 the extendable output function SHAKE. We explore the applicability of our techniques to other lattice-based KEMs in the NIST PQC Round 3 candidate-pool, e.g. Kyber, Saber, etc, as well as the difficulties that arise in the various settings. To conclude, we discuss various simple countermeasures to protect implementations against this, and similar, attacks.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. ACM CCS 2022
Keywords
Post Quantum cryptography Rowhammer
Contact author(s)
mjfahr @ uark edu
hkippen @ umd edu
ankwong @ umich edu
thinh @ gwu edu
jacob lichtinger @ nist gov
danadach @ ece umd edu
genkin @ gatech edu
ahnelson @ uark edu
ray perlner @ nist gov
arkady @ gwu edu
dapon @ mitre org
History
2022-07-23: approved
2022-07-23: received
See all versions
Short URL
https://ia.cr/2022/952
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/952,
      author = {Michael Fahr Jr. and Hunter Kippen and Andrew Kwong and Thinh Dang and Jacob Lichtinger and Dana Dachman-Soled and Daniel Genkin and Alexander Nelson and Ray Perlner and Arkady Yerukhimovich and Daniel Apon},
      title = {When Frodo Flips: End-to-End Key Recovery on FrodoKEM via Rowhammer},
      howpublished = {Cryptology ePrint Archive, Paper 2022/952},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/952}},
      url = {https://eprint.iacr.org/2022/952}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.