Keccak的安全性能分析與研究

周戰(zhàn)軍?程璐

摘 要：Hash函數(shù)，又稱哈希函數(shù)、散列函數(shù)或雜湊函數(shù)，是密碼體制中常用的一類公開函數(shù)。Hash函數(shù)主要用于消息完整性檢測和消息認(rèn)證等。由于MD-5、SHA-1等標(biāo)準(zhǔn)算法的安全性受到了嚴(yán)重的威脅，2012年10月，美國國家標(biāo)準(zhǔn)與技術(shù)研究所推選出Keccak為新的雜湊函數(shù)標(biāo)準(zhǔn)SHA-3的算法。本文主要對Keccak的競選、實(shí)現(xiàn)過程、安全性以及攻擊現(xiàn)狀進(jìn)行分析和研究。

關(guān)鍵詞：Hash函數(shù)；Keccak；SHA-3

1 背景介紹

1.1 散列函數(shù)的安全威脅

隨著對雜湊函數(shù)安全性分析不斷深入，傳統(tǒng)雜湊函數(shù)（MD4、 MD5、SHA-1、SHA-2等）安全性受到重大威脅。山東大學(xué)的王小云教授在美洲密碼年會（Crypot2004）上做了攻擊MD5、MD4、HAVAL-128和RIPEMD算法的報(bào)告，公布了MD系列算法的破解結(jié)果。對于MD5的攻擊，報(bào)告中給出了一個(gè)具體的碰撞例子。MD5的安全性受到了嚴(yán)重的威脅。在安全強(qiáng)度要求較高的系統(tǒng)中，應(yīng)避免MD5的使用。2005年2月，王小云教授等專家學(xué)者再次發(fā)表論文，證明SHA-1在理論上是可以破解的。雖然到目前為止，沒有找到可攻破SHA-1算法的碰撞實(shí)例。但是，SHA-1算法甚至SHA-2算法的安全性都己經(jīng)受到嚴(yán)重的威脅。

1.2 SHA-3計(jì)劃與Keccak

NIST于2007年12月仿照AES的征集過程公開征集新的雜湊函數(shù)標(biāo)準(zhǔn)算法SHA-3。NIST提出的對候選算法的主要要求包括：（1）算法應(yīng)該能夠廣泛地應(yīng)用在常用的軟件和硬件平臺上安全高效地實(shí)現(xiàn)；（2）算法提供的消息摘要長度為：224比特、256比特、384比特和512比特，能夠壓縮的最大消息長度應(yīng)至少為-1比特；（3）算法必須有效抵抗碰撞攻擊、原象攻擊及第二原象攻擊、長度擴(kuò)展攻擊等常見的攻擊方法，對于n比特長度的摘要，其碰撞攻擊的復(fù)雜度應(yīng)該至少為原象攻擊至少為，對長度小于的消息其第二原象攻擊復(fù)雜度應(yīng)至少為；（4）算法要能支持PRF、 HMAC和隨機(jī)化； （5）算法在保持SHA-2的一些性能參數(shù)等性質(zhì)外，要能夠確保替換SHA-2參與具體應(yīng)用；（6）算法的設(shè)計(jì)要簡單靈活，能夠通過并行實(shí)現(xiàn)獲得較高的效率和更好的性能；（7）算法有安全的可調(diào)節(jié)的參數(shù)，可以調(diào)和運(yùn)行性能及安全強(qiáng)度和；（8）算法可以使用新的迭代結(jié)構(gòu)，盡量避免老式結(jié)構(gòu)（如MD結(jié)構(gòu)）的通用攻擊。

2007年，NIST在全球范圍內(nèi)公開征集SHA-3算法標(biāo)準(zhǔn)。2008年10月提交結(jié)束，共收到64個(gè)算法，其中有51個(gè)算法通過審查作為第一輪的候選算法。2009年7月，在第一輪的51個(gè)算法中有14個(gè)算法通過篩選進(jìn)入了第二輪。2010年12月，NIST宣布通過最后一輪的5個(gè)算法，分別是Keccak、JH、Skein、Grstl和BLAKE。2012年10月2日，NIST公布了SHA-3標(biāo)準(zhǔn)算法。經(jīng)過三輪的篩選，最終選定Keccak成為SHA-3的標(biāo)準(zhǔn)算法。NIST的安全專家說，Keccak的優(yōu)勢在于它與SHA-2設(shè)計(jì)上存在極大差異，使用于SHA-2的攻擊方法將對無效。

