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

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

n/2
y 0 x,y ∈ {0,1}
其中, 变量 x 和 y 分别对应 x 0 和 , n/2 且 G(x,y) ∈ {0,1} . 依据公式 (18), 我们提出以下针对 5 轮 Misty R-
FK 结构的密钥恢复过程.
2
2
2
1 1 1 (x ,y = F 1 (x )), 并查询其对应的密文. 根据公式 (15)–(18), 可计算求得:
(1) 选择明文 (x ,y = F 1 (x )) 和
0 0 0 0 0 0
1
1
1
1
1
G(x ,y ) = F 3 (F 1 (x )⊕ F 2 (F 1 (x )⊕y ⊕k 1 )⊕k 2 )⊕k 4 ⊕k 5 ,
0 0 0 0 0
2
2
2
2
2
G(x ,y ) = F 3 (F 1 (x )⊕ F 2 (F 1 (x )⊕y ⊕k 1 )⊕k 2 )⊕k 4 ⊕k 5 .
0
0
0
0
0
1 1 2 2
(2) 将 G(x ,y ) 和 G(x ,y ) 异或后可得:
0 0 0 0
2
G(x ,y )⊕G(x ,y ) = F 3 (F 1 (x )⊕ F 2 (k 1 )⊕k 2 )⊕ F 3 (F 1 (x )⊕ F 2 (k 1 )⊕k 2 ).
1
1
2
1
2
0 0 0 0 0 0
( 3 ) 设 β 1 = F 1 (x )⊕ F 2 (k 1 )⊕k 2 β 2 = F 1 (x )⊕ F 2 (k 1 )⊕k 2 , 则 β 1 ⊕β 2 = F 1 (x )⊕ F 1 (x ) G(x ,y )⊕G(x ,y ) = F 3 (β 1 )
,
2
2
2
1
2
1
,
1
1
0 0 0 0 0 0 0 0
2
1 2 , 1 1 , 2 2 , 1 x 值, 可利用 Grover 算法搜索出未
⊕F 3 (β 1 ⊕ F 1 (x )⊕ F 1 (x )). 由于已知公开函数 F 3 和 F 1 G(x ,y ) G(x ,y ) x 和 0
0
0
0
0
0
0
0
β 1 .
知量
(x ,y ) y , F 1 (x )), 并查询器对应的密文. 根据公式 (15)–(18), 可计算求得:
3
1
1
3
(
(4) 选择明文
0 0 0 0
G(x ,y ) = F 3 (F 1 (x )⊕ F 2 (F 1 (x )⊕y ⊕k 1 )⊕k 2 )⊕k 4 ⊕k 5 .
1
1
1
3
3
0 0 0 0 0
1 1 1 3
(5) 将 G(x ,y ) 和 G(x ,y ) 异或后可得:
0 0 0 0
1
3
1
1
1
1
3
G(x ,y )⊕G(x ,y ) = F 3 (β 1 )⊕ F 3 (F 1 (x )⊕ F 2 (F 1 (x )⊕y ⊕k 1 )⊕k 2 ).
0 0 0 0 0 0 0
同样地, 可用 Grover 算法搜索出未知量 F 1 (x )⊕ F 2 (F 1 (x )⊕y ⊕k 1 )⊕k 2 值.
1
1
3
0 0 0
3
1 1 3 F 2 (k 1 )⊕ F 2 (F 1 (x )⊕y ⊕k 1 ), 依然可用 Grover 算法搜索
1
(6) 将 β 1 和 F 1 (x )⊕ F 2 (F 1 (x )⊕y ⊕k 1 )⊕k 2 异或后可得
0 0 0 0 0
出未知量 k 1 .
(7) 搜索出 k 1 后, 可依次计算出剩余轮密钥 k 2 k 5 .
–
复杂度分析. 在对 5 轮 Misty R-FK 结构的密钥恢复攻击过程中, 我们仅需选择 3 个明密文对即可恢复密钥, 且
在步骤 (3)、(5)、(6) 中利用 Grover 算法搜索未知量, 每一个未知量的规模为 2 , 所以每一步的时间复杂度都分别
n/2
n/4 n/4
为 O(2 ). 综上, 该密钥恢复攻击的总体时间复杂度为 O(2 ), 数据复杂度为 O(1) 且经典存储复杂度可忽略不计.
若在 5 轮 Misty R-FK 结构上再增加 r −5 轮, 则可先穷举轮密钥 k 6 k r , 再重复以上步骤恢复其他轮密钥, 并
–
用明密文进行验证正确性. 则整体时间复杂度为 O(2 n/4+(r−5)n/2 ), 数据复杂度依然仅为 O(1) 且经典存储复杂度可忽
略不计.

6 对 Type-1 型广义 Feistel 结构的密钥恢复攻击
如图 12 所示的 3d −3 轮 Type-1 型广义 Feistel-FK 结构, 分组长度为 n 比特, 其中每个分支与轮密钥 (
k i i =
j j = 0,1,...,
,
i
i i = 0,1,...,3d −3) 轮, 下标
1,2,...,3d −3) 的比特长度为 n/d F i 为轮函数, x 的上标 i 表示第 ( j 表示第 (
j
0
0
d −1) 个分支. 明文 (x , x ,..., x 0 ) 作为其输入, 经过 3d −3 轮加密后得到密文 (x 3d−3 , x 3d−3 ,..., x 3d−3 ).
0 1 d−1 0 1 d−1
根据 Type-1 型广义 Feistel-FK 结构加密过程, 我们选择密文中的 x 3d−3 和 x 3d−3 部分, 由于存在 x = x i+1 =
i
1 2 0 d−1
x i+2 = ... = x i+d−1 性质, 有:
d−2 1
x 3d−3 = x 2d−1 = F 2d−2 (x 2d−2 )⊕ x d ⊕k 2d−2 , x 3d−3 = F 2d−1 (F 2d−2 (x 2d−2 )⊕ x d ⊕k 2d−2 )⊕ x d ⊕k 2d−1 (19)
1 d−1 d−1 d−2 2 d−1 d−2 d−1
我们发现 x 3d−3 中函数 F 2d−1 的输入正好是 x 3d−3 值, 则可利用公开函数 F 2d−1 计算 F 2d−1 (x 3d−3 ), 并与 x 3d−3 异或后
2 1 1 2
可得:

F 2d−1 (x 3d−3 )⊕ x 3d−3 = x d ⊕k 2d−1 (20)
1 2 d−1
i
由于 x = x i+1 = x i+2 = ... = x i+d−1 , 则:
0 d−1 d−2 1

F 2d−1 (x 3d−3 )⊕ x 3d−3 = x d−1 ⊕k 2d−1 (21)
0
1
2
0
0
由于 x d−1 = F d−1 (F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 ⊕k d−2 )⊕ x 0 ⊕k d−1 , 则:
0 0 1 d−2 d−1
0
0
F 2d−1 (x 3d−3 )⊕ x 3d−3 = F d−1 (F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 ⊕k d−2 )⊕ x 0 ⊕k d−1 ⊕k 2d−1 (22)
1 2 0 1 d−2 d−1