分組密碼算法的不可能差分分析

發(fā)布時間：2020-07-20 13:45

【摘要】：分組密碼算法屬于對稱密碼算法,將明文消息分割為固定長度分組進行加解密運算。分組加密具有實現(xiàn)簡單、加解密速率快的優(yōu)點,是密碼體制的重要組成部分。典型的分組密碼算法如DES和AES是美國政府的標準加密算法,其應用領域從郵件加密到轉賬交易,與生活息息相關。對分組密碼算法進行安全性分析能夠評估算法的優(yōu)缺點,保證密碼算法的合理應用,非常具有現(xiàn)實意義。不可能差分分析由Knudsen和Biham分別獨立提出,屬于差分分析技術的變種,利用數(shù)據(jù)的差分傳播特性對密碼算法進行安全性評估,是分組密碼算法安全性分析的重要方法之一。與經(jīng)典差分分析技術中利用高概率差分進行密鑰恢復不同,不可能差分分析依靠不可能出現(xiàn),即概率為0的差分來過濾錯誤的候選密鑰,因為利用正確密鑰對數(shù)據(jù)加密不會出現(xiàn)這樣的差分。本文以不可能差分分析為主要技術手段,對幾個重要的分組密碼算法進行了分析,包括兩個部分:第一部分屬于不可能差分分析技術的經(jīng)典應用,對ASIACRYPT 2016算法Simpira進行了研究,結合大S盒技術和算法采用的廣義Feistel結構特點,尋找到Simpira算法4分支版本的首個9輪不可能差分區(qū)分器,給出了算法的首個分析結果;第二部分通過分析密鑰編排方案對差分傳播特性的影響,提出一種可以由單密鑰不可能差分推導更長輪相關密鑰不可能差分的自動化搜索方法,這也是首個針對相關密鑰不可能差分的自動化搜索方案,利用此方法,對FSE2017接收算法QARMA-64、CAESAR競賽勝出方案Deoxys的內(nèi)置可調(diào)分組密碼算法Deoxys-BC-256和CAESAR競賽第二輪入選方案Joltik內(nèi)置可調(diào)分組密碼算法Joltik-BC-128進行了分析,相較已有工作,給出了算法的更精確安全評估結果,具有國際水平。兩個工作結果均發(fā)表于 Science China Information Sciences�！� Simpira v2的單密鑰不可能差分分析密碼置換函數(shù)Simpira由Shay Gueron和Nicky Mouha設計,采用AES輪函數(shù)作為唯一基礎組件,支持128×b比特輸入,其中b為任意正整數(shù),用Simpira-b表示輸入分支數(shù)目為b的算法版本。當b = 1時,Simpira-1可以被看作輪密鑰為確定值的12輪AES算法;當b≥2時,Simpira-b是一個F函數(shù)由兩個AES輪函數(shù)構成的廣義Feistel結構。根據(jù)設計者推薦,Simpira可以作為Even-Mansour結構的置換函數(shù)構造成為一個沒有輪密鑰的分組密碼算法,算法的分組長度與密鑰長度均為128× b 比特。Simpira的多分支結構充分考慮了密碼學界和工業(yè)界對AES算法的研究進展。繼2001年Rijndael算法被美國國家標準與技術研究院(NIST)選為高級加密標準(AES)以來,如何更高效的實現(xiàn)AES算法是密碼工作者最關注的問題之一。許多芯片公司例如Intel、AMD和ARM都相繼研發(fā)了適用于各自處理器的AES算法實現(xiàn)指令,大大減少了數(shù)據(jù)處理時的資源開銷。但是,由于AES利用8比特S盒作為非線性層,高延遲無法避免的成為了算法的運算效率瓶頸。利用AES-GCM模式運行AES加密指令是當今比較有效的解決方案。在這種模式下,數(shù)據(jù)分組互相獨立,對加密指令進行流水線操作,從而可以提高吞吐量,彌補了算法高延遲的缺點。Simpira的設計靈感便是從這種獨立加密、并行計算的工作模式中獲得。此外,利用AES輪函數(shù)作為基礎組件可以充分利用已有的AES算法實現(xiàn)指令;F函數(shù)的安全性也直接依賴于兩輪AES算法的安全性。Simpira v2是在Simpira v1基礎上改進的正式發(fā)布版本,發(fā)表于國際密碼學會議ASIACRYPT 2016。本文對輸入為512比特的Simpira v2版本,即Simpira-4進行研究。通過對結構特點進行分析,我們發(fā)現(xiàn)了 Simpira-4的首個9輪不可能差分區(qū)分器�？紤]到Simpira-4和Even-Mansour結構的安全聲明,我們利用短輪不可能差分對Simpira-4作為置換函數(shù)在Even-Mansour下構造的分組密碼進行了安全性分析:利用8條6輪不可能差分路線,對7輪算法進行了攻擊,恢復了 256比特密鑰,數(shù)據(jù)復雜度為257,時間復雜度為257;利用10條7輪不可能差分,通過對不可能差分前擴1輪或后擴1輪,攻擊了8輪算法并可以恢復所有512比特密鑰,攻擊的數(shù)據(jù)復雜度為2170,時間復雜度為2170。這是Simpira v2的首個分析結果。·相關密鑰不可能差分分析在相關密鑰分析模型中,敵手可以獲取密碼算法在不同密鑰作用下的運算結果,雖然他不能得知不同密鑰的具體值,但可以知道甚至控制這些密鑰之間的某些數(shù)學關系。這種分析方法可以與其他密碼分析方法相結合對密碼算法進行分析,并且取得了很多有價值的攻擊結果,例如全輪AES-192、AES-256的理論破解便是得益于相關密鑰分析與飛去來器分析(Boomerang)的結合運用。但是,由于相關密鑰模型賦予了敵手對密鑰比特的控制能力,密碼學界一直認為這種假設條件過強,更傾向于將其歸為一種理想模型。隨著可調(diào)分組密碼算法和TWEAKEY框架概念的提出,這種模型的現(xiàn)實意義才重新引起了學界重視。在可調(diào)分組密碼中,調(diào)柄比特可以公開。此外,為了保證算法在各種資源受限環(huán)境中的高效計算,調(diào)柄編排所需要資源開銷應該盡可能小,為了滿足這一要求,可調(diào)分組密碼設計者往往采用非常簡單的密鑰編排方案。在TWEAKEY框架中,使用調(diào)柄密鑰來統(tǒng)一看待調(diào)柄比特和密鑰比特,只要保證調(diào)柄密鑰的總長度一定,密鑰長度和調(diào)柄長度可以任意變化。公開的調(diào)柄比特使得不同調(diào)柄密鑰之間的數(shù)學關系更容易被發(fā)現(xiàn);在TWEAKEY框架下,敵手則可以根據(jù)攻擊的復雜度需求選擇相應的密鑰比特長度。因此,可調(diào)分組密碼在相關密鑰模型下更容易遭受攻擊。相關密鑰不可能差分分析是相關密鑰模型和不可能差分分析技術的巧妙結合,與其他分析方法類似,對算法進行相關密鑰不可能差分分析的前提是尋找到有效的相關密鑰不可能差分區(qū)分器。在本文中,通過分析不同調(diào)柄/密鑰編排方案對算法內(nèi)部差分傳播特性的影響,我們給出一種基于MILP技術的相關調(diào)柄/密鑰不可能差分自動化搜索方案。當滿足一定條件時,該搜索方案可以利用單密鑰不可能差分進行更長輪相關調(diào)柄/密鑰不可能差分的推導。據(jù)我們所知,這是首個可以進行相關密鑰不可能差分自動化搜索的方案。本文以三種具有代表性的可調(diào)分組密碼算法為例,介紹了相關調(diào)柄/密鑰不可能差分區(qū)分器的搜索過程并進行了密鑰恢復攻擊:1.QARMA-64 QARMA-64是由Roberto Avanzi設計的輕量級可調(diào)分組密碼,發(fā)表于國際密碼學會議FSE 2017,已被ARM公司采用作為實現(xiàn)指針認證功能的標準算法。算法采用代替-置換網(wǎng)絡(SPN)結構,包括14個輪函數(shù)和一個中間結構,其中中間結構由兩個輪函數(shù)和一個稱作Pseudo-Reflector的結構組成。密鑰長度為128比特,調(diào)柄和分組長度均為64比特。在本文中,結合算法輪密鑰相等和其輪函數(shù)結構的特點,相關調(diào)柄/密鑰差分可以完全由調(diào)柄比特差分構造。通過將密鑰差分設為0,我們搜索到算法的7輪相關調(diào)柄不可能差分區(qū)分器并基于此區(qū)分器攻擊了 11輪算法。相較于之前的結果,將攻擊輪數(shù)提高了 1輪,攻擊的數(shù)據(jù)復雜度為261,時間復雜度為264.4。2.Deoxys-BC-256 Deoxys-BC-256為CAESAR認證加密競賽勝出方案Deoxys的內(nèi)置可調(diào)分組密碼算法,采用TWEAKEY框架,調(diào)柄密鑰為256比特,分組長度為128比特,采用SPN結構,輪函數(shù)與AES輪函數(shù)相同,屬于類AES算法。本文中,結合Deoxys-BC-256調(diào)柄密鑰編排方案的特點,通過對3.5輪單密鑰不可能差分后擴兩輪,我們得到了一條6輪相關調(diào)柄密鑰不可能差分,并基于此差分對Deoxys-BC-256進行了超文本攻擊。當密鑰長度大于174比特,調(diào)柄長度小于82比特時,我們的方法可以攻擊10輪算法(共14輪)。攻擊的數(shù)據(jù)復雜度為2135,時間復雜度為2173.1。在密鑰比特為192比特時,之前的結果只能攻擊9輪算法,比本文中結果少1輪。3.Joltik-BC-128Joltik-BC-128是CAESAR競賽第二輪入選方案Joltik的內(nèi)置可調(diào)分組密碼算法。算法的調(diào)柄密鑰長度為128比特,分組長度為64比特,采用SPN結構,由24個輪函數(shù)組成,同樣采用了類AES結構設計。本文中我們利用6輪相關調(diào)柄密鑰不可能差分分析了算法的10輪安全性,攻擊的數(shù)據(jù)復雜度為271,時間復雜度為2109.5。這是Joltik-BC的首個分析結果,相較設計者給出的分析結果,我們將分析輪數(shù)提高了兩輪。以上結果足以作為本文中相關調(diào)柄/密鑰不可能差分搜索方案有效性的證明。在終端體積不斷縮小,密鑰編排偏向輕量化設計的趨勢下,相關密鑰模型將在密碼算法安全評估工作中扮演越來越重要的角色,相信我們的相關調(diào)柄/密鑰不可能差分自動化搜索方案會成為分析算法安全性的有效工具。
【學位授予單位】：山東大學
【學位級別】：博士
【學位授予年份】：2018
【分類號】：TN918.1
【圖文】：

