分組密碼路線的自動(dòng)化搜索及SM4、SPECK線性分析.pdf

1、隨著科技的發(fā)展，特別是智能手機(jī)的普及，網(wǎng)絡(luò)已經(jīng)觸及到生活的每個(gè)角落，使得大眾對(duì)于網(wǎng)絡(luò)的依賴性逐漸增強(qiáng)，并且在一定程度上改變了原有的生活方式。在這樣的背景下，人們對(duì)于安全的網(wǎng)絡(luò)環(huán)境的需求日益巨大，全世界的網(wǎng)絡(luò)安全學(xué)者都致力于滿足人們不同應(yīng)用場(chǎng)景和不同安全需求的密碼協(xié)議的研究，包括:軟件和硬件安全，信息傳播安全，網(wǎng)絡(luò)系統(tǒng)信息安全，交互數(shù)據(jù)安全等。其中加密是實(shí)現(xiàn)數(shù)據(jù)機(jī)密性的一種重要的手段，可以將傳播的信息變成對(duì)非認(rèn)證用戶隱藏的亂碼。
　

2、　分組密碼算法是實(shí)現(xiàn)數(shù)據(jù)加密的方式之一，并且容易實(shí)現(xiàn)同步，故而適用于很多應(yīng)用場(chǎng)景，誕生了很多著名的密碼算法，其中SPECK算法族是在2013年6月由美國(guó)國(guó)家安全局公開(kāi)的為了優(yōu)化軟件實(shí)現(xiàn)的輕量級(jí)分組密碼算法族。基于SPECK算法廣泛的應(yīng)用前景，很有必要全面的評(píng)估該算法抗各種攻擊的安全性分析。目前已有很多SPECK的安全性分析結(jié)果。SMS4算法在2006年由中國(guó)政府發(fā)行公布，作為底層分組密碼算法服務(wù)于WAPI（WLAN認(rèn)證和隱私的基礎(chǔ)設(shè)施）

3、的無(wú)線局域網(wǎng)的安全性。于2012年，SMS4算法被宣布為中國(guó)商業(yè)分組密碼的標(biāo)準(zhǔn)，更名為SM4。SM4從出現(xiàn)之初就受到了密碼社會(huì)很多的關(guān)注，已有很多分析結(jié)果。
　　分組密碼算法的分析方法也是多種多樣，最早的安全性評(píng)估方法是著名的差分分析方法，這種分析方法很快就被整個(gè)密碼分析學(xué)界所熟知并被廣泛使用，成為了密碼算法最主要的分析方法之一，也是設(shè)計(jì)新算法時(shí)必須考慮可以免疫的分析方法。另一個(gè)著名的分析方法是線性分析，線性分析和差分分析是分析分

4、組密碼算法的最主要的兩種方法。從這兩種分析方法逐步衍生出很多其它的分析方法比如:截?cái)嗖罘址治?，反彈攻擊，多線性分析，飛去來(lái)器攻擊，多維線性分析，線性殼分析等。除此之外還有代數(shù)攻擊，積分分析，零相關(guān)線性分析方法，不可能差分分析等。對(duì)于一個(gè)分組密碼算法而言，需要考量算法的安全性，這就需要對(duì)算法用各種分析方法進(jìn)行分析。
　　本文的第一部分，介紹了如何構(gòu)建搜索基于S盒的密碼算法的（不可能）差分和線性路線的STP Constant solv

5、er模型。
　　構(gòu)建基于S盒的密碼算法的（不可能）差分和線性路線的STP模型:近年來(lái)，自動(dòng)化搜索工具在設(shè)計(jì)新的密碼算法或者評(píng)估密碼算法的安全性上發(fā)揮了重要的作用。常見(jiàn)的用于密碼學(xué)的自動(dòng)化搜索工具有三大類:基于MILP的自動(dòng)化搜索模型，基于SAT/SMT的自動(dòng)化搜索模型以及基于CP的自動(dòng)化搜索模型。本文關(guān)注基于SAT/SMT的自動(dòng)化搜索模型，并且使用的求解器是STP constraint solver(Simple Theorem

6、Prover SMT solver)。STP已被用于搜索ARX算法的差分和線性路線，但是還沒(méi)有發(fā)展搜索基于S盒算法的差分和線性路線的工作?；贛ILP的工具已經(jīng)從最初的簡(jiǎn)單搜索活性S盒個(gè)數(shù)發(fā)展到可以自動(dòng)化搜索真實(shí)的差分和線性路線的程度，并且可以構(gòu)建搜索基于S盒的密碼算法或者ARX算法的不可能差分以及零相關(guān)線性路線的模型。這些工具可以完全描述4比特S盒的差分分布表或者線性分布表的特征。然而難以有效得描述8比特S盒的差分分布表或者線性分布表

