【摘要】：隨著物聯(lián)網(wǎng)時代向萬物互聯(lián)時代的不斷推動,互聯(lián)網(wǎng)為生活方方面面帶來便利的同時,網(wǎng)絡(luò)安全問題也在新形勢下面臨新的挑戰(zhàn)。作為保障網(wǎng)絡(luò)安全的基石,密碼在安全認證、加密保護和信息傳遞等方面發(fā)揮了十分重要的作用。與公鑰密碼體制相比,對稱密碼算法由于效率高、算法簡單、適合加密大量數(shù)據(jù)的優(yōu)點應(yīng)用更為廣泛�；谶@一事實,對分組密碼算法分析與設(shè)計的研究在新環(huán)境下顯得尤為重要。本文圍繞分組密碼攻擊模型的構(gòu)建和自動化密碼分析這一主題展開。首先,在攻擊模型構(gòu)建方面,我們提出了卡方多重/多維零相關(guān)線性分析模型,并將該模型用于一系列算法的多重和多維零相關(guān)分析中。其次,針對自動化密碼分析,我們一方面著眼于攻擊路線的自動化搜索問題,另一方面試圖借助自動化思想解決密碼學中的理論問題。在路線自動化搜索方面,我們給出了基于MILP方法對具有復雜線性層的算法和ARX類算法搜索比特級分離特性的模型,使用新方法對一系列算法關(guān)于積分分析的抵抗性進行了評估。構(gòu)建了基于SAT方法ARX類算法比特級分離特性的自動化搜索工具和基于SMT方法自動化搜索字級分離特性的新工具,完善了分離特性自動化搜索框架。在自動化解決理論問題方面,討論了差分分析中的差分聚集現(xiàn)象,對兩個算法給出了更加精確的差分分析。最后,我們對SIMON算法的所有版本給出了零相關(guān)攻擊結(jié)果。具體結(jié)果如下。給出了基于SAT方法自動化搜索并分析帶S盒算法差分閉包的工具:為了填補SAT方法在搜索差分閉包方面的空白,我們給出了基于SAT問題的差分閉包自動化搜索工具。首先,我們給出對線性層和由多個小S盒構(gòu)成的非線性層的刻畫。隨后,給出了目標函數(shù)的SAT模型,這使得我們可以實現(xiàn)在固定權(quán)重下差分特征的搜索。最后,給出了搜索差分閉包中多條路線的方法。這一自動化搜索方法在對LED64算法和Midori64算法的分析中發(fā)揮了十分重要的作用。對于LED64算法,我們提出了一種自動化搜索差分閉包正確對的方法。首先,我們導出滿足差分路線正確對的約束條件,而后,將這些約束條件轉(zhuǎn)化為SAT問題,保證SAT問題的解與路線的所有正確對一一對應(yīng)。然后,使用求解器的多解搜索模式,搜索服從差分路線的所有正確對�；谶@一方法,我們改進了 Mendel等人[86]給出的迭代和非迭代差分閉包概率的結(jié)果�；谶@些針對差分閉包改進的結(jié)果,已有的對于LED64算法縮短輪的攻擊都得到了不同程度的改進。對于Midori64算法,我們構(gòu)建了一種自動化評估差分閉包弱密鑰空間的模型。首先,我們導出一個密鑰作為弱密鑰所滿足的必要條件,而后針對這些條件構(gòu)建SAT模型,并調(diào)用求解器求解�；谶@一方法,我們給出了 Midori64算法兩個4輪差分閉包的實例,對這兩個差分閉包,超過78%的密鑰將使其變?yōu)椴豢赡懿罘?換言之,它們的弱密鑰比例非常低。如果該路線用于差分攻擊,那么很可能錯誤的將正確密鑰當作錯誤密鑰,這就使得差分分析理論結(jié)果與實際情況產(chǎn)生偏差。與這一現(xiàn)象相對應(yīng),我們考慮差分閉包確定的那些“極弱的”密鑰,在這些密鑰下,差分攻擊的成功率將大于理論結(jié)果。該問題與討論差分閉包中同時成立的路線數(shù)量相關(guān),我們發(fā)現(xiàn)這類問題可以轉(zhuǎn)化為一類特殊的Max-PoSSo問題。對此,我們構(gòu)建SAT模型以確定差分閉包中可兼容路線的最大數(shù)量。最后,我們給出了 Midori64算法一條差分閉包的實例,對于2-12的密鑰,差分閉包的概率由期望值2-23.79提升到2-16。這一現(xiàn)象表明,在這些“極弱”密鑰下,差分攻擊將更有可能成功,或者說,我們可以以更低的代價實現(xiàn)差分攻擊。這些例子提醒我們,對于密鑰生成算法簡單的輕量級算法,在進行差分分析時,需要格外注意區(qū)分器本身的有效性。構(gòu)建卡方多重/多維零相關(guān)線性分析新模型,用該模型給出了TEA算法單密鑰情境下的最優(yōu)攻擊:作為更加成熟的密碼分析方法,多重和多維零相關(guān)線性分析克服了經(jīng)典零相關(guān)攻擊在數(shù)據(jù)復雜度方面的缺陷,使得零相關(guān)分析方法被廣泛應(yīng)用于系列對稱密碼攻擊的同時,成為了很多算法的最優(yōu)攻擊方法。雖然多重和多維零相關(guān)模型在對眾多密碼算法的分析中顯示出了優(yōu)越性,但這兩個模型對于零相關(guān)路線數(shù)量的限制條件仍然存在。為了消除這一約束條件,我們構(gòu)建了卡方多重/多維零相關(guān)線性分析模型。由于在模型構(gòu)建過程中取消了卡方分布的正態(tài)逼近過程,新模型在復雜度評估方面達到更高精度的同時,有效性不再依賴路線數(shù)量的假設(shè)�？ǚ侥Ｐ偷奶岢鲈诹阆嚓P(guān)分析領(lǐng)域具有十分重要的意義:一方面,新模型拓寬了零相關(guān)模型的應(yīng)用范圍,具有普適性;另一方面,新的卡方多重模型允許我們在單路線環(huán)境下使用低于整個明文空間的數(shù)據(jù)量對密碼算法進行分析,克服了傳統(tǒng)零相關(guān)分析在這一方面的不足。我們將卡方多維攻擊模型應(yīng)用于CLEFIA-192算法的分析,在對已有攻擊復雜度給出更精確評估的同時,使用更少的零相關(guān)路線對算法的多維零相關(guān)分析結(jié)果進行了改進。另外,我們使用新的卡方多重零相關(guān)分析模型對TEA算法和XTEA算法關(guān)于多重零相關(guān)分析的抵抗性重新進行了評估,給出的TEA算法的23輪攻擊是該算法在單密鑰環(huán)境下數(shù)據(jù)量低于整個明文空間的最好攻擊結(jié)果。完善了基于MILP方法自動化搜索比特級分離特性的工具:作為傳統(tǒng)積分性質(zhì)的一種推廣,分離特性由于能夠更確切的刻畫傳統(tǒng)的ALL特性和BAL-ANCE特性之間的隱含性質(zhì),已經(jīng)成為搜索積分區(qū)分器的一種強有力工具。而比特級分離特性由于能對算法的代數(shù)性質(zhì)進行更精準的把控,通�？梢詫С霰葌鹘y(tǒng)方法性質(zhì)更好的區(qū)分器,然而直接調(diào)用該方法在復雜度方面的缺陷限制了其廣泛應(yīng)用。2016年的亞密會上,Xiang等人提出了基于MILP思想自動化搜索比特級分離特性的方法,這在一定程度上緩解了比特級分離特性對目標算法分組長度的約束,改進了一些以比特置換作為線性層的算法的積分區(qū)分器。然而,對那些以復雜線性變換作為擴散層的算法,這一方法的適用性還不得而知。以此為動機,我們首先將原有的復制模型和異或模型分別進行推廣,使其適配于具有多輸出分支的復制操作和具有多輸入分支的異或操作�；趯�性變換本源表示的觀測,我們使用兩個推廣的模型給出了構(gòu)建復雜線性層MILP模型的一般方法。結(jié)合該方法,解決了基于MILP方法比特級分離特性的自動化搜索在具有非比特置換線性層算法上的適用性問題,拓寬了 MILP搜索方法的使用范圍,使其在搜索積分區(qū)分器方面發(fā)揮更大的優(yōu)勢�？紤]到ARX類算法在分組密碼算法中的重要地位,我們構(gòu)建了模加運算的MILP模型,使得基于MILP思想的比特級分離特性自動化搜索方法推廣到ARX類算法�；谏鲜鐾茝V的模型,我們對一系列算法的積分區(qū)分器進行了搜索,對Midori64算法、LED64算法、Joltik-BC算法、Serpent 算法、Noekeon算法、HIGHT算法和LEA等算法的積分區(qū)分器給出了不同程度的改進。構(gòu)建了基于SAT方法ARX類算法比特級分離特性的自動化搜索工具:注意到在ARX類算法差分/線性路線的自動化搜索中,基于SAT/SMT的方法在表現(xiàn)上優(yōu)于那些基于MILP的方法,我們針對ARX類算法構(gòu)建了基于SAT問題自動化搜索比特級分離特性的工具。首先,我們對三種基本運算(復制運算、與運算和異或運算)的比特級分離特性建模,將分離特性在運算中的傳遞規(guī)律轉(zhuǎn)化為滿足合取范式形式的邏輯表達式。隨后,基于這三種基本操作,我們構(gòu)建了刻畫模加運算比特級分離特性的SAT模型。設(shè)置好初始分離特性和終止規(guī)則后,ARX算法比特級分離特性的搜索問題將轉(zhuǎn)化為SAT問題,進而可調(diào)用求解器求解。為了快速定位目標算法的最優(yōu)積分區(qū)分器,我們給出了一種高效的搜索算法,這一算法可以幫助我們縮減初始分離特性的搜索空間,快速定位導出最優(yōu)積分區(qū)分器的初始分離特性的形式�；谶@一方法,我們得到了SHACAL-2算法的17輪積分區(qū)分器,這使得該算法最優(yōu)積分區(qū)分器輪數(shù)改進了 4輪。除此之外,對LEA算法、HIGHT算法和SPECK算法,新獲取的積分區(qū)分器與用MILP方法得到的結(jié)果相比都有不同程度的改進。構(gòu)建了基于SMT方法自動化搜索字級分離特性的新工具:一方面,考慮到自動化搜索在字級分離特性評估中的空白;另一方面,觀察到對大狀態(tài)/含復雜運算的算法在比特水平追蹤分離特性的困難性,我們使用基于SMT的方法實現(xiàn)了字級分離特性的自動化搜索。首先,考慮對字級分離特性在一些基本運算中的傳遞規(guī)律建模,模型的構(gòu)建采用排除法。而后,合理的設(shè)置初始分離特性和終止條件,以將字級分離特性的搜索問題轉(zhuǎn)化為SMT問題,并調(diào)用開源求解器對問題進行求解�；谠摲椒�,我們找到了 CLEFIA算法的10輪積分區(qū)分器,這些區(qū)分器比之前最好的區(qū)分器長一輪。對于哈希函數(shù)Whirlpool的內(nèi)層置換,我們改進了 4輪和5輪區(qū)分器的數(shù)據(jù)復雜度。對Rijndael-192和Rijndael-256算法,我們給出了6輪積分區(qū)分器,這比之前最好結(jié)果多兩輪。除此之外,使用新的積分區(qū)分器,我們將CLEFIA算法的積分攻擊結(jié)果改進一輪。
【圖文】：

