《分组密码线性分析技术.ppt》由会员分享，可在线阅读，更多相关《分组密码线性分析技术.ppt（42页珍藏版）》请在三一办公上搜索。
1、分组密码分析技术,密码分析和密码设计是相互对立、相互依存的。伴随着对任何一种密码的分析，分析者千方百计从该密码算法中寻找漏洞和缺陷，进而进行攻击。对现代分组密码的分析更是如此，如DES自从诞生以来，对它的分析工作就没停止过。,分组密码分析技术,代换置换网络线性密码分析差分密码分析,代换置换网络,算法的输入为16比特的数据块，并且重复四次相同的操作处理数据块。每一轮包括1)S-box置换2）比特变换3）密钥混合。,代换置换网络,S-box置换 S-box的最基本的性质是其非线性映射，S-box的输出不能通过对输入的线性变换而得到。S-box要可逆,代换置换网络,P置换（其中的数字表示比特的位置，
2、1表示最左边的比特，16表示最右边的比特）,线性密码分析 1 基本的分析概述,线性分析的分析者利用了包含明文、密文和子密钥的线性表达式发生的较大可能性。线性分析前提：假设攻击者已经知道了大量的明文和相对应的密文。,线性密码分析 1 基本的分析概述,线性分析最基本的思想就是用一个线性表达式来近似表示加密算法的一部分，该线性表达式是关于模2的操作（用表示XOR操作）。表达式具有如下的形式：该表达式是u比特的输入与v比特的输出进行XOR操作的结果。,线性密码分析,线性密码分析的方法就是测定上述形式的线性表达式发生的可能性的大小。如果一个密码算法使得等式成立的可能性非常大或者非常小，这说明该密码算法的
3、随机性比较差。一般情况下，假如我们随机选择uv个比特值，并且将它们代入等式,等式成立的可能性应该为1/2。,线性密码分析,在线性密码分析中，一个线性表达式成立的可能性与1/2之间的差值定义为偏移量（或偏差）。一个线性表达式成立的可能性与1/2的距离越大，密码分析者利用线性密码分析就越有效果。如果对于随机选择的明文找到相应的密文，使得上述表达式成立的可能性为PL，则线性可能性偏移量是PL1/2。线性可能性偏移量的绝对值|PL1/2|越大，线性密码分析对于知道较少明文情况下的攻击越有效。,线性密码分析 2 堆积引理,考虑两个二进制变量X1，X2。通过计算简单的关系开始：X1 X20是一个线性表达式
4、，等价于X1X2；X1 X21是一个仿射表达式，等价于X1X2。,线性密码分析 2 堆积引理,给出如下的概率分布：,线性密码分析 2 堆积引理,如果两个随机变量相互独立，则：,线性密码分析 2 堆积引理,可以等价表示为：Pr(X1 X20)Pr(X1X2)Pr(X10,X20)Pr(X11,X21)p1 p2(1p1)(1p2)另一种表示方法是：令p11/2，p21/22，、2是线性可能性偏移量，而且1/2,21/2。因此，Pr(X1 X20)1/222，并且X1 X20的线性偏移量1,2为22,线性密码分析 2 堆积引理,扩展到多个随机二进制变量的情况若有随机变量X1 Xn且概率为p11/2
5、1，p21/22，.，pn1/2n。Piling-Up 引理：对于n个相互独立的二进制随机变量，X1,X2,Xn，可得或者等价表示为，其中1,2,.,n表示X1 X2.Xn0的线性偏移量。,线性密码分析-2 堆积引理-例子,有四个相互独立的随机变量X1，X2，X3 和X4。Pr(X1 X20)1/21,2Pr(X2 X30)1/22,3，Pr(X1 X30)Pr(X1 X2 X2 X30)应用Piling-Up 引理可得：Pr(X1 X30)1/221,2 2,3相应地，1,321,2 2,3,线性密码分析 3 分析加密部件,在更详细的讨论攻击细节之前，首先需要知道S-box盒的线性脆弱性。S
6、-box的输入为XX1 X2 X3 X4，相应的输出为YY1 Y2 Y3 Y4。,S-box映射,线性密码分析 3 分析加密部件,例在下图中的S-box中 考虑表达式X2 X3 Y1 Y3 Y40或等价形式X2 X3Y1 Y3 Y4。,线性密码分析 3 分析加密部件,根据对S-box的线性近似采样，对于16种可能的输入X和其相应的输出Y，有12种情况可以使得X2 X3 Y1 Y3 Y40或等价形式X2 X3Y1 Y3 Y4成立，因此线性可能性偏移量是12/161/21/4。相似的，对于等式X1 X4Y2其线性可能性偏移量接近于0，而等式X3 X4Y1 Y4的线性可能性偏移量是2/161/23/
7、8。,线性密码分析3 分析加密部件,S-box线性近似采样,线性密码分析 3 分析加密部件,例如一个输入变量的线性近似表达式a1 X1 a2 X2 a3 X3 a4 X4，其中，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。,线性密码分析 3 分析加密部件,线性
8、近似偏移量,线性密码分析 3 分析加密部件,如线性表达式X3 X4Y1 Y4（输入行标是3，输出列标是9）表中值6代表线性表达式成立的数量为2次,线性密码分析 4 构造加密函数的线性近似表达式,通过构造一个关于明文和倒数第二轮输入的线性表达式就有可能恢复出最后一轮加密使用的子密钥的一个子集，以达到攻击的目的。,线性密码分析,考虑上图所示的关于S12、S22、S32和S34的线性近似表达式。实际上是建立了一个关于前3轮的表达式，而不是整个4轮加密过程。首先对于上图，有如下的S-box线性近似表达式：S12：X1 X3 X4Y2 概率为12/16，偏移量为1/4S22：X2Y2 Y4 概率为4/1
9、6，偏移量为1/4S32：X2Y2 Y4 概率为4/16，偏移量为1/4S34：X2Y2 Y4 概率为4/16，偏移量为1/4,线性密码分析,令Ui(Vi)作为第i轮S-box的16比特的输入（输出），并且Uij(Vij)作为第Ui块的第j比特。令Ki表示与第i轮输入进行XOR运算的子密钥。可知，K5表示与第四轮的输出进行XOR运算的子密钥。,线性密码分析,因此，U1P K1，其中P表示16比特的明文，表示比特之间的XOR运算。利用第一轮S12的线性近似表达式，可得：V1,6U1,5 U1,7 U1,8(P5 K1,5)(P7 K1,7)(P8 K1,8)表达式成立的概率为12/16。,线性密
10、码分析 4 构造加密函数的线性近似表达式,S12 V1,6U1,5 U1,7 U1,8(P5 K1,5)(P7 K1,7)(P8 K1,8)S22 V2,6 V2,8V1,6 K2,6 联合可得：V2,6 V2,8 P5 P7 P8 K1,5 K1,8 K2,60 由Piling-Up引理可得其成立的概率为1/22(3/41/2)(1/41/2)3/8（线性偏移量为1/8）。,线性密码分析,对于第3轮，可得到：S32 V3,6 V3,8U3,6 等式成立的概率为1/4 S34 V3,14 V3,16U3,14 等式成立的概率为1/4又由U3,6V2,6 K3,6 U3,14V2,8 K3,14
11、 可得：V3,6 V3,8 V3,14 V3,16 V2,6 K3,6 V2,8 K3,140 等式成立的概率为1/22(1/41/2)25/8（线性可能性偏移量为1/8）。,线性密码分析 4 构造加密函数的线性近似表达式,应用Piling-Up引理联合V2,6 V2,8 P5 P7 P8 K1,5 K1,8 K2,60V3,6 V3,8 V3,14 V3,16 V2,6 K3,6 V2,8 K3,140可得构成四个S-box的线性近似表达式：V3,6 V3,8 V3,14 V3,16 P5 P7 P8 K1,5 K1,7 K1,8 K2,6 K3,6 K3,140。,线性密码分析,计算U4,
12、6V3,6 K4,6，U4,8V3,16 K4,8，U4,14V3,8 K4,14U4,16V3,16 K4,16可以得到：U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0，其中，kK1,5 K1,7 K1,8 K2,6 K3,6 K3,14 K4,6 K4,8 K4,14 K4,16 利用Piling-Up引理，可以得出上述表达式成立的概率为1/223(3/41/2)(1/41/2)315/32（线性可能性偏移量为1/32）。,U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0，其中，kK1,5 K1,7 K1,8 K2,6 K3,6 K3,14 K4,6
13、K4,8 K4,14 K4,16 利用Piling-Up引理，可以得出上述表达式成立的概率为1/223(3/41/2)(1/41/2)315/32（线性可能性偏移量为1/32）。k是确定的（或者为0或者为1，取决于加密算法的密钥）。U4,6 U4,8 U4,14 U4,16 P5 P7 P80成立的概率为15/32或者(115/32)17/32（取决于k的值是0还是1）。换句话说，现在有前三轮加密过程的一个线性近似表达式，其线性偏移量是1/32。,线性密码分析,一旦获得了有R轮加密过程的加密算法的前R-1轮的线性近似表达式，且该表达式具有足够大的线性可能性偏移量，则恢复最后一轮的子密钥来攻击该
14、密码算法是可行的。,把从最后一个子密钥中恢复出的密钥的一部分称为局部目标子密钥（或部分目标子密钥）。局部目标子密钥来自与最后一轮的S-box相关联的子密钥。,5 获取密钥比特,特别地，对于所有可能的局部目标子密钥，相应的密文比特与其进行XOR运算，运算的结果向后通过最后一轮相应的S-box进行运算。对所有的明文/密文对进行这种运算过程，并且设置一个计数器对每个局部目标子密钥进行计数。若对于输入到最后一轮S-box的比特和已知明文，线性近似表达式成立，则计数器增加。U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0一个不正确的子密钥被认为导致一个向最后一轮S-box的随机猜测输入
15、，因而线性表达式成立的可能性非常接近1/2。,5 获取密钥比特,如果某个局部目标子密钥对于明文/密文对的计数值与明文/密文对数目的一半相差最大，则该子密钥被假定为正确的子密钥。U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0这样做的原因是一个正确的子密钥将使得线性近似表达式成立的概率偏离1/2,5 获取密钥比特,线性表达式U4,6 U4,8 U4,14 U4,16 P5 P7 P80对于每个明文/密文对，尝试部分目标子密钥K5,5.K5,8,K5,13.K5,16的256种可能。其中U5,5.U5,8,U5,13.U5,16是通过将相应的密文与子密钥K5,5.K5,8,K5,
16、13.K5,16进行XOR运算，然后将运算结果向后经过S42，S44运算得到的。,5 获取密钥比特,对每个局部目标子密钥，当表达式U4,6 U4,8 U4,14 U4,16 P5 P7 P80成立时，增加计数。若一个子密钥的计数值与明文/密文的数目的一半相差最多，被假定为正确的子密钥。,产生 10000个已知明文/密文对，取部分子密钥K5,5.K5,80010，K5,13.K5,16 0100 来模拟前面描述的攻击。下表给出了部分子密钥对应的偏移量计数值（完整的应该有256条记录，每个目标子密钥对应一个），从中可以确认找到正确的子密钥。结合表中的数据，可以计算出线性可能性偏移量，公式如下：|b
17、ias|count5000|/10000其中count表示对应的子密钥的计数值。U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0从表中可以看出偏移量最大的子密钥是K5,5.K5,8,K5,13.K5,162,4，实际上，这个结果对于所有可能子密钥产生的结果也是正确的。,线性密码分析 5 获取密钥比特,线性攻击的实验数据,线性密码分析 5 获取密钥比特,试验测定的偏移量是0.0336非常接近预期得线性可能性偏移量1/320.0315。,6 攻击的复杂度,线性近似表达式中包含的S-box称为活跃S-box。下图中，从第1轮到第3轮中被粗线条标出的四个S-box都是活跃的。一个线性近似表达式成立的可能性，与S-box的线性可能性偏移量的大小，活跃S-box的数目有关。,线性密码分析 6 攻击的复杂度,一般情况下，这些活跃S-box的线性可能性偏移量越大，整个线性近似表达式的线性可能性偏移量越大。同样，活跃S-box的线性可能性偏移量越小，整个线性表达式的线性可能性偏移量越小。一般地提高算法安全性抵抗线性分析的方法集中在优化S-box（例如，减小最大偏移量）和增加活跃S-box的数目。,
