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

幾個(gè)輕量級(jí)分組密碼算法的安全性分析隨著信息技術(shù)的飛速發(fā)展,密碼學(xué)作為保障信息安全的核心技術(shù),在現(xiàn)代信息安全領(lǐng)域中發(fā)揮著越來越重要的作用。分組密碼作為現(xiàn)代密碼學(xué)的一個(gè)重要分支,其研究?jī)?nèi)容主要包括分組密碼設(shè)計(jì)和分析兩個(gè)方面。一方面,密碼設(shè)計(jì)人員的目標(biāo)是設(shè)計(jì)出能夠抵抗所有已知攻擊的安全強(qiáng)度高的密碼算法,而另一方面,密碼分析者是在努力尋找密碼算法的安全性漏洞和破譯密碼算法的攻擊方法。這兩方面的研究相互促進(jìn),共同推動(dòng)了分組密碼理論的發(fā)展。隨著物聯(lián)網(wǎng)的發(fā)展,RFID芯片和無線傳感網(wǎng)絡(luò)等微型計(jì)算設(shè)備的應(yīng)用越來越廣泛,在給人們的生活帶來了極大便利的同時(shí),如何確保了這類資源受限設(shè)備上信息的安全性,越來越引起密碼學(xué)家的重視。為了適應(yīng)物聯(lián)網(wǎng)上所使用的微型計(jì)算設(shè)備資源受限的特點(diǎn),設(shè)計(jì)既具有低功耗和低資源占用又滿足所需要的安全性要求的輕量級(jí)分組密碼算法應(yīng)運(yùn)而生。例如TWINE,PRESENT,LED,LBlock,SIMON和SPECK等。由于輕量級(jí)分組密碼的設(shè)計(jì)目標(biāo)是力求尋找安全性與執(zhí)行性能的最佳折衷,然而在受限環(huán)境下運(yùn)行的密碼算法受資源條件約束,算法的安全性必然會(huì)受到一定影響,因此對(duì)輕量級(jí)密碼算法的安全性評(píng)估顯得尤為重要。2005年,王小云教授提出了模差分比特分析方法和消息修改技術(shù),破解了MD系列Hash函數(shù),引起了Hash函數(shù)研究的新高潮。在分組密碼研究中,因?yàn)槊荑€是未知的,不能直接運(yùn)用消息修改技術(shù)。分組密碼中帶密鑰的比特條件方程如何求解?對(duì)于該困難問題,我們提出了動(dòng)態(tài)密鑰猜測(cè)的技術(shù),取得了兩項(xiàng)重要成果。第一,我們充分研究密碼算法中非線性運(yùn)算的異或差分特性,提出基于比特的動(dòng)態(tài)密鑰猜測(cè)技術(shù),極大地降低了猜測(cè)密鑰的空間。第二,對(duì)4比特S盒的差分特性進(jìn)行了詳細(xì)的分析,提出基于半字節(jié)運(yùn)算的密鑰猜測(cè)技術(shù)求解條件方程,降低攻擊的復(fù)雜度。使用該方法對(duì)輕量級(jí)分組密碼算法SIMON和LBlock進(jìn)行安全性評(píng)估,主要研究成果簡(jiǎn)要介紹如下:·SIMON族分組密碼算法的動(dòng)態(tài)密鑰猜測(cè)差分分析SIMON算法是美國國家安全局(NSA)于2013年提出的一族分組密碼算法,其設(shè)計(jì)思路是使之在硬件上有較高的性能。SIMON算法采用的是Feistel結(jié)構(gòu),根據(jù)不同的分組長(zhǎng)度和密鑰長(zhǎng)度共分為10個(gè)版本。自從SIMON族算法發(fā)布以來,引起了很多密碼分析者的關(guān)注,許多分析方法被用于對(duì)SIMON算法的安全性分析,包括差分分析,線性分析,不可能差分分析,線性殼分析,零相關(guān)線性殼分析,動(dòng)態(tài)立方分析等。2013年,Alkhzaimi和Lauridsen等人提出了對(duì)SIMON算法的第一個(gè)安全性分析,給出了差分分析結(jié)果和不可能差分分析結(jié)果。同年Alizadeh等人給出了線性分析結(jié)果和不可能差分分析結(jié)果。2014年,Abed等人用線性、差分、不可能差分等分析了SIMON算法。在FSE2014上,Biryukov和Velichkov等人搜索到該算法新的差分特征,并使用差分分析攻擊了19輪的SIMON32/64,20輪的SIMON48和26輪的SIMON64。Wang等人在INDOCRYPT2014上提出了對(duì)SIMON的積分攻擊、線性攻擊和不可能差分攻擊。孫思維等人在ASIACRYPT2014上針對(duì)比特型的分組密碼,提出了一種新的自動(dòng)搜索差分特征的工具,并獲得了SIMON算法新的差分特征。Kolbl在CRYPTO2015上推導(dǎo)出SIMON算法輪函數(shù)的平方相關(guān)的顯示公式,并利用SAT/SMT求解器獲得了部分版本的最優(yōu)線性路線。我們的工作是在模差分比特分析方法和消息修改技術(shù)思想的基礎(chǔ)上,通過深入分析算法中非線性運(yùn)算的異或差分特性,將模差分比特分析方法用于分組密碼分析,于2014年提出了動(dòng)態(tài)密鑰猜測(cè)技術(shù)?；谝延械牟罘致肪€,利用輪函數(shù)非線性部件的差分特性,建立一系列使得擴(kuò)展輪差分路線成立的充分的比特條件方程。這些比特條件可以分成兩類,一類條件只依賴于明文和密文,我們將這一類條件用于選擇明文構(gòu)造數(shù)據(jù)結(jié)構(gòu),降低明文收集的復(fù)雜度,并提前過濾掉無效的明密文對(duì),降低計(jì)算候選密鑰過程的復(fù)雜度。第二類條件是與密鑰相關(guān)的,用于猜測(cè)密鑰。因?yàn)?在第二類條件方程中存在一些冗余信息,在攻擊過程中,通過不同的選擇明密文對(duì)及它們所對(duì)應(yīng)的不同的比特方程,盡量避免猜測(cè)包含在這些條件中冗余的子密鑰或等價(jià)密鑰比特。采用提出的動(dòng)態(tài)密鑰猜測(cè)思想,在使用相同的差分路線的情況下,通過選擇明文并動(dòng)態(tài)地求解相應(yīng)的比特方程,可以極大地降低猜測(cè)密鑰的空間,該方法可以提高經(jīng)典的差分、不可能差分及線性分析中密鑰恢復(fù)階段的密鑰猜測(cè)效率。應(yīng)用該技術(shù),針對(duì)SIMON32,SIMON48,SIMON64,SIMON96和SI-MON128版本算法,我們的攻擊結(jié)果比以往不使用動(dòng)態(tài)密鑰猜測(cè)技術(shù)的經(jīng)典差分分析提高了2-4輪。特別地,對(duì)SIMON64/96,SIMON64/128,SIMON96/96,SIMON128/128和SIMON128/192這5個(gè)版本的攻擊是目前在單密鑰模式下攻擊輪數(shù)最長(zhǎng)的結(jié)果。而且我們提出的技術(shù)已經(jīng)被用于對(duì)其它基于比特級(jí)運(yùn)算的分組密碼算法的各類分析工作中,相對(duì)于經(jīng)典的攻擊均獲得了明顯的提高。例如,陳懷鳳等在FSE2016上使用動(dòng)態(tài)密鑰猜測(cè)技術(shù)給出了SIMON算法的線性殼分析。·LBLOCK分組密碼算法的不可能差分分析LBlock是我國學(xué)者吳文玲和張蕾在ACNS2011上提出的32輪Feistel結(jié)構(gòu)的輕量級(jí)分組密碼,其密鑰和分組長(zhǎng)度分別為80和64比特。自該分組密碼提出以來,很多密碼分析學(xué)家都對(duì)它的安全性進(jìn)行了分析,包括差分分析、線性分析、不可能差分分析、零相關(guān)線性分析及積分攻擊等。對(duì)于該算法,在考慮攻擊的輪數(shù)上,不可能差分攻擊是一個(gè)相對(duì)有效的方法。Boura等人在ASIACRYPT2014上提出了對(duì)LBlock算法23輪的不可能差分分析結(jié)果,其使用的時(shí)間復(fù)雜度為275.36,數(shù)據(jù)復(fù)雜度為259。同時(shí),作者給出了一個(gè)不可能差分分析的通用計(jì)算公式,簡(jiǎn)化了不可能差分攻擊的數(shù)據(jù)、時(shí)間、存儲(chǔ)復(fù)雜度計(jì)算。將14輪不可能差分路線擴(kuò)展到24輪后,需要88個(gè)使得擴(kuò)展路線成立的充分的比特條件。如果使用以往文獻(xiàn)中給出的公式計(jì)算,所需要的最小數(shù)據(jù)量為288,已經(jīng)超出了窮盡密鑰的復(fù)雜度,這對(duì)于攻擊24輪似乎是不可能的。本文對(duì)算法中使用的4比特S盒的差分特性進(jìn)行了詳細(xì)的分析,類似于SIMON算法分析中提出的比特級(jí)的動(dòng)態(tài)密鑰猜測(cè)技術(shù),利用S盒的詳細(xì)的差分特性,提出了基于4比特半字節(jié)運(yùn)算的密鑰猜測(cè)技術(shù)。首先,建立一系列使得擴(kuò)展輪差分路線成立的充分的差分條件方程,并分析了條件卷式之間的關(guān)系,建立各條件之間的聯(lián)系。然后利用只與明密文相關(guān)的條件建立預(yù)計(jì)算表,用于更有效地收集有用的明密文對(duì),并提前過濾掉無用的明密文對(duì),降低選擇明文的數(shù)據(jù)復(fù)雜度和明密文收集過程的時(shí)間復(fù)雜度。利用與密鑰相關(guān)的條件建立預(yù)計(jì)算表,用于更有效地計(jì)算密鑰,降低過濾錯(cuò)誤密鑰過程的時(shí)間復(fù)雜度。同時(shí),深入地分析了密鑰恢復(fù)過程中所涉及的子密鑰之間的關(guān)系,設(shè)計(jì)最優(yōu)的密鑰猜測(cè)的順序。我們采用提出的技術(shù),結(jié)合預(yù)計(jì)算表和優(yōu)化的密鑰猜測(cè)順序,極大地