高階差分分析技術(shù)研究.pdf

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

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

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

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

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

6、2、我們給出了布爾函數(shù)高階導(dǎo)數(shù)關(guān)于快速點(diǎn)性質(zhì)的一個(gè)相對(duì)完整和有規(guī)律的總結(jié)。我們證明了一個(gè)n變?cè)牟紶柡瘮?shù)的快速點(diǎn)構(gòu)成一個(gè)線性子空間，并且其維數(shù)與函數(shù)的代數(shù)次數(shù)之和不超過變?cè)獋€(gè)數(shù)n。我們還證明了非零的快速點(diǎn)必定存在于如下函數(shù)之中:任意n變?cè)猲-1次的布爾函數(shù)、任意次數(shù)d滿足n(≠)d(mod2)的對(duì)稱布爾函數(shù)和任意奇數(shù)變?cè)尾紶柡瘮?shù)。我們還詳細(xì)地給出了n變?cè)猲-2次的布爾函數(shù)快速點(diǎn)的特殊性質(zhì)并指出了其它類型布爾函數(shù)快速點(diǎn)的大致規(guī)律。這些

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

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