SHA－3輪函數(shù)中χ及θ變換的性質(zhì)研究＊

王 淦，張文英

（1.山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014；2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南250014）

1 引言

近年來，由于一系列Hash 函數(shù)如 MD4、MD5、SHA－1和HAVAL等受到王小云教授提出的模差分和消息修改方法的重創(chuàng)［2～4］，因此美國國家標(biāo)準(zhǔn)與技術(shù)研究院NIST（National Institute of Standards and Technology）發(fā)起 了征集新Hash函數(shù)標(biāo)準(zhǔn)SHA－3的計(jì)劃［5］。該計(jì)劃于2007年啟動，經(jīng)過長達(dá)五年共計(jì)三輪的競賽，NIST 于2012年10月2日宣布由Bertoni G、Daemen J、Peeters M 等人［6，7］設(shè)計(jì)的Keccak［5］為SHA－3標(biāo)準(zhǔn)。由于其不同于以往Hash函數(shù)的獨(dú)特設(shè)計(jì)理念，Keccak成為當(dāng)前Hash函數(shù)研究的熱點(diǎn)。

χ是Keccak輪函數(shù)中唯一的非線性變換，它保證了整個輪函數(shù)的非線性。差分分析方法由Biham E和Shamir A［8］于1990年首先提出，它是對Hash函數(shù)攻擊的有效方法，也是目前攻擊Keccak的主要方法。在對Keccak的攻擊中，構(gòu)造使輸入差分以高概率通過χ變換而不發(fā)生改變或使輸出差分為指定狀態(tài)的差分路徑是降低攻擊復(fù)雜度的重要手段之一。進(jìn)行差分分析時常把χ看作一個輸入輸出均為5比特的S盒，其輸入輸出以一定概率相對應(yīng)，構(gòu)成一個線性仿射簇［6］。

由于布爾函數(shù)表達(dá)式的形式有利于進(jìn)一步的差分?jǐn)U散性質(zhì)推導(dǎo)，因此本文將χ 變換表示為布爾函數(shù)數(shù)表達(dá)式，通過布爾函數(shù)表達(dá)式對輸入差分的擴(kuò)散性質(zhì)進(jìn)行了推導(dǎo)，得到了32種輸入輸出差分情況的分布表，并由此對χ 的差分分布規(guī)律進(jìn)行了分析。

θ是Keccak算法規(guī)定的必須作為第一個的變換，因?yàn)槠鋽U(kuò)散能力很強(qiáng)，1 比特差分經(jīng)過θ后可擴(kuò)散至10比特。如何使差分順利通過θ變換而不被擴(kuò)散是對Keccak進(jìn)行差分分析時要解決的首要問題。在眾多對Keccak的攻擊方法中，文獻(xiàn)［1］首先提出利用符合Double Kernel形式的差分來構(gòu)造差分路徑，以保證差分不被θ變換擴(kuò)散，并成功找到了Keccak－256的2輪完全碰撞和3輪近似碰撞。文獻(xiàn)［9］在文獻(xiàn)［1］的基礎(chǔ)上提出了目標(biāo)差分算法，并利用該算法得到了Keccak－256的4 輪完全碰撞和5 輪近似碰撞，這也是目前對Keccak－256攻擊的最好結(jié)果。由于文獻(xiàn)［1，9］的攻擊方法都是以滿足Double Kernel形式的差分為條件的，因此快速有效地搜索滿足Double Kernel形式的差分是對Keccak進(jìn)行差分攻擊的基礎(chǔ)。文獻(xiàn)［1］中提出了一種搜索算法，但此算法近似于窮盡搜索，復(fù)雜度比較高。

本文提出了一種新的Double Kernel形式差分的搜索算法，通過施加限制條件縮小了搜索的范圍，復(fù)雜度較之文獻(xiàn)［1］中的算法有明顯降低。實(shí)驗(yàn)表明，本算法能夠快速有效地搜索符合給定條件的Double Kernel形式的差分，在差分漢明重量為6的情況下，算法搜索次數(shù)由25 600 降低到15 625。將本算法用于搜索漢明重量為4 的Double Kernel形式的差分時，實(shí)驗(yàn)表明，漢明重量為4的Double Kernel形式的差分不存在。對于漢明重量為2的Double Kernel的情況，本文從理論推導(dǎo)的角度證明其不存在。