7、。CP技術(shù)被用于設(shè)計(jì)新的通用工具來(lái)搜索（不可能/相關(guān)密鑰）差分路線，（零相關(guān)）線性路線以及積分區(qū)分器。從已有文獻(xiàn)中可以看出基于CP的工具的優(yōu)點(diǎn)是可以處理一些基于8比特S盒的算法。然而，當(dāng)前的自動(dòng)化搜索工具還不能處理完整描述S盒的差分分布表或者線性分布表中的項(xiàng)不全是2的冪次的情況。我們工作的目的是為了擴(kuò)充STP在自動(dòng)化搜索基于S盒的密碼算法的差分和線性路線的應(yīng)用，并且填補(bǔ)了搜索差分分布表和線性分布表中有非2的冪次的8比特S盒算法的具有最優(yōu)

8、概率和相關(guān)度的差分和線性自動(dòng)化工具的空白。首先，建立了搜索具有最少活性S盒的差分和線性路線的STP模型。在搜索具有最少活性S盒的路線時(shí)，僅關(guān)注合理的差分/線性傳遞不計(jì)算S盒的差分特征/線性近似的概率?；诖耍o出了一些等式來(lái)描述經(jīng)過(guò)S盒的合理的差分/線性傳遞。利用這些等式，構(gòu)建了搜索具有最少活性S盒的差分/線性路線的STP模型。特別地，該模型對(duì)基于8比特S盒的算法也很有效。其次，給出了搜索具有最優(yōu)概率的差分路線的STP模型和具有最優(yōu)相關(guān)

9、度的線性路線的STP模型。最優(yōu)概率或相關(guān)度的路線不一定具有最少活性S盒，同時(shí)具有相同活性S盒的路線概率未必相同，這需要具體描述每個(gè)S盒的差分特征/線性近似的概率。在描述概率的過(guò)程中，為了不丟失更好的路線，設(shè)計(jì)提出了近似函數(shù)，可以用來(lái)刻畫(huà)計(jì)算路線的概率或相關(guān)度。如果可以窮盡所有可能的搜索，就可以保證找到具有最優(yōu)概率/相關(guān)度的差分/線性路線。這是首次提出利用STP模型來(lái)搜索基于S盒的密碼算法的差分或線性路線，并且這種方法還適用于差分分布表或

10、線性分布表中的項(xiàng)有非2的冪次的情況。這種處理概率/相關(guān)度的近似函數(shù)構(gòu)建法同時(shí)也適用于其他難以做浮點(diǎn)運(yùn)算或乘運(yùn)算的自動(dòng)化搜索工具。最后，我們給出了考慮密鑰生成算法的不可能差分路線搜索模型。一般的不可能差分路線自動(dòng)化搜索工具都是建立在搜索具有最少活性S盒的路線的模型的基礎(chǔ)上，只需要去掉模型的活性S盒個(gè)數(shù)的限制，并限制合適的輸入輸出差分，如果無(wú)解，那么就可以確定一條不可能差分路線。但是這種方法無(wú)法考慮密鑰生成算法，我們既需要考慮差分傳遞還需要

11、考慮密鑰生成算法的影響，所以構(gòu)建的模型跟蹤算法從明文值到密文值的傳遞而非差分傳遞。據(jù)我們所知，這是首次給出的考慮密鑰生成算法的不可能差分路線搜索模型。最終，我們用給出的方法搜索ARIA和ICEBERG的線性路線，SM4的差分路線。并給出了ARIA算法最優(yōu)的4輪、5輪和6輪的線性路線，ICEBERG算法最優(yōu)的6輪線性路線以及SM4算法19輪概率為2-123的差分路線。這些結(jié)果不同程度的改進(jìn)了之前的最好結(jié)果，ARIA算法是輪數(shù)加長(zhǎng)，ICEB

