Recovery Attack on Bob's Reused Randomness in CRYSTALS-KYBER and SABER
Recovery Attack on Bob's Reused Randomness in CRYSTALS-KYBER and SABER
复制标题
DOI：
10.1007/978-3-030-90402-9_9
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
S. Okada;Yuntao Wang
中科院分区：
文献类型：
--
作者：
S. Okada;Yuntao Wang
量子计算能力压倒性地超过了经典计算机，这对现代公钥密码学构成了严重威胁。为此，美国国家标准与技术研究所(NIST)和其他几个标准组织正在推进后量子密码学(PQC)的标准化。在这些候选中有两个竞争者，Crystal-Kyber和Saber，它们是NIST PQC标准化项目第三轮决赛的基于晶格的加密算法。在现阶段，评估它们的安全性是很重要的，这是基于带错误的环学习(Ring-LWE)问题的变体的难易程度。在ProvSec 2020上，Wang等人。为Ring-LWE密码机制引入了“元PK”的概念。他们进一步提出了对满足元PKE模型的Newhope和LAC密码体制的随机性重用攻击。在他们的攻击中，加密器Bob的部分(甚至全部)随机性如果被重复使用就可以恢复。本文采用元PKE模型，改进Wang等人的S方法，提出了对Crystal-Kyber和Saber密码方案的攻击。然后，我们证明了对于晶体-Kyber中的任意安全级别I(AES-128)、III(AES-192)和V(AES-256)，我们提出的攻击最多花费4、3和4个查询来恢复Bob的随机性。同时，在Saber中恢复Bob的安全级别I、III和V的秘密不需要超过6、6和4个查询。
Quantum computing capability outperforms that of the classic computers overwhelmingly, which seriously threatens modern public-key cryptography. For this reason, the National Institute of Standards and Technology (NIST) and several other standards organizations are progressing the standardization for post-quantum cryptography (PQC). There are two contenders among those candidates, CRYSTALS-KYBER and SABER, lattice-based encryption algorithms in the third round finalists of NIST’s PQC standardization project. At the current phase, it is important to evaluate their security, which is based on the hardness of the variants of Ring Learning With Errors (Ring-LWE) problem. In ProvSec 2020, Wang et al. introduced a notion of “meta-PK” for Ring-LWE crypto mechanism. They further proposed randomness reuse attacks on NewHope and LAC cryptosystems which meet the meta-PKE model. In their attacks, the encryptor Bob’s partial (or even all) randomness can be recovered if it is reused. In this paper, we propose attacks against CRYSTALS-KYBER and SABER crypto schemes by adapting the meta-PKE model and improving Wang et al.’s methods. Then, we show that our proposed attacks cost at most 4, 3, and 4 queries to recover Bob’s randomness for any security levels of I (AES-128), III (AES-192), and V (AES-256), respectively in CRYSTALS-KYBER. Simultaneously, no more than 6, 6, and 4 queries are required to recover Bob’s secret for security levels I, III, and V in SABER.