2 Keccak算法介紹

2.1 Sponge結(jié)構(gòu)簡介

Keccak在迭代結(jié)構(gòu)上采用的是Sponge結(jié)構(gòu)。Sponge結(jié)構(gòu)與傳統(tǒng)的MD迭代結(jié)構(gòu)很不同，依賴一個(gè)固定長度的大置換。這就為算法提供了良好的實(shí)用性和可證明安全性，理論上可以證明在理想模型下該結(jié)構(gòu)與隨機(jī)預(yù)言是不可區(qū)分的。Sponge結(jié)構(gòu)是針對一個(gè)固定置換f的迭代過程。置換輸入/輸出的二進(jìn)制串稱為狀態(tài)，其長度b=r+c，其中r稱比特率，與輸入消息塊長度相同，該部分比特稱為外部狀態(tài)；c稱容量，該部分比特稱為內(nèi)部狀態(tài)。算法的初始時(shí)狀態(tài)為全零。

Keccak算法的Sponge結(jié)構(gòu)

如圖所示，Sponge結(jié)構(gòu)分成吸收（abstracting）和擠壓（squeezing）兩個(gè)階段。在吸收階段，輸入消息經(jīng)過填充，分為長度為r的各塊p0，…，pi，…，pm，每塊分別與各次置換的輸入狀態(tài)的r長外部狀態(tài)異或，而c長內(nèi)部狀態(tài)保持不變，形成作為本次置換f的輸入。在擠壓階段，根據(jù)所需的輸出長度，從各次置換的輸出中分別提取z0，…，zi各子串，連接后形成算法之輸出。Sponge結(jié)構(gòu)可以產(chǎn)生任意長度輸出。

2.2 Keccak算法分析

按照NIST的要求，算法的輸出長度分為224bit、256bit、384bit和512bit 。由于Sponge結(jié)構(gòu)是可以產(chǎn)生任意長度輸出的，所以Keccak算法的消息塊長度r是根據(jù)輸出長度而變化的： 輸出512bit時(shí)消息塊長度r為576bit；輸出384bit時(shí)r為832bit；輸出256bit時(shí)r為1088bit；輸出22bit4時(shí)r為1152bit。Keccak規(guī)定b=25 *，l= 0， 1， 2，…，6，因此b有{25，50，100，200，400，800，1600}共7種模型，在提交SHA-3的Keccak算法中b=1600bit。

Keccak的填充方式為：首先添加一個(gè)1，之后添加最少個(gè)數(shù)的0，最后添加一個(gè)1，即：10…01，其中0的個(gè)數(shù)應(yīng)使擴(kuò)展后的消息串S是消息分組長度r的整數(shù)倍。消息串S通過運(yùn)算：S[ （5y + x） +z]= a[x][y][z]進(jìn)入三維矩陣中進(jìn)行變換（x和y的坐標(biāo)都是模5之后的結(jié)果，z是模）。Keccak算法中置換f的輸入表示為5*5*的三維比特?cái)?shù)組a[x][y][z]，稱為狀態(tài)數(shù)組。當(dāng)b=1600時(shí)，數(shù)組大小為5*5*64（l=6時(shí)）。算法將該數(shù)組分為六種單元：slice（各5*5*1 bit）、plane（各5*1*bit）、sheet（各1* 5* bit）、lane（各1* 1* bit）、row（各5* 1* lbit）和column（各1* 5* lbit）。而置換就是分別對這些單元的各比特進(jìn)行12+2l輪迭代運(yùn)算。

置換f，每一輪迭代的輪函數(shù)為5個(gè)變換的復(fù)合：R=ι?χ?π?ρ?θ，它們分別對三維數(shù)組的不同方向進(jìn)行變換，以達(dá)到充分混淆和擴(kuò)散的目的。5個(gè)變換分別為：

θ：a[x][y][z]←a[x][y][z]+ +。該變換是將每比特附近的兩列（column）比特之和迭加到該比特上；

