差分密碼分析-年

1、1差分密碼分析差分密碼分析電子科技大學(xué)電子科技大學(xué)范明鈺范明鈺提要提要2u簡(jiǎn)介簡(jiǎn)介u技術(shù)要點(diǎn)技術(shù)要點(diǎn)uDESDES框圖框圖u差分分析原理差分分析原理uS S盒的非均勻性，盒的非均勻性，S1S1的差分分布的差分分布u2 2輪、輪、4 4輪、輪、8 8輪差分分析輪差分分析u已知明文攻擊已知明文攻擊u總結(jié)總結(jié)簡(jiǎn)介簡(jiǎn)介-3u 差分密碼分析是一種破解某些類(lèi)型的密碼系統(tǒng)的差分密碼分析是一種破解某些類(lèi)型的密碼系統(tǒng)的方法方法u 顯然，設(shè)計(jì)顯然，設(shè)計(jì)DESDES的的IBMIBM研究人員知道有關(guān)差分密研究人員知道有關(guān)差分密碼分析的情況。碼分析的情況。u 當(dāng)密碼分析人員可以進(jìn)行選擇明文分析時(shí)，差分當(dāng)密碼分析人員可以

2、進(jìn)行選擇明文分析時(shí)，差分密碼分析十分有效。密碼分析十分有效。u 已知明文的差分密碼分析也是可行的，但是要求已知明文的差分密碼分析也是可行的，但是要求已知明密文的量很大已知明密文的量很大簡(jiǎn)介簡(jiǎn)介-24u這一方法搜索明密文對(duì)，根據(jù)它們的差分這一方法搜索明密文對(duì)，根據(jù)它們的差分的恒定性，研究密碼系統(tǒng)的差分現(xiàn)象的恒定性，研究密碼系統(tǒng)的差分現(xiàn)象uDESDES中兩個(gè)元素中兩個(gè)元素P1P1和和P2P2的差分定義為的差分定義為P1P2 (P1P2 (比特異或操作比特異或操作) )u差分在不同的密碼系統(tǒng)中有不同的定義差分在不同的密碼系統(tǒng)中有不同的定義u差分密碼分析可用于弱輪函數(shù)的迭代密碼差分密碼分析可用于弱輪函

3、數(shù)的迭代密碼（如（如FeistelFeistel型密碼）型密碼）技術(shù)要點(diǎn)技術(shù)要點(diǎn)51. 1.將密文的差分，看作是相應(yīng)明文差分的函數(shù)將密文的差分，看作是相應(yīng)明文差分的函數(shù)2. 2.尋找大概率的差分輸入（稱(chēng)為特征），可以尋找大概率的差分輸入（稱(chēng)為特征），可以用于追蹤幾輪用于追蹤幾輪3. 3.計(jì)算密鑰的概率，定位最可能的密鑰計(jì)算密鑰的概率，定位最可能的密鑰DES的框圖的框圖6DES的單輪結(jié)構(gòu)的單輪結(jié)構(gòu)7DES的擴(kuò)展變換的擴(kuò)展變換8符號(hào)定義符號(hào)定義9uP P 表示明文表示明文，T T 表示密文表示密文u ( (P, PP, P ) )表示明文對(duì)，其異或后得到特定的值：表示明文對(duì)，其異或后得到特定的值：

4、P,P,使得使得 P = P PP = P P u ( (T, TT, T ) ) 表示密文對(duì)，其異或后得到特定的值表示密文對(duì)，其異或后得到特定的值TT，使得，使得 T = T TT = T T u 帶撇的值總是差分的，帶撇的值總是差分的，PP , ,TT, , aa, , AA。例例如，如，a= a aa= a a 差分分析原理差分分析原理- -110uDES DES 的設(shè)計(jì)要求之一是確保盡可能的分布均勻的設(shè)計(jì)要求之一是確保盡可能的分布均勻u例如，明文或密鑰的例如，明文或密鑰的1 1比特變化，將導(dǎo)致比特變化，將導(dǎo)致6464比特比特的密文中大約的密文中大約3232比特的看起來(lái)是不可預(yù)測(cè)和隨比特

