輕量級與非滿射S-box的分組密碼算法的分析.pdf

1、在過去的幾十年里，由于計算機(jī)技術(shù)的蓬勃發(fā)展給通信安全帶來了巨大的挑戰(zhàn)和機(jī)遇，密碼學(xué)在信息安全領(lǐng)域的作用日趨顯著。在當(dāng)今密碼學(xué)領(lǐng)域，分組密碼，作為對稱密碼算法的一種，是一種基礎(chǔ)密碼算法，其結(jié)構(gòu)也常常被用來構(gòu)造流密碼，哈希函數(shù)以及消息認(rèn)證碼。分組密碼的加密過程是一個由唯一密鑰來決定的置換過程，它先把消息分為等長分組，然后在密鑰的作用下轉(zhuǎn)換為等長的密文塊。分組密碼被廣泛應(yīng)用于如SSL，IPsec等各種安全協(xié)議和安全類應(yīng)用程序。直到現(xiàn)在，分組密

2、碼的設(shè)計與安全性評估一直是研究的熱點(diǎn)。
　　 分組密碼算法DES是由IBM公司設(shè)計，并在1977年被提名為第一個分組密碼加密標(biāo)準(zhǔn)。它密鑰長度為56比特，分組長度64比特。整個加密過程是Feistel結(jié)構(gòu)，由一個初始變換，16個迭代輪函數(shù)和一個逆變換組成。在此之后，出現(xiàn)了很多Feistel結(jié)構(gòu)的分組密碼，比如分組密碼CAMELLIA[1]，CAST-128[2]，ICE[4]，LOKI97[5]，LUCIFER[6]。與此同時，一

3、系列的分析方法也正在展開，比如差分分析，線性分析，代數(shù)攻擊等。因?yàn)?6比特的密鑰空間已經(jīng)不足以保證DES算法的安全性，1997年，美國國家標(biāo)準(zhǔn)與技術(shù)研究所(NIST)開始征集高級加密標(biāo)準(zhǔn)(AES)。2000年由JoanDaemen和VincentRijmen設(shè)計的分組密碼算法Rijndael被提名為新的高級加密標(biāo)準(zhǔn)(AES)，并在一年后由NIST發(fā)布于FIPSPUB197。AES是SPN結(jié)構(gòu)的，這種結(jié)構(gòu)比起Feistel結(jié)構(gòu)實(shí)現(xiàn)的效率更

4、高，這是因?yàn)闉檫_(dá)到同樣程度的混亂和擴(kuò)散，SPN結(jié)構(gòu)相對于Feistel結(jié)構(gòu)更易于并行化。
　　 S盒在分組密碼的設(shè)計中起著至關(guān)重要的作用。S盒是一個布爾函數(shù)映射{0，1}m→{0，1}n，它的非線性影響著分組密碼的混亂特性。為了抵抗差分分析，有些分組密碼如CAST-128[2]，CAST-256[3]，Blowfish[21]等的S盒采用輸出比特大于輸入比特的設(shè)計特點(diǎn)。對于一個輸入比特為m，輸出比特為n的S盒，也可以實(shí)現(xiàn)為一個2

5、m個元素的表。如果n大于m，那么S盒為非滿射。線性分析是一種已知明文攻擊或者唯密文攻擊，由Matsui在1993年提出[26]。因此在設(shè)計能抵抗線性分析的大S盒時，常常采用bent函數(shù)，這種函數(shù)的非線性度能夠達(dá)到上界2m-1-2m/2-1。在線性分析中，能找到非滿射大S盒的輸入掩碼為0，輸出掩碼為非0的線性近似表達(dá)式是很有用的。然而，遍歷S盒所有元素和所有輸出掩碼往往是非常耗時的。在針對采用非滿射大S盒的分組密碼的線性分析中，由于計算時

