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

杜小妮 等: 三类非平衡广义 Feistel 结构的量子中间相遇攻击 2267

在线阶段: 包括数据收集和密钥恢复两部分.
1) 数据收集. 包括如下 3 个步骤.
c, a ∈ F , 如图 4(b) 所示, 构造满足区分器第 1 ∆z 的两个密文集
ℓ
(1.1) 任意选取两个向量 分支输出差分为
2
ℓ ℓ ′

{(0,a,c),(1,a,c),...,(2 −1,a,c)},{(0,a,c⊕∆z),(1,a,c⊕∆z),...,(2 −1,a,c⊕∆z)}, 相应的密文差分 ∆C = (∆z ,0 ℓ ,∆z) ∈
F ℓ×3 , 将这 2 2ℓ 个密文对存储在列表 T C 中.
2
ℓ 2ℓ
(1.2) 对任意 u 1 , u 2 ∈ F , 将差分为 ∆C 的密文对 (u 1 ,a,c) 和 (u 2 ,a,c⊕∆z) 分别进行 11 轮解密得到 2 个差分为
2
∆P = (∆x,∆x ,0 ℓ ) ∈ F ℓ×3 的明文对, 并将其存储在列表 T P 中. 对于给定的 ∆x, ∆z, 由于明密文差分 ∆P 和 ∆C 均以
′
2
概率 p 1 = p 2 = 2 −ℓ 分别传播到区分器的输入差分 (0 ℓ ,0 ℓ ,∆x) 和输出差分 (∆z,0 ℓ ,0 ℓ ), 则 11 轮截断差分传播概率为
2ℓ
−2ℓ
′
′
p = 2 −2ℓ . 因此, 至少有 2 ×2 = 1 个明密文对 (P 0 ,P) 和 (C 0 ,C) 满足图 4(b) 所示 (∆x,∆x ,0 ℓ ) → (∆z ,0 ℓ ,∆z) 的 11 轮
差分特征.
(1.3) 根据步骤 C 0 = (X 0 ,X 0 ,X 0 b-δ-集G = {C r = (X 0 ⊕∆F , X 0 ,
O
(C 0 ,C), 利用密文
(1.2) 得到的密文对
11,1 11,2 11,3 ) 构造 11,1 10 11,2
ℓ
b
O
b
X 0 11,3 ⊕r) | r ∈ {0,1,...,2 −1}, ∆F ∈ F }, 利用 G 构造密文对 (C 0 ,C r ), r ∈ [2 −1], 并依次进行 11 轮解密得到对应的
2
10
2 −1 个明密文对满足图 4(b) 所示的 11 轮差分特征.
b
明文对 (P 0 ,P r ), 因此得到
2) 密钥恢复. 包括如下 4 个步骤.
(2.1) 选取步骤 (1.3) 中的一个密文对 (C 0 ,C r ), 其差分为 C 0 ⊕C r = (∆z ,0 ℓ ,∆z), 根据性质 1 和 F(t 10 )⊕ F(t 10 ⊕
′
′ b b ′
r
∆z) = ∆z 确定 t 10 的唯一值. 当 取遍 [2 −1] 时, 将得到 t 10 的 2 −1 个可能值存储在以 (∆z ,0 ℓ ,∆z) 为索引的表 T 6
b
中, 再由 k 10 = t 10 ⊕(X 0 ⊕r) 确定子密钥 k 10 的 2 −1 个可能值.
11,3
,
b r r r P 0 ⊕ P r = (∆x,∆x ,0 ℓ ). 类似地, 利用
′
(2.2) 对每个 r ∈ [2 −1], 依次选取明文对 (P 0 ,P r ) P r = (X ,X ,X ), 显然
0,1 0,2 0,3
r
′ b b (∆x,∆x ,0 ℓ ) 为索
′
F(t 0 )⊕ F(t 0 ⊕∆x) = ∆x 确定 t 0 的唯一值. 当 取遍 [2 −1] 时, 将得到 t 0 的 2 −1 个可能值存储在以
b
引的表 T 7 中, 再由 k 0 = t 0 ⊕ X r 确定子密钥 k 0 的 2 −1 个可能值.
0,1
(2.3) 根据 k 0 的猜测值, 对步骤 (1.3) 得到的明文集 {P 0 ,P 1 ,...,P 2 b −1 } 分别进行部分加密, 得到区分器输入处的
r r r r ℓ×3 b 0 r
可能值 X = (X ,X ,X ) ∈ F ,r ∈ {0,1,...,2 −1} , 从而得到 ∆-序列 Γ 4 = (∆ 1 ,∆ 2 ,...,∆ 2 b −1 ) , 其中, ∆ r = X ⊕ X ,
1,2
2
1,1
1,1
1,1
1,3
1
r ∈ [2 −1] .
b
(2.4) 将步骤 (1.3) 中的 2 −1 个明密文对 (P 0 ,P r ) 和 (C 0 ,C r ), 步骤 (2.1)–(2.3) 中的 2 −1 组子密钥 (k 0 , k 10 ) 以及
b
b
相应的 ∆-序列 Γ 4 = (∆ 1 ,∆ 2 ,...,∆ 2 b −1 ) 存储在表 T 8 中. 类似地, 当 b ⩾ 3 时, 检查表 T 5 和 T 8 中的 ∆-序列 是否匹配, 若
k 0 和 k 10 为正确密钥; 否则, 匹配不成功, 另外选取一对明文重复上述步骤 (2.1)–(2.4).
匹配, 猜测的子密钥
下面给出攻击的复杂度分析.
ℓ ℓ ℓ ℓ
(1) 由于在线阶段构造了两个大小分别为 2 的密文集, 故该攻击的数据复杂度为 O(2 +2 ) ≈ O(2 ) 个选择密文.
O(2 ) 次 11 轮解密, 因此, 攻击
2ℓ
(2) 由于预计算阶段构造表 T 5 和在线阶段猜测子密钥所需的时间复杂度均为
2ℓ
所需的时间复杂度为 O(2 ) 次 11 轮解密.
2ℓ 2ℓ 2ℓ b
(3) 存储表 T 5 和 T 8 所需的存储复杂度为 O(2 +2 ) ≈ O(2 ) 个长度为 (2 −1)ℓ 的比特块.
定理 2. 利用文献 [13] 的中间相遇区分器可对 3 分支 Type-I 型 GFS 进行 11 轮量子 DS-MITM 攻击, 数据复
ℓ 3ℓ/ 2 2ℓ
杂度为 O(2 ) 个选择密文, 时间复杂度为 O(2 ·ℓ) 次量子查询, 存储复杂度为 O(2 ·ℓ) 个量子比特.
证明: 量子 DS-MITM 攻击过程与第 3.3 节类似, 不再赘述.
ℓ
(1) 显然, 数据复杂度为 O(2 ) 个选择密文.
′ ℓ ℓ/ 2 ℓ ℓ 3ℓ/ 2 ·ℓ) 次量子查
(2) 由于构造表 T 和运行爪搜索算法 (l = 2 ) 的时间复杂度分别为 O(2 +2 ) ≈ O(2 ) 和 O(2
5
询. 因此, 总的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次量子查询.
′ ℓ 2ℓ ℓ 2ℓ
(3) 构造表 T 和运行爪搜索算法筛选密钥 (l = 2 ) 需要 O(2 ·ℓ +2 ·ℓ) ≈ O(2 ·ℓ) 个量子比特.
5
4 3-cell 型和 n-cell 型 GFS 的 (量子) DS-MITM 攻击
本节以 3-cell 型 GFS 为例探讨 n-cell 型 GFS 的 (量子) DS-MITM 攻击方案. 首先简要介绍 n-cell 型 GFS 的结