5、的看起來(lái)是不可預(yù)測(cè)和隨機(jī)的變化機(jī)的變化差分分析原理差分分析原理- -211u以色列研究人員以色列研究人員Eli Eli BihamBiham 和和 AdiAdi ShamirShamir 在在19901990年觀察到，對(duì)于固定的密鑰，年觀察到，對(duì)于固定的密鑰，DESDES的差分并不的差分并不呈現(xiàn)偽隨機(jī)現(xiàn)象呈現(xiàn)偽隨機(jī)現(xiàn)象u這一現(xiàn)象是，對(duì)于固定明文這一現(xiàn)象是，對(duì)于固定明文P P 和和P P 的異或的異或PP，T=TTT=TT 不是均勻分布的不是均勻分布的u反過(guò)來(lái)，兩個(gè)均勻分布的隨機(jī)數(shù)的異或，結(jié)果反過(guò)來(lái)，兩個(gè)均勻分布的隨機(jī)數(shù)的異或，結(jié)果本身應(yīng)該是均勻分布的。本身應(yīng)該是均勻分布的。S-Box是非差分均

6、勻的是非差分均勻的12u如果如果S S盒的輸入是均勻分布的隨機(jī)數(shù)，其輸出也盒的輸入是均勻分布的隨機(jī)數(shù)，其輸出也應(yīng)該是均勻分布的隨機(jī)數(shù)應(yīng)該是均勻分布的隨機(jī)數(shù)S-Box的差分均勻性的差分均勻性- -113u假設(shè)假設(shè)5656-bite-bite的密鑰是按照均勻分布的原則選擇的的密鑰是按照均勻分布的原則選擇的，則對(duì)于任意輪的任意，則對(duì)于任意輪的任意S S盒的輸入，在其盒的輸入，在其6464比特比特的可能取值上也是均勻分布的的可能取值上也是均勻分布的u任意輪的任意任意輪的任意S S盒的輸出，在其盒的輸出，在其1616個(gè)可能的值個(gè)可能的值( (0- 0-F F) )上也是均勻分布的。每個(gè)上也是均勻分布的。

7、每個(gè)S S盒中有盒中有4 4行，每個(gè)行，每個(gè)( (0- 0-F F) )值在值在S S盒中出現(xiàn)盒中出現(xiàn)4 4次，每行輸出一個(gè)值次，每行輸出一個(gè)值S-Box的差分均勻性的差分均勻性- -214u 考慮一個(gè)考慮一個(gè)S-boxS-box的差分現(xiàn)象：的差分現(xiàn)象：u 輸入：共有輸入：共有64642 2 = = 4096 4096 種可能的輸入種可能的輸入( (x, xx, x ) )值對(duì)，因?yàn)閷?duì)值對(duì)，因?yàn)閷?duì)于輸入于輸入S S盒的盒的6 6比特的比特的x, xx, x ，以及以及x= x xx= x x ，每一個(gè)取每一個(gè)取值都在值都在6464比特的可能值上變化比特的可能值上變化u 而其而其4 4比特輸出值

8、，比特輸出值，y=S(x), yy=S(x), y = S(x= S(x ) )，以及以及y=y yy=y y =S(x) S(x=S(x) S(x ) ) 每個(gè)取值都在其每個(gè)取值都在其1616個(gè)可能的值上變化個(gè)可能的值上變化u 差分輸出差分輸出yy的分布情況，可以針對(duì)的分布情況，可以針對(duì)8 8 個(gè)個(gè)S S 盒中的每一個(gè)盒中的每一個(gè)S S盒來(lái)計(jì)算，計(jì)算在輸入盒來(lái)計(jì)算，計(jì)算在輸入( (x, xx, x ) ) 在在4096 4096 個(gè)可能值上變化時(shí)，個(gè)可能值上變化時(shí)，每個(gè)每個(gè)y y值出現(xiàn)的次數(shù)值出現(xiàn)的次數(shù)S1 的差分分布表的差分分布表- -115.=2=26 6-1 -1出出現(xiàn)現(xiàn)的的次次數(shù)數(shù)S

