幾個(gè)輕量級分組密碼算法的安全性分析.pdf

1、隨著信息技術(shù)的飛速發(fā)展，密碼學(xué)作為保障信息安全的核心技術(shù)，在現(xiàn)代信息安全領(lǐng)域中發(fā)揮著越來越重要的作用。分組密碼作為現(xiàn)代密碼學(xué)的一個(gè)重要分支，其研究內(nèi)容主要包括分組密碼設(shè)計(jì)和分析兩個(gè)方面。一方面，密碼設(shè)計(jì)人員的目標(biāo)是設(shè)計(jì)出能夠抵抗所有已知攻擊的安全強(qiáng)度高的密碼算法，而另一方面，密碼分析者是在努力尋找密碼算法的安全性漏洞和破譯密碼算法的攻擊方法。這兩方面的研究相互促進(jìn)，共同推動了分組密碼理論的發(fā)展。
　　隨著物聯(lián)網(wǎng)的發(fā)展，RFID芯片

2、和無線傳感網(wǎng)絡(luò)等微型計(jì)算設(shè)備的應(yīng)用越來越廣泛，在給人們的生活帶來了極大便利的同時(shí)，如何確保了這類資源受限設(shè)備上信息的安全性，越來越引起密碼學(xué)家的重視。為了適應(yīng)物聯(lián)網(wǎng)上所使用的微型計(jì)算設(shè)備資源受限的特點(diǎn)，設(shè)計(jì)既具有低功耗和低資源占用又滿足所需要的安全性要求的輕量級分組密碼算法應(yīng)運(yùn)而生。例如TWINE,PRESENT,LED，LBlock，SIMON和SPECK等。
　　由于輕量級分組密碼的設(shè)計(jì)目標(biāo)是力求尋找安全性與執(zhí)行性能的最佳折衷

3、，然而在受限環(huán)境下運(yùn)行的密碼算法受資源條件約束，算法的安全性必然會受到一定影響，因此對輕量級密碼算法的安全性評估顯得尤為重要。2005年，王小云教授提出了模差分比特分析方法和消息修改技術(shù)，破解了MD系列Hash函數(shù)，引起了Hash函數(shù)研究的新高潮。在分組密碼研究中，因?yàn)槊荑€是未知的，不能直接運(yùn)用消息修改技術(shù)。分組密碼中帶密鑰的比特條件方程如何求解？對于該困難問題，我們提出了動態(tài)密鑰猜測的技術(shù)，取得了兩項(xiàng)重要成果。第一，我們充分研究密碼算

4、法中非線性運(yùn)算的異或差分特性，提出基于比特的動態(tài)密鑰猜測技術(shù)，極大地降低了猜測密鑰的空間。第二，對4比特S盒的差分特性進(jìn)行了詳細(xì)的分析，提出基于半字節(jié)運(yùn)算的密鑰猜測技術(shù)求解條件方程，降低攻擊的復(fù)雜度。使用該方法對輕量級分組密碼算法SIMON和LBlock進(jìn)行安全性評估，主要研究成果簡要介紹如下:
　　SIMON族分組密碼算法的動態(tài)密鑰猜測差分分析
　　SIMON算法是美國國家安全局(NSA)于2013年提出的一族分組密碼算法

5、，其設(shè)計(jì)思路是使之在硬件上有較高的性能。SIMON算法采用的是Feistel結(jié)構(gòu)，根據(jù)不同的分組長度和密鑰長度共分為10個(gè)版本。自從SIMON族算法發(fā)布以來，引起了很多密碼分析者的關(guān)注，許多分析方法被用于對SIMON算法的安全性分析，包括差分分析，線性分析，不可能差分分析，線性殼分析，零相關(guān)線性殼分析，動態(tài)立方分析等。
　　2013年，Alkhzaimi和Lauridsen等人提出了對SIMON算法的第一個(gè)安全性分析，給出了差分分

6、析結(jié)果和不可能差分分析結(jié)果。同年Alizadeh等人給出了線性分析結(jié)果和不可能差分分析結(jié)果。2014年，Abed等人用線性、差分、不可能差分等分析了SIMON算法。在FSE2014上，Biryukov和Velichkov等人搜索到該算法新的差分特征，并使用差分分析攻擊了19輪的SIMON32/64，20輪的SIMON48和26輪的SIMON64。Wang等人在INDOCRYPT2014上提出了對SIMON的積分攻擊、線性攻擊和不可能差分

7、攻擊。孫思維等人在ASIACRYPT2014上針對比特型的分組密碼，提出了一種新的自動搜索差分特征的工具，并獲得了SIMON算法新的差分特征。K(o)lbl在CRYPTO2015上推導(dǎo)出SIMON算法輪函數(shù)的平方相關(guān)的顯示公式，并利用SAT/SMT求解器獲得了部分版本的最優(yōu)線性路線。
　　我們的工作是在模差分比特分析方法和消息修改技術(shù)思想的基礎(chǔ)上，通過深入分析算法中非線性運(yùn)算的異或差分特性，將模差分比特分析方法用于分組密碼分析，于

