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是非差分均匀的, ：,位输入，位输
3、出,对于输入S盒的6比特的(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进
4、制是0-15) 可以看到：第一行除第一列外全为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 和2
5、7 时(只看后面的6位)：,12,S1 的差分分布表,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时，可能的
6、输入： 。,16,确定密钥的原理,16,这样就可以从,得到可能的密钥值,17,确定密钥的原理,17,而正确的密钥值必定同时出现在两个集合,因此可以确定密钥是在 中的一个。 要确定到底是哪一个，需要知道更多的输入输出异或对。以此类推得到此轮密钥,18,多轮DES的特征,差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到： E扩展中的异或值是线性的：,异或值与密钥是无关的：,19,2轮DES的特征差分密码分析,20,在第一轮中，输入到函数f的差分结果是a= 60 00 00 00 经f 中的扩展变换后， 把这部分放进了每个S盒的中间4个比特，顺序是S1：6 = 0110S2：0 = 000
7、0S3, . . . , S8 等等 因为所有边缘比特都是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,所以, 在第轮后，所有盒都得到差
8、分输入，产生的差分输出也是； f(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，检查结果是否等于,如果不相等，就说明特征不符，这个明文对就不能用。重返第一步，产生新的明文对； 如果相等，则
9、特征相符，进入第四步,2轮DES的特征差分密码分析,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值，就说明还需要更多的明文和密文差分对才
10、能唯一确定密钥S1K，转到第一步，计算更多的数据 需要的明文密文差分对的数量，大致等于使用的特征概率的倒数，本例中需要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-轮特征= 0 1 的概率是指在
11、明文和子密钥 1 , 2 , 独立, 均匀随机时, 明文对m和m*的差分为 0 的条件下, 第i(1 i r) 轮输出c(i)和c*(i)的差分为 1 的概率(或称为特征的差分扩散率) 。,若r-轮特征= 0 1 满足 (1) m与m*的差分为 0 ； (2) 第i轮输出c(i)与c*(i)的差分为 1 (1 i r),则称明文对m与m*是一个正确对，否则称其为错误对。,定义,R轮迭代密码的差分攻击步骤,1) 找出一个（r1）轮= 0 1 , 使它的概率达到最大或几乎最大.,2) 均匀随机地选择明文m, 并计算出m*, 使m m*= 0 , 再找出m和m*在实际密钥加密下所得的密文 c(r)和
12、c*(r).,3) 若最后一轮的子密钥 （或 的部分比特）有 2 个可能的值 (1 j 2 ), 我们就设置 2 个相应的计数器 (1 j 2 ), 用每一个可能的密钥解密c(r) 和 c*(r)得到c(r1)和 c*(r-1) . 若c(r1)+c*(r-1)= 1 , 则给相应的计数器 加1。,4) 重复第2、3步, 直到有一个或几个计数器的值明显高于其它计数器的值, 输出它们所对应的子密钥（或部分比特）。,攻击成功！,对r轮迭代密码的差分攻击的步骤如下:,线性密码分析概述,线性密码分析的基本思想是通过寻找一个给定密码算法有效的线性近似表达式来破译密码系统。由于每个密码系统均为非线性系统，
13、因此只能寻找线性近似表达式。 线性分析的分析者利用了包含明文、密文和子密钥的线性表达式发生的较大可能性 。,线性密码分析的基本方法,线性密码分析的方法是寻找一个给定密码算法的 具有下列形式的“有效的”线性表达式这里 1 , 2 , ； 1 , 2 , 和 1 , 2 , , 表示固定 的比特位置。,随机给定的明文P和相应的密文C上面的等 式成立的概率p1/2,线性密码分析的基本方法相关定理,设 1 , 2 , , 是取值于集合0,1的独立随机变量. 设 1 , 2 ,.都是实数, 且对所有的i, i=1,2, k有0 1, 再设Pr = 0 = , 则Pr = 1 = 1 . 对取值于0,1的
14、随机变量, 用分布偏差来表示它的概率分布. 随机变量Xi的偏差定义为 = 1 2,（堆积引理. Piling-up lemma）设 1 , 2 , , 是取值于集合0,1的独立随机变量. 1 2 表示随机变量 1 2 的偏差,则, 1 2 = 2 1 1 ,线性密码分析的基本方法,用堆积引理, 我们可以将每轮变换中偏差最大的线性逼近式进行组合, 组合后的所有轮变换的线性逼近式, 也将拥有最佳的偏差, 即寻找分组密码的最佳线性逼近式.,由上述分析我们知道, 分组密码的最佳线性逼近式的寻找, 归结为每轮线性逼近式的寻找, 而每轮的变换中, 除了非线性变换(即S-盒)部分, 线性部分是自然的线性关系
15、, 也就是说, 每轮线性逼近式的寻找, 只需寻求S-盒部分的最佳线性逼近式.,线性密码分析例子SPN,算法的输入为16比特的数 据块，并且重复四次相同 操作处理数据块。 每一轮包括 1) S-box置换 2）比特变换 3）密钥混合。,S-box置换 S-box的最基本的性质是其非线性映射，S-box的输出不能通过输入的线性变换而得到。,线性密码分析例子SPN,P置换 （其中的数字表示比特的位置，1表示最左边的比特，16表示最右边的比特）,分析加密部件,在下图中的S-box中 考虑表达式X2 X3 Y1 Y3 Y40 或等价形式X2 X3Y1 Y3 Y4。,线性密码分析例子SPN,例子：对于16
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 X4，其中，ai0, 1。“”为二进制的“与”运算，输入行的16进制的值是a1 a2 a3 a4的组合。相似的，对于一个输出变量的线性近似表达式b1 Y1 b2 Y2 b3 Y3 b4 Y4，其中，bi0, 1，输出行的16进制的值是b1
17、 b2 b3 b4的组合。其中，Input表示表达式的输入系数，而output表示表达式的输出系数，行和列交集处的值表示以此行列值代表线性表达式成立的数量减去8。,分析加密部件,线性密码分析例子SPN,线性近似偏移量,分析加密部件,线性密码分析例子SPN,例子：线性表达式X3 X4Y1 Y4NL(3,9)=2 (3,9)=-3/8,分析加密部件,线性密码分析例子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,
18、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 S3
19、2：X2Y2 Y4 概率为4/16，偏移量为1/4 S34：X2Y2 Y4 概率为4/16，偏移量为1/4,构造加密函数的线性近似表达式,线性密码分析例子SPN,令Ui(Vi)作为第i轮S-box的16比特的输入（输出），并且Uij(Vij)作为第Ui块的第j比特。 令Ki表示与第i轮输入进行XOR运算的子密钥。可知，K5表示与第四轮的输出进行XOR运算的子密钥。,线性密码分析例子SPN,因此，U1P K1，其中P表示16比特的明文，表示比特之间的XOR运算。 利用第一轮S12的线性近似表达式，可得：V1,6U1,5 U1,7 U1,8 (P5 K1,5) (P7 K1,7) ( P8 K1,
20、8)表达式成立的概率为12/16。,X1 X3 X4Y2,构造加密函数的线性近似表达式,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,7 K1,8 K2,60 由Piling-Up引理可得其成立的概率为1/22(3/41/2)(1/41/2)3/8（线性偏移量为1/8）。,构造加密函数的线性近似表达式,线性密码分析例子SPN,X2Y2 Y4,对于第3轮，可得到：S32 V3,6 V3,8U3,6 等式成立的概率为1/ 4S3
21、4 V3,14 V3,16U3,14 等式成立的概率为1/4又由U3,6V2,6 K3,6 U3,14V2,8 K3,14 可得：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）。,构造加密函数的线性近似表达式,线性密码分析例子SPN,应用Piling-Up引理联合V2,6 V2,8 P5 P7 P8 K1,5 K1,7 K1,8 K2,60V3,6 V3,8 V3,14 V3,16 V2,6 K3,6 V2,8 K3,140可得构成四个S-box的线性近似表达式：V3,6 V3,
22、8 V3,14 V3,16 P5 P7 P8 K1,5 K1,7 K1,8 K2,6 K3,6 K3,140。,构造加密函数的线性近似表达式,线性密码分析例子SPN,计算U4,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（线性
23、可能性偏移量为1/32）。,构造加密函数的线性近似表达式,线性密码分析例子SPN,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轮的线性近似表达式，且该表达式具有足够大的线性可能性偏移量，则恢复最后一轮的子密钥来攻击该密码算法是可行的。,线性密码分析例子SPN,把从最后一个子密钥中恢复出的密钥的一部分称为局部目标子密钥（
24、或部分目标子密钥）。 局部目标子密钥来自与最后一轮的S-box相关联的子密钥。,获取密钥比特,特别地，对于所有可能的局部目标子密钥，相应的密文比特与其进行XOR运算，运算的结果向后通过最后一轮相应的S-box进行运算。 对所有的明文/密文对进行这种运算过程，并且设置一个计数器对每个局部目标子密钥进行计数。若对于输入到最后一轮S-box的比特和已知明文，线性近似表达式成立，则计数器增加。 U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0 一个不正确的子密钥被认为导致一个向最后一轮S-box的随机猜测输入，因而线性表达式成立的可能性非常接近1/2。,获取密钥比特,线性密码分析例子
25、SPN,线性表达式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,13.K5,16进行XOR运算，然后将运算结果向后经过S42，S44运算得到的。,获取密钥比特,线性密码分析例子SPN,对每个局部目标子密钥，当表达式U4,6 U4,8 U4,14 U4,16 P5 P7 P80成立时，增加计数。 若一个子密钥的计数值与明文/密文的数目的一半相差最多，被假定为正确的子密钥。(一个正确
26、的子密钥将使得线性近似表达式成立的概率偏离1/2),产生 10000个已知明文/密文对，取部分子密钥K5,5.K5,80010，K5,13.K5,16 0100 来模拟前面描述的攻击。下表给出了部分子密钥对应的偏移量计数值（完整的应该有256条记录，每个目标子密钥对应一个），从中可以确认找到正确的子密钥。结合表中的数据，可以计算出线性可能性偏移量，公式如下：| bias |count5000 | / 10000其中count表示对应的子密钥的计数值。U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0从表中可以看出偏移量最大的子密钥是K5,5.K5,8, K5,13.K5,162
27、, 4，实际上，这个结果对于所有可能子密钥产生的结果也是正确的。,线性攻击的实验数据,线性近似表达式中包含的S-box称为活跃S-box。 图中，从第1轮到第3轮中被粗线条标出的四个S-box都是活跃的。 一个线性近似表达式成立的可能性，与S-box的线性可能性偏移量的大小，活跃S-box的数目有关。,线性密码分析攻击的复杂度,一般情况下，这些活跃S-box的线性可能性偏移量越大，整个线性近似表达式的线性可能性偏移量越大。 同样，活跃S-box的线性可能性偏移量越小，整个线性表达式的线性可能性偏移量越小。 一般地提高算法安全性抵抗线性分析的方法集中在优化S-box（例如，减小最大偏移量）和增加
28、活跃S-box的数目。,假如我们能够在一个明文比特子集和最后一轮即将进行代换的输入状态比特子集之间找到一个概率线性关系, 换句话说, 即存在一个比特子集使得其中元素的异或表现出非随机的分布（即明文和最后一轮输入的最佳线性逼近式）, 再假设一个攻击者拥有大量的用同一未知密钥加密的明文密文对.,对每一个明文密文对, 将用所有的(最后一轮)候选密钥来对最后一轮解密密文. 对每一个候选密钥, 计算包含在线性关系式中的相关比特的异或的值, 然后确定上述的线性关系式是否成立. 如果成立, 就在对应于特定候选密钥的计数器上加1.,在这个过程的最后, 我们希望计数频率离明-密文对数的一半最远的候选密钥含有那些密钥比特的正确值. 可以看到, 线性攻击成功只依赖于明文的个数N和|p1/2|, 并且随着N或|p 1/2|的增加而增加.,要说明的是：在选择从一轮到多轮线性逼近式时，除了考虑有效性外，还需使得得到的最后关系式中，只包含明文、密文和最后一轮的密钥比特，才能实施有效攻击。,线性密码分析攻击过程,总结,差分密码分析和线性密码分析是目前常用于攻击迭代分组密码的方法之一，但是有些密码为了抵抗差分密码分析和线性密码分析，设计得很复杂，很难用一般的差分密码分析和线性密码分析的理论去研究，如何把差分密码分析和线性密码分析的理论应用于不同类型的密码上，也是许多学者研究的问题。,谢谢聆听,THANKS,
