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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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