2 Keccak算法簡介

Keccak算法基于海綿結(jié)構(gòu)［10］，海綿結(jié)構(gòu)如圖1所示，其處理過程分為吸收和擠壓兩個階段。Keccak輪函數(shù)表示為Keccak－f［b］，b稱為輪函數(shù)的寬度，也稱為狀態(tài)的個數(shù)，b＝25×2l，l∈｛0，1，2，3，4，5，6｝。b可表示為b＝r＋c，其中r稱為外部部分，又稱為比特率，c稱為內(nèi)部部分，又稱為容量。消息經(jīng)過填充后分割為r比特的塊進(jìn)行處理，輸出長度為n的摘要，n∈｛224，256，384，512｝并滿足c＝2n。Keccak算法共有12＋2l輪，每輪包含五個變換，表示為R＝ι?χ?π?ρ?θ，其運(yùn)算均在GF（2）上進(jìn)行。SHA－3 使用的是Keccak－f［1600］，共24輪，其1 600比特狀態(tài)的每一比特可看作三維數(shù)組a［x］［y］［z］中的一個元素，其中0≤x≤4，0≤y≤4，0≤z≤63。

Figure 1 Sponge construction of Keccak圖1 Keccak海綿結(jié)構(gòu)

Keccak輪函數(shù)的五個變換如下：

（2）ρ：a［x］［y］［z］←a［x］［y］［z－t（x，y）］，ρ使其沿z軸方向移動，移動的距離由t（x，y）指定。

（4）χ：a［x］［y］［z］←a［x］［y］［z］＋（﹁a［x＋1］［y］［z］∧a［x＋2］［y］［z］），χ對沿x軸方向一行中的比特進(jìn)行非線性運(yùn)算。

（5）ι：a［0］［0］［z］←a［0］［0］［z］＋RC［i］，ι添加一個每輪均不相同的64比特的常量。

有關(guān)Keccak算法的詳細(xì)描述可參考文獻(xiàn)［6］。

3 χ的差分分布

3.1 χ的布爾函數(shù)表達(dá)

我們可以將χ的布爾函數(shù)表達(dá)式寫為：xi＝xi＋（xi＋1＋1）xi＋2＝xi＋xi＋1xi＋2＋xi＋2，1≤i≤5。χ可看作對某一行的5個比特同時進(jìn)行運(yùn)算，因此通常將χ作為一個輸入輸出均為5 比特的S盒。令X＝（x1，x2，x3，x4，x5）表示一行，則χ變換可表示為（x1，x2，x3，x4，x5）→χ（f（x1），f（x2），f（x3），f（x4），f（x5））。

3.2 χ的差分分布推導(dǎo)

分別考察當(dāng)χ的輸入差分的漢明重量為0、1、2、3、4、5 時的差分?jǐn)U散情況。給定輸入差分Δin，根據(jù)Δout＝χ（X）＋χ（X＋Δin）計(jì)算輸出差分Δout。這里只給出輸入差分漢明重量分別為1和3兩種情況的詳細(xì)推導(dǎo)。

輸入差分漢明重量為1，令Δin＝（1，0，0，0，0），則：

x1＝［x1＋（x2＋1）x3］＋［x1＋1＋（x2＋1）x3］＝1

x2＝［x2＋（x3＋1）x4］＋［x2＋（x3＋1）x4］＝0

x3＝［x3＋（x4＋1）x5］＋［x3＋（x4＋1）x5］＝0

x4＝［x4＋（x5＋1）x1］＋［x4＋（x5＋1）（x1＋1）］＝1＋x5

x5＝［x5＋（x1＋1）x2］＋［x5＋（x1＋1＋1）x2］＝x2

