六轮DES截断差分攻击算法的改进与实现

引用本文

刘伟, 何永忠, 赵佳, 黎琳. 六轮DES截断差分攻击算法的改进与实现[J]. 北京交通大学学报, 2017,41(2): 28-35.
LIU Wei, HE Yongzhong, ZHAO Jia, LI Lin. Rapid realization of truncated differential attack on 6-round DES[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 2017,41(2): 28-35.
Doi:10.11860/j.issn.1673-0291.2017.02.005 复制到剪切板

Permissions

六轮DES截断差分攻击算法的改进与实现

刘伟, 何永忠, 赵佳, 黎琳

北京交通大学计算机与信息技术学院,北京 100044

第一作者:刘伟(1991—),女,河北唐山人,硕士.研究方向为信息安全.email:14120405@bjtu.edu.cn.

收稿日期: 2016-03-02

基金: 国家自然科学基金青年科学基金(61502030,61402035); 中央高校基本科研业务费专项基金(2016JBM020)

摘要

对分组密码进行截断差分攻击时,部分S盒会产生很多组子密码候选值,导致暴力攻击剩余密钥位时消耗大量时间.本文详细分析了截断差分算法中出现多组密钥候选值的原因,并分析了其出现的概率.提出两种改进截断差分攻击方案,减少候选子密码的数量并提高了攻击效率.第1种方法基于各轮S盒子密钥的非独立性,利用轮密钥在初始密钥中的重复位得到最终的候选值,最终筛选出只有一组候选值的概率达到40%左右.第2种方法将计算得到的8个S盒的所有6比特候选子密钥进行计数,选取出现频率最高的密钥,最终使48比特的候选密码个数缩减为一个.通过对六轮DES密码算法攻击的实验数据分析得知:第2种方法能够恢复出唯一的48比特子密码.

关键词: 差分分析; 数据加密标准; 截断差分; S盒; 分组密码

中图分类号:TP393.4 文献标志码:A 文章编号:1673-0291(2017)02-0028-08

Rapid realization of truncated differential attack on 6-round DES

LIU Wei, HE Yongzhong, ZHAO Jia, LI Lin

School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044,China

Fund:National Natural Science Foundation of China(61502030 61402035); Fundamental Research Funds for the Central Universities(2016JBM020)

Abstract

In the process of the truncated differential attack to block cipher, some substitution-boxes(S-boxes) will have a great deal of cipher candidate values, which will use a lot of time when the remaining key is attacked by violence. This paper mainly analyzes the reasons and the related probability of the emergence of multi sets of recommended values, and then puts forward two improvement schemes to reduce the number of the candidate key and improve the efficiency of the attack. The first method uses the incomplete dependence among round keys, and makes full use of the identical key that is in the first and in the final round. But the probability of one set of candidate value is about 40%. The second method uses the whole 6 bits candidate key in 8 S-boxes, and obtains the final key by counting the numbers of values. Using this method can reduce the number of 48 bits candidate to 1 with the probability close to one. Through the 6-round DES attack experimental results, the second method can recover the initial key with the probability close to one.

Keyword: differential cryptanalysis; data encryption standard; truncated differential; S-boxes; block cipher

文章图片

数据加密标准(Data Encryption Standard, DES)由美国国家标准局于1977年颁布, 具有加解密速度快、易于标准化等特点^[1].DES是典型分组密码算法之一, 早期对分组密码的研究基本都是围绕DES进行.到了20世纪90年代, 对DES类密码的分析研究更加深入^[2], 并取得了丰硕的研究成果.具有重大意义的成果之一便是差分密码分析(Differential Cryptanalysis)^[3]和线性密码分析(Linear Cryptanalysis)^[4]的提出, 这两种分析方法也可用于当前的迭代密码.同时, 人们也在差分密码分析和线性密码分析的基础上, 提出了很多其他的分析方法.如对差分密码分析推广的高阶差分密码分析、不可能差分密码分析和矩阵分析等^[5]; 而非线性密码分析、多重线性密码分析和差分-线性密码分析等都是线性密码分析的推广和扩充.

差分密码分析和线性密码分析被认为是迄今已知攻击迭代密码最有效的方法之一^[6].线性密码分析方法与差分密码分析方法的结合也被认为是一种非常有效的方案^{[7, 8]}.差分密码分析在1990年的CRYpto会议上被发表^{[9, 10]}, 它由文献[10]针对DES算法提出, 本质上属于选择明文攻击.其分析过程如下:分析者寻找具有某些特定差分的明文, 同时获得相应的密文对, 比较这些带有某种特性的明文对和密文对, 计算密钥的概率值, 取概率最高的密钥作为最可能的加密密钥^{[11, 12]}.

但是差分攻击方法并不是对所有分组密码都有用, 因为对于某些分组密码, 几乎不可能找到高概率的差分特征^[13].差分密码分析也会受到分组密码轮数的影响.如当轮数为17时, 差分密码分析需要花费的时间与穷尽密钥搜索相同.另一方面, 差分密码分析需要大量具有某些特定差分的明文对及其相应的密文对作为支持.

针对这些缺点, 1995年, 文献[14]提出了针对DES的截断差分密码分析方法.截断差分密码分析只需要知道部分比特上的差分特征, 相对于传统的差分特征, 它可以完成更多轮数的攻击, 或是以更低的复杂度攻击相同的轮数.因此截断差分的思想在分组密码中得到了广泛的应用, 如文献[15]使用截断差分的方法成功的攻击了13轮的3D分组密码.文献[16]应用了截断差分的思想攻击了5轮Salsa算法.文献[17]使用截断差分攻击方法成功的攻击了12轮Camellia-128算法, 恢复了所有的密钥.文献[18]则将截断差分的思想与线性密码分析方法结合, 分析了对9轮和11轮DES算法的攻击过程.

尽管截断差分攻击算法相对于传统的差分攻击算法具有一定的优点, 但是其密钥恢复算法存在缺陷.比如, 截断差分攻击在最终使用穷举方法前得到的45比特密钥候选值有很多组.所有的这些45比特密钥候选值剩余的11比特使用暴力攻击方法, 这将浪费很多资源.

本文作者针对上述问题, 提出了两种改进方案.实验结果表明:这两种方案都能减少候选密钥的个数, 特别是第2种方法能够以很大的概率获得唯一的候选密钥, 大大提高了密钥攻击时的效率.

1 预备知识

1.1 记号

本文所用记号及其含义分别如下:“ |” 代表4 比特的级联; “ ||” 代表32 比特的级联; $K_{i, j} 代表第 i 轮中第 j$ 个S盒的6比特输入值; $P$ 是DES算法中轮函数的最后置换函数.

1.2 数据加密标准DES

DES加密算法是一种对称加密算法, 它使用56比特的密钥, 明文和密文的长度均为64比特, 加密算法和解密算法基本相同.算法中的S盒的结构对算法的安全性有较大的影响.

1.3 六轮DES截断差分密码分析算法

截断差分密码分析是差分密码分析的推广, 它只要求知道某些比特的差分, 甚至某些情况下, 仅仅知道1比特的差分就能够成功的攻击一个分组密码或其低轮变形.

六轮DES截断差分攻击方法基于一个四轮的截断差分特征, 如图1所示.由于DES的初始置换和末尾置换函数均为公开函数, 不影响攻击方法分析, 本文作者在分析过程中将忽略初始和末尾置换, 以及DES加密最后一轮得到密文也不再做交换.

	Figure Option View Download New Window
	图1 DES的四轮差分特征Fig.1 Differential characteristics of 4-round DES

在DES加密算法中, 由于扩展函数 $E 和置换 P$ 的影响, 一个S盒的4 比特输出最多只能够影响下一轮6个S盒的输入.经过一些简单的计算, 就可以得到上一轮S盒输出与下一轮S盒输入的比特关系, 如表1所示.例如第1个S盒的输出不会影响下一轮中第1个和第7个S盒的输入.本文实现的截断差分密码分析方法正是利用了DES的这个特性.

表1 S盒输出的比特流向 Tab. 1 Flow of the S-box output bits

用R表示扩展函数E的32 比特输入, K表示扩展函数E的轮密钥, 它的长度为48比特.表2为DES算法的比特选择表.

表2 扩展函数E Tab. 2 Diffusion function

E

扩展函数 $E$
32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

表2 扩展函数E Tab. 2 Diffusion function

E

根据表2可知, 扩展函数 $E$ 的作用是将32比特的输入 $R$ 扩充为48比特.而这48比特根据DES算法的设计, 将分为长度为6的8组二进制串, 这8组数据将分别与轮密钥进行异或操作后, 作为8个S盒的输入.因此在轮密钥不发生变化的前提下, 如果只改变 $R$ 的第2比特和第3比特(从0开始计数), 则只影响第1个S盒的输出, 而不会影响其他7个S盒的输出.

同理, 只改变 $R$ 的第6比特和第7比特, 只会影响第2个S盒的输出.以此类推, 可以得到, 只改变表2某一行的第3列和第4列比特, 对应的只影响该行所代表的S盒输出.图1是攻击中所用到的四轮截断差分特征, 它所用的差分为0x20000000, 即改变了第2个比特.仅用1个差分只能得到3个S盒的子密钥, 因此还需要其他的差分特征.如仅改变第3个比特得到的差分0x40000000, 同时改变第2比特和第3比特得到的差分0x60000000, 具体实现过程中从这3个中任意选择两个即可.六轮DES截断差分密码分析的步骤如下: 1)由表1可知, 第1个S盒的输出不影响下一轮中第1个和第7个S盒的输入, 基于该原理, 构造概率值为1的四轮DES的截断差分, 如图1所示.2)根据所选用的四轮DES截断差分特征, 构造相应的明文对, 同时遍历DES中 $K_{1, 1}$ 的每个候选值, 筛选出满足四轮截断差分特征的明文对.3)利用所选用的4组明文对, 筛选出第6轮相关S盒的子密钥, 筛选方法为只保留所有明文对均建议的密钥.4)利用其他的截断差分特征, 恢复出其余的比特密钥.