8、2014年提出了動態(tài)密鑰猜測技術(shù)。基于已有的差分路線，利用輪函數(shù)非線性部件的差分特性，建立一系列使得擴(kuò)展輪差分路線成立的充分的比特條件方程。這些比特條件可以分成兩類，一類條件只依賴于明文和密文，我們將這一類條件用于選擇明文構(gòu)造數(shù)據(jù)結(jié)構(gòu)，降低明文收集的復(fù)雜度，并提前過濾掉無效的明密文對，降低計(jì)算候選密鑰過程的復(fù)雜度。第二類條件是與密鑰相關(guān)的，用于猜測密鑰。因?yàn)?，在第二類條件方程中存在一些冗余信息，在攻擊過程中，通過不同的選擇明密文對及它們

9、所對應(yīng)的不同的比特方程，盡量避免猜測包含在這些條件中冗余的子密鑰或等價(jià)密鑰比特。采用提出的動態(tài)密鑰猜測思想，在使用相同的差分路線的情況下，通過選擇明文并動態(tài)地求解相應(yīng)的比特方程，可以極大地降低猜測密鑰的空間，該方法可以提高經(jīng)典的差分、不可能差分及線性分析中密鑰恢復(fù)階段的密鑰猜測效率。
　　應(yīng)用該技術(shù)，針對SIMON32，SIMON48，SIMON64，SIMON96和SIMON128版本算法，我們的攻擊結(jié)果比以往不使用動態(tài)密鑰猜測

10、技術(shù)的經(jīng)典差分分析提高了2-4輪。特別地，對SIMON64/96，SIMON64/128，SIMON96/96，SIMON128/128和SIMON128/192這5個(gè)版本的攻擊是目前在單密鑰模式下攻擊輪數(shù)最長的結(jié)果。而且我們提出的技術(shù)已經(jīng)被用于對其它基于比特級運(yùn)算的分組密碼算法的各類分析工作中，相對于經(jīng)典的攻擊均獲得了明顯的提高。例如，陳懷鳳等在FSE2016上使用動態(tài)密鑰猜測技術(shù)給出了SIMON算法的線性殼分析。
　　LBLO

11、CK分組密碼算法的不可能差分分析
　　LBlock是我國學(xué)者吳文玲和張蕾在ACNS2011上提出的32輪Feistel結(jié)構(gòu)的輕量級分組密碼，其密鑰和分組長度分別為80和64比特。自該分組密碼提出以來，很多密碼分析學(xué)家都對它的安全性進(jìn)行了分析，包括差分分析、線性分析、不可能差分分析、零相關(guān)線性分析及積分攻擊等。對于該算法，在考慮攻擊的輪數(shù)上，不可能差分攻擊是一個(gè)相對有效的方法。Boura等人在ASIACRYPT2014上提出了對LB

12、lock算法23輪的不可能差分分析結(jié)果，其使用的時(shí)間復(fù)雜度為27536，數(shù)據(jù)復(fù)雜度為259。同時(shí)，作者給出了一個(gè)不可能差分分析的通用計(jì)算公式，簡化了不可能差分攻擊的數(shù)據(jù)、時(shí)間、存儲復(fù)雜度計(jì)算。
　　將14輪不可能差分路線擴(kuò)展到24輪后，需要88個(gè)使得擴(kuò)展路線成立的充分的比特條件。如果使用以往文獻(xiàn)中給出的公式計(jì)算，所需要的最小數(shù)據(jù)量為288，已經(jīng)超出了窮盡密鑰的復(fù)雜度，這對于攻擊24輪似乎是不可能的。本文對算法中使用的4比特S盒的差

13、分特性進(jìn)行了詳細(xì)的分析，類似于SIMON算法分析中提出的比特級的動態(tài)密鑰猜測技術(shù)，利用S盒的詳細(xì)的差分特性，提出了基于4比特半字節(jié)運(yùn)算的密鑰猜測技術(shù)。首先，建立一系列使得擴(kuò)展輪差分路線成立的充分的差分條件方程，分析了條件等式之間的關(guān)系，建立各條件之間的聯(lián)系。然后利用只與明密文相關(guān)的條件建立預(yù)計(jì)算表，用于更有效地收集有用的明密文對，并提前過濾掉無用的明密文對，降低選擇明文的數(shù)據(jù)復(fù)雜度和明密文收集過程的時(shí)間復(fù)雜度。利用與密鑰相關(guān)的條件建立預(yù)

14、計(jì)算表，用于更有效地計(jì)算密鑰，降低過濾錯(cuò)誤密鑰過程的時(shí)間復(fù)雜度。同時(shí)，深入地分析了密鑰恢復(fù)過程中所涉及的子密鑰之間的關(guān)系，設(shè)計(jì)最優(yōu)的密鑰猜測的順序。
　　我們采用提出的技術(shù)，結(jié)合預(yù)計(jì)算表和優(yōu)化的密鑰猜測順序，極大地降低了不可能差分攻擊的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度。給出了LBlock算法的24輪不可能差分攻擊結(jié)果，需要的時(shí)間復(fù)雜度為277.50次加密運(yùn)算，數(shù)據(jù)復(fù)雜度為259個(gè)選擇明文。對LBlock的攻擊結(jié)果比以往最好的不可能差分攻擊結(jié)