可將Δin和Δout的對應(yīng)關(guān)系表示為（1，0，0，0，0）→（1，0，0，1＋x5，x2）。

輸入差分漢明重量為1的其它情況可直接移位得到。例如，只需將（1，0，0，0，0）→（1，0，0，1＋x5，x2）所有元素右移一位并同時增大其下標(biāo)，即可得到（0，1，0，0，0）→（x3，1，0，0，1＋x1）。同理：

（0，0，1，0，0）→（1＋x2，x4，1，0，0）

（0，0，0，1，0）→（0，1＋x3，x5，1，0）

（0，0，0，0，1）→（0，0，1＋x4，x1，1）

輸入差分漢明重量為3時有兩種不同的情況，首先令Δin＝（1，1，1，0，0），則：

x1＝［x1＋（x2＋1）x3］＋［x1＋1＋（x2＋1＋1）（x3＋1）］＝1＋x2＋x3

x2＝［x2＋（x3＋1）x4］＋［x2＋1＋（x3＋1＋1）x4］＝1＋x4

x3＝［x3＋（x4＋1）x5］＋［（x3＋1）＋（x4＋1）x5］＝1

x4＝［x4＋（x5＋1）x1］＋［x4＋（x5＋1）（x1＋1）］＝1＋x5

x5＝［x5＋（x1＋1）x2］＋［x5＋（x1＋1＋1）（x2＋1）］＝x1＋x2

即（1，1，1，0，0）→（1＋x2＋x3，1＋x4，1，1＋x5，x1＋x2）。移位得：

（0，1，1，1，0）→（x2＋x3，1＋x3＋x4，1＋x5，1，1＋x1）

（0，0，1，1，1）→（1＋x2，x3＋x4，1＋x4＋x5，1＋x1，1）

（1，0，0，1，1）→（1，1＋x3，x4＋x5，1＋x5＋x1，1＋x2）

（1，1，0，0，1）→（1＋x3，1，1＋x4，x5＋x1，1＋x1＋x2）

輸入差分漢明重量為3的另一種情況，令Δin＝（1，1，0，1，0），則：

x1＝［x1＋（x2＋1）x3］＋［x1＋1＋（x2＋1＋1）x3］＝1＋x3

x2＝［x2＋（x3＋1）x4］＋［x2＋1＋（x3＋1）（x4＋1）］＝x3

x3＝［x3＋（x4＋1）x5］＋［x3＋（x4＋1＋1）x5］＝x5

x4＝［x4＋（x5＋1）x1］＋［（x4＋1）＋（x5＋1）（x1＋1）］＝x5

x5＝［x5＋（x1＋1）x2］＋［x5＋（x1＋1＋1）（x2＋1）］＝x1＋x2

即（1，1，0，1，0）→（1＋x3，x3，x5，x5，x1＋x2）。移位得：

（0，1，1，0，1）→（x2＋x3，1＋x4，x4，x1，x1）

（1，0，1，1，0）→（x2，x3＋x4，1＋x5，x5，x2）

（0，1，0 ，1，1）→（x3，x3，x4＋x5，1＋x1，x1）

（1，0，1 ，0，1）→（x2，x4，x4，x5＋x1，1＋x2）

χ的輸入差分漢明重量為0、2、4、5的情況可通過類似推導(dǎo)得出。

3.3 χ的差分分布表

綜上推導(dǎo)，可將χ的輸入輸出差分分布的32種情況列表如表1所示（采用Big－Endian表示）。

3.4 χ的差分分布規(guī)律

由表1可以看出，χ的輸出差分分布是有規(guī)律的。定義Nχ為給定輸入差分時輸出差分的分布數(shù)，定義Mχ為任一輸出差分分布中的差分?jǐn)?shù)，則Nχ∈｛1，4，8，16｝，Mχ∈｛2，4，8，32｝，當(dāng)且僅當(dāng)差分為0時Nχ為1，當(dāng)且僅當(dāng)Nχ＝1時Mχ＝32，給定Nχ則Mχ唯一確定，當(dāng)輸入無差分時輸出也無差分，當(dāng)輸入有差分時輸出一定會有差分。

