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

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

构特征, 其次, 利用多重集和差分枚举技术给出 3-cell 型 GFS 的 6 轮中间相遇区分器, 并在此基础上进行 8 轮
(量子) DS-MITM 攻击, 最后, 将上述相关结果推广至 n-cell 型 GFS, 并进行 2(n+1) 轮 (量子) DS-MITM 攻击.
设 n-cell 型 GFS 的分组长度为 nℓ 比特, 每个分支的输入长度为 比特, 如图 5(a). 记 X i = (X i,1 ,X i,2 ,...,X i,n ) ∈ F ℓ×n
ℓ
2
为第 i 轮的输入, i ∈ N, 则有:

(X i+1,1 ,X i+1,2 ,...,X i+1,n ) = (X i,2 ,X i,3 ,...,X i,n ,F i (k i ⊕ X i,1 )⊕ X i,2 ⊕ X i,3 ⊕...⊕ X i,n ),
ℓ
ℓ
其中, F i = F(k i ⊕ X i,1 ) ∈ F 为第 i 轮的轮函数, k i ∈ F 为参与第 i 轮轮密钥.
2 2

X X X
0,1 0,2 0,3
Δx' Δx 0
0 F 0 k
i X ,1 X i ,2 i X ,3 X , i n Δx X 1,1 0 X 1,2 0 X 1,3
6 轮中间相遇区分器
F i i k ··· Δz X 7,1 0 X 7,2 Δz X 7,3
7 F 7 k

0 Δz Δz'
X X X X
i X + 1,1 i X + 1,2 i+ 1,n− 1 i X + 1,n 8,1 8,2 8,3
(a) n-cell 型 GFS 的第 i 轮结构 (b) 3-cell 型 GFS 的 8 轮 DS-MITM 攻击
图 5 n-cell 型 GFS 的第 i 轮结构和 3-cell 型 GFS 的 8 轮 DS-MITM 攻击

4.1 3-cell 型 GFS 的 8 轮 (量子) DS-MITM 攻击
本节首先构造 3-cell 型 GFS 的 6 轮中间相遇区分器, 其次, 对其分别向前向后扩展 1 轮, 实现 8 轮 3-cell 型
GFS 的 (量子) DS-MITM 攻击, 并分析该攻击的复杂度.
4.1.1 3-cell 型 GFS 的 6 轮中间相遇区分器
构造 3-cell 型 GFS 的中间相遇区分器, 需要讨论在给定轮函数输入和输出差分时各轮内部状态的所有可能
值, 具体见命题 2.
命题 2. 对于 6 轮 3-cell 型 GFS, 若给定 ∆x, ∆z ∈ F , 选取一个输入对 (A 0 ,A) ∈ F 3ℓ×2 满足 ∆A = A 0 ⊕ A = (∆x,0 ℓ ,0 ℓ ),
ℓ
2 2
进行加密后得到输出对 (B 0 ,B) ∈ F 3ℓ×2 且 ∆B = B 0 ⊕ B = (∆z,0 ℓ ,∆z), 则有:
2
(1) 存在 (∆x,0 ℓ ,0 ℓ ) → (∆z,0 ℓ ,∆z) 的一条 6 轮中间相遇区分器.
(2) 满足区分器第 1, 4 和 5 轮内部状态值的数量平均为 2 .
ℓ
证明:
(1) 如图 ∆F = ∆x , 0 ℓ , 显然
I
(∆x,0 ℓ ,0 ℓ ) 时, 由于
6(a) 所示, 从加密方向考虑, 根据差分传播特性, 当输入差分为
1
O O I I (∆z,0 ℓ ,∆z) 时, 根据差分传播规律, 有
∆F , 0 ℓ , 记 ∆y = ∆F , 则 ∆F = ∆F = ∆y. 从解密方向考虑, 当输出差分为
1 1 4 5
O O (∆x,0 ℓ ,0 ℓ ) → (∆z,0 ℓ ,∆z) 的
,
∆F = ∆z ∆F = ∆y⊕∆z. 由此可得一条满足 6 轮中间相遇区分器.
5 4
(2) 下面讨论区分器第 1、4 和 5 i 轮轮函数的输入, 从加密方向可得:
轮内部状态的可能值, 令 t i 为第

F 1 (t 1 )⊕ F 1 (t 1 ⊕∆x) = ∆y




 F 4 (t 4 )⊕ F 4 (t 4 ⊕∆y) = ∆y⊕∆z (3)



F 5 (t 5 )⊕ F 5 (t 5 ⊕∆y) = ∆z

S 盒会影响差分, 根据性质 1, 当公式 ∆x, ∆z 给定, ∆y 取固定值时, 轮函数的内
由于轮函数内部仅有 (3) 中的
ℓ
ℓ
部状态值 t 1 , t 4 和 t 5 平均只有 1 个解. 由于 ∆y 最多可取 2 个值, 所以上述 3 个内部状态值的数量平均为 2 . 证毕.
下面利用区分器的输入对讨论 3-cell 型 GFS 的 ∆-序列 Γ 5 可能值的个数.