ρ： a[x][y][z]←a[x][y][其中0 ≤t<24，滿足以 （） = （）矩陣元素為GF （5 ）中元素，且x=y=0時(shí)t=-1。該變換是針對每個(gè)z方向的lane的比特循環(huán)移位；

π： a[x][y][z]←a[x][y]，（），其中矩陣元素為 GF（5）中元素。該變換是針對每個(gè)x-y平面的slice的比特移位；

χ： a[x]←a[x] + （a[x+1]+1）a[x+2]，這是針對每個(gè)x方向的row的非線性運(yùn)算，其作用等效為5*5的S盒；

ι：a←a+RC[]，該變換是加輪常數(shù)RC，逐比特進(jìn)行，且每輪的輪常數(shù)不同。

3 Keccak的安全性能

3.1 迭代結(jié)構(gòu)

Keccak采用的Sponge結(jié)構(gòu)具有良好的適應(yīng)性和可證明安全性。與多數(shù)具有明顯壓縮函數(shù)結(jié)構(gòu)的算法不同，Sponge結(jié)構(gòu)采用大狀態(tài)的固定置換。在假設(shè)置換為理想狀態(tài)的情況下，可證明該結(jié)構(gòu)與隨機(jī)預(yù)言是不可區(qū)分的，區(qū)分復(fù)雜度的下界為（c即容量，亦即安全參數(shù)）。由此保證了算法具有抵抗一般性攻擊的能力，一般性攻擊也就是結(jié)構(gòu)上的攻擊。這種可證明性與第三輪其他幾種候選算法是相似的，都是將算法的安全性歸結(jié)于置換或壓縮函數(shù)的安全性之上。與此同時(shí)Sponge結(jié)構(gòu)還可以輸出任意長度，有較強(qiáng)的適用能力。

3.2 置換

Keccak的置換操作是基于比特級的，實(shí)現(xiàn)簡單，其軟件實(shí)現(xiàn)性能與SHA-2類似，而硬件實(shí)現(xiàn)性能則比SHA-2更加優(yōu)異。整個(gè)算法不僅有較大的安全余量，而且還有良好的適應(yīng)性。Sponge結(jié)構(gòu)可以容易地調(diào)整使安全強(qiáng)度和處理速度之間處于平衡，能很方便地根據(jù)需要產(chǎn)生較大和較小的輸出值，并且可定義修改的鏈接模式來提供認(rèn)證加密等其它功能。

Keccak的置換中比特級的運(yùn)算即邏輯運(yùn)算可達(dá)到不易發(fā)生截?cái)嗖罘止?、積分攻擊等攻擊的目的，并且硬件實(shí)現(xiàn)簡便。除了加常數(shù)運(yùn)算以外，其他運(yùn)算都具有平移不變性（對稱性），這使算法具有實(shí)現(xiàn)性能和良好的適用性。在安全性分析上，χ是唯一的非線性部件，相當(dāng)于一個(gè)可逆的S盒，而代數(shù)次數(shù)只是2，這將便于分析差分特性和線性特性，并且方便加入防護(hù)措施用以防止差分能量攻擊。θ很好地實(shí)現(xiàn)了slice間的擴(kuò)散性；π是為打亂水平和垂直方向的規(guī)律性；加常數(shù)ι打破了整個(gè)置換的對稱性，保證各輪的變換不相同進(jìn)而防止不動點(diǎn)的存在。

3.3 整體安全性能

Keccak具有較大的安全余量。碰撞和近似碰撞的結(jié)果最能反映雜湊算法的安全性，Keccak的24輪之中僅發(fā)現(xiàn)5輪的近似碰撞。區(qū)分攻擊能夠反映算法的隨機(jī)性，在評選時(shí)僅發(fā)現(xiàn)了Keccak的12輪區(qū)分器。而針對Keccak的原象攻擊只有很少輪數(shù)并且復(fù)雜性較高的結(jié)果。Keccak用同一個(gè)置換產(chǎn)生所有輸出長度的摘要，這樣的好處是易于實(shí)現(xiàn)簡便變型算法，但是為了保證其安全性，消息分塊要隨輸出長度而變化，而且摘要越長，執(zhí)行速度就越慢。進(jìn)入第二輪后，Keccak進(jìn)行了一些修改：輪數(shù)由12+l增至12+2l；224bit輸出所對應(yīng)的消息塊長度從1024bit增加到1152bit ；256bit輸出對應(yīng)的消息塊長度從1024 bit增到1088 bit，來保證原象安全。進(jìn)入第三輪后Keccak填充方式進(jìn)行了簡化。

4 Keccak的攻擊現(xiàn)狀分析

