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

许垠松 等: 分组密码结构的低数据量子密钥恢复攻击 3329

5.1 对 Misty L-KF 结构的密钥恢复攻击
在本节中, 我们将主要以 Misty L-KF 结构作为攻击目标. 如图 8 所示的 4 轮 Misty L-KF 结构, 其中 F i (x i−1 ⊕k i )
( i = 1,2,3,4) 为轮函数, k i 为轮密钥且 |k i | = n/2 i = 1,2,3,4 (x 0 ,y 0 ) 为 4 轮 Misty L-KF 结构的明文输入且 |(x 0 ,y 0 )| =
(
),
,
n (x 4 ,y 4 ) 作为密文输出.

y 1 y 2 y 3
y 0 y 4
k 1 k 2 k 3 k 4
x 0 F 3 x 4
F 1 F 2 F 4
x 1 x 2 x 3
图 8 4 轮 Misty L-KF 结构

根据 Misty L-KF (x 4 ,y 4 ) 的值为:
结构的加密过程, 我们可以得到密文
x 4 = y 0 ⊕ F 1 (x 0 ⊕k 1 )⊕ F 2 (y 0 ⊕k 2 )⊕ F 3 (y 0 ⊕ F 1 (x 0 ⊕k 1 )⊕k 3 ),

y 4 = y 0 ⊕ F 1 (x 0 ⊕k 1 )⊕ F 2 (y 0 ⊕k 2 )⊕ F 3 (y 0 ⊕ F 1 (x 0 ⊕k 1 )⊕k 3 )⊕ F 4 (y 0 ⊕ F 1 (x 0 ⊕k 1 )⊕ F 2 (y 0 ⊕k 2 )⊕k 4 ),
将密文的左半部分 x 4 与右半部分 y 4 异或后可得:

x 4 ⊕y 4 = F 4 (y 0 ⊕ F 1 (x 0 ⊕k 1 )⊕ F 2 (y 0 ⊕k 2 )⊕k 4 ) (9)
根据公式 (9) 可设函数:

G(x,y) = F 4 (y⊕ F 1 (x⊕k 1 )⊕ F 2 (y⊕k 2 )⊕k 4 ) (10)
n/2
y x 0 和 ; n/2 G(x,y) ∈ {0,1} . 在公式 (10) 的基础上, 我们可以构建新的
y 0 x,y ∈ {0,1}
其中, 变量 x 和 分别对应明文 且
4 轮 Misty L-KF 结构密钥恢复攻击, 具体过程如下.
2
1 1 (x ,y ), 并查询其对应的密文. 根据公式 (9)、(10) 可得:
1
(1) 选择明文 (x ,y ) 和
0 0 0 0
1
1
1
2
1
2
1
G(x ,y ) = F 4 (y ⊕ F 1 (x ⊕k 1 )⊕ F 2 (y ⊕k 2 )⊕k 4 ),G(x ,y ) = F 4 (y ⊕ F 1 (x ⊕k 1 )⊕ F 2 (y ⊕k 2 )⊕k 4 ).
1
2
1
0
0
0
0
0
0
0
0
0
0
设 β 1 = y ⊕ F 1 (x ⊕k 1 )⊕ F 2 (y ⊕k 2 )⊕k 4 , β 2 = y ⊕ F 1 (x ⊕k 1 )⊕ F 2 (y ⊕k 2 )⊕k 4 , 则 G(x ,y ) = F 4 (β 1 ) 且 G(x ,y ) =
1
1
1
2
1
2
1
2
1
1

0 0 0 0 0 0 0 0 0 0
2
1
1
1

F 4 (β 2 ). 由于已知公开函数 F 4 , G(x ,y ) 和 G(x ,y ) 值, 利用 Grover 算法可搜索出 β 1 和 β 2 值.
0 0 0 0
1
2
2
1
(2) β 1 和 β 2 异或后可得 β 1 ⊕β 2 = y ⊕y ⊕ F 2 (y ⊕k 2 )⊕ F 2 (y ⊕k 2 ). 由于已知公开函数 F 2 β 1 ⊕β 2 y , 1 0 和 y 值, 依然
2
,
0
0
0
0
0
可利用 Grover 算法搜索出轮密钥 k 2 .
k 1 k 4 和 , 可依次通过
(3) 对于剩下的轮密钥 , k 3 Grover 算法搜索出来.
复杂度分析. 通过上述密钥恢复攻击过程可知, 我们的攻击仅需 4 个明文, 且每一步中的 Grover 搜索时间为
n/4 n/4
O(2 ), 则总的时间复杂度依然为 O(2 ). 其数据复杂度仅为 O(1), 经典存储复杂度可忽略不计.
–
–
如果扩展 r −4 轮构成 轮 r Misty L-KF 结构, 则可先穷举 k 5 k r , 对每一次猜测的 k 5 k r , 重复以上 3 个步骤, 若
k 1 k r 计算正确. 整个密钥恢复过程的时间复
–
得到的所有轮密钥 k 1 k r 都能使明密文正确地加解密, 则所有轮密钥 –
杂度为 O(2 n/4+(r−4)n/2 ), 数据复杂度同样仅为 O(1), 且经典存储复杂度可忽略不计.

5.2 对 Misty L-FK 结构的密钥恢复攻击
在本节中, 我们将先给出针对 5 轮 Misty L-FK 结构 (如图 9 所示) 的密钥恢复攻击过程.

y 1 y 2 y 3 y 4
y 0 y 5
x 0 F 1 F 2 F 3 F 4 F 5 x 5
x 1 x 2 x 3 x 4
k 1 k 2 k 3 k 4 k 5
图 9 5 轮 Misty L-FK 结构