分組密碼攻擊模型的構建和自動化密碼分析6頁

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

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

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

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

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

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

7、度的同時,有效性不再依賴路線數量的假設。卡方模型的提出在零相關分析領域具有十分重要的意義:一方面,新模型拓寬了零相關模型的應用范圍,具有普適性;另一方面,新的卡方多重模型允許我們在單路線環(huán)境下使用低于整個明文空間的數據量對密碼算法進行分析,克服了傳統(tǒng)零相關分析在這一方面的不足。我們將卡方多維攻擊模型應用于CLEFIA-192算法的分析,在對已有攻擊復雜度給出更精確評估的同時,使用更少的零相關路線對算法的多維零相關分析結果進行了改進。另外,我們使用新的卡方多重零相關分析模型對TEA算法和XTEA算法關于多重零相關分析的抵抗性重新進行了評估,給出的TEA算法的23輪攻擊是該算法在單密鑰環(huán)境下數據量

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

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

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

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