Keccak作為SHA-3的獲勝者，己經(jīng)引起了人們更廣泛的關(guān)注，對它的分析也日益增多。目前關(guān)于Keccak的攻擊方式主要有：利用差分技術(shù)的碰撞攻擊和部分碰撞攻擊；利用Biclique等技術(shù)的原象或第二原象攻擊；零和區(qū)分攻擊和旋轉(zhuǎn)區(qū)分攻擊等。

4.1 碰撞和近似碰撞攻擊

I. Dinur等從己有的2輪低重量的狀態(tài)差分開始，反向擴(kuò)展1輪產(chǎn)生目標(biāo)狀態(tài)差分，再由目標(biāo)差分算法從初始值開始進(jìn)行1輪正向擴(kuò)展，產(chǎn)生4輪Keccak-224的實(shí)際碰撞在PC機(jī)上僅用時(shí)2-3分鐘；產(chǎn)生4輪的Kecca-256實(shí)際碰撞用時(shí)為15-30分鐘；產(chǎn)生5輪的近似碰撞（只差5 bit、10 bit）耗時(shí)為幾天時(shí)間。2013年，I.Dinur等又采用目標(biāo)內(nèi)部差分算法提高了上述結(jié)果，對5輪的Keccak-256產(chǎn)生了碰撞攻擊，其復(fù)雜度為。并結(jié)合Squeeze攻擊產(chǎn)生了3輪的Keccak-512的實(shí)際性攻擊，產(chǎn)生了4輪Keccak-384的碰撞，其復(fù)雜度為。

J.Daemen等提出了有效產(chǎn)生給定重量的Keccak-f[1600]的所有差分路徑的方法。利用計(jì)算機(jī)程序搜索得到了重量為36時(shí)3輪的所有差分軌跡，并確認(rèn)了A.Duc等找到的重量為32的3輪軌跡是最輕的，指出6輪的軌跡中重量沒有比74小的。

4.2 原象攻擊

Naya-Plasencia等采用中間相遇攻擊方法，提出了2輪Keccak-224和Keccak-256的原象和第二原象攻擊，其時(shí)間復(fù)雜度為，存儲復(fù)雜度為。這種攻擊是一可以實(shí)際實(shí)現(xiàn)的攻擊。

4.3 區(qū)分攻擊（隨機(jī)性攻擊）

C.Boura等采用零和子集劃分的方式對Keccak進(jìn)行了區(qū)分攻擊。零和攻擊可以看作是積分攻擊的推廣，即是利用輸入和輸出的和為零的子集進(jìn)行區(qū)分攻擊。他們針對Keccak的17輪、19輪和20輪置換產(chǎn)生了零和劃分，其復(fù)雜度分別為、和。在“Higher-order differential properties of Keccak and Luffa”中又提出了針對全輪Keccak置換的零和劃分，其復(fù)雜度為?？梢钥吹竭@種攻擊是復(fù)雜性很大的攻擊。

A.Duc等找到了Keccak目前最好的（即重量最輕的）5輪差分路徑，針對θ變換的零和特性，利用unalignedrebound技術(shù)，構(gòu)造了8輪區(qū)分器，其復(fù)雜度為。這比零和區(qū)分器的復(fù)雜度要小的多。這里所謂的“unaligned”是指：Keccak不像存在截?cái)嗖罘值腁ES那樣可以很容易地處理rebound過程，因?yàn)槠?個(gè)活躍行經(jīng)過1輪后會影響多個(gè)slice。

P.Morawiecki等采用旋轉(zhuǎn)攻擊方法，提出了5輪Keccak的區(qū)分攻擊，并且復(fù)雜度僅為但是對于更多輪數(shù)則有較大困難。另外，這一攻擊方式與其他區(qū)分攻擊的不同之處在于：可以產(chǎn)生4輪原象攻擊，復(fù)雜度為理論值減少倍。

5 結(jié)束語

Keccak作為SHA - 3的獲勝者，己經(jīng)引起人們更廣泛的關(guān)注，對它的分析日益增多。Keccak不僅具有良好的安全性能，更重要的是其設(shè)計(jì)結(jié)構(gòu)新穎，并且有優(yōu)秀的整體實(shí)現(xiàn)性能和良好的適應(yīng)能力。對于Kecca的分析與研究將有力促進(jìn)了整個(gè)領(lǐng)域的設(shè)計(jì)和分析水平。