2 截断差分攻击算法的实现与分析

截断差分密码分析过程中, 对于每一个 $K_{1, 1}$ , 均生成4个明文正确对, 利用这4个明文正确对来筛选 $K_{6, 1}$ 和 $K_{6, 7}$ .同理, 再对 $K_{1, 2}$ 的每一个候选值生成4个明文对来筛选 $K_{6, 2} 和 K_{6, 6} 使用 K_{1, 5} 得到 K_{6, 5} 和 K_{6, 8}$ .这样可以得到54比特密钥, 因为部分密钥有重叠部分, 故实际为45比特.剩余11比特使用暴力攻击.

对每一个K_{1, 1} 的候选值, 都有相应的4个正确对与之对应, 如果每一个K_{1, 1}与相对应的4个正确对是一一映射的关系, 文献[14]实现攻击的过程将会更加完美, 然而这种关系并不是一一映射关系, 而是多对多的关系.这种关系的存在使得在密钥恢复的过程中具有多种组合, 而且存在这种多对多的关系的密钥和明文对所占百分比为47%.其具体关系如表3所示.由于K_{1, 1} 代表的是二进制000000到111111的所有可能取到的值, 可能情况较多且直接表示较为麻烦, 因此本文为了方便, 将二进制K_{1, 1} 的所有取值使用十进制来表示.例如表中K_{1, 1}等于10, 则实际代表的是6位二进制001010.