9、1 的差分分布表的差分分布表- -216u 6 6比特的差分輸入比特的差分輸入xx有有6464個(gè)值：個(gè)值：00-3F00-3F(16(16進(jìn)制，進(jìn)制，1010進(jìn)制是進(jìn)制是0-630-63) )u 4 4比特的差分輸出比特的差分輸出yy有有1616個(gè)值：個(gè)值：0-F0-F(16(16進(jìn)制，進(jìn)制，1010進(jìn)制是進(jìn)制是0-150-15) )u 每一行的總和是每一行的總和是6464，因?yàn)槊總€(gè)差分輸入因?yàn)槊總€(gè)差分輸入xx針對(duì)針對(duì)40964096個(gè)個(gè)( (x, xx, x ) )對(duì)中的對(duì)中的6464個(gè)個(gè)u 可以看到：第一行除第一列外全為可以看到：第一行除第一列外全為0 0，因?yàn)楫?dāng)，因?yàn)楫?dāng)x= x xx=

10、x x = 0 = 0，同樣的輸入出現(xiàn)了兩次，因此其輸出同樣的輸入出現(xiàn)了兩次，因此其輸出y=y yy=y y = 0= 0S1 的差分分布表的差分分布表- -317u 后面的行：后面的行：u 例如，當(dāng)例如，當(dāng) x= 01 x= 01 時(shí)時(shí), , 6 6個(gè)可能的個(gè)可能的yy中有中有5 5個(gè)值個(gè)值: :0, 1, 2, 4, 0, 1, 2, 4, 8 8呈現(xiàn)呈現(xiàn)0 0可能次數(shù)，就是說(shuō)不出現(xiàn)?？赡艽螖?shù)，就是說(shuō)不出現(xiàn)。uA A 出現(xiàn)的概率是出現(xiàn)的概率是16/6416/64u 9 9 和和C C 出現(xiàn)的概率是出現(xiàn)的概率是10/6410/64u 這就是說(shuō)，這就是說(shuō)，S1S1呈現(xiàn)出很強(qiáng)的不均勻分布呈現(xiàn)出很

11、強(qiáng)的不均勻分布u 這種差分不均勻性對(duì)于所有的這種差分不均勻性對(duì)于所有的S S盒盒S1, S2, . . . , S8S1, S2, . . . , S8都有體都有體現(xiàn)現(xiàn)S1 的差分分布表的差分分布表- -418u 考慮輸入異或值為考慮輸入異或值為3434時(shí)，可能的輸出異或是：時(shí)，可能的輸出異或是：u 輸出：輸出：u 出現(xiàn)次數(shù)：出現(xiàn)次數(shù)：u 其中：其中：34344 4有兩種可能，這種輸入對(duì)是成雙有兩種可能，這種輸入對(duì)是成雙的，即：的，即：( (, , ) )和和 ( (, , ) )S1 的差分分布表的差分分布表- -19對(duì)對(duì)S1S1構(gòu)建差分表，發(fā)現(xiàn)當(dāng)構(gòu)建差分表，發(fā)現(xiàn)當(dāng)輸入是輸入是13 13 和

12、和27 27 時(shí)時(shí)( (只看后只看后面的面的6 6位位) )：S1 的差分分布表的差分分布表- -20列出列出S1S1中輸中輸入異或值為入異或值為3434的可能的的可能的輸入值：輸入值：確定密鑰的原理確定密鑰的原理- -21u 假設(shè)已知假設(shè)已知S1S1的兩個(gè)輸入是的兩個(gè)輸入是0101和和3535，其異或的結(jié)果是，其異或的結(jié)果是3434，經(jīng)過(guò)經(jīng)過(guò)S1S1之后輸出異或的結(jié)果是之后輸出異或的結(jié)果是D D。查。查S1S1的差分分布表，的差分分布表，得到輸入異或?yàn)榈玫捷斎氘惢驗(yàn)?434，輸出異或?yàn)?，輸出異或?yàn)镈 D時(shí)，可能的輸入：時(shí)，可能的輸入：確定密鑰的原理確定密鑰的原理- -22實(shí)際上，輸入異或的結(jié)

