Page 391 - 《软件学报》2026年第5期

2270 软件学报 2026 年第 37 卷第 5 期

ℓ
可能值, 故 ∆-序列 Γ 5 有 2 个可能值. 证毕.
4.1.2 3-cell 型 GFS 的 8 轮 DS-MITM 攻击及复杂度分析
本节利用命题 2 构造的 6 轮中间相遇区分器, 分别向前向后扩展 1 轮, 实现 8 轮 3-cell 型 GFS 的 DS-MITM
攻击, 攻击包括预计算阶段和在线阶段, 具体过程见图 5(b).
预计算阶段: 详细过程如定理 3 所示, 并将 ∆-序列 Γ 5 的 2 种可能值存储在表 T 9 中.
ℓ

在线阶段: 包括数据收集和密钥恢复两部分.
1) 数据收集. 包括如下 3 个步骤.
ℓ
m, a ∈ F , 如图 5(b) 所示, 构造满足区分器第 1 ∆x 的两个明文
(1.1) 任意选取两个向量 分支差分输入差分为
2
ℓ ℓ ′ ℓ×3 2ℓ
集 {(0,m,a),...,(2 −1,m,a)},{(0,m⊕∆x,a),...,(2 −1,m⊕∆x,a)}, 对应差分 ∆P = (∆x ,∆x,0 ℓ ) ∈ F 2 , 将得到的 2 个
明文对存储在表 T P 中.
ℓ (u 1 ,m,a) 和 (u 2 ,m⊕∆x,a) 分别进行 2ℓ 个差分为
(1.2) 对任意 u 1 , u 2 ∈ F , 将差分为 ∆P 的明文对 8 轮加密得到 2
2
(0 ℓ ,∆z,∆z ) ∈ F ℓ×3 的密文对, 并将其存储在表 T C 中. 对于给定的 ∆x,∆z, 由于 ∆P 和 ∆C 均以概率 p 1 = p 2 = 2 −ℓ 分别
′
2
传播到区分器的输入差分 (∆x,0 ℓ ,0 ℓ ) 和输出差分 (∆z,0 ℓ ,∆z), 则 8 轮截断差分传播概率为 p = 2 −2ℓ . 因此, 至少有
−2ℓ 2ℓ ′ ′
2 ×2 = 1 个明密文对 (P 0 ,P) 和 (C 0 ,C) 满足图 5(b) 所示 (∆x ,∆x,0 ℓ ) → (0 ℓ ,∆z,∆z ) 的 8 轮差分特征.
(1.3) 根据步骤 0 0 0 b-δ-集 G = {P r = (X ⊕∆F ,X ⊕r,
0

I
0
(1.2) 得到的明文对
(P 0 ,P), 利用明文
P 0 = (X ,X ,X ) 构造
0,1 0,2 0,3 0,1 0 0,2
b
0 b I ℓ (P 0 ,P r ), r ∈ [2 −1], 并进行 (C 0 ,C r ),
X )|r ∈ {0,1,...,2 −1}, ∆F ∈ F }, 利用 G 构造明文对 8 轮加密得到对应的密文对
2
0
0,3
2 −1 个明密文对满足图 5(b) 所示的 8 轮差分特征.
b
因此得到
2) 密钥恢复. 包括如下 4 个步骤.
(2.1) 选取步骤 (1.3) 中的一个明文对 (P 0 ,P r ), 根据性质 1, 利用 F(t 0 )⊕ F(t 0 ⊕∆x ) = ∆x 确定 t 0 的唯一值. 当 取
r
′
b b ′ k 0 = t 0 ⊕(X ⊕∆F ) 确定子
I
0
遍 [2 −1] 时, 将得到 t 0 的 2 −1 个可能值存储在以 (∆x ,∆x,0 ℓ ) 为索引的表 T 10 中, 再由
0,1 0
b
密钥 k 0 的 2 −1 个可能值.
b r r r ′
,
(2.2) 对每个 r ∈ [2 −1], 依次选取密文对 (C 0 ,C r ) C r = (X ,X ,X ), 显然 C 0 ⊕C r = (0 ℓ ,∆z,∆z ). 猜测子密钥 k 7
8,1 8,2 8,3
的值, 根据性质 1 和 F(k 7 ⊕ X ) = X ⊕ X ⊕ X r 确定 X r 的唯一值. 当 r 取遍 [2 −1] 时, 将得到 X r 的 2 −1 个可
r
r
r
b
b
7,1 8,1 8,2 8,3 7,1 7,1
′
能值存储在以 (0 ℓ ,∆z,∆z ) 为索引的表 T 11 中.
k 7 的猜测值, 对步骤 {C 0 ,C 1 ,...,C 2 b −1 } 分别进行部分解密, 得到区分器输出处的
(2.3) 根据 (1.3) 得到的密文集
r r r r ℓ×3 b 0 r

可能值 X = (X ,X ,X ) ∈ F , r ∈ {0,1,...,2 −1}, 从而得到 ∆-序列 Γ 6 = (∆ 1 ,∆ 2 ,···,∆ 2 b −1 ), 其中, ∆ r = X ⊕ X , r ∈
7 7,1 7,2 7,3 2 7,1 7,1
b
[2 −1].
b , b
(2.4) 将得到的 2 −1 个明密文对 (P 0 ,P r ) 和 (C 0 ,C r ) 2 −1 组子密钥 (k 0 ,k 7 ) 以及相应的 ∆-序列 Γ 6 = (∆ 1 ,∆ 2 ,...,
∆ 2 b −1 ) 存储在表 T 12 中. 类似地, 当 b ⩾ 3 时, 检查表 T 9 和 T 12 中的 ∆-序列 是否匹配, 若匹配, 则猜测的子密钥 k 0 和 k 7
为正确密钥; 否则, 匹配不成功, 另外选取一对明文重复上述步骤 (2.1)–(2.4).
下面给出攻击的复杂度分析.
ℓ O(2 +2 ) ≈ O(2 ) 个选择
ℓ
ℓ
ℓ
(1) 由于在线阶段构造了两个大小分别为 2 的明文集, 故该攻击的数据复杂度为
明文.
2ℓ
(2) 由于预计算阶段构造表 T 9 和在线阶段猜测密钥所需的时间复杂度均为 O(2 ) 次 8 轮加密, 因此, 攻击所需
O(2 ) 次 8 轮加密.
2ℓ
的时间复杂度为
2ℓ b
(3) 存储表 T 9 和 T 12 所需的存储复杂度为 O(2 ) 个长度为 (2 −1)ℓ 的比特块.
最后, 为了降低攻击的时间复杂度, 需要在 Q1 模型下对 3-cell 型 GFS 做量子并行运算, 此处我们给出该结构
的 8 轮量子 DS-MITM 攻击及复杂度分析, 具体见定理 4.
定理 4. 利用命题 2 构造的中间相遇区分器可对 3-cell 型 GFS 进行 8 轮量子 DS-MITM 攻击, 数据复杂度为
ℓ 3ℓ/ 2 2ℓ
O(2 ) 个选择密文, 时间复杂度为 O(2 ·ℓ) 次量子查询, 存储复杂度为 O(2 ·ℓ) 个量子比特.
证明: 量子 DS-MITM 攻击过程与第 3.3 节类似, 不再赘述.