表3中, 数值0~63代表的就是K_{1, 1} 可能取到的全部十进制值, 与该数值所对应的下一行数据代表的是与K_{1, 1} 对应的4个正确明文对的下标值. 第1个明文对是P_i 和P_{1_j}组成的正确对, 第2个明文对是P_{2_j}和P_{3_j}组成的正确对, 这两个明文对形成的差分为0x20000000.第3个则为P_i 和P_{2_j}组成的正确对, 第4个为P_{1_j}和P_{3_j}组成的正确对, 这两个形成的差分为0x40000000, 其中 $i 和 j$ 的取值范围是0~3.举例来说, 当K_{1, 1} 的值为0时, 4个明文正确对依次为P₃ 与P_{1, 0} 、P_{2_2}与P_{3_1}、P₀ 与P _{2_3}、P_{1_1}与P_{3_2}, 即这4组明文对具有图1所示的四轮截断差分特征, 可以用来恢复当K_{1, 1}为0时第6轮的子密钥 $K_{6, 1} 和 K_{6, 7}$ .但是通过对表3的简单分析, 可以发现, 有多个密钥对应着相同的4个正确对.如当K_{1, 1} 为35、39、43、47时, 对应的4个正确对均为P₂ $与 P_{1_3} 、 P_{2_3} 与 P_{3_2} 、 P_{1} 与 P_{2_1} 、 P_{1_1} 与 P_{3_1}$ .换句话说, 假设当正确密钥为43时, 实验在恢复的过程中会得到35、39、43、47这4个密钥.但是, 对于错误组合, 仍需要对其余的11比特做暴力破解, 这就使得很多工作都是无效努力, 占用了程序的大部分时间, 例如有4种组合, 那么其中的3组均为错误组合, 对于这3种错误组合, 也是需要对其余的11比特做暴力破解, 也就是, 在这段程序中, 有3/4的工作是白费的.

表3 密钥与正确对的关系 Tab. 3 Relationship of key and a set of plaintexts

分析表3后可得以下结论, 在 $K_{1, 1}$ 的64个候选值密钥中, 能够与4个明文对具有一对一关系的有34个, 即恢复过程中能够唯一确定6比特轮密钥.具有多对多关系的有30个, 恢复过程成功概率为50%的有18个, 概率为25%的密钥值为12个.

本文的第1种改进方案选择了第1轮中第1个、第2个、第5个S盒, 并相应得到第6轮中第1个和第7个、第2个和第6个、第5个和第8个S盒的6比特子密钥.这样可以得到54比特的密钥, 但是因为有些轮密钥在初始密钥中所占的位是相同的, 所以最终得到的是45比特密钥.

同时, 充分利用这些恢复的密钥中有重复位这一特点, 如果初始密钥中有一位在某一轮密钥中不能确定时, 则因为另外一个轮密钥, 很有可能使得该位变得唯一而确定.如 $K_{1, 1}$ 在初始密钥中所占的位分别为15、18、12、25、2、6, $K_{6, 1}$ 在初始密钥中所占的位分别为24、27、21、6、11、15, 第6轮 $K_{6, 2}$ 所占位为13、10、25、16、3、20.当在密钥恢复的过程中, 第1轮 $K_{1, 1}$ 有4组候选值, 二进制表示分别为100011 、100111 、101011 、101111.即初始密钥中的第12位、第25位不能确定.但是 $K_{6, 2}$ 只有一组候选值110100, 则可以确定初始密钥中的第25位为0.从而将候选值的个数折半.每个S盒出现4组候选值的概率为12/64, 但是根据概率论相关知识可知, 多个S盒同时出现这种情况的概率比较低, 这就使得该方法能够达到最初的目的.即45比特的密钥候选值个数降低很多, 比例也随之降低.但只有一个45 比特密钥建议值的概率仍然没有超过50%.