而后，我們將所得的約束條件轉(zhuǎn)化為滿足合取范式形式的ＳＡＴ模型。最后，逡逑使用ＳＡＴ求解器的多解功能，求解差分閉包的正確對。逡逑關(guān)于正確對的約束條件如圖２．２所示，記和Ａｙｉ為第ｉ輪ＳｕｂＣｅｌｌｓ運逡逑算的輸入和輸出差分，ｆ和Ｖ分別表示第ｉ輪ＳｕｂＣｅｌｌｓ運算的輸入值和輸出逡逑值，，表示第＊輪使用的輪常數(shù)矩陣。逡逑由于步函數(shù)中不含有關(guān)于密鑰的操作，在這里等式（２．５）應(yīng)調(diào)整為逡逑Ｍａｆｊｔ１邋■邋ｘｉ＋１邋＝邐？邋ｙ｛邋？邋ｃｌ＋１）邋＝邋Ｍａｔ＾Ｔ１邋■邋Ｐ邋■邋ｙｌ邋＠邋Ｍａｔ＾ｔ１邋？邋ｃ�。卞澹藉澹郑澹悖蓿�，逡逑其中尸＝邋ＭＣ。ＳＲ。因此，給定的差分路線僅對＃的值構(gòu)成約束。換言之，式逡逑－２７邋－逡逑

