分組密碼攻擊模型的構(gòu)建和自動(dòng)化密碼分析6頁(yè)

1、分組密碼攻擊模型的構(gòu)建和自動(dòng)化密碼分析隨著物聯(lián)網(wǎng)時(shí)代向萬(wàn)物互聯(lián)時(shí)代的不斷推動(dòng),互聯(lián)網(wǎng)為生活方方面面帶來(lái)便利的同時(shí),網(wǎng)絡(luò)安全問(wèn)題也在新形勢(shì)下面臨新的挑戰(zhàn)。作為保障網(wǎng)絡(luò)安全的基石,密碼在安全認(rèn)證、加密保護(hù)和信息傳遞等方面發(fā)揮了十分重要的作用。與公鑰密碼體制相比,對(duì)稱密碼算法由于效率高、算法簡(jiǎn)單、適合加密大量數(shù)據(jù)的優(yōu)點(diǎn)應(yīng)用更為廣泛?；谶@一事實(shí),對(duì)分組密碼算法分析與設(shè)計(jì)的研究在新環(huán)境下顯得尤為重要。本文圍繞分組密碼攻擊模型的構(gòu)建和自動(dòng)化密碼分析這一主題展開(kāi)。首先,在攻擊模型構(gòu)建方面,我們提出了卡方多重/多維零相關(guān)線性分析模型,并將該模型用于一系列算法的多重和多維零相關(guān)分析中。其次,針對(duì)自動(dòng)化密碼分析

2、,我們一方面著眼于攻擊路線的自動(dòng)化搜索問(wèn)題,另一方面試圖借助自動(dòng)化思想解決密碼學(xué)中的理論問(wèn)題。在路線自動(dòng)化搜索方面,我們給出了基于MILP方法對(duì)具有復(fù)雜線性層的算法和ARX類算法搜索比特級(jí)分離特性的模型,使用新方法對(duì)一系列算法關(guān)于積分分析的抵抗性進(jìn)行了評(píng)估。構(gòu)建了基于SAT方法ARX類算法比特級(jí)分離特性的自動(dòng)化搜索工具和基于SMT方法自動(dòng)化搜索字級(jí)分離特性的新工具,完善了分離特性自動(dòng)化搜索框架。在自動(dòng)化解決理論問(wèn)題方面,討論了差分分析中的差分聚集現(xiàn)象,對(duì)兩個(gè)算法給出了更加精確的差分分析。最后,我們對(duì)SIMON算法的所有版本給出了零相關(guān)攻擊結(jié)果。具體結(jié)果如下。給出了基于SAT方法自動(dòng)化搜索并分析

3、帶S盒算法差分閉包的工具:為了填補(bǔ)SAT方法在搜索差分閉包方面的空白,我們給出了基于SAT問(wèn)題的差分閉包自動(dòng)化搜索工具。首先,我們給出對(duì)線性層和由多個(gè)小S盒構(gòu)成的非線性層的刻畫(huà)。隨后,給出了目標(biāo)函數(shù)的SAT模型,這使得我們可以實(shí)現(xiàn)在固定權(quán)重下差分特征的搜索。最后,給出了搜索差分閉包中多條路線的方法。這一自動(dòng)化搜索方法在對(duì)LED64算法和Midori64算法的分析中發(fā)揮了十分重要的作用。對(duì)于LED64算法,我們提出了一種自動(dòng)化搜索差分閉包正確對(duì)的方法。首先,我們導(dǎo)出滿足差分路線正確對(duì)的約束條件,而后,將這些約束條件轉(zhuǎn)化為SAT問(wèn)題,保證SAT問(wèn)題的解與路線的所有正確對(duì)一一對(duì)應(yīng)。然后,使用求解器的

4、多解搜索模式,搜索服從差分路線的所有正確對(duì)?；谶@一方法,我們改進(jìn)了 Mendel等人86給出的迭代和非迭代差分閉包概率的結(jié)果?；谶@些針對(duì)差分閉包改進(jìn)的結(jié)果,已有的對(duì)于LED64算法縮短輪的攻擊都得到了不同程度的改進(jìn)。對(duì)于Midori64算法,我們構(gòu)建了一種自動(dòng)化評(píng)估差分閉包弱密鑰空間的模型。首先,我們導(dǎo)出一個(gè)密鑰作為弱密鑰所滿足的必要條件,而后針對(duì)這些條件構(gòu)建SAT模型,并調(diào)用求解器求解。基于這一方法,我們給出了 Midori64算法兩個(gè)4輪差分閉包的實(shí)例,對(duì)這兩個(gè)差分閉包,超過(guò)78%的密鑰將使其變?yōu)椴豢赡懿罘?換言之,它們的弱密鑰比例非常低。如果該路線用于差分攻擊,那么很可能錯(cuò)誤的將正確