为了进一步提高此阶段只有一个建议值的比例, 本文作者第2种改进方法对恢复的第1轮多个子密钥建议处理措施为直接抛弃, 具体措施如下:使用第1轮中第1个S盒, 可以获得第6轮第1个和第7个S盒子密钥, 以此类推, 结合表1, 如果第1轮的8个S盒均被使用, 恰好能够得到完整的两组第6轮8个S盒的48比特密钥, 通过对两组48比特密钥的筛选, 能够得到唯一确定的48比特子密钥.

每组轮密钥中, 每个S盒的6比特密钥可能具有多个值.解决方式是构建8个具有64个计数器的计数矩阵.将长度为6的子密钥视为一个0~63的整数表示, 用64个值对应位置0, 1, 2, 3, …, 63.也就是说, 位置标号代表着长度为6的子密钥.

8个计数矩阵代表8个S盒64种子密钥的候选值.将获得的两组子密钥按照对应标号对相应的计数矩阵做相应的操作, 这样, 每一个矩阵中都有相同的值2, 这些计数器的位置确定了8个S盒的子密钥, 最终获得48比特的第6轮子密钥.

3 改进的截断差分算法

由于第1种改进方法前面叙述的较为详细, 本节将重点介绍第2种改进方法的实现过程.

3.1 构造明文

由于截断差分攻击属于一种选择明文攻击方法, 因此构造明文是重中之重.本算法构造明文的方法具体过程如下:

1)选取4个明文对, 选取的方法如下:

$P_{i} = A_{i} || P_{R} . 其中 : i = 0, 1, 2, 3; A_{i} = P (a_{i} | r_{0} | r_{1} | r_{2} | r_{3} | r_{4} | r_{5} | r_{6}); a_{i} = i (a_{i} 为长度为 4 的二进制串); 而 r_{k} (k = 0, 1, 2, 3, 4, 5, 6) 代表随机选择的 4 比特二进制串; P 表示轮函数中的置换; P_{R}$ 为随机选择的32比特二进制串.

2)选取另4个明文, 选取方法为: $P_{1, j} = B_{j} ‖ P_{R} \oplus 20000000 . 其中 : B_{j} = P (b_{j} | r_{0} | r_{1} | r_{2} | r_{3} | r_{4} | r_{5} | r_{6}); j = 0, 1, 2, 3; b_{0} = 0 x 0; b_{1} = 0 x 4; b_{2} = 0 x 8; b_{3} = 0 x c (b_{j} 为长度为 4 的二进制串) .$

根据选用的明文 $P_{i} 和 P_{1, j} 可知, 每一个 P_{i} 和每一个 P_{1, j} 可形成具有如下差分的明文对 : P$ (0x $h | 0 | 0 | 0 | 0 | 0 | 0 | 0) ‖ 20000000, h 为 1 ~ 16 的所有可能值 .$ 在8个明文中, 一定存在某一个明文对(称为正确对)满足图1所示的四轮截断差分特征.利用类似的原理, 可以得到更多的正确对.

3)同理再选4个明文 $P_{2, j} = B_{j} || P_{R} \oplus 40000000 及另外的 4 个明文 P_{3, j} = B_{j} || P_{R} \oplus 20000000 \oplus 40000000, 其中 j = 0, 1, 2, 3 . P_{2, j} 和 P_{3, j}$ 结合, 仍然会得到能够满足图1所示的截断差分特征的明文对.

同理, 将 $P_{1, j} 和 P_{2, j} 组合, 以及 P_{i} 和 P_{3, j}$ 组合, 将会得到另外两个可利用的明文对.

本文实验在实现的过程中, 32比特的 $P_{R} 全部取为 0, 即 P_{R}$ =0x00000000, 不再使用随机比特, 这种选法便于计算, 同时节省程序的运行时间, 提高程序的效率, 也能够方便人工计算中间结果, 进一步理解算法.同理, 每一个 $r_{k} (k = 0, 1, 2, 3, 4, 5, 6) 都取值为 0, 即 r_{k}$ =0x0.

3.2 攻击过程

对于 $K_{1, 1}$ 的每一个候选值, 按照以下方法筛选4个正确对.

1)计算c₀ =f(K₁, P_i_R), c₁ =f(K₁, $P_{1, j_{R}}$ ), 其中K₁的前6比特为K₁_{_}₁, 剩余42比特全部设为0. P_i_R为明文P_i的右32比特, P₁, j_R同理.

2)在P_i和P_1,_j中寻找能够使得等式c₀⊕c₁ = P_i_L⊕P_1,_j_L成立的明文对.

3)对P_2,_j和P_3,_j, P_1,_j和P_2,_j, 以及P_i和P_3,_j做同样的操作, 筛选出4个明文对.

4个正确对选出来之后, 过滤第6轮子密钥, 过滤方法如下:

1)首先获得DES第3轮函数的32比特输入差分, 记为L'₃.在本实验中, 前两组明文对所对应的差分值为0x20000000, 后两组明文对的差分值为0x40000000.