6、間的限制，以有的工作只是搜索了部分線性近似表達(dá)式，沒有達(dá)到全部搜索的目的。
　　 比如，在分組密碼算法CAST-128和CAST-256中，有三種輪函數(shù)F1，F(xiàn)2，F(xiàn)3，每種都由4個8×32的非滿射S盒通過模加、模減和異或的混合運(yùn)算構(gòu)成，這導(dǎo)致無法構(gòu)建S盒的線性分布表。由于CAST的Feistel結(jié)構(gòu)，為了控制每輪的偏差，分析者對0→Γ的線性近似表達(dá)式進(jìn)行了搜索。在[63]中，Nakahara等考慮到模加模減運(yùn)算會產(chǎn)生借位，因此

7、只考慮了輪函數(shù)F1，F(xiàn)2，F(xiàn)3的最優(yōu)線性近似表達(dá)式是00000000x→00000001x，其偏差是2-17，利用它構(gòu)造了兩輪迭代線性近似表達(dá)式進(jìn)而給出了12輪CAST-256的分析結(jié)果，需要2101個明文，2101次12輪CAST-256加密。但隨后王美琴等在[14]的對CAST-128和CAST256的線性分析中[14]指出進(jìn)位和借位不總是降低偏差，由于計算時間的限制，他們搜索了輪函數(shù)F1和F3的輸出掩碼的漢明重量不大于3的線性近似

8、表達(dá)式;對于輪函數(shù)F2，搜索了輸出掩碼的漢明重量不大于6的線性近似表達(dá)式，最后利用F2的最優(yōu)線性近似表達(dá)式00000000x→03400000x，偏差為2-12.91，給出了24輪CAST-256的分析結(jié)果，需要2124.1個明文，2156.2次24輪CAST-256加密。然而，輪函數(shù)F1，F(xiàn)2，F(xiàn)3的輸出比特數(shù)為32。所以還有大量的線性近似表達(dá)式的偏差沒有被計算。是否存在偏差更高的線性近似表達(dá)式是未知的。
　　 本文中，我們提

9、出一種針對非滿射大S盒(32×32)的所有線性近似表達(dá)式(0→Γ)實(shí)際可行的搜索方法。該算法充分利用了64位高性能并行計算機(jī)的硬件特性，能夠分析任何具有非滿射大S盒的分組密碼算法。為了清晰的描述我們的算法，我們以CAST-256為例。我們找到了比王美琴等找到的最好線性近似表達(dá)式更好的線性近似表達(dá)式。我們主要描述了對于CAST-256中的輪函數(shù)F2的搜索過程。在我們的并行環(huán)境里(64顆CPU核，主頻2.4GHZ，3MB二級緩存，型號IBM

10、X3950M2)，搜索完所有232個線性近似表達(dá)式用時85.3個小時。這里需要提及的一點(diǎn)是我們的工作不只是并行化實(shí)現(xiàn)，而是充分利用了硬件的特性來顯著降低計算時間。如果沒有我們的改進(jìn)，即便采用并行化，這個搜索過程在我們的并行環(huán)境下，也將在256天才能完成。我們得到了CAST-256的輪函數(shù)F2的最好線性近似表達(dá)式00000000x→8021c53ax，偏差為2-12.63，比已有的最優(yōu)偏差2-12.91更優(yōu)。而且我們給出一個通用的針對非滿

11、射大S盒的線性近似表達(dá)式(0→Γ)搜索方法，利用該方法在我們的并行環(huán)境下可以在47.72小時內(nèi)搜索完CAST-256算法的任一輪函數(shù)F1，F(xiàn)2，F(xiàn)3的所有線性近似表達(dá)式(0→Γ)。
　　 在最近幾年里，由于因特網(wǎng)的迅猛發(fā)展，越來越多的微型終端設(shè)備被普遍使用，它們可以提供快捷的計算與通信，比如射頻標(biāo)簽和傳感器網(wǎng)絡(luò)。然而，廣受歡迎的密碼算法AES并不能完全適合這種低耗能和計算資源有限的環(huán)境。所以最近幾年國際密碼領(lǐng)域設(shè)計了很多輕量級分

