Horizontal Side-Channel Vulnerabilities of Post-Quantum Key Exchange and Encapsulation Protocols
Horizontal Side-Channel Vulnerabilities of Post-Quantum Key Exchange and Encapsulation Protocols
复制标题
DOI：
10.1145/3476799
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Furkan Aydin;Aydin Aysu;Mohit Tiwari;A. Gerstlauer;M. Orshansky
中科院分区：
文献类型：
--
作者：
Furkan Aydin;Aydin Aysu;Mohit Tiwari;A. Gerstlauer;M. Orshansky
密钥交换协议和密钥封装机制建立秘密密钥以在公共信道上秘密地传递数字信息。这些协议的基于格的密码变体是有前途的替代方案，因为它们具有量子密码分析抗性和实现效率。虽然格密码系统在数学上是安全的，但它们的实现已经显示出侧信道漏洞。但这类攻击在很大程度上假定在固定密钥下收集多个测量值，从而使更危险的单轨迹攻击未被探索。本文演示了对基于格的密钥交换和封装协议的成功的单迹功率侧信道攻击。我们的攻击目标的硬件和软件实现的矩阵乘法用于格密码系统。我们的想法的关键是应用一个水平攻击，使假设在一个单一的执行中的几个中间值都涉及到同一个秘密，并结合联合收割机的相关性，准确地估计秘密密钥。我们说明了协议的设计与格算术的性质相结合可以实现我们的攻击。由于一个简单的攻击遭受误报，我们展示了一种新的扩展和修剪过程中恢复的关键以下的中间更新的序列在乘法。我们分析了两个协议，Frodo和FrodoKEM，并揭示了它们容易受到我们的攻击。我们实现了独立的硬件和基于RISC-V的软件实现，并通过使用这些协议的具体参数在物理平台上进行真实的测量来测试所提出的攻击的有效性。我们表明，建议的攻击可以估计秘密密钥从一个单一的功率测量超过99%的成功率。
Key exchange protocols and key encapsulation mechanisms establish secret keys to communicate digital information confidentially over public channels. Lattice-based cryptography variants of these protocols are promising alternatives given their quantum-cryptanalysis resistance and implementation efficiency. Although lattice cryptosystems can be mathematically secure, their implementations have shown side-channel vulnerabilities. But such attacks largely presume collecting multiple measurements under a fixed key, leaving the more dangerous single-trace attacks unexplored. This article demonstrates successful single-trace power side-channel attacks on lattice-based key exchange and encapsulation protocols. Our attack targets both hardware and software implementations of matrix multiplications used in lattice cryptosystems. The crux of our idea is to apply a horizontal attack that makes hypotheses on several intermediate values within a single execution all relating to the same secret, and to combine their correlations for accurately estimating the secret key. We illustrate that the design of protocols combined with the nature of lattice arithmetic enables our attack. Since a straightforward attack suffers from false positives, we demonstrate a novel extend-and-prune procedure to recover the key by following the sequence of intermediate updates during multiplication. We analyzed two protocols, Frodo and FrodoKEM , and reveal that they are vulnerable to our attack. We implement both stand-alone hardware and RISC-V based software realizations and test the effectiveness of the proposed attack by using concrete parameters of these protocols on physical platforms with real measurements. We show that the proposed attack can estimate secret keys from a single power measurement with over 99% success rate.