差分密碼分析-年

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

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

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

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

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

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

7、每個S S盒中有盒中有4 4行，每個行，每個( (0- 0-F F) )值在值在S S盒中出現(xiàn)盒中出現(xiàn)4 4次，每行輸出一個值次，每行輸出一個值S-Box的差分均勻性的差分均勻性- -214u 考慮一個考慮一個S-boxS-box的差分現(xiàn)象：的差分現(xiàn)象：u 輸入：共有輸入：共有64642 2 = = 4096 4096 種可能的輸入種可能的輸入( (x, xx, x ) )值對，因為對值對，因為對于輸入于輸入S S盒的盒的6 6比特的比特的x, xx, x ，以及以及x= x xx= x x ，每一個取每一個取值都在值都在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 ) ) 每個取值都在其每個取值都在其1616個可能的值上變化個可能的值上變化u 差分輸出差分輸出yy的分布情況，可以針對的分布情況，可以針對8 8 個個S S 盒中的每一個盒中的每一個S S盒來計算，計算在輸入盒來計算，計算在輸入( (x, xx, x ) ) 在在4096 4096 個可能值上變化時，個可能值上變化時，每個每個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個值：個值：00-3F00-3F(16(16進制，進制，1010進制是進制是0-630-63) )u 4 4比特的差分輸出比特的差分輸出yy有有1616個值：個值：0-F0-F(16(16進制，進制，1010進制是進制是0-150-15) )u 每一行的總和是每一行的總和是6464，因為每個差分輸入因為每個差分輸入xx針對針對40964096個個( (x, xx, x ) )對中的對中的6464個個u 可以看到：第一行除第一列外全為可以看到：第一行除第一列外全為0 0，因為當(dāng)，因為當(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 時時, , 6 6個可能的個可能的yy中有中有5 5個值個值: :0, 1, 2, 4, 0, 1, 2, 4, 8 8呈現(xiàn)呈現(xiàn)0 0可能次數(shù)，就是說不出現(xiàn)。可能次數(shù)，就是說不出現(xiàn)。uA A 出現(xiàn)的概率是出現(xiàn)的概率是16/6416/64u 9 9 和和C C 出現(xiàn)的概率是出現(xiàn)的概率是10/6410/64u 這就是說，這就是說，S1S1呈現(xiàn)出很強的不均勻分布呈現(xiàn)出很

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

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

13、果是實際上，輸入異或的結(jié)果是3434，與密鑰無關(guān)，與密鑰無關(guān)，這是因為：這是因為：因為因為所以所以確定密鑰的原理確定密鑰的原理- -23這樣就得到：這樣就得到：所以，可能的密鑰就是所以，可能的密鑰就是確定密鑰的原理確定密鑰的原理- -24此外，假設(shè)已知此外，假設(shè)已知S1S1的兩個輸入是的兩個輸入是2121和和1515，它們異或后的結(jié)，它們異或后的結(jié)果是果是3434，輸出異或后的結(jié)果是，輸出異或后的結(jié)果是3 3 。查。查S1S1的差分分布表，得的差分分布表，得到輸入異或為到輸入異或為3434，輸出異或為，輸出異或為3 3時，可能的輸入：時，可能的輸入： 。確定密鑰的原理確定密鑰的原理- -25這

14、樣就可以從這樣就可以從得到可能的密鑰值得到可能的密鑰值確定密鑰的原理確定密鑰的原理- -26而正確的密鑰值必定同時出現(xiàn)在兩個集合而正確的密鑰值必定同時出現(xiàn)在兩個集合因此可以確定密鑰是在因此可以確定密鑰是在 中的一個。中的一個。要確定到底是哪一個，需要知道更多的輸入輸要確定到底是哪一個，需要知道更多的輸入輸出異或?qū)?。出異或?qū)?。多輪多輪DES的特征的特征27差分輸入具有很高的或然性，可以直接追蹤到多輪的差分輸入具有很高的或然性，可以直接追蹤到多輪的情況，觀察到：情況，觀察到： E擴展中的異或值是線性的：擴展中的異或值是線性的：異或值與密鑰是無關(guān)的：異或值與密鑰是無關(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 中的擴展變換后，中的擴展變換后， 把這部分放進了每個把這部分放進了每個S S盒的中間盒的中間4 4個比特，順序是個比特，順序是 S1S1：6 = 01106 = 0110 S2 S2：0 = 00000 = 0000 S3, . . . , S8 S3, . . . , S8 等等等等因為所有邊緣比特都是因為所有邊緣比特都是0 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時，最可能時，最可能的差分輸出的差分輸出yy是是 E = 1110 E = 1110，出現(xiàn)的概率是，出現(xiàn)的概率是1414/64/64；所有其他；所有其他盒的輸入一定是盒的輸入一定是x= 0 x= 0 且且 y= 0 y= 0盒的輸入通過置換盒的輸入通過置換 成為

17、成為f(R,K)f(R,K)的輸出。的輸出。如前所述，如前所述，f(R,K)f(R,K)的差分輸出是的差分輸出是而而 AA與與LL異或后得到異或后得到 00 00 00 0000 00 00 00，因為，因為 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輪的差分分析輪的差分分析共有個步驟。共有個步驟。Step 1Step 1: : 產(chǎn)生明文對產(chǎn)生明文對( (P, PP, P ) )，使得，使得辦法是，隨機產(chǎn)生一個辦法是，隨機產(chǎn)生一個P P ，將其與下述值進，將其與下述值進行異或得到行異或得到P P 2輪輪DES的差分分析的差分分析-233Step 2Step 2: : 對于產(chǎn)生的明文對對于產(chǎn)生的明文對( (P, PP, P ) ) ，計算加密后產(chǎn)生密，計算加密后產(chǎn)生密文對文對( (T, TT, T ) )（選擇明文攻擊）（選擇明文攻擊）Step 3Step 3: : 計

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

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

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

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

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

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