2)将明密文对记为(L₀R₀, L₆R₆)和( $L_{0}^{*} R_{0}^{*}$ , $L_{6}^{*} R_{6}^{*}$ ), L₀R₀和 $L_{0}^{*} R_{0}^{*}$ 为明文对, L₆R₆和 $L_{6}^{*} R_{6}^{*}$ 为密文对.则R₆的计算公式如下

$\begin{array}{l} R_{6} = L_{5} \oplus f (R_{5}, K_{6}) = R_{4} \oplus f (R_{5}, K_{6}) = \\ L_{3} \oplus f (R_{3}, K_{4}) \oplus f (R_{5}, K_{6}) (1) \end{array}$

同样的, $R_{6}^{*}$ 计算公式为

$\begin{array}{l} R_{6}^{*} = L_{5}^{*} \oplus f (R_{5}^{*}, K_{6}) = R_{4}^{*} \oplus f (R_{5}^{*}, K_{6}) = \\ L_{3}^{*} \oplus f (R_{3}^{*}, K_{4}) \oplus f (R_{5}^{*}, K_{6}) (2) \end{array}$

从而有

$\begin{array}{l} R'_{6} = L'_{3} \oplus f (R_{3}, K_{4}) \oplus f (R_{3}^{*}, K_{4}) \oplus \\ f (R_{5}, K_{6}) \oplus f (R_{5}^{*}, K_{6}) (3) \end{array}$

式(3)中, R'₆为R₆和 $R_{6}^{*}$ 的差分值, 其值已知.L'₃在步骤1)中已经获得.通过图1可知, 第4轮轮函数的输出中有8个比特为0, 而这8位正是第6轮第1个和第7个S盒的输出差分.在仅考虑这两个S盒的条件下, 通过式(3)可得

$\begin{array}{l} C'_{1} C'_{2} C'_{3} C'_{4} C'_{5} C'_{6} C'_{7} C'_{8} = \\ P^{- 1} (R'_{6} \oplus 0 x 40000000) (4) \end{array}$

式中, 每个C_i是长度为4的比特串.那么C₁和C₇分别是第6轮中S₁和S₇的输出异或.

3)对于每一个K_{6, 1}和K_{6, 7}的候选值, 按照下式进行计算

$\begin{array}{l} C'_{1} C'_{2} C'_{3} C'_{4} C'_{5} C'_{6} C'_{7} C'_{8} = \\ P^{- 1} (f (R_{5}, K_{6})) (5) \end{array}$

通过上述计算可以得到S₁和S₇的另一个输出异或.当两个异或相等时, 记录K_{6, 1}和K_{6, 7}的候选值, 即为该组正确对的候选密钥.最终结果选择4组明文对均建议的候选密钥.

经过上述筛选, 可以获得 $K_{6, 1} 和 K_{6, 7}$ , 可能具有多个建议值.

接下来使用 $K_{1, 2}$ 攻击 $K_{6, 2}$ 和 $K_{6, 6}$ .使用类似于图1的四轮截断差分特征, 差分在0x20000000, 0x40000000与0x60000000中3个任意选择2个, 可以这样选择的原因在上面已经描述过, 这里不再叙述.

该过程构造的明文为

P_i =A_i || P_R其中i=0, 1, 2, 3, A_i = P(a_i| r₀ | r₁| r₂ |r₃ | r₄ | r₅ | r₆), P_R和r_k仍全部为0.

P_1,_j= B_j|| P_R⊕0x02000000, P_2,_j= B_j|| P_R⊕0x04000000, P_3,_j = B_j|| P_R⊕0x06000000, 其中B_j =P( r₀ |b_j| r₁| r₂|r₃| r₄ | r₅ | r₆), j =0, 1, 2, 3, b₀ =0x0, b₁ =0x4, b₂ =0x8, b₃ =0xc.

对这十六个明文根据上述攻击第1个和第7个S盒子密钥做同样的操作, 即根据第2个S盒的6比特子密钥筛选出需要的4组正确对, 使用这些正确对按照筛选第6轮子密钥的算法获得 $K_{6, 2}$ 和 $K_{6, 6} .$

后面使用第3、4、5、6、7、8个第1轮S盒过程均与第2轮相同.明文与差分的选择过程较为方便, 只需要将 $L_{0} 按 4 比特为一组, a_{i} 和 b_{j}, 4 个比特循环赋值给 L_{0} 的每一组即可 .$

上述所有过程均实现完成之后, 则可以获得两组第6轮8个S盒的子密钥.构造8个具有64个计数器的计数矩阵.对两组内每个建议的S盒子密钥进行计数.例如第1组第1个S盒子密钥为010100和011000, 在 $J_{1}$ 的计数矩阵中的位置20和24处增加1.当8个计数矩阵均完成后, 找到8个计数矩阵中数值为2的位置, 并将这些位置所在的整数转换为相应的二进制, 即可获得最终48比特密钥值.其余8个比特使用暴力破解得到.

4 改进算法评估与分析

通过大量实验测试数据统计, 可得到以下结果:使用第1种方法时, 只有一个密钥候选值的比率在35%~40%左右.有两组候选值比例在45%左右.第2种方法能够使得只有一组密钥候选值的概率为1.