輪函數(shù)

邐＾；＋１逡逑圖３．１：邋Ｓｉｍｐｉｒａ－４的輪函數(shù)逡逑圖３．１中給出了邋Ｓｉｍｐｉｍ－４輪函數(shù)的具體結構，函數(shù)狀態(tài)的計算規(guī)則可以描逡逑述為：逡逑Ｓ＾＋１邋＝邋Ｓｌ？Ｆ２ｉ＋１Ａ（Ｓ＾），逡逑Ｓ｝＋ｉ邋＝邋ｓｆ，逡逑Ｓｆ＋１邋＝邋Ｓｆ？Ｆ２ｉ＋２Ａ（Ｓｆ），逡逑Ｈ逡逑其中邋０邋ｓ邋ｉ邋￥邋１４。逡逑注意到當輪數(shù)不為４的倍數(shù)時，函數(shù)的最后輸出狀態(tài)需要進行一個簡單的逡逑置換以保證輸入輸出順序的一致性。逡逑在Ｓｉｍｐｉｒａ使用的Ｆｅｉｓｔｅｌ結構輪函數(shù)中，ｊＰ函數(shù)可以表不為＝邋ｉ＾，其逡逑中６是輸入分組中子塊的數(shù)量，ｃ是一個計數(shù)器來標記＾函數(shù)所在的輪數(shù)，從逡逑１開始計數(shù)。Ｆ函數(shù)由兩輪ＡＥＳ輪函數(shù)構成，兩個密鑰加操作與ＡＥＳ輪函數(shù)逡逑不同

分組密碼算法的不可能差分分析