高階差分分析技術研究.pdf

1、高階差分分析是差分分析的高階推廣，又是積分分析的一個特例。差分分析研究的是迭代密碼中一個明密文差分對的概率分布，而高階差分分析和積分分析研究的是迭代密碼中多個差分對的密碼特性。高階差分分析和積分分析的不同之處在于前者是對一組線性子空間中的明文所對應的密文求和，而后者對這個集合沒有硬性要求，前者具有普遍性，而后者依賴于迭代密碼的結構。
　　 1994年來學嘉首次將高階差分的概念引入到密碼學中，他推導了離散函數(shù)高階導數(shù)的基本性質，并

2、將差分分析的思想推廣到高階差分分析。1997年Jakobsen和Knudsen給出了第一個針對具體密碼算法的有效的高階差分攻擊。從此，高階差分分析作為一種非常有效的密碼分析方法，應用到了很多密碼算法的分析之中。經(jīng)過不斷的實踐和總結之后，2001年，Knudsen將高階差分分析的思想擴展到了積分攻擊。2007年Vielhaber在對流密碼Trivium進行分析時提出了AIDA攻擊，緊接著的2008年，Shamir在美密會的報告中介紹了Cu

3、be攻擊，這些發(fā)現(xiàn)又重新將密碼學團體的注意力吸引到高階差分分析上。AIDA攻擊方法和Cube攻擊方法類似，Shamir承認前者是后者的先驅，而Vielhaber認為后者對前者的改進不足以重新命名這種攻擊技術，Bernstein則認為后者是高階差分攻擊的重發(fā)現(xiàn)，這些發(fā)現(xiàn)和爭議說明高階差分還有很多問題值得深入研究。我們從理論和實際出發(fā)，對高階差分分析技術進行了深入分析，主要得到了如下結果。
　　 1、我們證明了已知的高階差分相關攻擊

4、方法，高階差分攻擊、AIDA攻擊、Cube攻擊、Cube測試和比特高階差分攻擊，本質上都是基于布爾函數(shù)高階導數(shù)的基本性質，這些性質的給出有利于加深對這些攻擊的理解。然后我們給出了一個基于布爾函數(shù)高階導數(shù)性質的高階差分分析框架，該框架能夠涵蓋以上所有高階差分相關攻擊。注意到高階差分相關攻擊方法都是基于布爾函數(shù)高階導數(shù)的如下性質:布爾函數(shù)在任意點上進行求導運算得到的導函數(shù)的次數(shù)比原函數(shù)的次數(shù)至少要降低1次，導函數(shù)的次數(shù)降得越快，攻擊中用到的

5、選擇明文數(shù)量就越少，所以探討布爾函數(shù)導函數(shù)次數(shù)下降至少2次以上的差分點的性質對高階差分分析有著很重要的意義。自然地，我們定義這種差分點為快速點。受到高階差分分析框架的啟發(fā)，我們深入研究了布爾函數(shù)某些特殊差分點為快速點的充分必要條件，并且計算了其概率，這些結果對高階差分分析有著很好的參考價值。進一步的，我們基于一個布爾函數(shù)特殊差分點為快速點的必要條件給出了一個實際的高階差分分析技術，利用該技術我們給出了一個可行的攻擊算法。
　　

6、2、我們給出了布爾函數(shù)高階導數(shù)關于快速點性質的一個相對完整和有規(guī)律的總結。我們證明了一個n變元的布爾函數(shù)的快速點構成一個線性子空間，并且其維數(shù)與函數(shù)的代數(shù)次數(shù)之和不超過變元個數(shù)n。我們還證明了非零的快速點必定存在于如下函數(shù)之中:任意n變元n-1次的布爾函數(shù)、任意次數(shù)d滿足n(≠)d(mod2)的對稱布爾函數(shù)和任意奇數(shù)變元二次布爾函數(shù)。我們還詳細地給出了n變元n-2次的布爾函數(shù)快速點的特殊性質并指出了其它類型布爾函數(shù)快速點的大致規(guī)律。這些

7、性質都是對布爾函數(shù)高階導數(shù)基本性質的一個補充。
　　 3、我們證明了擁有最高次數(shù)不足以保證分組密碼算法能夠抵抗高階差分區(qū)分攻擊。具體地，我們證明了一個有最優(yōu)次數(shù)n-1的n比特分組密碼算法在如下兩種情況下能夠以不可忽略的區(qū)分優(yōu)勢和2n-1的區(qū)分復雜度進行區(qū)分:超過一半的分量布爾函數(shù)的次數(shù)低于n-1或者超過一半的n-1次分量布爾函數(shù)的最高次單項式完全相同?；谏鲜鲂再|，我們?yōu)榉纸M密碼提出了一個基于輸出分量布爾函數(shù)次數(shù)概率分布的設計準

8、則，即一個好的分組密碼算法應該有盡可能多的分量布爾函數(shù)次數(shù)達到最高，盡可能少的分量布爾函數(shù)具有完全相同的n-1次單項式。這是第一個關于次數(shù)的設計準則。
　　 4、Keccak是一族密碼學海綿函數(shù)，它是SHA-3算法競選中第三輪也是最終輪5個候選算法之一，它的核心組件是一個長為1600比特的置換Keccak-f，該置換由五個變換迭代構成，其中只有一個是非線性變換。我們深入研究了該非線性變換的逆變換的性質，發(fā)現(xiàn)該逆變換的輸出分量布爾