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

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

X 0,1 X 0,2 X 0,3
0 Δx Δx'
k 0,1 k 0,2
F 0,1 F 0,2
t 0,1 t 0,2
X i,1 X i,2 X i,3
Δx 0 0
k i,1 k i,2 X 1,1 X 1,2 X 1,3
F i,1 F i,2 4 轮中间相遇区分器
0 X 5,1 Δz X 5,2 0 X 5,3
k 5,1 k 5,2
F 5,1 F 5,2
X i+1,1 X i+1,2 X i+1,3 t 5,1 t 5,2
Δz Δz' 0
X 6,1 X 6,2 X 6,3
(a) 第 i 轮结构 (b) 6 轮 DS-MITM 攻击
图 2 3 分支 Type-III 型 GFS 第 i 轮结构和 6 轮 DS-MITM 攻击

2.1 3 分支 Type-III 型 GFS 的 4 轮中间相遇区分器
为研究 Type-III 型 GFS 各轮轮函数内部状态的所有可能值, 引入 Guo 等人 [12] 对于经典 5 轮 Feistel 结构内部
状态所有可能值的相关结论, 具体见引理 1.
引理 1 [12] . 对于一个经典的 5 轮 ℓ (A 0 ,A) ∈ F 2ℓ×2 ∆A = A 0 ⊕
∆x , ∆z ∈ F , 选取一个输入对
Feistel 结构, 若给定
2 2 满足
A = (0 ℓ ,∆x), 进行加密后得到输出对 (B 0 ,B) ∈ F 2ℓ×2 且 ∆B = B 0 ⊕ B = (0 ℓ ,∆z), 则满足截断差分 ∆A → ∆B 的中间 3 轮
2
ℓ
内部状态值的数量平均为 2 .
类似地, 可以得到下述 3 分支 Type-III 型 GFS 中间相遇区分器的相关结论.
命题 1. 对于 3 分支 Type-III 型 GFS, 若给定 ∆x, ∆z ∈ F , 选取一个输入对 (A 0 ,A) ∈ F 3ℓ×2 满足 ∆A = A 0 ⊕ A = (∆x,0 ℓ ,
ℓ
2 2
0 ℓ ), 进行加密后得到输出对 (B 0 ,B) ∈ F 3ℓ×2 且 ∆B = B 0 ⊕ B = (0 ℓ ,∆z,0 ℓ ), 记 ∆y 为 F 1,1 的输出差分, 则当 (∆x → ∆y) 为
2
F 3,2 的一条有效差分传播时:
(∆x,0 ℓ ,0 ℓ ) → (0 ℓ ,∆z,0 ℓ ) 的一条 4 轮中间相遇区分器.
(1) 存在
(2) 满足区分器前 3 轮内部状态值的数量平均为 2 .
ℓ
证明:
(1) 如图 3(a) 所示, 从加密方向考虑, 当该结构的输入差分为 (∆x,0 ℓ ,0 ℓ ) 时, 根据差分传播规律, 有 ∆F I =
3,2
,
O
∆F I = ∆x. 从解密方向考虑, 根据差分传播规律, 当输出差分为 (0 ℓ ,∆z,0 ℓ ) 时, 有 ∆F O = ∆x ∆F O = (∆F ⊕0 ℓ )⊕
1,1 3,1 2,1 1,2
O I I O O
(∆F ⊕∆z) = ∆z , 0 ℓ , 显然 ∆F , 0 ℓ , 记 ∆y = ∆F , 则 ∆F = ∆F = ∆y. 由此可得一条满足 (∆x,0 ℓ ,0 ℓ ) → (0 ℓ ,∆z,0 ℓ )
4,2 2,1 2,1 3,2 1,1
的 4 轮中间相遇区分器.
(2) 下面讨论前 3 i 轮第 个轮函数的输入, 从加密方向可得:
j
轮内部状态的可能值, 令 t i,j 为第

F 1,1 (t 1,1 )⊕ F 1,1 (t 1,1 ⊕∆x) = ∆y, F 2,1 (t 2,1 )⊕ F 2,1 (t 2,1 ⊕∆y) = ∆z

(1)

F 3,1 (t 3,1 )⊕ F 3,1 (t 3,1 ⊕∆z) = ∆x, F 3,2 (t 3,2 )⊕ F 3,2 (t 3,2 ⊕∆x) = ∆y

S 盒会影响差分, 根据性质 1, 当公式 ∆x,
由于轮函数内部的线性运算不影响差分, 只有非线性运算 (1) 中的
ℓ
∆z 给定, ∆y 取固定值时, 轮函数的内部状态值 t 1,1 , t 2,1 , t 3,1 和 t 3,2 平均只有 1 个解. 由于 ∆y 最多可取 2 个值, 所以
上述 4 个内部状态值的数量平均为 2 . 证毕.
ℓ
下面基于区分器的输入对讨论 3 分支 Type-III 型 GFS 的 ∆-序列 Γ 1 可能值的个数.
定理 1. 若输入对 (A 0 ,A) ∈ F 3ℓ×2 满足命题 1 中区分器的输入, 利用 A 0 构造 b-δ-集 M = {(A 0 ⊕(r,0 ℓ ,0 ℓ )) ∈ F |r ∈
3ℓ

2 2
b ℓ
{0,1,...,2 −1}}, 则可得 ∆-序列 Γ 1 = (∆ 1 ,∆ 2 ,...,∆ 2 b −1 ) 有 2 个可能值.
证明: 如图 3(b) 所示, 设 X 1,1 ∈ F 的 b 比特活跃, 输入对 (A 0 ,A) ∈ F 3ℓ×2 的差分 ∆A = A 0 ⊕ A = (r,0 ℓ ,0 ℓ ), 根据集合
ℓ
2
2
(A 0 ,A 0 ⊕(r,0 ℓ ,0 ℓ )) r ∈ [2 −1], 将其加密 4 r r r r ∆ r =
,
b
M 可得输入对 轮得到差分为 ∆X = (∆X ,∆X ,∆X ) 的输出对. 则
5,1
5
5,3
5,2