密码算法、协议分析攻击

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,破解技术（三）：密码算法、协议分析攻击,邱 卫 东,qiuwd,13585917063,上海交通大学信息安全工程学院,对称密码算法分析,非对称密码算法分析,密钥协商协议分析攻击,哈希函数分析攻击,主要内容,对称密码算法分析,方法一：,强力攻击（密钥空间穷搜索），以,DES,为例：,64,位密钥，有效密钥长度为,56-bit,密钥有,256 = 72,057,584,037,927,936 7.2,亿亿之多,强力搜索,( brute force search ),似乎很困难，,20,世纪,70,年代估计要,1000,2000,年,技术进步使穷举搜索成为可能,“,AES Encryption Implementation and Analysis,on Commodity Graphics Processing Units,”,CHES 2007, LNCS 4727, pp. 209226, 2007,Owen Harrison and John Waldron,“,Symmetric Key Cryptography on,Modern Graphics Hardware,”,ASIACRYPT 2007, LNCS 4833, pp. 249264, 2007,Jason Yang and James Goodman,1997,年,1,月,29,日，,RSA,公司发起破译,RC4,、,RC5,、,MD2,、,MD5,，以及,DES,的活动，破译,DES,奖励,10000,美金。明文是：,Strong cryptography makes the world a safer place.,结果仅搜索了,24.6%,的密钥空间便得到结果，耗时,96,天。,电子前沿基金会（,EFF,）在,1997,年开始研制自己的,DES,破解器。原始的计划中包括了很多,FPGA,芯片。一个,DES-,破解芯片需要花很多年破解密码，但是用,1000,个破解芯片来破解的话会节约数年时间。真正的,EFF,机器包括了,1500,个芯片。不到一年时间，这台机器证明了,DES,算法不再安全，以及制造这样一台机器也不是太贵。,太平洋标准时间,1998,年,7,月,13,日的早上,9,点钟，,EFF,的,DES,破解器开始破解。这台机器在,7,月,15,日下午,5,点,03,分成功破解密码。一共用了,56,个小时找到,56,位的密钥。当,EFF,的团队在,13,日早上开启机器，机器随后在,26,个主板上进行了,35868,次搜索。然后,EFF,团队在第二天的晚上为了对机器的软件进行部分优化而停止了搜索。随后，加快了机器的搜索速度。最终,DES,破解器一共搜索了,1,7902,8066,6919,7312,次，才找到正确的密码。这差不多是所有密钥可能性的四分之一,(24.8%),。,1999,年在超级计算机上只要,22,小时,!,Ciphertext-only attack,（唯密文攻击）,deduce the decryption key or plaintext by only observing ciphertext.,Known-plaintext attack,（已知明文攻击）,using a quantity of plaintext and corresponding ciphertext.,Chosen-plaintext attack,（选择明文攻击）,chooses plaintext and is then given corresponding ciphertext.,Adaptive chosen-plaintext attack,（自适应选择明文攻击）,chosen-plaintext attack where the choice of plaintext may depend on the ciphertext received from previous requests.,Chosen-ciphertext attack,（选择密文攻击）,selects the ciphertext and is then given the corresponding plaintext.,Adaptive chosen-ciphertext attack,（自适应选择密文攻击）,chosen-ciphertext attack where the choice of ciphertext may depend on the plaintext received from previous requests.,密码分析攻击简单分类,方法二：,差分密码分析,Differential Cryptanalysis,历史,1990,年，以色列密码学家,Murphy,、,Biham,和,Shamir,首次提出用差分密码分析攻击分组密码和散列函数，是第一种可以以少于,2,55,的复杂性对,DES,进行破译的方法。,Differential Cryptanalysis compares two related pairs of encryptions.,至今最有效的攻击迭代密码的方法,差分密码分析攻击方法,with a known difference in the input, searching for a known difference in output when same subkeys are used.,两个报文的异或,m=m,m,，中间过程有,m,i,=m,i,m,i,，则,以选择明文攻击为例,差分密码分析：基本思想,通过分析明文对的差值对密文对的差值影响来恢复某些密钥比特,未破译,16,轮,DES,破译轮数低的,DES,很有效,利用差分攻击来破译,DES,必须要收集到,247,个明文及其相对应的密文，从而使计算复杂度从暴力破解的,256,显著,地下降到了,247,8 rounds: 214 chosen plaintexts12 rounds: 231 chosen plaintexts16 rounds: 247 chosen plaintexts,推广方法：截断差分密码分析、高阶差分密码分析、不可能差分密码分析等,差分密码分析：攻击,DES,或者是在某个集合中，通过多组明密文对即可恢复出密钥,首先说明：,1.,对于,DES,的分析，可忽略初始置换,IP,和,IP,-1,。,2.,对,DES,限制到,n,轮（,n=16,）。,3.,以,L,0,R,0,为明文，且以,L,n,R,n,作为,n,轮,DES,的密文。4. 对两个明文,L,0,R,0,和,L,0,*,R,0,*,，,规定它们的异或值为,L,0,R,0, =L,0,R,0,L,0,*,R,0,*,，,整个讨论都使用撇号（,）表示两个比特串的异或值。,定义,1,：设,S,j,是一个特定的,S,盒（1=,j=8),，,考虑长度为6的比特串的一个有序对（,B,j,B,j,*,）,我们说,S,j,的输入异或是,B,j,B,j,*,输出异或是,S,j,(B,j,),S,j,(B,j,*,),注：输入异或是长度为6的比特串，输出异或是长度为4的比特串,。,定义2：对任何一个,B,j,(Z,2,),6,= a,0,a,1,a,2,a,3,a,4,a,5,|a,j, 0,1,，定义集合,(B,j,),是由输入异或为,B,j,的有序对,(B,j,B,j,*,),组成。,注,：,1,*,.,对比特串,B,j,来说，集合,(B,j,),包含,2,6,=64,个有序对元素。有 ,(B,j,)=(B,j,B,j,B,j,)| B,j,(Z,2,),6, 2,*,.,对,(B,j,),中的每一对，我们能计算出,S,j,的输出异或，同时用表列出结果的分布。 有,64,个输入异或，它们经,S,j,的输出分布在,2,4,=16,种可能值之中，这些分布的非均匀性，,就是攻击,DES,的基础。,3,*,.,表示一个,S,盒的所有可能对的输入异或和输出异或分布的表称为该,S,盒的差分分布表。,例子,1,。若考虑第一个,S,盒,S1,，输入异或为,B,1,=110100,那么： ,(B,1,)= (110100)=(000000,110100), (000001, 110101), ., (111111, 001011),对集合,(B,1,),中的每一对，计算,S,1,盒的输出异或。 例如,S,1,(000000)=E,16,=1110 S,1,(110100)=9,16,=1001,所以,(000000,110100),的输出异或是,0111,。计算,(B,1,)= (110100)= ,（,34x,）中所有,64,对的输出异或，得输出异或分布表：,+,0,个,8,个,16,个,6,个,2,个,0,个,0,个,12,个,1000 1001 1010 1011 1100 1101 1110 1111,6,个,0,个,0,个,0,个,0,个,8,个,0,个,6,个,0000 0001 0010 0011 0100 0101 0110 0111,表一,注意！,16,个可能,输出异或中，仅有,8,种出现。它们的分布是不均匀的。,为描述这类分布如何产生的，先表述一些进一步的概念。,表二,定义,3,：对长度为,6,的比特串,B,j,和长度为4的比特串,C,j,(1=j=8),定义,IN,j,(B,j,C,j,)=B,j,（,Z,2,）,6,|S,j,(B,j,),S,j,(B,j,B,j,)=C,j, N,j,(B,j,C,j,)=|IN,j,(B,j,C,j,)|,注：,1,*,.,这里,N,j,(B,j,C,j,),用来表示输入对,异或值为,B,j,的数目，这些输入对经过特定,S,盒的,S,j,输出异或值均为,C,j,。 2,*,.例子1中的输出异或分布表,表示,N,1,（,110100,，,C,1,）,(,其中,C,1,(Z,2,),4,),，表示,对,S,盒,S,1,来说，它的输入异或为（110100）且相应的输出异或为,C,1,的,输入对数目,分布情况。 3,*,. 集合,IN,1,（,110100,，,C,1,）将,输入异或为（110100）的所有,2*,中的数目列举出来，,见下页,：,表三,考虑一般的情况：对于,DES,的,8,个,S,盒的每一个盒有,64,种可能的输入异或，于是可算出有,512,个分布。回忆,DES,：知在第,i,轮中,S,盒的输入为,B=E,J,，,其中,E=E,（,R,i-1,）,是,R,i-1,的扩展，,J=K,i,是由第,i,轮的密钥比特组成。现在对所有8个,S,盒的输入异或计算如下：,B =B,B,*,=(E,J),(E,*,J)= E,E,*,=E,由此可见，输入异或不依赖于密钥比特,J.,这也说明,E=B,将,B,，,B*,，,E,，,E*,和,J,，,J*,均写成,8,个,6,比特串的并：,B=B,1,B,2,B,3,B,4,B,5,B,6,B,7,B,8,；,B*=B*,1,B*,2,B*,3,B*,4,B*,5,B*,6,B*,7,B*,8,E=E,1,E,2,E,3,E,4,E,5,E,6,E,7,E,8,；,E*=E*,1,E*,2,E*,3,E*,4,E*,5,E*,6,E*,7,E*,8,J=J,1,J,2,J,3,J,4,J,5,J,6,J,7,J,8,；,J*=J*,1,J*,2,J*,3,J*,4,J*,5,J*,6,J*,7,J*,8,假设我们知道,E,j,和,E,j,*,的值（对某一个,j,1= j=8,）,和,Sj,的输出异或值,C,j,=S,j,(B,j,),S,j,(B,j,*,),那么必有,E,j,J,j,=B,j,IN,j,(B,j,C,j,)=,IN,j,(E,j,C,j,),，,B,j,=E,j,=E,j,E,j,*,我们的目的是要破译密钥,J,的部分比特串,J,j,。定义测试集合,Test,j,定义,4,（,Test,j,）,:,设,E,j,和,E,j,*,是长度为,6,的比特串，,C,j,是长度为,4,的比特串，定义,Test,j,(E,j,E,j,*,C,j,)=B,j,E,j,=J,j,|B,j,IN,j,(E,j,C,j,),这里,B,j,E,j,是,J,j,的形式，,E,j,是固定的,E,j,=,B,j,=E,j,E,j,*,我们,有,定理,1,：,假设,E,j,和,E,j,*,是,S,盒,S,j,的两个输入，,S,j,的输出异或为,C,j,，记,E,j,=E,j,E,j,*,，那么密钥比特,J,j,出现在集合,Test,j,(E,j,E,j,*,C,j,),之中。,注：,在集合,Test,j,(E,j,E,j,*,C,j,),中，,J,j,的正确值一定是,N,j,(E,j,C,j,)or,N,j,(B,j,C,j,),个,可能值中的一个。,例子,2,：假设,E,1,=000001,，,E,1,*,=110101,和,C,1,=1101,，因为,N,1,（,110100,，,1101,）,=8,，（由表一,or,表二），可知集合,Test,1,(000001,，,110101,，,1101,）中，刚好有,8,个比特串：可从表三中得到：,IN,1,（,110100,，,1101,）,=000110,，,010000,，,010110,，,011100,，,100010,，,100100,，,101000,，,110010,分别计算它们与,E,1,=000001,的异或得：,Test,1,(000001,110101,1101)=000111,010001,0101111,011101,100011,100101,101001,110011,如果有两个这样的三元组,E,1,，,E,1,*,，,C,1,，那么就可得到,J,1,中密钥比特可能值的第,2,个集合,Test,1,(2),(E,1,E,1,*,C,1,),。易见密钥比特,J,j,Test,1,Test,1,(2),!,自然这样的三元组如果更多些，定出,J,j,是肯定的。关于这方面的计算，可想出若干技巧。,攻击,3,轮,DES,Li=Ri-1,Ri=Li-1,f(Ri-1,Ki),R,1,=L,0,f(R,0,K,1,),R,2,=L,1,f(R,1,K,2,),R,3,=L,2,f(R,2,K,3,),明文,P(64bits),F,F,F,+,L,0,+,+,密文,R,0,K,1,K,2,K,3,L,1,=R,0,L,2,=R,1,L,3,=R,2,3,轮,DES,图,A,B,C,DES,的,F,函数,输入,32,比特,E,48bits,E,1,|E,2,|E,3,|E,4,|E,5,|E,6,|E,7,|E,8,子密钥,J,1,|J,2,|J,3,|J,4,|J,5,|J,6,|J,7,|J,8,+,B,B,1,B,2,B,3,B,4,B,5,B,6,B,7,B,8,S,1,S,2,S,3,S,4,S,5,S,6,S,7,S,8,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,P,Output(32bits),我们对,3,轮作选择明文攻击。用明文对和相应的密文对开始我们的分析：明文对为：,L,0,R,0,; L,0,*,R,0,*,密文对为：,L,3,R,3,; L,3,*,R,3,*,。有表达式：,R,3,=L,2,f(R,2,K,3,)=R,1,f(R,2,K,3,) =L,0,f(R,0,K,1,) f(R,2,K,3,)R,3,*,可用类似的方法得到：,R,3,*,=L,0,*,f(R,0,*,K,1,) f(R,2,*,K,3,),于是有,R,3,=L,0, f(R,0,K,1,) f(R,0,*,K,1,) f(R,2,K,3,) f(R,2,*,K,3,),假设选择了明文，使,R,0,=R,0,*,此时,R,0,=000,则,f(R,0,K)=f(R,0,*,K),，所以,R,3,=L,0, f(R,2,K,3,) f(R,2,*,K,3,),由于,R,3,可从两个密文,R,3,R,3,*,计算出，可知,R,3,和,L,0,已知。有：,f(R,2,K,3,),f(R,2,*,K,3,)=R,3, L,0,知,f(R,2,K,3,)=P(C),和,f(R,2,*,K,3,)=P(C,*,),其中,C,和,C,*,分别表示,8,个,S,盒的两个输出。而,P,是固定的，为公开已知的置换，因此,P(C) P(C,*,)=P(C,C,*,)=R,3, L,0,由此可知,C=C C,*,=P,-1,(R,3, L,0,).,为,3,轮中,8,个,S,盒的两个输出异或。,另外，,R,2,=L,3,和,R,2,*,=L,3,*,是已知的（它们是密文的一部分），因此，可用公开已知的扩展函数,E,计算,E=E(R,2,)=E(L,3,),和,E,*,=E(R,2,*,)=E(L,3,*,),对第三轮说来，它们是,S,盒的输入。于是可由,E,，,E,*,和,C,。象前面的例子那样对,J,1,，,J,2,，,J,3,，,J,4,，,J,5,，,J,6,，,J,7,，,J,8,中密钥比特可能值，着手构造集合,Test,1,Test,2, Test,8,。由它们来确定第三轮密钥,K,3,中的,48bits,。,56bits,密钥中剩下的,8,比特可通过穷举,2,8,=256,种可能来确定。,3,轮,DES,的差分攻击模式：,输入：,L,0,R,0,L,0,*,R,0,*,L,3,R,3,和,L,3,*,R,3,*,，其中,R,0,=R,0,*,1.,计算,C,=P,-1,(R,3,L,0,)2.,计算,E=E(L,3,),和,E,*,=E(L,3,*,),3. For j=1 to 8 do,计算,Test,j,(E,j,E,j,*,C,j,),例子,3,。我们有如下三组明密文对，并有固定的异或值。用相同的密钥进行加密。为简单用,16,进制表示,.,明文密文,748502CD3845109703C70306D8A09F1038747564 3845109778560A0960E6D4CB48691102 6ACDFF3145FA28BE5ADC730375BD31F6ACDFF31134F7915AC253457357418DA013FEC86D8A31B2F28BBC5CF12549847 013FEC860F317AC2B23CB944,对第一组，可计算,S,盒的输入（对第三轮），它们是,E=E(L,3,)=0000000001111110000011101 00000000110100000001100E,*,=E(L,3,*),=10111111000000101010110000 0001010100000001010010,还可算出,S,盒的输出异或为：,C,=C,C,*,=P,-1,(R,3, ,L,0,)=10010110010111010101101100111,对第二组，第二组给出相同的计算，结果（略）。我们给出八个计数器阵列，每个阵列为,16*4,。这样按书写方式排有,64,个位置：,0,1,2,63,。在第一组中，我们有,E,1,=101111,和,C,1,=1001,集合,IN,1,(101111,1001)=000000,000111,101000,101111,因为,E,1,=000000,，,E,1,*=101111,，有,J,1,Test,1,(E,1,，,E,1,*,，,C,1,）,=Test,1,（,000000,101111,1001)= 000000, 000111,101000,101111,将其中,6bits,串用,2,进制数表示成对应,J1,阵列中的位置数,0,7,40,47,对应于,000000,000111,101000,101111,相当于在阵列表的空位的相应位置增值,1 J,1,对三组算得的三个集合,Test,1,(1),Test,1,(2),Test,1,(3),。它们中的元素对应的数增值,J,1,位置处的,1,个单位数。于是算得,J,1,=47=101111,，类似地方法定出,J,2,=000101,，,J,3,=010011,，,J,4,=0000000,，,J,5,=011000,，,J,6,=000111,，,J,7,=000111,，,J,8,=110001,注：,1,*,.,差分攻击技术还可用于,6,轮,DES,，对,8,轮的,DES,需,2,14,个组选择明文。现在对,16,轮,DES,也是相当有效的。见,:,。,2,*,.,对其它体制的攻击，例,Feal,LOKI,REDOC-II,，也是有效的。,是,1993,年提出的另一种统计攻击，基于找到,DES,中进行变换的线性近似，可以在有,2,47,个已知明文的情况下破译,DES,密钥,基本,思想,一种已知明文攻击方法,基本思想是通过寻找一个给定密码算法的有效线性近似表达式来破译密码算法。,可用,2,47,个已知明文,破译,16,轮的,DES,某些情况下还能够进行唯密文攻击,方法三：,线性密码分析,Linear Cryptanalysis,差分密码分析、线性密码分析技术改善了破译速度，降低了破译计算复杂度，但仍然不够理想,新一代密码分析技术：基于物理特性的分析技术,电压分析技术,电磁辐射分析技术,时间分析技术,高阶差分分析技术,汉明差分分析技术,例子：智能卡加密的能量分析、定时攻击：利用半导体逻辑电路和密码器件的性能特征，通过检测器件的电子活动，运用先进的物理统计方法确定器件上的秘密信息，如密钥和个人身份信息等,方法四：,边界信道攻击,能量分析,Encryption/Decryption,Secret key K,input,output,Power,Have access to power supply?,Power Analysis,Difference caused by jump instruction,参考书籍：,分组密码的攻击方法与实例分析，李超，科学出版社，,2010.5,在公钥密码体制中，攻击者拥有公钥，可以随便选择明文进行加密，攻击者还有机会获得密文，而且还可能利用各种途径来获得解密，为此，公钥密码体制应该不会泄露其他密文的的明文信息，这就要求该密码体制能抗选择密文攻击,抗选择密文攻击密码体制是一种安全性很高的体制。现在它已是被密码学家们普遍接受的概念，研究表明，利用抗选择密文攻击密码体制，可以设计许多安全强度很高的重要的密码协议,密钥传输，密钥交换，公平交换协议等等,Bellare,和,Rogaway,提出的,OAEP,（,1994,）体制就成为,SET,协议的新的加密标准,抗选择密文攻击是当今公钥加密侯选标准的最重要的要求之一，,2004,年的最新的几个候选标准的原型就是几个重要的抗选择密文攻击公钥加密密码方案,公钥密码算法分析,二,公钥密码体制按照可能的攻击目标，可以分为：,单向性（,OW,）安全：由密文不能恢复相应的明文,不可区分性（,IND,）安全：对已知给定的的两个明文，加密者随机的选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密,非延展性（,NM,）安全：攻击者无法构造与已给密文相关的新密文,以上安全性概念依次加强：,NM,比,IND,强，,IND,比,OW,强,不可区分性,(IND),Attacker,Challenger,M,0, M,1,b,0,1,Attacker wins if b=b,C=E(M,b,),b,R,0,1,Challenge,Decryption oracle,C,按照可能的攻击模型可分为：,选择明文（,CPA,）攻击：攻击者可以先适应性选择明文，获得相应的密文,非适应性选择密文（,CCA1,）攻击：攻击者除了可以适应性选择明文攻击外，在给定,Challenge,密文前，还可以选择密文获得相应的解密,适应性选择密文（,CCA2,）攻击：攻击者的唯一限制就是不可以直接用,Challenge,密文获得相应的明文，但还可以在给定,Challenge,密文后，选择密文获得相应的解密,同时考虑攻击目标和攻击模型，可以获得不同的安全，其中最重要的是,IND-CCA2,和,NM-CCA2,安全，而二者被证明是等价的，所以加密中通常所说的选择密文安全是指,IND-CCA2,安全,方法一：,强力攻击（密钥空间穷搜索），不可能，密钥长，以,RSA,为例：至少,1024,比特,64,位密钥，有效密钥长度为,56-bit,密钥有,2,56,= 72,057,584,037,927,936 7.2,亿亿之多 那么,1024,呢？,2048,？,强力搜索,( brute force search ),到,21,世纪的今天也非常困难,方法二：,加密方式弱点攻击，仍然以,RSA,为例,RSA,直接明文加密方式,public key:,(N,e),Encrypt:,C = M,e,(mod N),private key:,d,Decrypt:,C,d,= M,(mod N),(,M, Z,N,*,),不安全的加密模式,- RSA,陷门置换不再成为加密系统,-,不满足安全的基本定义,RSA,直接明文加密方式的简单攻击,Session-key K,：,64 bits. View K, 0,2,64,中间窃听者,:,C = K,e,(mod N),.,假设,K = K,1,K,2,where,K,1, K,2, 2,34,. (prob.,20%)Then:,C/K,1,e,= K,2,e,(mod N),构建表格,:,C/1,e, C/2,e, C/3,e, , C/2,34e,. time: 2,34,For,K,2,= 0, 2,34,test if,K,2,e,is in table. time: 2,34,34,攻击复杂度,:,2,40,Y=x,3,mod (n1*n2*n3),n1,n2,n3,一般互素，,x,3,Y,是一个,Hash,函数，,X,和,Y,都是有限的，记,|X|=m,，,|Y|=n,，在,m2n,时显然至少有,n,个碰撞，如何找到碰撞？很自然的我们可以选取,k,个不同的明文,x,1,，,x,2,，,x,k,X,计算,y,i,H,（,x,i,），,1ik,，然后判断是否出现碰撞。下面计算这种方法找到碰撞概率的下界，这个下界只与,k,和,n,相关，而不依赖于,m,Hash,函数攻击（一）,我们假定对任意,yY,，,|H,-1,（,y,）,|m/n,，这是合理的假设，如果原像集个数不是近似相等的，则找到碰撞的概率会增大。由原像集个数近似相等且,x,i,随机选择，可将,y,i,H,（,x,i,）,（,1ik,）,视作,Y,中的随机元素,。考虑没有碰撞，即,y,i,（,1ik,）各不相同的概率为：,因此碰撞的概率,略去,k,项有：,取 有,这表明只要取 个随机明文就能以,50%,的概率找到碰撞。例如散列值为,64,位，则,n,2,64,，只需选取,2,32,（约,40,亿）个随机明文作,Hash,就可以,50%,概率找到碰撞，这在一般的计算机上也只需数分钟的时间。因此目前的,Hash,值长度至少在,128,位以抵抗生日攻击。,Hash,函数攻击（二）,王晓云对,MD5,的攻击,2005,年欧密会上王晓云教授的论文宣布攻破,MD4,、,MD5,、,sha-0,等,Hash,函数，引起轰动。在论文,How to Break MD5 and Other Hash Functions,中说明了对,MD5,的攻击,王晓云采用整数模减的差分方法，不同于一般异或的差分，目的是在,MD5,初始值：,寻找两个,1024bits,的消息组合（,M,0,，,M,1,）和（,M,0,，,M,1,）它们的,Hash,值相同。步骤如下：,第一步：选择两个,512bits,的消息,和,表示两个消息分组的差异,模减表示第,i,个字（,32bits,）不同,做一个带两次迭代的差分碰撞：,其中,其中 表示第,5,12,15,的位置上是非零输入，之所以这样选择是要保证,MD5,的第三轮和第四轮能以较高的概率产生差分， 还要保证能产生输出差分， 是第一轮迭代后的,4,个链接值的差分。随机选择消息,第二步计算