两种方法分别举例说明如下:第1种方法:当被攻击的密钥为0x1d1cf6932d3ce51c时, 以 $攻击 K_{1, 1}, K_{6, 1}$ 和 $K_{6, 7}$ 为例.明文与密文分别如表4所示.

表4 攻击所用明文对与密文对 Tab. 4 Plaintexts and ciphertexts in the attack

根据表4中的4对明文及其相应的密文攻击得到的第1轮第1个S盒子密钥 $K_{1, 1}$ 的候选值与第6轮第1个与第7个S盒子密钥 $K_{6, 1} 与 K_{6, 7}$ 的候选值分别如表5所示.

表5 攻击获得的K_{1, 1}、K_{6, 1}与K_{6, 7}候选值 Tab. 6

K_{1, 1} 、 K_{6, 1}

and

K_{6, 7}

suggested by attack

K_i_,_j	可能的候选值(二进制)
K_{1, 1}	0 1 0 0 1 1
	0 1 0 1 1 1
	0 1 1 0 1 1
	0 1 1 1 1 1
K_{6, 1}	0 0 0 1 1 1
K_{6, 1}	0 1 0 1 0 0
K_{6, 7}	1 0 0 1 1 0

表5 攻击获得的K_{1, 1}、K_{6, 1}与K_{6, 7}候选值 Tab. 6

K_{1, 1} 、 K_{6, 1}

and

K_{6, 7}

suggested by attack

由表5的数据可知, K_{1, 1}有两位不能确定, K_{6, 1} 有两组候选值, K_{6, 7}有一组候选值.利用同样的方法, 可以得到其他所需要的子密钥候选值, 所有的候选值如表6所示.

表6 攻击得到的所有密钥候选值 Tab. 6 All keys value suggested by attack

由表6可知, 如果不做任何处理, 最终得到的45比特密钥的候选值将有4× 4× 4× 2=128种.如果利用轮密钥在初始密钥中的重复位, 可以去掉很多候选值, 如表7所示.

表7 S盒子密钥在初始密钥中的位置 Tab. 7 Sub-keys position in the initial key

可以看到, 表7中有很多重复位, 当K_{1, 1} 不能确定初始密钥的第25位时, 当K_{6, 1}有两组候选值时, 由于K_{1, 1} 能够确定初始密钥的第15位, 据此位就可确 $定 K_{6, 1}$ 两组候选值中正确的那一个.根据同样的道理, 可以得到最终的几组密钥候选值, 见表8.

表8 最终S盒的密钥候选值 Tab.8 Final keys of K_i_,_j

到目前为止, 只有初始密钥中的第12位、第7位、第32位不能确定, 对这3位使用穷举方法将得到8组45比特子密钥候选值, 达到了降低候选值个数的目的.

第2种方法使用了8个S盒, 假设初始密钥为0x747b5237ba4e2afd, 仍以攻击 $K_{1, 1}, K_{6, 1} 和 K_{6, 7}$ 为例.明文与密文分别如表9所示.

表9 明文对和相应的密文对 Tab.9 Plaintexts and the corresponding ciphertexts

利用表9中的4对明文对与相应的密文对, 可以得到表10 中的K_{1, 1}、K_{6, 1}和K_{6, 7}密钥候选值.其中K_{1, 1}有4组候选值, K_{6, 1}和K_{6, 7}分别各有一组候选值.

表10 K_{1, 1}、K_{6, 1}和K_{6, 7}密钥候选值 Tab.10 K_{1, 1}、K_{6, 1} and K_{6, 7}candidate key

同理, 按上述方式, 依次用其余7个S盒进行攻击, 这里不再列出相应明文对及密文对, 可得第1轮其他7个S盒子密钥的候选值及两组第6轮8个S盒子密钥候选值, 分别如表11和表12所示.

表11 第1轮8个S盒的密钥候选值 Tab.11 8-S-boxes candidate key in first 1 round

表12 两组第6轮8个S盒的密钥候选值 Tab.12 Two groups of 8-S-boxes in 6 round candidate key

方法2中抛弃了第1轮8个S盒得到的相应候选值, 只保留两组第6轮8个S盒的子密钥, 将6比特子密钥的二进制形式转换为十进制数, 填入计数器中相应的位置.

通过8个计数器中数据可知, 每一个计数器中都有一个唯一的位置是2, 代表该位置的十进制数正是相应S盒6比特二进制子密钥转换得到, 通过8个计数器, 可以得到唯一的48比特子密钥候选值.

5 结语

本文首先对截断差分密码攻击的整个过程做了详尽的介绍, 并分析了截断差分密码攻击过程中密钥恢复时会产生多组候选值的原因.基于上述不足, 本文作者提供了以下两种解决方案:

1)由于每一轮的轮密钥都是经过初始密钥变换得来的, 因此, 每轮的轮密钥经过相应的逆变换就可以得到初始密钥.这就导致了不同轮之间的轮密钥中某些位是由初始密钥中的同一位变换而来, 基于此性质, 本文提出了第1种改进方法.该方法能够实现只有一组密钥候选值的概率在35%~40%左右, 而有两组的概率为45%左右.

