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

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

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

輪函數(shù)

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

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