13、果是實(shí)際上，輸入異或的結(jié)果是3434，與密鑰無(wú)關(guān)，與密鑰無(wú)關(guān)，這是因?yàn)椋哼@是因?yàn)椋阂驗(yàn)橐驗(yàn)樗运源_定密鑰的原理確定密鑰的原理- -23這樣就得到：這樣就得到：所以，可能的密鑰就是所以，可能的密鑰就是確定密鑰的原理確定密鑰的原理- -24此外，假設(shè)已知此外，假設(shè)已知S1S1的兩個(gè)輸入是的兩個(gè)輸入是2121和和1515，它們異或后的結(jié)，它們異或后的結(jié)果是果是3434，輸出異或后的結(jié)果是，輸出異或后的結(jié)果是3 3 。查。查S1S1的差分分布表，得的差分分布表，得到輸入異或?yàn)榈捷斎氘惢驗(yàn)?434，輸出異或?yàn)?，輸出異或?yàn)? 3時(shí)，可能的輸入：時(shí)，可能的輸入： 。確定密鑰的原理確定密鑰的原理- -25這

14、樣就可以從這樣就可以從得到可能的密鑰值得到可能的密鑰值確定密鑰的原理確定密鑰的原理- -26而正確的密鑰值必定同時(shí)出現(xiàn)在兩個(gè)集合而正確的密鑰值必定同時(shí)出現(xiàn)在兩個(gè)集合因此可以確定密鑰是在因此可以確定密鑰是在 中的一個(gè)。中的一個(gè)。要確定到底是哪一個(gè)，需要知道更多的輸入輸要確定到底是哪一個(gè)，需要知道更多的輸入輸出異或?qū)?。出異或?qū)?。多輪多輪DES的特征的特征27差分輸入具有很高的或然性，可以直接追蹤到多輪的差分輸入具有很高的或然性，可以直接追蹤到多輪的情況，觀察到：情況，觀察到： E擴(kuò)展中的異或值是線性的：擴(kuò)展中的異或值是線性的：異或值與密鑰是無(wú)關(guān)的：異或值與密鑰是無(wú)關(guān)的：2輪輪DES的特征的特征-1

15、-1282輪輪DES的特征的特征-2-229在第一輪中，輸入到函數(shù)在第一輪中，輸入到函數(shù)f f的差分結(jié)果是的差分結(jié)果是 a a = 60 00 00 00= 60 00 00 00經(jīng)經(jīng)f f 中的擴(kuò)展變換后，中的擴(kuò)展變換后， 把這部分放進(jìn)了每個(gè)把這部分放進(jìn)了每個(gè)S S盒的中間盒的中間4 4個(gè)比特，順序是個(gè)比特，順序是 S1S1：6 = 01106 = 0110 S2 S2：0 = 00000 = 0000 S3, . . . , S8 S3, . . . , S8 等等等等因?yàn)樗羞吘壉忍囟际且驗(yàn)樗羞吘壉忍囟际? 0，所以，所以S1S1是唯一的得到非是唯一的得到非0 0差分差分輸入的輸入的S

16、 S盒。盒。S1S1的差分輸入是的差分輸入是 0 0110 0 = 0C 0 0110 0 = 0C 而其他所有盒而其他所有盒S2, . . . , S8S2, . . . , S8的差分輸入都是的差分輸入都是2輪輪DES的特征的特征-3-330察看察看S1S1的差分分布表，發(fā)現(xiàn)當(dāng)輸入異或的差分分布表，發(fā)現(xiàn)當(dāng)輸入異或x= 0Cx= 0C時(shí)，最可能時(shí)，最可能的差分輸出的差分輸出yy是是 E = 1110 E = 1110，出現(xiàn)的概率是，出現(xiàn)的概率是1414/64/64；所有其他；所有其他盒的輸入一定是盒的輸入一定是x= 0 x= 0 且且 y= 0 y= 0盒的輸入通過(guò)置換盒的輸入通過(guò)置換 成為