12、組密碼被設(shè)計出來滿足這種資源受限的環(huán)境的安全需求，比如分組算法DESL[7],mCRYPTON[8],HEIGHT[9],ICEBERG[10],PRESENT[11],PUFFIN[12]等。
　　 PUFFIN是一種輕量級分組密碼，由Cheng，Heys和Wang在DSD2008上發(fā)表。它是一種32輪SPN結(jié)構(gòu)的分組密碼，分組長度為64比特，密鑰長度為128比特。和ICEBERG一樣，PUFFIN也是一種自反的SPN結(jié)構(gòu)的算

13、法，這使得它能在硬件要求低的環(huán)境下使用。在CCECE2009上，Wang和Heys又提出了分組密碼算法PUFFIN2[13]，該算法結(jié)構(gòu)與PUFFIN相似，只是輪數(shù)為34輪，密鑰生成算法略有不同。
　　 PUFFIN原文中提出31輪PUFFIN差分特征的概率小于2-62。Cheng等聲稱利用這一差分特征，需要262個選擇明文對才能破解，這種攻擊的數(shù)據(jù)復(fù)雜度接近于字典攻擊。但是，PUFFIN的密鑰長度為128比特，分組長度是64比

14、特。Cheng等認(rèn)為對于一個理想的加密算法，即使利用整個數(shù)據(jù)空間也無法恢復(fù)密鑰。因此Cheng等聲稱32輪PUFFIN可以抵抗差分攻擊[12]。然而，如果一個攻擊能夠利用整個數(shù)據(jù)空間恢復(fù)密鑰，時間復(fù)雜度低于窮搜，那么這種攻擊就是有效的。在本文中，我們利用整個數(shù)據(jù)空間對32輪PUFFIN進(jìn)行差分分析，進(jìn)而恢復(fù)128比特密鑰。同時，我們利用28輪的線性近似表達(dá)式恢復(fù)128比特的密鑰。其數(shù)據(jù)復(fù)雜度為262個明文，計算復(fù)雜度為293.7次32輪

15、加密。另外，我們的攻擊結(jié)果也適用于32輪PUFFIN2。
　　 差分分析是分組密碼算法的一種經(jīng)典攻擊方法[24，25]，由Biham和Shamir相繼發(fā)現(xiàn)[24]，是一種選擇明文攻擊，它能夠恢復(fù)出迭代分組密碼的密鑰。它通過在迭代密碼算法中存在的高概率差分特征來作為與隨機(jī)置換的區(qū)分器。抵抗差分分析已經(jīng)成為分組密碼算法設(shè)計的安全準(zhǔn)則。代數(shù)攻擊也是分組密碼算法的一種通用的攻擊類型，它被廣泛應(yīng)用于分析流密碼[28,29]，多變元密碼系統(tǒng)

16、[30]和一些分組密碼算法[31-35]。代數(shù)攻擊的基本思想是將分組密碼算表示為多變量多項式方程組，進(jìn)而通過求解來恢復(fù)密鑰。一般來說，變量越多，非線性方程越多，多項式方程組求解的時間復(fù)雜度越高，如AES的密鑰恢復(fù)可以看成對一個已知明文攻擊，方程組包含4000個多變元二次方程[31]，其求解復(fù)雜度至今仍然是難以估計的。然而個別密碼算法導(dǎo)出的方程組其代數(shù)特性可能是容易解的[38，39]。如今，人們還在不斷尋找更優(yōu)的求解方法[36,37,40

17、]。一般認(rèn)為，稀疏的多項式方程組是容易解的。有兩類方法Gr(o)bnerBasis，SATSolver可以用來求解這一類多項式方程組，如Magma，Singular，PolyBori，MiniSat2等[43-46]。PolyBori是計算Gr(o)bnerBasis的工具，MiniSat2是一種快速的SATSolver。如果分組密碼算法的多項式方程組可以被求解，那么只需要很少的明密文對便可以恢復(fù)密鑰。
　　 然而，由于多項式方

18、程組的求解時間難以估計，對于分組密碼的代數(shù)攻擊的可行性至今是未知的。近年來，差分分析與代數(shù)分析的組合成為人們關(guān)注的分析方法。在FSE2009上，Albrecht等提出了一種新型的攻擊方法，差分代數(shù)攻擊[47]。他們提出了三種攻擊方法，命名為攻擊A，攻擊B和攻擊C。他們認(rèn)為攻擊A的計算復(fù)雜度是難以估計的;攻擊B和攻擊C的目標(biāo)是過濾掉不滿足差分特征或者差分的錯誤對，進(jìn)而識別正確對以恢復(fù)密鑰。最后給出了對16輪PRESENT-80，17，18