2)第2种改进方案依次使用了8个S盒进行攻击, 最终能够得到两组第6轮轮密钥候选值.由于这两组候选值中均包含正确的密钥值, 因此通过对这些候选值进行计数, 选出两组均建议的候选值即可.实验结果表明, 该方法的效果优于第1种, 它能够实现只有一组密钥候选值的概率接近为1.

The authors have declared that no competing interests exist.

参考文献

文献列表

[1]	吴杨, 王韬, 邢萌. 基于密文随机性度量值分布特征的分组密码算法识别方案[J]. 通信学报, 2015, 36(4): 146-155. WU Yang, WANG Tao, XING Meng. Block ciphers identification scheme based on the distribution character of rand omness test values of ciphertext[J]. Journal on Communication, 2015, 36(4): 146-155. (in Chinese) [本文引用:1]
[2]	吴杨, 王韬, 李进东. 分组密码算法密文的统计检测新方法研究[J]. 军械工程学院学报, 2015, 27(3): 59-64. WU Yang, WANG Tao, LI Jindong. Research on new statistical and testing method for ciphertexts of block cipher[J]. Journal of Ordnance Engineering College, 2015, 27(3): 59-64. (in Chinese) [本文引用:1]
[3]	BIHAM E, SHAMIR A. Differential cryptanalysis of the data encryption stand ard[M]. Springer Verlag, 1993. [本文引用:1]
[4]	MATSUI M. Linear cryptoanalysis method for DES ciper[C]. Advances in Cryptology-EUROCRYPT’93, 1994, 765: 386-397. [本文引用:1]
[5]	MATSUI M. The first experimental cryptanalysis of the data encryption stand ard[C]. Advances in Cryptology-Crypto’94, 1994, 839: 1-11. [本文引用:1]
[6]	多磊. 分组密码的设计与分析[D]. 北京: 国防科技大学, 2001. DUO Lei. Analysis and design of block ciphers[D]. Bei-jing: National University of Defense Technology, 2001. (in Chinese) [本文引用:1]
[7]	BLONDENU C, NYBERG K. New Links between differential and linear cryptanalysis[J]. LNCS, 2013, 7881: 388-404. [本文引用:1]
[8]	LANGFORD S K, HELLMAN M E. Differential-linear cryptanalysis[C]. Advances in Cryptology-Crypto’94 Proc, 1994: 17-26. [本文引用:1]
[9]	冯登国, 吴文玲. 分组密码的设计与分析[M]. 北京: 清华大学出版社, 2000 FENG Dengguo, WU Wenling. Analysis and design of block cipher[M]. Beijing: Tsinghua University Press, 2000. (in Chinese) [本文引用:1]
[10]	BIHAM E, SHAMIR A. Differential cryptanalysis of the full 16-round DES[C]. International Cryptology Conference on Advances in Cryptology, 1992, 740 : 487-496. [本文引用:2]
[11]	BIHAM E, SHAMIR A. Differential cryptanalysis of DES-like cryptosystem[J]. Journal of Cryptology, 1991, 4(1): 3-72. [本文引用:1]
[12]	CHAUM D, EVERTSE J H. Cryptanalysis of DES with a reduced number of rounds[C]. Sequences of Linear Factors in Block Ciphers, Advance in Cryptology, Proceeding of Crypto’85, 1985: 192-211. [本文引用:1]
[13]	SHAMIR A. On the security of DES[C]. Advance in Cryptology-Crypto’85, Lecture Notes in Computer Science, 1985, 218: 280-281. [本文引用:1]
[14]	KNUDSON L R. Truncated and higher order differential[J]. LNCS, 1995: 196-211. [本文引用:2]
[15]	KOYAMA T, WANG L, SASAKI Y, et al. New truncated differential cryptanalysis on 3D block ciper[J]. LNCS, 2012, 7232: 109-125. [本文引用:1]
[16]	关杰, 张中亚. 5轮Salsa20的代数-截断差分攻击[J]. 软件学报, 2013, 24(5): 1111-1126. GUAN Jie, ZHANG Zongya. Algebraic truncated differential cryptanalysis of 5-round Salsa20[J]. Journal of Software, 2013, 24(5): 1111-1126. (in Chinese) [本文引用:1]
[17]	李艳俊, 张伟, 欧海文. Camellia-128的截断差分攻击改进[J]. 计算机应用研究, 2013, 30(7): 2129-2131. LI Yanjun, ZHANG Wei, OU Haiwen. Improved truncated differential analysis on Camellia-128[J]. Application Research of Computers, 2013, 30(7): 2129-2131. (in Chinese) [本文引用:1]
[18]	贺也平, 吴文玲, 卿斯汉. 截断差分-线性密码分析[J]. 软件学报, 2000, 11(10): 1294-1298. HE Yeping, WU Wenling, QING Sihan. Truncated differential-linear cryptanalysis[J]. Journal of Software, 2000, 11(10): 1294-1298. (in Chinese) [本文引用:1]

2015

0.0

吴杨, 王韬, 邢萌. 基于密文随机性度量值分布特征的分组密码算法识别方案[J]. 通信学报, 2015, 36(4): 146-155.