17、成為f(R,K)f(R,K)的輸出。的輸出。如前所述，如前所述，f(R,K)f(R,K)的差分輸出是的差分輸出是而而 AA與與LL異或后得到異或后得到 00 00 00 0000 00 00 00，因?yàn)椋驗(yàn)?2輪輪DES的差分分析的差分分析31所以所以, , 在第輪后，所有盒都得到差分輸在第輪后，所有盒都得到差分輸入入，產(chǎn)生的差分輸出也是，產(chǎn)生的差分輸出也是；f(R,K)f(R,K)的輸出在輪后是的輸出在輪后是，差分輸出則是，差分輸出則是 (00 00 00 00 (00 00 00 00 , 60 00 00 00), 60 00 00 00)2輪輪DES的差分分析的差分分析-132假定：

18、去掉初始置換假定：去掉初始置換IPIP和最終置換和最終置換FPFP。2 2輪的差分分析輪的差分分析共有個(gè)步驟。共有個(gè)步驟。Step 1Step 1: : 產(chǎn)生明文對(duì)產(chǎn)生明文對(duì)( (P, PP, P ) )，使得，使得辦法是，隨機(jī)產(chǎn)生一個(gè)辦法是，隨機(jī)產(chǎn)生一個(gè)P P ，將其與下述值進(jìn)，將其與下述值進(jìn)行異或得到行異或得到P P 2輪輪DES的差分分析的差分分析-233Step 2Step 2: : 對(duì)于產(chǎn)生的明文對(duì)對(duì)于產(chǎn)生的明文對(duì)( (P, PP, P ) ) ，計(jì)算加密后產(chǎn)生密，計(jì)算加密后產(chǎn)生密文對(duì)文對(duì)( (T, TT, T ) )（選擇明文攻擊）（選擇明文攻擊）Step 3Step 3: : 計(jì)

19、算計(jì)算T=TTT=TT ，檢查結(jié)果是否等于檢查結(jié)果是否等于如果不相等，就說(shuō)明特征不符，這個(gè)明文對(duì)就不能用。如果不相等，就說(shuō)明特征不符，這個(gè)明文對(duì)就不能用。重返第一步，產(chǎn)生新的明文對(duì)；重返第一步，產(chǎn)生新的明文對(duì)；如果相等，則特征相符，進(jìn)入第四步如果相等，則特征相符，進(jìn)入第四步2輪輪DES的差分分析的差分分析-334Step 4Step 4: : 因?yàn)橐驗(yàn)镾2, . . . , S8S2, . . . , S8的差分輸入都為的差分輸入都為，所以沒(méi)有信，所以沒(méi)有信息可以從息可以從S2S2K K, . . . , S8, . . . , S8K K得到。得到。在在S1S1的差分分布表中，的差分分布表中

20、，0C E0C E有有14/6414/64的概率，即只有的概率，即只有6464分之分之1414可以得到可以得到產(chǎn)生產(chǎn)生2輪輪DES的差分分析的差分分析-435這這14 14 個(gè)可能值可以通過(guò)把每個(gè)可能的個(gè)可能值可以通過(guò)把每個(gè)可能的S1S1K K 與相應(yīng)與相應(yīng)的的S1S1E E 和和S1S1 E E 的比特相異或來(lái)確定，計(jì)算的比特相異或來(lái)確定，計(jì)算S1S1的差分輸出的差分輸出S1S1O O，檢查其是否等于，檢查其是否等于E E把把S1S1K K 的這的這1414個(gè)值放進(jìn)表中個(gè)值放進(jìn)表中2輪輪DES的差分分析的差分分析-536Step 5Step 5: : 計(jì)算這些表的交集計(jì)算這些表的交集因?yàn)檎_