Table 1 Differential distribution table ofχ表1 χ的差分分布表

4 一種新的Double Kernel形式差分的搜索算法

4.1 Double Kernel的定義

若某列中差分的個數(shù)為偶數(shù)，則稱此列奇偶性為偶，若某狀態(tài)的所有列均為偶，則稱此狀態(tài)為Column Parity Kernel［6］或簡稱為Kernel。狀態(tài)為Kernel的差分經(jīng)過θ變換時差分不會擴(kuò)散，否則一列中的差分會擴(kuò)散至10比特。構(gòu)造差分路徑時，為了使Kernel狀態(tài)能夠維持盡可能多的輪數(shù)，不僅要求差分保持Kernel狀態(tài)而且要求差分兩兩位于同一行，稱為Double Kernel［1］，Double Kernel形式的差分為最優(yōu)的Kernel形式的差分。

4.2 新的Double Kernel形式差分搜索算法

文獻(xiàn)［1］中提出一種搜索符合條件的Double Kernel形式差分的算法，此算法近似于窮盡搜索，效率較低。其過程可簡述為：隨機(jī)選擇某一道在xy面上的位置作為起始點(diǎn)，計(jì)算此位置上的點(diǎn)經(jīng)過ρ和π置換后的位置；然后對與新位置位于同一列的另外四個點(diǎn)逐一進(jìn)行π－1和ρ－1運(yùn)算，對于得到的新位置再進(jìn)行ρ和π變換；重復(fù)此過程直到達(dá)到所設(shè)定的片數(shù)k為止。本文提出了一種效率更高的Double Kernel形式差分的搜索算法，將要搜索的位置用數(shù)學(xué)變量表示，得到經(jīng)過θ、ρ、π變換之后的數(shù)學(xué)形式。由Double Kernel的定義可得出此數(shù)學(xué)形式成立需要滿足的條件，在搜索過程中，若不滿足設(shè)定的條件則不進(jìn)行計(jì)算和搜索，從而減少了計(jì)算量，縮小了搜索范圍，提高了搜索效率。以搜索漢明重量為6 的Double Kernel形式差分為例，此時k＝3，假設(shè)6個差分初始位置為：

經(jīng)過θ、ρ和π變換后其位置可表示為：

若式（2）為Double Kernel形式，則（y1，z1＋r1）、（y2，z1＋r2）、（y3，z2＋r3）、（y4，z2＋r4）、（y5，z3＋r5）、（y6，z3＋r6）必定兩兩對應(yīng)相等。所有八種可能的對應(yīng)情況如下：

實(shí)驗(yàn)已經(jīng)證明八種情況是等價(jià)的，這里選擇第一種情況，根據(jù)式（2）得：

y1＝y(tǒng)4，z1＋r1＝z2＋r4

y2＝y(tǒng)5，z1＋r2＝z3＋r5

y3＝y(tǒng)6，z2＋r3＝z3＋r6

若以上三式成立則必須滿足r6－r3＝r1－r2＋r5－r4。算法中只需判斷r6－r3＝r1－r2＋r5－r4是否滿足即可，不滿足條件者排除在搜索范圍之外。另由Double Kernel的定義，x1≠x2且x1≠x3且x2≠x3且y1≠y2且y1≠y3且y2≠y3，不符合此條件者也應(yīng)排除在搜索范圍之外。以上施加的兩個限制條件大大縮小了本算法的搜索范圍，提高了搜索效率。算法偽代碼如下：

算法 1

本算法采用C 語言實(shí)現(xiàn)，編譯環(huán)境為Microsoft Visual Studio 2010。經(jīng)過程序搜索，共有256個符合條件的結(jié)果，分為四組不同的Double Kernel，每組64個。四組Double Kernel如下（以每組第一個元素代表，其余63個元素可通過依次增大下標(biāo)z得到）：

（0，3，0）（0，1，0）（1，2，60）（1，3，60）（3，1，45）（3，2，45）

