When Frodo Flips: End-to-End Key Recovery on FrodoKEM via Rowhammer
When Frodo Flips: End-to-End Key Recovery on FrodoKEM via Rowhammer
复制标题
DOI：
10.1145/3548606.3560673
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Michael Fahr;Hunter Kippen;Andrew Kwong;T. Dang;Jacob Lichtinger;Dana Dachman-Soled;Daniel Genkin;Alexander Nelson;Ray A. Perlner;Arkady Yerukhimovich;Daniel Apon
中科院分区：
文献类型：
--
作者：
Michael Fahr;Hunter Kippen;Andrew Kwong;T. Dang;Jacob Lichtinger;Dana Dachman-Soled;Daniel Genkin;Alexander Nelson;Ray A. Perlner;Arkady Yerukhimovich;Daniel Apon
在这项工作中，我们恢复了提交给NIST Post量子密码(PQC)标准化过程的FrodoKEM密钥交换机制的私钥材料。实现这一点的新机制是Rowhammer协助毒化FrodoKEM密钥生成(KeyGen)过程。Rowhammer侧通道是一种基于硬件的安全漏洞，它允许通过重复访问内存来“敲打”与目标受害者内存位置相邻的内存行，从而翻转DRAM中的位。使用Rowhammer，我们诱导FrodoKEM软件输出错误更高的公钥(PK)(\mata，\matB=\mata\mats+\vec\widetildeE)，其中错误\宽波浪号\Vess由Rowhammer修改。然后，我们执行解密失败攻击，使用各种可公开访问的超级计算资源，运行在仅20万核心小时的数量级上。我们巧妙地降低了解密失败率，以确保对手的攻击在实际中取得成功，但诚实的用户不容易发现篡改。实现这种公钥“毒化”需要极端的工程工作，因为FrodoKEM的KeyGen运行在8毫秒的数量级上。(以前Rowhammer协助的针对密码学的攻击需要长达8小时的持续访问。)为了处理这种真实世界的计时条件，我们需要各种预先的和全新的低级工程技术，包括例如内存消息算法--即“风水”--以及对可扩展输出函数抖动进行精确定向的性能降级攻击。我们探索了我们的技术对NIST PQC第三轮候选库中其他基于晶格的KEM的适用性，以及在各种设置中出现的困难。最后，我们讨论了各种简单的对策，以保护实现免受这种和类似的攻击。
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 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), (\matA, \matB = \matA \matS +\vec\widetildeE ), where the error \widetilde\vecE 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 milli seconds. (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.