12、ERG和SM4算法分別是相關(guān)度和概率增加。而且，利用考慮密鑰生成算法的不可能差分路線搜索模型，對(duì)5輪AES-128進(jìn)行截?cái)嗖豢赡苈肪€搜索，發(fā)現(xiàn)不存在輸入輸出差分儀有一個(gè)活性字節(jié)的5輪AES-128截?cái)嗖豢赡懿罘帧?br>　　論文的后半部分我們對(duì)SM4和SPECK這兩種算法的線性分析結(jié)果進(jìn)行了改進(jìn)。
　　利用部分線性分布表搜索短輪迭代路線改進(jìn)SM4的線性分析結(jié)果:在之前對(duì)SM4的所有攻擊中，可以攻擊輪數(shù)最多的方法是線性分析和差分攻擊

13、，并且兩者都是基于19輪的區(qū)分器。為改進(jìn)之前的結(jié)果，我們首先關(guān)注能否找到更長(zhǎng)的SM4區(qū)分器。之前最好的線性攻擊利用的是19輪的線性近似，如果直接搜索大輪數(shù)的線性近似，搜索代價(jià)太大并且可能無(wú)法搜索出比現(xiàn)有結(jié)果更好的線性近似。我們想設(shè)計(jì)一個(gè)算法可以利用S盒的部分線性掩碼表來(lái)搜索小輪數(shù)的迭代線性近似。首先證明了SM4不存在一輪或兩輪的非平凡迭代線性近似，其后給出了SM4三輪非平凡線性近似的一些特性?；谶@些特性，使用搜索算法得到短輪的線性近似

14、，如果搜索過(guò)程中直接將S盒的線性分布表全部放進(jìn)去會(huì)導(dǎo)致搜索效率低下，所以借鑒Biryukov和Velichkov利用部分差分分布表搜索ARX算法差分路線的方法，利用S盒的部分線性分布表搜索SM4的三輪迭代線性近似，基于找到的三輪迭代線性近似構(gòu)建出20輪SM4的線性近似。到目前為止，我們給出的線性近似是最好的。更進(jìn)一步，利用新找到的20輪線性近似，給出了24輪SM4的密鑰恢復(fù)攻擊，這是目前攻擊輪數(shù)最長(zhǎng)的攻擊結(jié)果。其次，利用3輪迭代線性近似

15、，還可以構(gòu)建19輪線性近似，比之前最好的19輪線性近似的相關(guān)度高。利用這條線性近似改進(jìn)了之前最好的23輪線性攻擊的結(jié)果，同之前最好的線性分析結(jié)果比較存儲(chǔ)復(fù)雜度由2116字節(jié)降為285字節(jié)，數(shù)據(jù)復(fù)雜度由2126.5次23輪加密降為2120.3次23輪加密。
　　利用部分線性掩碼表結(jié)合分段搜索策略改進(jìn)SPECK算法線性分析:在當(dāng)時(shí)所有的分析結(jié)果中，最好的減輪SPECK分析結(jié)果是Abed等人和Dinur提出的差分分析結(jié)果。而線性分析結(jié)果

16、當(dāng)時(shí)僅有Yao等人給出的線性分析結(jié)果。這個(gè)線性分析是應(yīng)用Wallén的列舉算法結(jié)合Matsui的分支定界法來(lái)搜索線性近似。但是同差分分析相比，線性分析還有很大的差距，特別是對(duì)于SPECK-96和SPECK-128。為了實(shí)現(xiàn)SPECK算法的線性攻擊，首先需要找到更好的線性近似，這需要設(shè)計(jì)一個(gè)合適的搜索算法。將所有合理的輸入輸出掩碼及其相關(guān)度存入預(yù)計(jì)算表，并將該表記為模2n加的線性掩碼表。但是，如果搜索中使用模2n加的線性掩碼表，那么搜索效

17、率非常低，以至于搜索不可行，故而為了加速路線搜索算法，我們將非線性操作的線性掩碼表改為部分線性掩碼表，借鑒Biryukov和Velichkov搜索ARX算法差分路線的方法。并且使用紅黑樹(shù)來(lái)存儲(chǔ)部分線性掩碼表來(lái)進(jìn)一步的減少搜索時(shí)間并降低存儲(chǔ)復(fù)雜度。搜索算法同時(shí)還結(jié)合分支定界法和分段搜索方法來(lái)降低搜索時(shí)間。最后給出了SPECK算法族比當(dāng)時(shí)最好的線性路線更好的線性路線，包括SPECK-32的9輪區(qū)分器，SPECK-48的10輪區(qū)分器，SPEC