19、，19輪PRESENT-128的攻擊。在本文中，我們指出攻擊B和攻擊C并不適用于PRESENT算法，因?yàn)樗鼈儾荒苓^濾掉大多數(shù)滿足密文差分的錯誤對。而且，我們解釋了攻擊C是不適用于一般的分組密碼算法。其次，我們利用PolyBori和MiniSat2對PRESENT算法執(zhí)行差分代數(shù)攻擊，驗(yàn)證其是無效的。在此基礎(chǔ)上，我們提出了兩種新的差分代數(shù)攻擊:固定部分密鑰比特和多向量的差分代數(shù)攻擊?；诘谝粋€方法，我們可以攻擊16輪PRESENT-80，

20、這需要263個選擇明文，最差時間復(fù)雜度是279.4次加密。雖然攻擊的時間復(fù)雜度分析結(jié)果更高，但數(shù)據(jù)復(fù)雜度有所降低。
　　 本論文中，我們首先給出了非滿射大S盒的線性近似表達(dá)式的搜索方法，對32輪PUFFIN進(jìn)行了差分分析和線性分析，并對Albrecht等在FSE2009上提出的差分代數(shù)攻擊技術(shù)進(jìn)行了研究。其中差分代數(shù)攻擊技術(shù)的研究內(nèi)容，主要思想和證明由王美琴老師完成，本文作者負(fù)責(zé)大批量試驗(yàn)數(shù)據(jù)測試。具體來講，本文主要貢獻(xiàn)分為以下

21、三個方面:
　　 (1)對非滿射大S盒的線性近似表達(dá)式的搜索算法
　　 利用硬件特性進(jìn)行改進(jìn)
　　 我們將計數(shù)器累加操作并行處理分給64個子進(jìn)程，父進(jìn)程負(fù)責(zé)計算偏差。為了降低計數(shù)器帶來的巨大內(nèi)存需求，我們重復(fù)利用有限的計數(shù)器來計算更多不同輸出掩碼的線性近似表達(dá)式的偏差。我們還利用64位寄存器一次內(nèi)存讀獲取S盒中的兩個元素。
　　 Dot_Multiply運(yùn)算的優(yōu)化
　　 受對分查找思想[67]的啟

22、發(fā)，我們把Dot_Multiply運(yùn)算從32次異或運(yùn)算，33次與運(yùn)算，31次右移運(yùn)算減少到6次異或運(yùn)算，8次與運(yùn)算，6次右移運(yùn)算。
　　 S盒重排序和累加運(yùn)算的優(yōu)化
　　 這里我們以CAST-256的輪函數(shù)F2為例。因?yàn)檩斎胙诖a始終是0，所以S盒中元素的順序不影響偏差的計算。因此我們把非滿射大S盒中的元素進(jìn)行了重新排序，重新排序后的S盒包含64個新的組，在每一組里都有40000x個元素，然后將每一組分配給一個子進(jìn)程。

23、r>　　 每一組最多由B1，B2和B3三種塊組成，其中在B1或B2中，所有元素的6比特最低有效位相同。每一個子進(jìn)程都會用不同的方式去處理不同類型的塊。這樣我們可以在對64個連續(xù)的輸出掩碼的計數(shù)器累加操作中，只進(jìn)行最多2次Dot_Multiply運(yùn)算，并且僅需要操作2個計數(shù)器。
　　 最后，在對CAST-256的輪函數(shù)F2的最優(yōu)線性近似表達(dá)式的搜索算法基礎(chǔ)上，我們給出了對非滿射大S盒的線性近似表達(dá)式更有效的通用搜索算法。利用這個