5、密鑰當(dāng)作錯(cuò)誤密鑰,這就使得差分分析理論結(jié)果與實(shí)際情況產(chǎn)生偏差。與這一現(xiàn)象相對(duì)應(yīng),我們考慮差分閉包確定的那些“極弱的”密鑰,在這些密鑰下,差分攻擊的成功率將大于理論結(jié)果。該問(wèn)題與討論差分閉包中同時(shí)成立的路線數(shù)量相關(guān),我們發(fā)現(xiàn)這類問(wèn)題可以轉(zhuǎn)化為一類特殊的Max-PoSSo問(wèn)題。對(duì)此,我們構(gòu)建SAT模型以確定差分閉包中可兼容路線的最大數(shù)量。最后,我們給出了 Midori64算法一條差分閉包的實(shí)例,對(duì)于2-12的密鑰,差分閉包的概率由期望值2-23.79提升到2-16。這一現(xiàn)象表明,在這些“極弱”密鑰下,差分攻擊將更有可能成功,或者說(shuō),我們可以以更低的代價(jià)實(shí)現(xiàn)差分攻擊。這些例子提醒我們,對(duì)于密鑰生成算

6、法簡(jiǎn)單的輕量級(jí)算法,在進(jìn)行差分分析時(shí),需要格外注意區(qū)分器本身的有效性。構(gòu)建卡方多重/多維零相關(guān)線性分析新模型,用該模型給出了TEA算法單密鑰情境下的最優(yōu)攻擊:作為更加成熟的密碼分析方法,多重和多維零相關(guān)線性分析克服了經(jīng)典零相關(guān)攻擊在數(shù)據(jù)復(fù)雜度方面的缺陷,使得零相關(guān)分析方法被廣泛應(yīng)用于系列對(duì)稱密碼攻擊的同時(shí),成為了很多算法的最優(yōu)攻擊方法。雖然多重和多維零相關(guān)模型在對(duì)眾多密碼算法的分析中顯示出了優(yōu)越性,但這兩個(gè)模型對(duì)于零相關(guān)路線數(shù)量的限制條件仍然存在。為了消除這一約束條件,我們構(gòu)建了卡方多重/多維零相關(guān)線性分析模型。由于在模型構(gòu)建過(guò)程中取消了卡方分布的正態(tài)逼近過(guò)程,新模型在復(fù)雜度評(píng)估方面達(dá)到更高精

7、度的同時(shí),有效性不再依賴路線數(shù)量的假設(shè)?？ǚ侥Ｐ偷奶岢鲈诹阆嚓P(guān)分析領(lǐng)域具有十分重要的意義:一方面,新模型拓寬了零相關(guān)模型的應(yīng)用范圍,具有普適性;另一方面,新的卡方多重模型允許我們?cè)趩温肪€環(huán)境下使用低于整個(gè)明文空間的數(shù)據(jù)量對(duì)密碼算法進(jìn)行分析,克服了傳統(tǒng)零相關(guān)分析在這一方面的不足。我們將卡方多維攻擊模型應(yīng)用于CLEFIA-192算法的分析,在對(duì)已有攻擊復(fù)雜度給出更精確評(píng)估的同時(shí),使用更少的零相關(guān)路線對(duì)算法的多維零相關(guān)分析結(jié)果進(jìn)行了改進(jìn)。另外,我們使用新的卡方多重零相關(guān)分析模型對(duì)TEA算法和XTEA算法關(guān)于多重零相關(guān)分析的抵抗性重新進(jìn)行了評(píng)估,給出的TEA算法的23輪攻擊是該算法在單密鑰環(huán)境下數(shù)據(jù)量

8、低于整個(gè)明文空間的最好攻擊結(jié)果。完善了基于MILP方法自動(dòng)化搜索比特級(jí)分離特性的工具:作為傳統(tǒng)積分性質(zhì)的一種推廣,分離特性由于能夠更確切的刻畫(huà)傳統(tǒng)的ALL特性和BAL-ANCE特性之間的隱含性質(zhì),已經(jīng)成為搜索積分區(qū)分器的一種強(qiáng)有力工具。而比特級(jí)分離特性由于能對(duì)算法的代數(shù)性質(zhì)進(jìn)行更精準(zhǔn)的把控,通?？梢詫?dǎo)出比傳統(tǒng)方法性質(zhì)更好的區(qū)分器,然而直接調(diào)用該方法在復(fù)雜度方面的缺陷限制了其廣泛應(yīng)用。2016年的亞密會(huì)上,Xiang等人提出了基于MILP思想自動(dòng)化搜索比特級(jí)分離特性的方法,這在一定程度上緩解了比特級(jí)分離特性對(duì)目標(biāo)算法分組長(zhǎng)度的約束,改進(jìn)了一些以比特置換作為線性層的算法的積分區(qū)分器。然而,對(duì)那些以

