Message-Recovery Laser Fault Injection Attack on the Classic McEliece Cryptosystem
Message-Recovery Laser Fault Injection Attack on the Classic McEliece Cryptosystem
复制标题
对经典 McEliece 密码系统的消息恢复激光故障注入攻击
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
L. Bossuet
中科院分区：
文献类型：
--
作者：
Pierre;Brice Colombier;V. Dragoi;A. Menu;L. Bossuet
基于代码的公钥密码系统是作为抗量子公钥密码算法标准化的有希望的候选者。它们的安全性基于综合症解码问题的难度。在有限域（通常是 F2）中计算校正子可以保证构造的安全性。我们在本文中表明，如果用 N 来计算校正子，那么问题就会变得更容易解决。通过激光故障注入，我们说明了如何通过破坏特定指令来计算 N 中的矩阵向量积，并通过实验对其进行验证。为了解决 N 中的校正子解码问题，我们提出将问题简化为整数线性规划问题。我们利用线性编程求解器的计算效率来获得针对 NIST 后量子密码学标准化挑战的基于代码的提案的实时消息恢复攻击。我们在最坏的情况下执行攻击，即考虑随机二进制代码，并在几分钟内在台式计算机上检索初始消息。我们的攻击目标是 NIST PQC 竞赛决赛入围者 Classic McEliece 中 Niederreiter 密码系统的参考实现，并且对于本次提交的所有建议参数集来说实际上都是可行的。例如，对于 256 位安全参数集，我们在台式计算机上几秒钟内成功恢复了消息。最后，我们强调这样一个事实：如果只有一小部分综合症条目有错误，攻击仍然是可能的。即使故障注入不具有完美的可重复性，这也使得攻击变得可行，并降低了攻击的计算复杂度，使其整体上更加实用。
Code-based public-key cryptosystems are promising candidates for standardization as quantum-resistant public-key cryptographic algorithms. Their security is based on the hardness of the syndrome decoding problem. Computing the syndrome in a finite field, usually F2, guarantees the security of the constructions. We show in this article that the problem becomes considerably easier to solve if the syndrome is computed in N instead. By means of laser fault injection, we illustrate how to compute the matrix-vector product in N by corrupting specific instructions, and validate it experimentally. To solve the syndrome decoding problem in N, we propose a reduction to an integer linear programming problem. We leverage the computational efficiency of linear programming solvers to obtain real-time message recovery attacks against the code-based proposal to the NIST Post-Quantum Cryptography standardization challenge. We perform our attacks in the worst-case scenario, i.e. considering random binary codes, and retrieve the initial message within minutes on a desktop computer. Our attack targets the reference implementation of the Niederreiter cryptosystem in the NIST PQC competition finalist Classic McEliece and is practically feasible for all proposed parameters sets of this submission. For example, for the 256-bit security parameters sets, we successfully recover the message in a couple of seconds on a desktop computer. Finally, we highlight the fact that the attack is still possible if only a fraction of the syndrome entries are faulty. This makes the attack feasible even though the fault injection does not have perfect repeatability and reduces the computational complexity of the attack, making it even more practical overall.