24、通用算法，搜索CAST-256的輪函數(shù)F1或F3的線性近似表達(dá)式僅需要242.81次內(nèi)存寫，內(nèi)存需求為228個字節(jié)，在我們的并行環(huán)境下，這實(shí)際需要47.72小時。而如果直接采用對輪函數(shù)F2的搜索算法來完成，將需要251.58次內(nèi)存寫，內(nèi)存需求為228個字節(jié)。
　　 (2)對32輪PUFFIN的差分分析和線性分析結(jié)果
　　 我們識別了4條2輪PUFFIN的迭代差分特征，它們的概率都是2-4，每一輪都只有一個活性S盒。利用其

25、中任一條2輪迭代差分特征，我們可以構(gòu)建更多輪的差分特征。它們的概率都為2-60，我們列舉了其中1條30輪PUFFIN的差分特征，如下，其中(30r→)表示30輪，(00000000x，00004000x)(30r→)(00000000x,00004000x).我們在第2輪到第31輪使用第1條差分特征。我們推出明文差分的4個比特和密文差分的4個比特要滿足如下的集合。所以我們選擇了264個明文，來構(gòu)建260個結(jié)構(gòu)，在每一個結(jié)構(gòu)里都有56個明

26、文對，它們僅在第14，22，38，55比特上可能為1。
　　 (△P55,△P38,△P22,△P14)∈{(1,1,0,0),(0,0,0,1),(0,1,0,1),(1,0,1,0),(1,0,1,1),(0,1,1,1),(1,1,1,1)},(△C48,△C46,△C18,△C0)∈{(1,0,0,1),(0,1,0,0),(1,1,0,0),(0,0,1,1),(0,1,1,1),(1,1,1,0),(1,1,1,1)

27、}.然后我們恢復(fù)第0輪和第32輪的輪密鑰。我們利用其它3條差分特征來恢復(fù)其它密鑰比特。恢復(fù)128比特的密鑰，共需要264個明密文對，2112次32輪加密和28個6比特計數(shù)器，成功率為99.99999999996％。
　　 要得到多輪數(shù)的線性近似表達(dá)式，我們在搜索時首先考慮2輪迭代線性近似表達(dá)式。我們最終找到了14條2輪迭代線性近似表達(dá)式，它們的偏差都是最大值2-3，其中一條如下:(0000000000000010)x(1r→)(

28、0004000000000000)x(1r→)(0000000000000010)x.我們迭代此2輪的線性近似表達(dá)式得到28輪的線性近似表達(dá)式，它的偏差為2-29。我們在第3輪到第30輪使用這個28輪的線性近似表達(dá)式，進(jìn)而恢復(fù)了32輪PUFFIN的主密鑰。在密鑰恢復(fù)過程中，要猜測的輪密鑰比特為第0，1，2，31，32輪的輪密鑰，總計41比特。從密鑰生成算法看，這41個比特等價于主密鑰的35個比特。因此剩下的93個比特用窮搜來恢復(fù)。因此我

29、們用262個已知明文，293.7次32輪加密，235個64比特計數(shù)器恢復(fù)32輪PUFFN的128比特主密鑰，成功率為91％。
　　 (3)Albrecht等的差分代數(shù)攻擊技術(shù)的研究
　　 Albrecht等發(fā)表在FSE2009上的一篇文章里指出差分代數(shù)攻擊可以用來攻擊PRESENT，并給出了三種攻擊方法，攻擊A，攻擊B，攻擊C。首先，我們指出攻擊C是不能過濾掉滿足密文差分值的錯誤對的。其次，我們用PolyBori和Min

30、iSat2證實(shí)了攻擊B對于PRESENT算法的攻擊也是不可行。原因是在多項式方程組中，能使得錯誤對較短時間產(chǎn)生矛盾或者使得正確對較短時間求解的約束條件太少。因此，我們給出了兩種方法可以更可靠的利用正確對在有效的時間內(nèi)求解出正確密鑰，而且錯誤對不會求解出錯誤密鑰。第一種方法是在多項式方程組中固定部分密鑰比特值。另外一種是用兩組以上的明密文對構(gòu)建多項式方程組。
　　 基于第一種方法，我們給出了16輪PRESENT-80算法的分析結(jié)果