中剩余的行向量Ｍｚ（ｉ）均為Ｍ0，邋Ｍｘ，．．．，的線性組合，那么相應(yīng)的變量逡逑Ｍ／ｊ）ｉ可以表示成變量；ｒ0，化，．．．，的異或。為了更直觀的理解這一過程，逡逑請參考圖２．４。由于我們使用了主密鑰的線性組合，那么ｘａｌｈｌ丨…丨的一個逡逑確定值相當于對整個密鑰空間加入了纟個線性約束條件，因此ｚｏｌｌｎｌｌ邋？邋？邋■邋｜｜ｍ逡逑的一個解對應(yīng)了主密鑰ＭＭ…Ｍｍ的１冗丨／２￡種可能的取值。如果我們最終逡逑對變量孫ＩＮ丨丨…丨丨Ａｄ可以得到＆個解，那么一個密鑰落入集合／ｃ邋一邋Ｉ］１邋Ｖ；？逡逑ｉ＝Ｑ逡逑的概率應(yīng)為ｔ／２￡。逡逑弱密鑰比例低于５０％的４輪差分閉包我們將上述基于ＳＡＴ問題的搜索技巧逡逑應(yīng)用于Ｍｉｄｏｒｉ６４的一些４輪差分閉包的分析。下面給出兩個例子。對于第一逡逑個差分閉包，其弱密鑰比例低于２１．３６％。對于第二個差分閉包，其期望條件概逡逑率在理論上保證了其在差分分析中的有效性，但其弱密鑰比例低于３．９４％，這逡逑也說明對于９６．０６％的密鑰，該差分閉包將變?yōu)椴豢赡懿罘�。這些反例具有非常逡逑重要的意義，因為在進行差分分析時，我們很少考慮區(qū)分器本身成立的概率，而逡逑差分閉包的概率關(guān)于密鑰的分布影響了攻擊的有效性。如果一個差分閉包在固逡逑定密鑰下差分概率為零的概率非常高，當我們將其用于攻擊時，那么很可能錯逡逑誤的將正確密鑰當作錯誤密鑰
【學位授予單位】：山東大學
【學位級別】：博士
【學位授予年份】：2019
【分類號】：TN918.1


本文編號：2601091