Page 401 - 《软件学报》2025年第7期

3322 软件学报 2025 年第 36 卷第 7 期

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 O(1) data and belongs to the Q1 model, and is even reduced by the n2 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
分组密码作为一种底层加密手段, 在网络空间安全中扮演着重要角色. 分组密码结构作为分组密码的底层设
计, 对分组密码结构的分析研究是对具体分组密码的安全性考量, 也是对分组密码设计的参考. 分组密码包含着诸
多结构, 如 Feistel 结构 [1] 、Even-Mansour 结构 [2] 、Lai-Massey 结构 [3] 等. 其中, Feistel 结构又包含着一些变体结构,
[5]
如 Misty 结构 [4] 、Type-1/2/3 型广义 Feistel 结构 (generalized Feistel structure, GFS) 、类 SMS4 广义 Feistel 结构 [6] 、
类 MARS 广义 Feistel 结构 [6] 等.
随着量子计算机和量子计算理论的发展, 人们也迫切需要了解分组密码在未来量子计算环境下的安全性, 越
来越多的工作开始评估分组密码, 尤其是其底层结构的后量子安全性. 2010 年, Kuwakado 等人 [7] 提出了 3 轮
Feistel 结构的量子区分器, 利用 Simon 算法 [8] 可在多项式时间区分是否为随机置换, 结果证明在量子选择明文攻
击下 (qCPA), 3 轮 Feistel 结构将不再安全. 2012 年, Kuwakado 等人 [9] 又利用 Simon 算法对 Even-Mansour 结构在
多项式时间内实现密钥恢复攻击. 2016 年美密会上, Kaplan 等人 [10] 依然利用 Simon 算法对不同加密结构和工作
模式的消息认证密码实现伪造攻击. 2017 年亚密会上, Leander 等人 [11] 将 Grover 算法 [12] 和 Simon 算法结合起来提
出了“Grover Meets Simon”方法, 并应用在 FX 结构上. 后续, “Grover Meets Simon”方法被不断应用在 Feistel 结
构 [13] 、Type-1/2/3 型广义 Feistel 结构 [14,15] 等结构. 为了优化基于“Grover Meets Simon”方法的量子攻击, 研究者们
试图寻找更长的量子区分器. 例如, Ito 等人 [16] 提出了新的 4 轮 Feistel-F/KF 结构和 6 轮 Feistel-FK 的量子区分器,
在相同轮数 Feistel 结构的密钥恢复攻击条件下, 其复杂度将更低.
以上量子攻击都属于 Q2 模型, 即攻击者可以对加密黑盒 (量子选择明文攻击, qCPA) 或解密黑盒 (量子选择
密文攻击, qCCA) 进行量子叠加查询. 而研究者们更希望攻击者能仅对黑盒做经典查询, 再辅以量子计算机做离
线计算, 即 Q1 模型. 可以看出, Q2 模型需要攻击者能够访问量子加密或解密黑盒这一理想情况, 一旦被禁止访问,
则攻击将无法进行, 并且在现实情况中数据都被经典计算机进行加密, 所以只需要经典查询的 Q1 模型更具有实
际意义. 2018 年, Hosoyamada 等人 [17] 在 Guo 等人 [18] 的工作基础上, 提出了针对 6 轮 Feistel 结构的量子中间相遇
攻击. 该工作无需量子叠加查询, 且复杂度低于 Guo 等人的工作. 2022 年, Daiza 等人 [19] 提出了 3 轮 Feistel 结构的
新型简洁高效的密钥恢复攻击方法, 在已知明文或选择明文攻击环境下, 仅需几个明密文, 再辅以 Grover 算法进
行搜索计算, 即可实现密钥恢复攻击.
受 Daiza 等人 [19] 的工作启发, 本文针对不同分组密码结构, 包含 Lai-Massey 结构、Misty 结构、Type-1 型
GFS 结构、类 SMS4 GFS 结构和类 MARS GFS 结构, 提出了新型低数据密钥恢复攻击方法, 即仅需选择常数项级
别的明密文, 分析分组密码结构的加密过程, 利用 Grover 算法对某些中间态和轮密钥进行搜索计算, 从而恢复密
钥. 本文所提方法与其他量子攻击方法的复杂度比较见表 1. 相比于其他量子攻击, 本文的攻击无需量子叠加查询,
O(1). 对于 3 轮 Lai-Massey O(2 ), 高于文献 [20], 但是仅
n/4
且数据复杂度仅为 结构 , 虽然本文的方法时间复杂度为
需 O(1) 明密文, 无需量子叠加查询, 且在所有复杂度乘积 (时间×数据×经典存储×量子比特) 的评估上, 更少了
n2 n/4 因子. 对于 6 轮 Misty L-KF 结构, 相比于文献 [21], 本文的方法仅需 O(1) 明密文. 而对于 6 轮 Misty L-FK 结
构, 本文与文献 [21] 保持相同的时间复杂度, 但数据复杂度仅为 O(1), 且复杂度乘积更低了 2 n/2 因子, 甚至更优于
文献 [6] 的 qCPA 方法. 对于 6 轮 Misty R-KF 结构, 本文的方法相比于文献 [21] 属于选择明文攻击, 而非选择密文
攻击. 对于 6 轮 Misty R-FK 结构, 本文的方法相比于文献 [21], 只需 O(1) 明密文, 且属于选择明文攻击. 当 d = 3