【摘要】：隨著物聯(lián)網(wǎng)時(shí)代向萬物互聯(lián)時(shí)代的不斷推動(dòng),互聯(lián)網(wǎng)為生活方方面面帶來便利的同時(shí),網(wǎng)絡(luò)安全問題也在新形勢(shì)下面臨新的挑戰(zhàn)。作為保障網(wǎng)絡(luò)安全的基石,密碼在安全認(rèn)證、加密保護(hù)和信息傳遞等方面發(fā)揮了十分重要的作用。與公鑰密碼體制相比,對(duì)稱密碼算法由于效率高、算法簡單、適合加密大量數(shù)據(jù)的優(yōu)點(diǎn)應(yīng)用更為廣泛�；谶@一事實(shí),對(duì)分組密碼算法分析與設(shè)計(jì)的研究在新環(huán)境下顯得尤為重要。本文圍繞分組密碼攻擊模型的構(gòu)建和自動(dòng)化密碼分析這一主題展開。首先,在攻擊模型構(gòu)建方面,我們提出了卡方多重/多維零相關(guān)線性分析模型,并將該模型用于一系列算法的多重和多維零相關(guān)分析中。其次,針對(duì)自動(dòng)化密碼分析,我們一方面著眼于攻擊路線的自動(dòng)化搜索問題,另一方面試圖借助自動(dòng)化思想解決密碼學(xué)中的理論問題。在路線自動(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)化解決理論問題方面,討論了差分分析中的差分聚集現(xiàn)象,對(duì)兩個(gè)算法給出了更加精確的差分分析。最后,我們對(duì)SIMON算法的所有版本給出了零相關(guān)攻擊結(jié)果。具體結(jié)果如下。給出了基于SAT方法自動(dòng)化搜索并分析帶S盒算法差分閉包的工具:為了填補(bǔ)SAT方法在搜索差分閉包方面的空白,我們給出了基于SAT問題的差分閉包自動(dòng)化搜索工具。首先,我們給出對(duì)線性層和由多個(gè)小S盒構(gòu)成的非線性層的刻畫。隨后,給出了目標(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問題,保證SAT問題的解與路線的所有正確對(duì)一一對(duì)應(yīng)。然后,使用求解器的多解搜索模式,搜索服從差分路線的所有正確對(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è)差分閉包,超過78%的密鑰將使其變?yōu)椴豢赡懿罘?換言之,它們的弱密鑰比例非常低。如果該路線用于差分攻擊,那么很可能錯(cuò)誤的將正確密鑰當(dāng)作錯(cuò)誤密鑰,這就使得差分分析理論結(jié)果與實(shí)際情況產(chǎn)生偏差。與這一現(xiàn)象相對(duì)應(yīng),我們考慮差分閉包確定的那些“極弱的”密鑰,在這些密鑰下,差分攻擊的成功率將大于理論結(jié)果。該問題與討論差分閉包中同時(shí)成立的路線數(shù)量相關(guān),我們發(fā)現(xiàn)這類問題可以轉(zhuǎn)化為一類特殊的Max-PoSSo問題。對(duì)此,我們構(gòu)建SAT模型以確定差分閉包中可兼容路線的最大數(shù)量。最后,我們給出了 Midori64算法一條差分閉包的實(shí)例,對(duì)于2-12的密鑰,差分閉包的概率由期望值2-23.79提升到2-16。這一現(xiàn)象表明,在這些“極弱”密鑰下,差分攻擊將更有可能成功,或者說,我們可以以更低的代價(jià)實(shí)現(xiàn)差分攻擊。這些例子提醒我們,對(duì)于密鑰生成算法簡單的輕量級(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)建過程中取消了卡方分布的正態(tài)逼近過程,新模型在復(fù)雜度評(píng)估方面達(dá)到更高精度的同時(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ù)量低于整個(gè)明文空間的最好攻擊結(jié)果。完善了基于MILP方法自動(dòng)化搜索比特級(jí)分離特性的工具:作為傳統(tǒng)積分性質(zhì)的一種推廣,分離特性由于能夠更確切的刻畫傳統(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)算法分組長度的約束,改進(jìn)了一些以比特置換作為線性層的算法的積分區(qū)分器。然而,對(duì)那些以復(fù)雜線性變換作為擴(kuò)散層的算法,這一方法的適用性還不得而知。以此為動(dòng)機(jī),我們首先將原有的復(fù)制模型和異或模型分別進(jìn)行推廣,使其適配于具有多輸出分支的復(fù)制操作和具有多輸入分支的異或操作。基于對(duì)線性變換本源表示的觀測(cè),我們使用兩個(gè)推廣的模型給出了構(gòu)建復(fù)雜線性層MILP模型的一般方法。結(jié)合該方法,解決了基于MILP方法比特級(jí)分離特性的自動(dòng)化搜索在具有非比特置換線性層算法上的適用性問題,拓寬了 MILP搜索方法的使用范圍,使其在搜索積分區(qū)分器方面發(fā)揮更大的優(yōu)勢(shì)�？紤]到ARX類算法在分組密碼算法中的重要地位,我們構(gòu)建了模加運(yùn)算的MILP模型,使得基于MILP思想的比特級(jí)分離特性自動(dòng)化搜索方法推廣到ARX類算法�；谏鲜鐾茝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問題自動(dòng)化搜索比特級(jí)分離特性的工具。首先,我們對(duì)三種基本運(yùn)算(復(fù)制運(yùn)算、與運(yùn)算和異或運(yùn)算)的比特級(jí)分離特性建模,將分離特性在運(yùn)算中的傳遞規(guī)律轉(zhuǎn)化為滿足合取范式形式的邏輯表達(dá)式。隨后,基于這三種基本操作,我們構(gòu)建了刻畫模加運(yùn)算比特級(jí)分離特性的SAT模型。設(shè)置好初始分離特性和終止規(guī)則后,ARX算法比特級(jí)分離特性的搜索問題將轉(zhuǎn)化為SAT問題,進(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í)分離特性的搜索問題轉(zhuǎn)化為SMT問題,并調(diào)用開源求解器對(duì)問題進(jìn)行求解�；谠摲椒�,我們找到了 CLEFIA算法的10輪積分區(qū)分器,這些區(qū)分器比之前最好的區(qū)分器長一輪。對(duì)于哈希函數(shù)Whirlpool的內(nèi)層置換,我們改進(jìn)了 4輪和5輪區(qū)分器的數(shù)據(jù)復(fù)雜度。對(duì)Rijndael-192和Rijndael-256算法,我們給出了6輪積分區(qū)分器,這比之前最好結(jié)果多兩輪。除此之外,使用新的積分區(qū)分器,我們將CLEFIA算法的積分攻擊結(jié)果改進(jìn)一輪。
【圖文】：

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

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


本文編號(hào)：2601091