| 摘要: |
| 在Q1量子模型下, 针对Lai-Massey结构、Misty结构、Type-1型广义Feistel结构、类SMS4 广义Feistel结构和类MARS 广义Feistel结构, 提出了低数据量子密钥恢复攻击. 该攻击仅需选择常数项级别规模的明密文, 通过分析分组密码结构的加密过程, 利用Grover算法对某些中间态进行搜索计算, 从而恢复密钥. 且该攻击属于Q1模型, 相比于Q2模型, 无需量子叠加查询, 更具有实际意义. 对于3轮Lai-Massey结构, 相比于其他量子攻击, 该攻击仅需$ \mathrm{O}(1) $数据, 且属于Q1模型, 在复杂度乘积(时间×数据×经典存储×量子比特)评估上降低了$ n{2^{n/4}} $因子. 对于6轮Misty结构, 该方法依然保留着低数据复杂度的优势, 尤其是6轮Misty L/R-FK结构, 在复杂度乘积评估上降低了$ {2^{n/2}} $因子. 对于9轮3分支Type-1型广义Feistel结构, 与其他量子攻击在复杂度乘积评估上保持一致, 该攻击依然保留着低数据复杂度的优势, 且属于选择明文攻击. 此外, 也给出了针对类SMS4 广义Feistel结构和类MARS 广义Feistel结构的低数据量子密钥恢复攻击, 补充了其在Q1模型下的安全性评估. |
| 关键词: Lai-Massey结构 Misty结构 Type-1型广义Feistel结构 类SMS4 广义Feistel结构 类MARS 广义Feistel结构 密钥恢复攻击 |
| DOI：10.13328/j.cnki.jos.007218 |
| 分类号:TP309 |
| 基金项目:国家自然科学基金(62072207); 广东省基础与应用基础研究基金(2022A1515140090); 北京邮电大学博士创新基金(CX2022140) |
|
| Low-data Quantum Key-recovery Attack on Block Cipher Structures |
|
XU Yin-Song1, LUO Yi-Yuan2, DONG Xiao-Yang3, YUAN Zheng4
|
|
1.School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China;2.School of Computer Science and Engineering, Huizhou University, Huizhou 516007, China;3.Institute for Advanced Study, Tsinghua University, Beijing 100190, China;4.Beijing Electronic Science and Technology Institute, Beijing 100070, China
|
| Abstract: |
| In the Q1 model, this paper proposes a low-data quantum key-recovery attack against Lai-Massey structures, Misty structures, Type-1 generalized Feistel structures, SMS4-like generalized Feistel structures and MARS-like generalized Feistel structures. This attack only needs to select constant-sized plain-ciphertexts, analyze the encryption process of block cipher structures, and recover the key by searching and calculating some intermediate states and round keys using Grover’s algorithm. This attack belongs to the Q1 model, which is more practical than the Q2 model since no quantum superposition query is required. For the 3-round Lai-Massey structure, compared with other quantum attacks, this attack requires only $ {\rm O}(1) $ data and belongs to the Q1 model, and is even reduced by the $ n{2^{n/4}} $ factor on the evaluation of the complexity product (time×data×classical memory×quantum bits). For the 6-round Misty structure, this attack still retains the advantage of low data complexity, and especially for the 6-round Misty L/R-FK structure, this attack is reduced by the$ {2^{n/2}} $factor on the evaluation of the complexity product. For the 9-round 3-branch Type-1 generalized Feistel structure, in line with other quantum attacks on the evaluation of the complexity product, this attack still retains the advantage of low data complexity and belongs to the chosen plaintext attack. In addition, a low-data quantum key-recovery attack for SMS4-like generalized Feistel structures and MARS-like generalized Feistel structures are also given in this study, complementing their security evaluation in the Q1 model. |
| Key words: Lai-Massey structure Misty structure Type-1 generalized Feistel structure SMS4-like generalized Feistel structure MARS-like generalized Feistel structure key-recovery attack |
