Keccak的安全性能分析與研究

周戰軍?程璐

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

關鍵詞：Hash函數；Keccak；SHA-3

1 背景介紹

1.1 散列函數的安全威脅

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

1.2 SHA-3計劃與Keccak

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

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

2 Keccak算法介紹

2.1 Sponge結構簡介

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

Keccak算法的Sponge結構

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

2.2 Keccak算法分析

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

Keccak的填充方式為：首先添加一個1，之后添加最少個數的0，最后添加一個1，即：10…01，其中0的個數應使擴展后的消息串S是消息分組長度r的整數倍。消息串S通過運算：S[ （5y + x） +z]= a[x][y][z]進入三維矩陣中進行變換（x和y的坐標都是模5之后的結果，z是模）。Keccak算法中置換f的輸入表示為5*5*的三維比特數組a[x][y][z]，稱為狀態數組。當b=1600時，數組大小為5*5*64（l=6時）。算法將該數組分為六種單元：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）。而置換就是分別對這些單元的各比特進行12+2l輪迭代運算。

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

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

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

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

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

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

3 Keccak的安全性能

3.1 迭代結構

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

3.2 置換

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

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

3.3 整體安全性能

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

4 Keccak的攻擊現狀分析

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

4.1 碰撞和近似碰撞攻擊

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

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

4.2 原象攻擊

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

4.3 區分攻擊（隨機性攻擊）

C.Boura等采用零和子集劃分的方式對Keccak進行了區分攻擊。零和攻擊可以看作是積分攻擊的推廣，即是利用輸入和輸出的和為零的子集進行區分攻擊。他們針對Keccak的17輪、19輪和20輪置換產生了零和劃分，其復雜度分別為、和。在“Higher-order differential properties of Keccak and Luffa”中又提出了針對全輪Keccak置換的零和劃分，其復雜度為。可以看到這種攻擊是復雜性很大的攻擊。

A.Duc等找到了Keccak目前最好的（即重量最輕的）5輪差分路徑，針對θ變換的零和特性，利用unalignedrebound技術，構造了8輪區分器，其復雜度為。這比零和區分器的復雜度要小的多。這里所謂的“unaligned”是指：Keccak不像存在截斷差分的AES那樣可以很容易地處理rebound過程，因為其1個活躍行經過1輪后會影響多個slice。

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

5 結束語

Keccak作為SHA - 3的獲勝者，己經引起人們更廣泛的關注，對它的分析日益增多。Keccak不僅具有良好的安全性能，更重要的是其設計結構新穎，并且有優秀的整體實現性能和良好的適應能力。對于Kecca的分析與研究將有力促進了整個領域的設計和分析水平。