《差分密码分析和线性密码分析原理.ppt》由会员分享，可在线阅读，更多相关《差分密码分析和线性密码分析原理.ppt（58页珍藏版）》请在金锄头文库上搜索。
1、,差分密码分析和线性密码分析原理,01,02,差分密码分析,线性密码分析,差分密码分析是迄今为止已知的攻击迭代分组密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值来影响来恢复某些密钥比特 当密码分析人员可以进行选择明文分析时，差分密码分析十分有效。 已知明文的差分密码分析也是可行的，但是要求已知明密文的量很大,差分密码分析简介,设计DES的IBM小组知道了差分分析,1974,1991,1990,Biham和Shamir对多种加密算法和Hash函数进行差分密码分析攻击，结果发表在BIHA93中,差分密码分析公开发表 最早研究是Murphy分析分组密码FEAL【MURP90】
2、,差分密码分析的历史,6,符号定义,P 表示明文，T 表示密文 (P, P)表示明文对，其异或后得到特定的值：P,使得 P = P P (T, T) 表示密文对，其异或后得到特定的值T，使得 T = T T 带撇的值总是表示差分，P ,T, a, A。例如，a= a a,7,差分密码分析_DES,DES 的设计要求之一是确保尽可能的分布均匀 例如，明文或密钥的1比特变化，将导致64比特的密文中大约32比特的看起来是不可预测和随机的变化,不过对于固定的密钥，DES的差分并不呈现伪随机现象,即对于固定明文P 和P 的异或P T=TT 不是均匀分布的,8,S-Box是非差分均匀的,对于输入S盒的6比
3、特的(x, x)值对，一共有多少种可能？,考虑一个S-box的差分现象：,输入值对的差分为x= x x 差分值可能有多少种？,对于其4比特输出值，y=S(x), y= S(x)，以及y=y y =S(x) S(x) 输出差分值有多少种可能？,642 = 4096,26= 64,24= 16,S-Box是非差分均匀的,输入差分f=1111,10,S1 的差分分布表, . . . . . . . . . =26-1,出现的次数,6比特的差分输入x有64个值：00-3F(16进制，10进制是0-63) 4比特的差分输出y有16个值：0-F(16进制，10进制是0-15) 可以看到：第一行除第一列外全
4、为0，因为当x= x x = 0，同样的输入出现了两次，因此其输出y=y y = 0,后面的行： 例如，当 x= 01 时, 6个可能的y中有5个值:0, 1, 2, 4, 8呈现0可能次数，就是说不出现。 A 出现的概率是12/64 9 和C 出现的概率是10/64 这就是说，S1呈现出很强的不均匀分布 这种差分不均匀性对于所有的S盒S1, S2, . . . , S8都有体现,考虑输入异或值为34时，可能的输出异或是： 其中：344有两种可能，这种输入对是成双的，即：(, )和 (, ),S1 的差分分布表,对S1构建差分表，发现当输入是13 和27 时(只看后面的6位)：,12,S1 的
5、差分分布表,12,列出S1中输入异或值为34的可能的输入值(16进制)：,13,确定密钥的原理,假设已知S1的两个输入是01和35，其异或的结果是34，经过S1之后输出异或的结果是D。查S1的差分分布表，得到输入异或为34，输出异或为D时，可能的输入：,14,确定密钥的原理,14,实际上，输入异或的结果是34，与密钥无关，这是因为：,因为 所以,这样就得到：,所以，可能的密钥就是,15,确定密钥的原理,此外，假设已知S1的两个输入是21和15，它们异或后的结果是34，输出异或后的结果是3 。查S1的差分分布表，得到输入异或为34，输出异或为3时，可能的输入： 。,16,确定密钥的原理,16,这
6、样就可以从,得到可能的密钥值,17,确定密钥的原理,17,而正确的密钥值必定同时出现在两个集合,因此可以确定密钥是在 中的一个。 要确定到底是哪一个，需要知道更多的输入输出异或对。以此类推得到此轮密钥,18,多轮DES的特征,差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到： E扩展中的异或值是线性的：,异或值与密钥是无关的：,19,2轮DES的特征差分密码分析,20,在第一轮中，输入到函数f的差分结果是 a= 60 00 00 00 经f 中的扩展变换后， 把这部分放进了每个S盒的中间4个比特，顺序是 S1：6 = 0110 S2：0 = 0000 S3, . . . , S8 等
7、等 因为所有边缘比特都是0，所以S1是唯一的得到非0差分输入的S盒。 S1的差分输入是 0 0110 0 = 0C 而其他所有盒S2, . . . , S8的差分输入都是,2轮DES的特征差分密码分析,21,察看S1的差分分布表，发现当输入异或 x= 0C时，最可能的差分输出y是 E = 1110，出现的概率是14/64；其他盒的输入一定是x= 0 且 y= 0 盒的输入通过置换 成为f(R,K)的输出。 如前所述，f(R,K)的差分输出是,而 A与L异或后得到 00 00 00 00，因为,2轮DES的特征差分密码分析,22,所以, 在第轮后，所有盒都得到差分输入，产生的差分输出也是； f(
8、R,K)的输出在轮后是，差分输出则是 (00 00 00 00 , 60 00 00 00),2轮DES的特征差分密码分析,23,假定：去掉初始置换IP和最终置换FP。2轮的差分分析共有个步骤。 Step 1: 产生明文对(P, P)，使得,办法是，随机产生一个P ，将其与下述值进行异或得到P,2轮DES的特征差分密码分析,24,Step 2: 对于产生的明文对(P, P) ，计算加密后产生密文对(T, T)（选择明文攻击）,Step 3: 计算T=TT，检查结果是否等于,如果不相等，就说明特征不符，这个明文对就不能用。重返第一步，产生新的明文对； 如果相等，则特征相符，进入第四步,2轮DES
9、的特征差分密码分析,25,Step 4: 因为S2, . . . , S8的差分输入都为，所以没有信息可以从S2K, . . . , S8K得到。 在S1的差分分布表中，0C E有14/64的概率，即只有64分之14可以得到 产生,2轮DES的特征差分密码分析,这14 个可能值可以通过把每个可能的S1K 与相应的S1E 和S1E 的比特相异或来确定，计算S1的差分输出S1，检查其是否等于E , 把S1K 的这14个值放进表中,26,Step 5: 计算这些表的交集 因为正确的密钥必定同时出现在每张表中 如果有不止一个S1K值，就说明还需要更多的明文和密文差分对才能唯一确定密钥S1K，转到第一步
10、，计算更多的数据 需要的明文密文差分对的数量，大致等于使用的特征概率的倒数，本例中需要64/14 5对 如果只得到一个S1K ，就是正确的，转到第六步。,2轮DES的特征差分密码分析,27,Step 6: 这个阶段，要恢复构成S1K的6个比特。 采用类似的特征，恢复第一轮中与S2-S8的输入相异或的6比特密钥 Step 7: 这个阶段已经有了构成S1K密钥的48比特，等同于S1K -S8K。 其余的比特密钥，采用穷举方法在64个可能的值中搜寻,2轮DES的特征差分密码分析,差分密码分析破解DES效率,R轮迭代密码的差分攻击步骤,定义,R轮迭代密码的差分攻击步骤,4) 重复第2、3步, 直到有一
11、个或几个计数器的值明显高于其它计数器的值, 输出它们所对应的子密钥（或部分比特）。,攻击成功！,对r轮迭代密码的差分攻击的步骤如下:,线性密码分析概述,线性密码分析的基本思想是通过寻找一个给定密码算法有效的线性近似表达式来破译密码系统。由于每个密码系统均为非线性系统，因此只能寻找线性近似表达式。 线性分析的分析者利用了包含明文、密文和子密钥的线性表达式发生的较大可能性 。,线性密码分析的基本方法,随机给定的明文P和相应的密文C上面的等 式成立的概率p1/2,线性密码分析的基本方法相关定理,线性密码分析的基本方法,用堆积引理, 我们可以将每轮变换中偏差最大的线性逼近式进行组合, 组合后的所有轮变
12、换的线性逼近式, 也将拥有最佳的偏差, 即寻找分组密码的最佳线性逼近式.,由上述分析我们知道, 分组密码的最佳线性逼近式的寻找, 归结为每轮线性逼近式的寻找, 而每轮的变换中, 除了非线性变换(即S-盒)部分, 线性部分是自然的线性关系, 也就是说, 每轮线性逼近式的寻找, 只需寻求S-盒部分的最佳线性逼近式.,线性密码分析例子SPN,算法的输入为16比特的数 据块，并且重复四次相同 操作处理数据块。 每一轮包括 1) S-box置换 2）比特变换 3）密钥混合。,S-box置换 S-box的最基本的性质是其非线性映射，S-box的输出不能通过输入的线性变换而得到。,线性密码分析例子SPN,P
13、置换 （其中的数字表示比特的位置，1表示最左边的比特，16表示最右边的比特）,分析加密部件,在下图中的S-box中 考虑表达式X2 X3 Y1 Y3 Y40 或等价形式X2 X3Y1 Y3 Y4。,线性密码分析例子SPN,例子：对于16种可能的输入X和其相应的输出Y，有12种情况可以使得该式成立，因此线性可能性偏移量是12/161/21/4。 相似的，对于等式X1 X4Y2其线性可能性偏移量接近于0， 而等式X3 X4Y1 Y4的线性可能性偏移量是2/161/23/8。,S-box线性近似采样,线性密码分析例子SPN,例如一个输入变量的线性近似表达式a1 X1 a2 X2 a3 X3 a4 X
14、4，其中，ai0, 1。“”为二进制的“与”运算，输入行的16进制的值是a1 a2 a3 a4的组合。 相似的，对于一个输出变量的线性近似表达式b1 Y1 b2 Y2 b3 Y3 b4 Y4，其中，bi0, 1，输出行的16进制的值是b1 b2 b3 b4的组合。 其中，Input表示表达式的输入系数，而output表示表达式的输出系数，行和列交集处的值表示以此行列值代表线性表达式成立的数量减去8。,分析加密部件,线性密码分析例子SPN,线性近似偏移量,分析加密部件,线性密码分析例子SPN,例子：线性表达式X3 X4Y1 Y4 NL(3,9)=2 (3,9)=-3/8,分析加密部件,线性密码分
15、析例子SPN,(a,b):表示随机变量 输入a: a=(a1,a2,a3,a4) 输出b: b=(b1,b2,b3,b4) NL(a,b)： 表示满足如下条件的二元8重组(x1,x2,x3,x4,y1,y2,y3,y4)的个数： (y1,y2,y3,y4)= f(x1,x2,x3,x4) 并且 a1 X1 a2 X2 a3 X3 a4 X4 b1 Y1 b2 Y2 b3 Y3 b4 Y4 =0 偏差计算公式(a,b)=(NL(a,b) -8)/16,例如：随机变量X1 X4 Y2 可以表示成（9，4）,通过构造一个关于明文和倒数第二轮输入的线性表达式 就有可能恢复出最后一轮加密使用的子密钥的一个子集，以达到攻击的目的。,构造加密函数的线性近似表达式,线性密码分析例子SPN,首先对于上图，有如下的S-box线性近似表达式： S12：X1 X3 X4Y2 概率为12/16，偏移量为1/4 S22：X2Y2 Y4 概率为4/16，偏移量为1/4 S32：X2Y2 Y4 概率为4/16，偏移量为1/4 S34：X2Y2 Y4 概率为4/16，偏移量为1/4,构造加密函数的线性近似表达式,线性密码分析例子SPN,令Ui(Vi)
