312-差分密码分析-09年解析课件.ppt

1、1差分密码分析差分密码分析电子科技大学电子科技大学范明钰范明钰提要提要2u简介简介u技术要点技术要点uDESDES框图框图u差分分析原理差分分析原理uS S盒的非均匀性，盒的非均匀性，S1S1的差分分布的差分分布u2 2轮、轮、4 4轮、轮、8 8轮差分分析轮差分分析u已知明文攻击已知明文攻击u总结总结简介简介-3u 差分密码分析是一种破解某些类型的密码系统的差分密码分析是一种破解某些类型的密码系统的方法方法u 显然，设计显然，设计DESDES的的IBMIBM研究人员知道有关差分密研究人员知道有关差分密码分析的情况。码分析的情况。u 当密码分析人员可以进行选择明文分析时，差分当密码分析人员可以

2、进行选择明文分析时，差分密码分析十分有效。密码分析十分有效。u 已知明文的差分密码分析也是可行的，但是要求已知明文的差分密码分析也是可行的，但是要求已知明密文的量很大已知明密文的量很大简介简介-24u这一方法搜索明密文对，根据它们的差分这一方法搜索明密文对，根据它们的差分的恒定性，研究密码系统的差分现象的恒定性，研究密码系统的差分现象uDESDES中两个元素中两个元素P1P1和和P2P2的差分定义为的差分定义为P1P2(P1P2(比特异或操作比特异或操作)u差分在不同的密码系统中有不同的定义差分在不同的密码系统中有不同的定义u差分密码分析可用于弱轮函数的迭代密码差分密码分析可用于弱轮函数的迭代

3、密码（如（如FeistelFeistel型密码）型密码）技术要点技术要点51.1.将密文的差分，看作是相应明文差分的函数将密文的差分，看作是相应明文差分的函数2.2.寻找大概率的差分输入（称为特征），可以寻找大概率的差分输入（称为特征），可以用于追踪几轮用于追踪几轮3.3.计算密钥的概率，定位最可能的密钥计算密钥的概率，定位最可能的密钥DES的框图的框图6DES的单轮结构的单轮结构7DES的扩展变换的扩展变换8符号定义符号定义9uP P 表示明文表示明文，T T 表示密文表示密文u(P,PP,P)表示明文对，其异或后得到特定的值：表示明文对，其异或后得到特定的值：P,P,使得使得 P=P PP

4、=P P u(T,TT,T)表示密文对，其异或后得到特定的值表示密文对，其异或后得到特定的值TT，使得，使得 T=T TT=T T u 带撇的值总是差分的，带撇的值总是差分的，PP,TT,aa,AA。例例如，如，a=a aa=a a 差分分析原理差分分析原理-110uDES DES 的设计要求之一是确保尽可能的分布均匀的设计要求之一是确保尽可能的分布均匀u例如，明文或密钥的例如，明文或密钥的1 1比特变化，将导致比特变化，将导致6464比特比特的密文中大约的密文中大约3232比特的看起来是不可预测和随比特的看起来是不可预测和随机的变化机的变化差分分析原理差分分析原理-211u以色列研究人员以色

5、列研究人员Eli Eli BihamBiham 和和 AdiAdi ShamirShamir 在在19901990年观察到，对于固定的密钥，年观察到，对于固定的密钥，DESDES的差分并不的差分并不呈现伪随机现象呈现伪随机现象u这一现象是，对于固定明文这一现象是，对于固定明文P P 和和P P 的异或的异或PP，T=TTT=TT 不是均匀分布的不是均匀分布的u反过来，两个均匀分布的随机数的异或，结果反过来，两个均匀分布的随机数的异或，结果本身应该是均匀分布的。本身应该是均匀分布的。S-Box是非差分均匀的是非差分均匀的12u如果如果S S盒的输入是均匀分布的随机数，其输出也盒的输入是均匀分布的

6、随机数，其输出也应该是均匀分布的随机数应该是均匀分布的随机数S-Box的差分均匀性的差分均匀性-113u假设假设5656-bite-bite的密钥是按照均匀分布的原则选择的的密钥是按照均匀分布的原则选择的，则对于任意轮的任意，则对于任意轮的任意S S盒的输入，在其盒的输入，在其6464比特比特的可能取值上也是均匀分布的的可能取值上也是均匀分布的u任意轮的任意任意轮的任意S S盒的输出，在其盒的输出，在其1616个可能的值个可能的值(0-0-F F)上也是均匀分布的。每个上也是均匀分布的。每个S S盒中有盒中有4 4行，每个行，每个(0-0-F F)值在值在S S盒中出现盒中出现4 4次，每行输

7、出一个值次，每行输出一个值S-Box的差分均匀性的差分均匀性-214u 考虑一个考虑一个S-boxS-box的差分现象：的差分现象：u 输入：共有输入：共有64642 2=4096 4096 种可能的输入种可能的输入(x,xx,x)值对，因为对值对，因为对于输入于输入S S盒的盒的6 6比特的比特的x,xx,x，以及以及x=x xx=x x，每一个取每一个取值都在值都在6464比特的可能值上变化比特的可能值上变化u 而其而其4 4比特输出值，比特输出值，y=S(x),yy=S(x),y=S(x=S(x)，以及以及y=y yy=y y =S(x)S(x=S(x)S(x)每个取值都在其每个取值都在

8、其1616个可能的值上变化个可能的值上变化u 差分输出差分输出yy的分布情况，可以针对的分布情况，可以针对8 8 个个S S 盒中的每一个盒中的每一个S S盒来计算，计算在输入盒来计算，计算在输入(x,xx,x)在在4096 4096 个可能值上变化时，个可能值上变化时，每个每个y y值出现的次数值出现的次数S1 的差分分布表的差分分布表-115.=2=26 6-1-1出出现现的的次次数数S1 的差分分布表的差分分布表-216u 6 6比特的差分输入比特的差分输入xx有有6464个值：个值：00-3F00-3F(16(16进制，进制，1010进制是进制是0-630-63)u 4 4比特的差分输

9、出比特的差分输出yy有有1616个值：个值：0-F0-F(16(16进制，进制，1010进制是进制是0-150-15)u 每一行的总和是每一行的总和是6464，因为每个差分输入因为每个差分输入xx针对针对40964096个个(x,xx,x)对中的对中的6464个个u 可以看到：第一行除第一列外全为可以看到：第一行除第一列外全为0 0，因为当，因为当x=x xx=x x =0=0，同样的输入出现了两次，因此其输出同样的输入出现了两次，因此其输出y=y yy=y y =0=0S1 的差分分布表的差分分布表-317u 后面的行：后面的行：u 例如，当例如，当 x=01 x=01 时时,6 6个可能的

10、个可能的yy中有中有5 5个值个值:0,1,2,4,0,1,2,4,8 8呈现呈现0 0可能次数，就是说不出现。可能次数，就是说不出现。uA A 出现的概率是出现的概率是16/6416/64u 9 9 和和C C 出现的概率是出现的概率是10/6410/64u 这就是说，这就是说，S1S1呈现出很强的不均匀分布呈现出很强的不均匀分布u 这种差分不均匀性对于所有的这种差分不均匀性对于所有的S S盒盒S1,S2,.,S8S1,S2,.,S8都有体都有体现现S1 的差分分布表的差分分布表-418u 考虑输入异或值为考虑输入异或值为3434时，可能的输出异或是：时，可能的输出异或是：u 输出：输出：u

11、 出现次数：出现次数：u 其中：其中：34344 4有两种可能，这种输入对是成双有两种可能，这种输入对是成双的，即：的，即：(,)和和 (,)S1 的差分分布表的差分分布表-19对对S1S1构建差分表，发现当构建差分表，发现当输入是输入是13 13 和和27 27 时时(只看后只看后面的面的6 6位位)：S1 的差分分布表的差分分布表-20列出列出S1S1中输中输入异或值为入异或值为3434的可能的的可能的输入值：输入值：确定密钥的原理确定密钥的原理-21u 假设已知假设已知S1S1的两个输入是的两个输入是0101和和3535，其异或的结果是，其异或的结果是3434，经过经过S1S1之后输出异

12、或的结果是之后输出异或的结果是D D。查。查S1S1的差分分布表，的差分分布表，得到输入异或为得到输入异或为3434，输出异或为，输出异或为D D时，可能的输入：时，可能的输入：确定密钥的原理确定密钥的原理-22实际上，输入异或的结果是实际上，输入异或的结果是3434，与密钥无关，与密钥无关，这是因为：这是因为：因为因为所以所以确定密钥的原理确定密钥的原理-23这样就得到：这样就得到：所以，可能的密钥就是所以，可能的密钥就是确定密钥的原理确定密钥的原理-24此外，假设已知此外，假设已知S1S1的两个输入是的两个输入是2121和和1515，它们异或后的结，它们异或后的结果是果是3434，输出异或

13、后的结果是，输出异或后的结果是3 3 。查。查S1S1的差分分布表，得的差分分布表，得到输入异或为到输入异或为3434，输出异或为，输出异或为3 3时，可能的输入：时，可能的输入：。确定密钥的原理确定密钥的原理-25这样就可以从这样就可以从得到可能的密钥值得到可能的密钥值确定密钥的原理确定密钥的原理-26而正确的密钥值必定同时出现在两个集合而正确的密钥值必定同时出现在两个集合因此可以确定密钥是在因此可以确定密钥是在 中的一个。中的一个。要确定到底是哪一个，需要知道更多的输入输要确定到底是哪一个，需要知道更多的输入输出异或对。出异或对。多轮多轮DES的特征的特征27差分输入具有很高的或然性，可以

14、直接追踪到多轮的差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到：情况，观察到：E扩展中的异或值是线性的：扩展中的异或值是线性的：异或值与密钥是无关的：异或值与密钥是无关的：2轮轮DES的特征的特征-1-1282轮轮DES的特征的特征-2-229在第一轮中，输入到函数在第一轮中，输入到函数f f的差分结果是的差分结果是 a a=60 00 00 00=60 00 00 00经经f f 中的扩展变换后，中的扩展变换后，把这部分放进了每个把这部分放进了每个S S盒的中间盒的中间4 4个比特，顺序是个比特，顺序是 S1S1：6=01106=0110 S2 S2：0=00000=0000 S

15、3,.,S8 S3,.,S8 等等等等因为所有边缘比特都是因为所有边缘比特都是0 0，所以，所以S1S1是唯一的得到非是唯一的得到非0 0差分差分输入的输入的S S盒。盒。S1S1的差分输入是的差分输入是 0 0110 0=0C 0 0110 0=0C 而其他所有盒而其他所有盒S2,.,S8S2,.,S8的差分输入都是的差分输入都是2轮轮DES的特征的特征-3-330察看察看S1S1的差分分布表，发现当输入异或的差分分布表，发现当输入异或x=0Cx=0C时，最可能时，最可能的差分输出的差分输出yy是是 E=1110 E=1110，出现的概率是，出现的概率是1414/64/64；所有其他；所有其

16、他盒的输入一定是盒的输入一定是x=0 x=0 且且 y=0 y=0盒的输入通过置换盒的输入通过置换 成为成为f(R,K)f(R,K)的输出。的输出。如前所述，如前所述，f(R,K)f(R,K)的差分输出是的差分输出是而而 AA与与LL异或后得到异或后得到 00 00 00 0000 00 00 00，因为，因为 2轮轮DES的差分分析的差分分析31所以所以,在第轮后，所有盒都得到差分输在第轮后，所有盒都得到差分输入入，产生的差分输出也是，产生的差分输出也是；f(R,K)f(R,K)的输出在轮后是的输出在轮后是，差分输出则是，差分输出则是 (00 00 00 00(00 00 00 00,60

17、00 00 00),60 00 00 00)2轮轮DES的差分分析的差分分析-132假定：去掉初始置换假定：去掉初始置换IPIP和最终置换和最终置换FPFP。2 2轮的差分分析轮的差分分析共有个步骤。共有个步骤。Step 1Step 1:产生明文对产生明文对(P,PP,P)，使得，使得办法是，随机产生一个办法是，随机产生一个P P，将其与下述值进，将其与下述值进行异或得到行异或得到P P 2轮轮DES的差分分析的差分分析-233Step 2Step 2:对于产生的明文对对于产生的明文对(P,PP,P)，计算加密后产生密，计算加密后产生密文对文对(T,TT,T)（选择明文攻击）（选择明文攻击）S

18、tep 3Step 3:计算计算T=TTT=TT，检查结果是否等于检查结果是否等于如果不相等，就说明特征不符，这个明文对就不能用。如果不相等，就说明特征不符，这个明文对就不能用。重返第一步，产生新的明文对；重返第一步，产生新的明文对；如果相等，则特征相符，进入第四步如果相等，则特征相符，进入第四步2轮轮DES的差分分析的差分分析-334Step 4Step 4:因为因为S2,.,S8S2,.,S8的差分输入都为的差分输入都为，所以没有信，所以没有信息可以从息可以从S2S2K K,.,S8,.,S8K K得到。得到。在在S1S1的差分分布表中，的差分分布表中，0C E0C E有有14/6414/

19、64的概率，即只有的概率，即只有6464分之分之1414可以得到可以得到产生产生2轮轮DES的差分分析的差分分析-435这这14 14 个可能值可以通过把每个可能的个可能值可以通过把每个可能的S1S1K K 与相应与相应的的S1S1E E 和和S1S1 E E 的比特相异或来确定，计算的比特相异或来确定，计算S1S1的差分输出的差分输出S1S1O O，检查其是否等于，检查其是否等于E E把把S1S1K K 的这的这1414个值放进表中个值放进表中2轮轮DES的差分分析的差分分析-536Step 5Step 5:计算这些表的交集计算这些表的交集因为正确的密钥必定同时出现在每张表中因为正确的密钥必

20、定同时出现在每张表中如果有不止一个如果有不止一个S1S1K K值，就说明还需要更多的明文和值，就说明还需要更多的明文和密文差分对才能唯一确定密钥密文差分对才能唯一确定密钥S1S1K K，转到第一步，计，转到第一步，计算更多的数据算更多的数据需要的明文密文差分对的数量，大致等于使用的特需要的明文密文差分对的数量，大致等于使用的特征概率的倒数，本例中需要征概率的倒数，本例中需要6464/14 5/14 5对对如果只得到一个如果只得到一个S1S1K K ，就是正确的，转到第六步。，就是正确的，转到第六步。2轮轮DES的差分分析的差分分析-637Step 6Step 6:这个阶段，要恢复构成这个阶段，

21、要恢复构成S1S1K K的的6 6个比特。个比特。采用类似的特征，恢复第一轮中与采用类似的特征，恢复第一轮中与S2-S8S2-S8的输入相异的输入相异或的或的6 6比特密钥比特密钥Step 7Step 7:这个阶段已经有了构成这个阶段已经有了构成S1S1K K密钥的密钥的4848比特，等比特，等同于同于S1S1K K-S8-S8K K。其余的比特密钥，采用穷举方法在其余的比特密钥，采用穷举方法在6464个可能的值中个可能的值中搜寻搜寻密码分析的概率密码分析的概率38u 去掉第三步，假定在每一对密文中都出现一个特征去掉第三步，假定在每一对密文中都出现一个特征u 该特征出现的概率是该特征出现的概率

22、是1414/64 1=14/64/64 1=14/64u 所以，出错的概率是所以，出错的概率是50/64 50/64 对对u 正确的正确的S1S1K K 值不一定出现在每个表中，需要寻找的是值不一定出现在每个表中，需要寻找的是最常出现的最常出现的S1S1K K 值值u 正确值以正确值以14/64 14/64 出现在各表中，剩余的出现在各表中，剩余的6363个值以大致个值以大致等概的方式出现等概的方式出现已知明文攻击已知明文攻击-139前面一直假定前面一直假定,采用选择明文攻击，就是说，攻击者可以采用选择明文攻击，就是说，攻击者可以得到任意选择明文的密文得到任意选择明文的密文而已知明文攻击则是，

23、攻击者可以从大量的明密对的集合而已知明文攻击则是，攻击者可以从大量的明密对的集合中进行选择性分析中进行选择性分析假设，选择明文攻击需要假设，选择明文攻击需要m m对明密对应。已知对明密对应。已知对随机明密对，这是从对随机明密对，这是从对可能的明密文中选择出来的对可能的明密文中选择出来的已知明文攻击已知明文攻击-240u 每一对都有一个异或值，因为分组大小是每一对都有一个异或值，因为分组大小是6464，总共，总共就有就有2 26464种可能的明文异或值所以，有种可能的明文异或值所以，有对产生每个明文异或值对产生每个明文异或值u 特别是，有很大的概率，大致有特别是，有很大的概率，大致有m m对，每

24、一对都有对，每一对都有几个明文异或值需要进行差分分析几个明文异或值需要进行差分分析结论结论41改进后改进后42总结总结-143u DESDES降至降至6 6轮后，用轮后，用PCPC机采用选择明文攻击，可以在机采用选择明文攻击，可以在0.30.3秒秒内进行破解，使用的密文量有内进行破解，使用的密文量有240240；采用已知明文攻击需；采用已知明文攻击需要要2 23636密文密文u DESDES降至降至8 8轮后，用轮后，用PCPC机采用选择明文攻击，可以在机采用选择明文攻击，可以在2 2分钟分钟内进行破解，使用的密文量有内进行破解，使用的密文量有2 21414；采用已知明文攻击需要；采用已知明文

25、攻击需要2 23838密文密文u 整个整个DESDES的破解：有的破解：有2 23737次从次从2 24747的量中进行选择明文攻击，的量中进行选择明文攻击，分析分析2 23636密文密文u 上述结果，在密钥频繁变化，以及收集的数据是从不同的上述结果，在密钥频繁变化，以及收集的数据是从不同的密钥得到的清况下仍然成立密钥得到的清况下仍然成立总结总结-244u 这一努力，与密钥量大小无关，破解这一努力，与密钥量大小无关，破解5656比特密钥的比特密钥的DES需要的努力，与破解需要的努力，与破解1616个不同的个不同的4848比特密钥的比特密钥的DES所需所需要的几乎相同要的几乎相同u 差分密码分析证明了轮数，以及差分密码分析证明了轮数，以及S S盒的构造方法的重要性盒的构造方法的重要性u DES变化后比原变化后比原DES更容易分析，例如更容易分析，例如Schaumuller-Bich提出的提出的GDES(Generalized DES)方案很容易分析，只需方案很容易分析，只需要要6 6个密文，在不到个密文，在不到0.2秒的时间就可以破解秒的时间就可以破解总结总结-45DESDES的某些变的某些变化还可能造成化还可能造成灾难性后果灾难性后果