Yang

, WANG

Tao

, XING

Meng

. Block ciphers identification scheme based on the distribution character of rand omness test values of ciphertext[J]. Journal on Communication, 2015, 36(4): 146-155. (in Chinese)

... 数据加密标准(Data Encryption Standard,DES)由美国国家标准局于1977年颁布,具有加解密速度快、易于标准化等特点^[1] ...

2015

0.0

吴杨, 王韬, 李进东. 分组密码算法密文的统计检测新方法研究[J]. 军械工程学院学报, 2015, 27(3): 59-64.

Yang

, WANG

Tao

, LI

Jindong

. Research on new statistical and testing method for ciphertexts of block cipher[J]. Journal of Ordnance Engineering College, 2015, 27(3): 59-64. (in Chinese)

... 到了20世纪90年代,对DES类密码的分析研究更加深入^[2],并取得了丰硕的研究成果 ...

1993

0.0

... 具有重大意义的成果之一便是差分密码分析(Differential Cryptanalysis)^[3]和线性密码分析(Linear Cryptanalysis)^[4]的提出,这两种分析方法也可用于当前的迭代密码 ...

1994

0.0

1994

0.0

... 如对差分密码分析推广的高阶差分密码分析、不可能差分密码分析和矩阵分析等^[5] ...

2001

0.0

... 差分密码分析和线性密码分析被认为是迄今已知攻击迭代密码最有效的方法之一^[6] ...

2013

0.0

... 线性密码分析方法与差分密码分析方法的结合也被认为是一种非常有效的方案^[7,8] ...

1994

0.0

... 线性密码分析方法与差分密码分析方法的结合也被认为是一种非常有效的方案^[7,8] ...

2000

0.0

... 差分密码分析在1990年的CRYpto会议上被发表^[9,10],它由文献[10]针对DES算法提出,本质上属于选择明文攻击 ...

1992

0.0

... 差分密码分析在1990年的CRYpto会议上被发表^[9,10],它由文献[10]针对DES算法提出,本质上属于选择明文攻击 ...

1991

0.0

... 其分析过程如下:分析者寻找具有某些特定差分的明文,同时获得相应的密文对,比较这些带有某种特性的明文对和密文对,计算密钥的概率值,取概率最高的密钥作为最可能的加密密钥^[11,12] ...

1985

0.0

1985

0.0

... 但是差分攻击方法并不是对所有分组密码都有用,因为对于某些分组密码,几乎不可能找到高概率的差分特征^[13] ...

1995

0.0

... 针对这些缺点,1995年,文献[14]提出了针对DES的截断差分密码分析方法 ...

... 对每一个K_1,1 的候选值,都有相应的4个正确对与之对应,如果每一个K_1,1与相对应的4个正确对是一一映射的关系,文献[14]实现攻击的过程将会更加完美,然而这种关系并不是一一映射关系,而是多对多的关系 ...

2012

0.0

... 因此截断差分的思想在分组密码中得到了广泛的应用,如文献[15]使用截断差分的方法成功的攻击了13轮的3D分组密码 ...

2013

0.0

关杰, 张中亚. 5轮Salsa20的代数-截断差分攻击[J]. 软件学报, 2013, 24(5): 1111-1126.

GUAN

Jie

, ZHANG

Zongya

. Algebraic truncated differential cryptanalysis of 5-round Salsa20[J]. Journal of Software, 2013, 24(5): 1111-1126. (in Chinese)

摘　要： Salsa20 流密码算法是Estream 最终胜出的7 个算法之一.结合非线性方程的求解及Salsa20 的两个3 轮高概率差分传递链,对5 轮Salsa20 算法进行了代数-截断差分攻击.计算复杂度不大于O（2105）,数据复杂度为O（211）,存储复杂度为O（211）,成功率为97.72%.到目前为止,该攻击结果是对5 轮Salsa20 算法攻击最好的结果.

... 文献[16]应用了截断差分的思想攻击了5轮Salsa算法 ...

2013

0.0

... 文献[17]使用截断差分攻击方法成功的攻击了12轮Camellia-128算法,恢复了所有的密钥 ...

2000

0.0

贺也平, 吴文玲, 卿斯汉. 截断差分-线性密码分析[J]. 软件学报, 2000, 11(10): 1294-1298.

Yeping

, WU

Wenling

, QING

Sihan

. Truncated differential-linear cryptanalysis[J]. Journal of Software, 2000, 11(10): 1294-1298. (in Chinese)

对差分-线性密码分析方法进行推广,提出了截断差分-线性密码分析方法.对9-轮和11- 轮DES(data encryption standard)密码算法的分析表明,该方法具有更加方便、灵活,适用范围更广的特点.同时,利用截断差分-线性密码分析方法得出,在类似DES结构的算法中,S -盒的摆放顺序对密码的强度有较大的影响.由此,截断差分-线性分析方法给出了优化S- 盒排序的一种参考判别准则.

... 文献[18]则将截断差分的思想与线性密码分析方法结合,分析了对9轮和11轮DES算法的攻击过程 ...