（0，4，0）（0，2，0）（2，3，21）（2，4，21）（4，2，28）（4，3，28）

（1，2，0）（1，0，0）（2，3，31）（2，2，31）（4，0，38）（4，3，38）

（2，0，0）（2，4，0）（3，3，34）（3，0，34）（4，4，47）（4，3，47）

4.3 漢明重量為4及以下的Double Kernel形式差分的不存在性

選擇Double Kernel的原則是盡可能選擇低漢明重量的差分，即差分的漢明重量越小越好，高漢明重量意味著需要滿足的條件較多，因此找到碰撞的概率減小。文獻(xiàn)［1］中使用的是漢明重量為8的差分，而文獻(xiàn)［9］對此進(jìn)行了改進(jìn)，使用了漢明重量為6 的差分進(jìn)行攻擊，因而其效率更高。由Double Kernel形式差分的定義，漢明重量低于6的差分還有漢明重量為4及漢明重量為2的差分。

本文對算法1進(jìn)行修改，使之適用于漢明重量為4 的Double Kernel形式差分的搜索。實(shí)驗(yàn)結(jié)果顯示，符合條件的Double Kernel形式差分個數(shù)為0，即漢明重量為4的Double Kernel形式差分不存在。

對于漢明重量為2的差分，本文從理論推導(dǎo)證明了其不存在。

證明 設(shè)兩個差分初始位置為：

經(jīng)過θ、ρ和π變換后其位置可表示為：

若要使式（3）為Double Kernel，則式（4）需滿足y1＝y(tǒng)2且z1＋r1＝z1＋r2，由Double Kernel定義知，y1≠y2，由Keccak算法知，r1≠r2，矛盾！故假設(shè)不成立，即漢明重量為2的Double Kernel形式差分不存在。

綜上，漢明重量為4及以下的Double Kernel形式差分不存在。

4.4 算法復(fù)雜度分析

文獻(xiàn)［1］中提到其算法的復(fù)雜度為25＊42k－1，本文算法復(fù)雜度為52k。以差分漢明重量為6的情況（即k＝3）為例，文獻(xiàn)［1］中算法復(fù)雜度為25＊45，本文算法復(fù)雜度為56，本算法復(fù)雜度明顯小于文獻(xiàn)［1］中的算法。本算法在差分漢明重量為4（k＝2）、差分漢明重量為6（k＝3）、差分漢明重量為8（k＝4）時均優(yōu)于文獻(xiàn)［1］中的算法。兩種算法的復(fù)雜度見表2（文獻(xiàn)［1］中算法復(fù)雜度以O(shè)1表示，本文算法復(fù)雜度以O(shè)2表示）。

Table 2 Complexities of two algorithms表2 兩種算法的復(fù)雜度

5 結(jié)束語

本文分析研究了Keccak輪函數(shù)中最重要也是最復(fù)雜的兩個變換θ和χ。對于Keccak輪函數(shù)中唯一的非線性變換χ，將χ表示為布爾函數(shù)表達(dá)式形式，由其布爾函數(shù)表達(dá)式進(jìn)行差分?jǐn)U散推導(dǎo)，得到了輸入輸出差分32種情況下的分布表并分析了其輸出差分的分布規(guī)律。

對文獻(xiàn)［1］中提出的搜索Double Kernel形式差分的算法進(jìn)行了改進(jìn)，通過施加限制條件減少了計(jì)算量，縮小了搜索的范圍，提高了搜索效率，新算法復(fù)雜度較文獻(xiàn)［1］中算法有明顯降低。本文還通過程序驗(yàn)證了漢明重量為4 的Double Kernel形式差分不存在，通過理論推導(dǎo)證明了漢明重量為2的Double Kernel形式差分不存在。