21、的密鑰必定同時(shí)出現(xiàn)在每張表中因?yàn)檎_的密鑰必定同時(shí)出現(xiàn)在每張表中如果有不止一個(gè)如果有不止一個(gè)S1S1K K值，就說(shuō)明還需要更多的明文和值，就說(shuō)明還需要更多的明文和密文差分對(duì)才能唯一確定密鑰密文差分對(duì)才能唯一確定密鑰S1S1K K，轉(zhuǎn)到第一步，計(jì)，轉(zhuǎn)到第一步，計(jì)算更多的數(shù)據(jù)算更多的數(shù)據(jù)需要的明文密文差分對(duì)的數(shù)量，大致等于使用的特需要的明文密文差分對(duì)的數(shù)量，大致等于使用的特征概率的倒數(shù)，本例中需要征概率的倒數(shù)，本例中需要6464/14 5/14 5對(duì)對(duì)如果只得到一個(gè)如果只得到一個(gè)S1S1K K ，就是正確的，轉(zhuǎn)到第六步。，就是正確的，轉(zhuǎn)到第六步。2輪輪DES的差分分析的差分分析-637Step 6

22、Step 6: : 這個(gè)階段，要恢復(fù)構(gòu)成這個(gè)階段，要恢復(fù)構(gòu)成S1S1K K的的6 6個(gè)比特。個(gè)比特。采用類(lèi)似的特征，恢復(fù)第一輪中與采用類(lèi)似的特征，恢復(fù)第一輪中與S2-S8S2-S8的輸入相異的輸入相異或的或的6 6比特密鑰比特密鑰Step 7Step 7: : 這個(gè)階段已經(jīng)有了構(gòu)成這個(gè)階段已經(jīng)有了構(gòu)成S1S1K K密鑰的密鑰的4848比特，等比特，等同于同于S1S1K K -S8 -S8K K。其余的比特密鑰，采用窮舉方法在其余的比特密鑰，采用窮舉方法在6464個(gè)可能的值中個(gè)可能的值中搜尋搜尋密碼分析的概率密碼分析的概率38u 去掉第三步，假定在每一對(duì)密文中都出現(xiàn)一個(gè)特征去掉第三步，假定在每一

23、對(duì)密文中都出現(xiàn)一個(gè)特征u 該特征出現(xiàn)的概率是該特征出現(xiàn)的概率是1414/64 1 = 14/64/64 1 = 14/64u 所以，出錯(cuò)的概率是所以，出錯(cuò)的概率是50/64 50/64 對(duì)對(duì)u 正確的正確的S1S1K K 值不一定出現(xiàn)在每個(gè)表中，需要尋找的是值不一定出現(xiàn)在每個(gè)表中，需要尋找的是最常出現(xiàn)的最常出現(xiàn)的S1S1K K 值值u 正確值以正確值以14/64 14/64 出現(xiàn)在各表中，剩余的出現(xiàn)在各表中，剩余的6363個(gè)值以大致個(gè)值以大致等概的方式出現(xiàn)等概的方式出現(xiàn)已知明文攻擊已知明文攻擊-139前面一直假定前面一直假定, ,采用選擇明文攻擊，就是說(shuō)，攻擊者可以采用選擇明文攻擊，就是說(shuō)，攻

24、擊者可以得到任意選擇明文的密文得到任意選擇明文的密文而已知明文攻擊則是，攻擊者可以從大量的明密對(duì)的集合而已知明文攻擊則是，攻擊者可以從大量的明密對(duì)的集合中進(jìn)行選擇性分析中進(jìn)行選擇性分析假設(shè)，選擇明文攻擊需要假設(shè)，選擇明文攻擊需要m m對(duì)明密對(duì)應(yīng)。已知對(duì)明密對(duì)應(yīng)。已知對(duì)隨機(jī)明密對(duì)，這是從對(duì)隨機(jī)明密對(duì)，這是從對(duì)可能的明密文中選擇出來(lái)的對(duì)可能的明密文中選擇出來(lái)的已知明文攻擊已知明文攻擊-240u 每一對(duì)都有一個(gè)異或值，因?yàn)榉纸M大小是每一對(duì)都有一個(gè)異或值，因?yàn)榉纸M大小是6464，總共，總共就有就有2 26464種可能的明文異或值所以，有種可能的明文異或值所以，有對(duì)產(chǎn)生每個(gè)明文異或值對(duì)產(chǎn)生每個(gè)明文異或值u 特別是，有很大的概率，大致有特別是，有很大的概率，大致有m m對(duì)，每一對(duì)都有對(duì)，每一對(duì)都有幾個(gè)明文異或值需要進(jìn)行差分分析幾