9、復(fù)雜線性變換作為擴(kuò)散層的算法,這一方法的適用性還不得而知。以此為動(dòng)機(jī),我們首先將原有的復(fù)制模型和異或模型分別進(jìn)行推廣,使其適配于具有多輸出分支的復(fù)制操作和具有多輸入分支的異或操作?；趯?duì)線性變換本源表示的觀測(cè),我們使用兩個(gè)推廣的模型給出了構(gòu)建復(fù)雜線性層MILP模型的一般方法。結(jié)合該方法,解決了基于MILP方法比特級(jí)分離特性的自動(dòng)化搜索在具有非比特置換線性層算法上的適用性問(wèn)題,拓寬了 MILP搜索方法的使用范圍,使其在搜索積分區(qū)分器方面發(fā)揮更大的優(yōu)勢(shì)?？紤]到ARX類算法在分組密碼算法中的重要地位,我們構(gòu)建了模加運(yùn)算的MILP模型,使得基于MILP思想的比特級(jí)分離特性自動(dòng)化搜索方法推廣到ARX類算

10、法?；谏鲜鐾茝V的模型,我們對(duì)一系列算法的積分區(qū)分器進(jìn)行了搜索,對(duì)Midori64算法、LED64算法、Joltik-BC算法、Serpent 算法、Noekeon算法、HIGHT算法和LEA等算法的積分區(qū)分器給出了不同程度的改進(jìn)。構(gòu)建了基于SAT方法ARX類算法比特級(jí)分離特性的自動(dòng)化搜索工具:注意到在ARX類算法差分/線性路線的自動(dòng)化搜索中,基于SAT/SMT的方法在表現(xiàn)上優(yōu)于那些基于MILP的方法,我們針對(duì)ARX類算法構(gòu)建了基于SAT問(wèn)題自動(dòng)化搜索比特級(jí)分離特性的工具。首先,我們對(duì)三種基本運(yùn)算(復(fù)制運(yùn)算、與運(yùn)算和異或運(yùn)算)的比特級(jí)分離特性建模,將分離特性在運(yùn)算中的傳遞規(guī)律轉(zhuǎn)化為滿足合取范式

11、形式的邏輯表達(dá)式。隨后,基于這三種基本操作,我們構(gòu)建了刻畫(huà)模加運(yùn)算比特級(jí)分離特性的SAT模型。設(shè)置好初始分離特性和終止規(guī)則后,ARX算法比特級(jí)分離特性的搜索問(wèn)題將轉(zhuǎn)化為SAT問(wèn)題,進(jìn)而可調(diào)用求解器求解。為了快速定位目標(biāo)算法的最優(yōu)積分區(qū)分器,我們給出了一種高效的搜索算法,這一算法可以幫助我們縮減初始分離特性的搜索空間,快速定位導(dǎo)出最優(yōu)積分區(qū)分器的初始分離特性的形式。基于這一方法,我們得到了SHACAL-2算法的17輪積分區(qū)分器,這使得該算法最優(yōu)積分區(qū)分器輪數(shù)改進(jìn)了 4輪。除此之外,對(duì)LEA算法、HIGHT算法和SPECK算法,新獲取的積分區(qū)分器與用MILP方法得到的結(jié)果相比都有不同程度的改進(jìn)。構(gòu)建了基于SMT方法自動(dòng)化搜索字級(jí)分離特性的新工具:一方面,考慮到自動(dòng)化搜索在字級(jí)分離特性評(píng)估中的空白;另一方面,觀察到對(duì)大狀態(tài)/含復(fù)雜運(yùn)算的算法在比特水平追蹤分離特性的困難性,我們使用基于SMT的方法實(shí)現(xiàn)了字級(jí)分離特性的自動(dòng)化搜索。首先,考慮對(duì)字級(jí)分離特性在一些基本運(yùn)算中的傳遞規(guī)律建模,模型的構(gòu)建采用排除法。而后,合理的設(shè)置初始分離特性和終止條件,以將字級(jí)分離特性的搜索問(wèn)題轉(zhuǎn)化為SMT問(wèn)題,并調(diào)用開(kāi)源求解器對(duì)問(wèn)題進(jìn)行求