Signature Correction Attack on Dilithium Signature Scheme
Signature Correction Attack on Dilithium Signature Scheme
复制标题
DOI：
10.1109/eurosp53844.2022.00046
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Saad Islam;K. Mus;Richa Singh;P. Schaumont;B. Sunar
中科院分区：
文献类型：
--
作者：
Saad Islam;K. Mus;Richa Singh;P. Schaumont;B. Sunar
在量子计算机兴起的推动下，现有的公钥密码系统预计将在未来十年被数十亿设备的后量子方案所取代。为了促进过渡，NIST正在运行一个标准化过程，目前已进入最后一轮。竞争中只剩下三个数字签名方案，其中Dilithium和Falcon是基于格子的数字签名方案。除了安全性和性能外，还对针对侧通道泄漏或故障注入响应的实施攻击给予了极大的关注。经典的签名方案错误攻击是利用错误和正确的签名对来恢复密钥，而密钥只适用于确定性方案。为了对抗这种攻击，Dilithium提供了一个随机版本，使每个签名都是唯一的，即使签名相同的消息也是如此。在这项工作中，我们引入了一种新的签名纠正攻击，它不仅适用于确定性版本，也适用于随机版本的Dilithium，甚至在使用AVX2指令的恒定时间实现中也是有效的。签名纠正攻击利用diilithium的数学结构，通过使用错误签名和公钥来恢复秘密密钥位。它可以适用于任何可能引起单比特翻转的故障机制。为了演示，我们使用Rowhammer诱发故障。因此，我们的攻击不需要任何物理访问或特殊权限，因此也可以在共享云服务器上实现。我们利用Rowhammer攻击，在diilithium的秘钥s1中注入位翻转，导致签名算法生成错误的签名。由于我们可以使用签名校正算法找到正确的签名，我们可以使用正确和错误签名之间的差异来推断翻转位的位置和值，而不需要正确和错误的对。为了量化安全级别的降低，我们对Dilithium进行了彻底的经典和量子安全分析，并成功地恢复了安全级别2的3,072位密钥$s_{1}$中的1,851位。使用完全恢复的比特来降低晶格的维数，而使用部分恢复的系数来降低密钥系数的范数。对原始攻击和对偶攻击的进一步分析表明，抵抗量子攻击者的晶格强度从2128降低到281，而抵抗经典攻击者的晶格强度从2141降低到289。因此，在NIST后量子标准化过程的第三轮中，可以使用签名校正攻击来实现对Dilithium（安全级别2）的实际攻击。
Motivated by the rise of quantum computers, existing public-key cryptosystems are expected to be replaced by post-quantum schemes in the next decade in billions of devices. To facilitate the transition, NIST is running a standardization process which is currently in its final Round. Only three digital signature schemes are left in the competition, among which Dilithium and Falcon are the ones based on lattices. Besides security and performance, significant attention has been given to resistance against implementation attacks that target side-channel leakage or fault injection response. Classical fault attacks on signature schemes make use of pairs of faulty and correct signatures to recover the secret key which only works on deterministic schemes. To counter such attacks, Dilithium offers a randomized version which makes each signature unique, even when signing identical messages. In this work, we introduce a novel Signature Correction Attack which not only applies to the deterministic version but also to the randomized version of Dilithium and is effective even on constant-time implementations using AVX2 instructions. The Signature Correction Attack exploits the mathematical structure of Dilithium to recover the secret key bits by using faulty signatures and the public-key. It can work for any fault mechanism which can induce single bit-flips. For demonstration, we are using Rowhammer induced faults. Thus, our attack does not require any physical access or special privileges, and hence could be also implemented on shared cloud servers. Using Rowhammer attack, we inject bit flips into the secret key s1 of Dilithium, which results in incorrect signatures being generated by the signing algorithm. Since we can find the correct signature using our Signature Correction algorithm, we can use the difference between the correct and incorrect signatures to infer the location and value of the flipped bit without needing a correct and faulty pair. To quantify the reduction in the security level, we perform a thorough classical and quantum security analysis of Dilithium and successfully recover 1,851 bits out of 3,072 bits of secret key $s_{1}$ for security level 2. Fully recovered bits are used to reduce the dimension of the lattice whereas partially recovered coefficients are used to to reduce the norm of the secret key coefficients. Further analysis for both primal and dual attacks shows that the lattice strength against quantum attackers is reduced from 2128 to 281 while the strength against classical attackers is reduced from 2141 to 289. Hence, the Signature Correction Attack may be employed to achieve a practical attack on Dilithium (security level 2) as proposed in Round 3 of the NIST post-quantum standardization process.