目前對Keccak進(jìn)行差分攻擊所構(gòu)造的差分路徑均是滿足Kernel或Double Kernel形式的差分路徑，本文也只是對Double Kernel形式差分的搜索算法進(jìn)行了改進(jìn)，以更高效率地找到符合條件的Double Kernel形式差分。一些研究者已經(jīng)指出，Kernel或Double Kernel形式的差分路徑至多只能維持兩輪，兩輪之后差分便會急劇擴(kuò)散，漢明重量大大增加。文獻(xiàn)［9］及文獻(xiàn)［11］中均對Kernel或Double Kernel形式的差分路徑進(jìn)行倒推以增加攻擊的總輪數(shù)，然而倒推也遇到了極大的困難。鑒于上述情況，要想得到更多輪數(shù)的攻擊，最好的方法是尋找能維持更多輪數(shù)的高概率差分路徑，而不僅僅局限于Kernel或Double Kernel形式，這也是進(jìn)一步研究Keccak的重要方向之一。

［1］ María Naya－Plasencia，Rock A，Meier W.Practical analysis of reduced－round Keccak［C］∥Proc of INDOCRYPT’11，2011：236－254.

［2］ Wang Xiao－yun，Yiqun Lisa Yin，Yu Hong－bo.Finding collisions in the full SHA－1［C］∥Proc of CRYPTO，2005：17－36.

［3］ Wang Xiao－yun，F(xiàn)eng Deng－guo，Yu Xiu－yuan.An attack on hash function HAVAL－128［J］.Science in China（ser.F），2005，48（5）：545－556.

［4］ Wang Xiao－yun，Yu Hong－bo.How to break MD5and other Hash functions［C］∥Proc of EUROCRYPT’05，2005：19－35.

［5］ NIST.SHA－3Competition（2007－2012）［EB/OL］.［2012－12－13］.http：//csrc.nist.gov/groups/ST/hash/sha－3/index.html.

［6］ Bertoni G，Daemen J，Peeters M，et al.The Keccak reference［EB/OL］.［2011－11－17］.http：//KECCAK.noekeon.org/KECCAK－reference－3.0.0.pdf.

［7］ Bertoni G，Daemen J，Peeters M，et al.The Keccak SHA－3 submission［EB/OL］.［2011－11－17］.http：//www.keccak.noekeon.org/keccak－submission－3.pdf.

［8］ Biham E，Shamir A.Differential cryptanalysis of DES－like cryptosystems［C］∥Proc of CRYPTO’09，1990：2－21.

［9］ Dinur I，Dunkelman O，Shamir A.Improved practical attacks on round－reduced Keccak［J］.Journal of Cryptography，2014，27（2）：183－209.

［10］ Bertoni G，Daemen J，Peeters M，et al.Sponge functions［C］∥Proc of ECRYPT Hash Workshop，2007：1.

［11］ Duc A，Guo Jian，Peyrin T，et al.Unaligned rebound attack：Application to Keccak［C］∥Proc of FSE’12，2012：402－421.

［12］ Dinur I，Dunkelman O，Shamir A.Collision attacks on up to 5rounds of SHA－3using generalized internal differentials［C］∥Proc of FSE’13，2013：219－240.

［13］ Lin Dong－dai，Cao Tian－jie.Applied cryptography［M］.Beijing：Science Press，2009.（in Chinese）

［14］ Zhang Shi－bin，Sun Wu－nan，Zhang Jin－quan，et al.Applied cryptography［M］.Xi’an：Xidian University Press，2009.（in Chinese）

［15］ Li Qian－nan，Li Yun－qiang，Jiang Shu－jing，et al.Research on differential properties of Keccak－like nonlinear transform［J］.Journal of Communications，2012，33（9）：140－146.（in Chinese）

附中文參考文獻(xiàn)

［13］ 林東岱，曹天杰.應(yīng)用密碼學(xué)［M］.北京：科學(xué)出版社，2009.

［14］ 張仕斌，孫武南，張金全，等.應(yīng)用密碼學(xué)［M］.西安：西安電子科技大學(xué)出版社，2009.

［15］ 李倩男，李云強(qiáng)，蔣淑靜，等.Keccak類非線性變換的差分性質(zhì)研究［J］.通信學(xué)報(bào)，2012，33（9）：140－146.