Page 222 - 《软件学报》2021年第9期

2846 Journal of Software 软件学报 Vol.32, No.9, September 2021

(8)
(9)
攻击的主要思想是:通过猜测第 9 轮轮密钥 RK 及第 8 轮轮密钥 RK 的部分比特,对密文进行部分解密后,
观察第 7 轮输出的对应位置是否概率平衡来得到正确密钥.
−m
以 20~22 这 3 个高概率平衡位置为例,进行 N 次实验(其中,N=⎡C⋅p ⎤),每次实验的攻击步骤如下.
• 第 1 步,选取 m 组明文,对每组明文进行如下操作:
16
(1) 对每组明文(其中,{p 5 ,p 8 ,p 9 ,p 10 ,p 11 ,p 26 ,p 27 ,p 28 ,p 29 ,p 30 ,p 35 ,p 42 ,p 50 ,p 51 ,p 61 ,p 63 }遍历{0,1} ,其余位置随
16
,
机选定为常数,故一组明文包含 2 个明文)进行 9 轮加密,密文记为 CC 1 ,...,C 2 − 1
16 ;
0
(9)
(9)
(9)
(2) 猜测 RK 的 4 个密钥字(共 16 比特) RK 4 (9) ,RK 10 ,RK 11 ,RK 14 (9) ,计算 Q ()i j = γ − 1 (64 ( )P − 1 C ⊕ i RK (9) ) ,
j
j∈{4,10,11,14};
(8)
(i)
i
−1
(3) 计算 T =P64 (Q ),猜测 RK 的一个密钥字 RK (8) ,计算 R = i S − 1 (T ⊕ i RK 8 ) ;
5 5 5
16
i
(4) 判断 t = ⊕ 2 − 1 R 是否为 0,j∈{20,21,22},若 t 20 ,t 21 ,t 22 均为 0,则给该组密钥( RK (9) ,RK (9) ,RK (9) ,
j = i 0 j 4 10 11
RK (9) ,RK (8) ,共 20 比特)计数器+1;
14 5
20
• 第 2 步,对 m 组明文重复上述过程,在 2 个计数器中,若某组密钥计数值与 m 相同,则将其视为该次实
验的候选密钥.
统计 N 次实验候选密钥总数,其中正确密钥出现次数约为 C,与错误密钥相比具有一定的显著性,故正确密
钥可唯一恢复.
2.4 密钥恢复实验结果
在 PC 机上,利用 Visual Studio 2010 编程模拟了密钥筛选过程.以 20~22 这 3 个高概率平衡位置为例,分析
组数 m、显著度 C 与复杂度的关系.每种情形分别进行了 100 次实验.
表 3 表明:随着组数的增加,错误密钥量越来越少,但数据复杂度越来越大.正确密钥量与显著度 C 基本一致.
Table 3 Relationship among group number m, key amount and complexity when C=2
表 3 固定 C=2,分析组数 m、密钥量以及复杂度之间的关系
正确密钥量/个 错误密钥量/个 数据复杂度
16
m=7 2.57 15.1 8×7×2 ≈2 21.81
16
m=8 2.23 3.79 9×8×2 ≈2 22.17
16
m=9 2.26 1.46 11×9×2 ≈2 22.63
16
m=10 2.22 1.11 13×10×2 ≈2 23.02
表 4 表明:随着显著度 C 的增加,正确密钥与错误密钥相比越来越显著,但错误密钥整体个数也会相应有所
增长,数据复杂度也随之增大.
Table 4 Relationship among saliency C, key amount, and complexity when m=7
表 4 固定 m=8,分析显著度 C、密钥量以及复杂度之间的关系
正确密钥量/个 错误密钥量/个 数据复杂度
16
C=2 2.23 3.79 9×8×2 ≈2 22.17
16
C=3 3.54 5.62 14×8×2 ≈2 22.81
16
C=4 5.78 9.92 23×8×2 ≈2 23.52
以上两个表格中的实验结果,验证了通过控制组数 m 与显著度 C,概率积分分析方法可唯一恢复正确密钥.
2.5 复杂度分析
实际攻击时可根据表 5 从上到下(利用的平衡位置由多到少排序)对密钥字进行猜测,即攻击共需进行 10
(9)
轮实验.表 5 中:RK 对应列粗体标注表示此密钥字经过前几轮猜测已经唯一确定;第 6 列给出了当使用 m 组明
(8)
文进行攻击时,各次实验中除正确密钥外候选密钥量.经过 10 轮实验,可将表 5 中涉及的 RK 中 10 个密钥字和
(9)
RK 中 13 个密钥字共 92 比特密钥信息唯一确定.由于经过加密的明密对在 10 轮实验中可重复使用,故攻击的
16
16
20
数据复杂度选取最大组数,为 11×41×2 ≈2 42.17 .以表 5 中第 1 轮实验为例,其所需的时间复杂度为 9×8×2 ×2 ≈