代數(shù)系統(tǒng)求解4輪Keccak-256原像攻擊的完善

裴君翎，陳魯生

南開(kāi)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，天津 300071

Keccak哈希函數(shù)[1]由比利時(shí)密碼學(xué)家Bertoni等領(lǐng)銜設(shè)計(jì)，于2008年成為了美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）開(kāi)展的第三代安全哈希算法（SHA-3）競(jìng)賽[2]的候選作品，于2012年贏得了該競(jìng)賽，隨后，美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所于2015年將其標(biāo)準(zhǔn)化為第三代安全哈希函數(shù)。自公開(kāi)發(fā)布以來(lái)，Keccak哈希函數(shù)接受了深入的安全分析，包括傳統(tǒng)的安全概念，如抗碰撞攻擊、抗原像攻擊、立方攻擊[3]、零和區(qū)分器[4]以及在消息認(rèn)證碼[5]、流密碼和認(rèn)證密碼模式下的安全性。

由于Keccak哈希函數(shù)在全球應(yīng)用的廣泛性和重要性，針對(duì)它的多種原像攻擊方法被相繼提出。文獻(xiàn)[6]基于中間相遇攻擊的方法實(shí)現(xiàn)了2輪Keccak哈希函數(shù)的原像攻擊；文獻(xiàn)[7]利用SAT求解器實(shí)現(xiàn)了2輪Keccak哈希函數(shù)的原像攻擊且運(yùn)行時(shí)間更短；文獻(xiàn)[8]利用旋轉(zhuǎn)密碼分析法實(shí)現(xiàn)了4輪Keccak-384和Keccak-512的原像攻擊；文獻(xiàn)[9]基于多項(xiàng)式枚舉算法實(shí)現(xiàn)了8輪Keccak哈希函數(shù)的原像攻擊；文獻(xiàn)[10]實(shí)現(xiàn)了9輪Keccak哈希函數(shù)的原像攻擊。

2016年，文獻(xiàn)[11]提出了基于代數(shù)系統(tǒng)求解的方法，利用線性結(jié)構(gòu)得到原像攻擊的更好分析結(jié)果。隨后的一年，文獻(xiàn)[12]沿用了這一方法并提出了更精細(xì)的交叉線性結(jié)構(gòu)，在這個(gè)結(jié)構(gòu)中，不同的多項(xiàng)式存在相同的線性因子，通過(guò)枚舉這些線性因子可以得到更多線性方程，這進(jìn)一步降低了3輪Keccak-256原像攻擊的復(fù)雜度。2019年，文獻(xiàn)[13]在文獻(xiàn)[12]的基礎(chǔ)上又進(jìn)行了改進(jìn)，基于非線性代數(shù)方法將攻擊過(guò)程分為兩個(gè)階段，第一階段受到一組新提出的中間狀態(tài)的約束，第二階段受到給定哈希值的約束，這兩個(gè)階段的約束條件均比直接由初始值和哈希值得到的條件弱，因此每次只需考慮較少的約束進(jìn)而降低了復(fù)雜度，給出了目前3輪和4輪Keccak-256原像攻擊的最好結(jié)果，4輪Keccak-256原像攻擊的理論復(fù)雜度為2239。隨后，文獻(xiàn)[14]將這種非線性代數(shù)的思想引入到Keccak-384和Keccak-512的原像攻擊中，給出了目前2輪、3輪和4輪Keccak-384以及2輪和3輪Keccak-512原像攻擊的最好結(jié)果。

求解代數(shù)系統(tǒng)是目前Keccak哈希函數(shù)原像攻擊的最有效方法之一，在構(gòu)造代數(shù)系統(tǒng)時(shí)，降低系統(tǒng)的次數(shù)是攻擊成功的關(guān)鍵。本文討論4輪Keccak-256的原像攻擊，對(duì)文獻(xiàn)[13]的線性化過(guò)程進(jìn)行了完善，將更多的非線性比特位線性化，理論復(fù)雜度由2239降低為2216。

1 Keccak哈希函數(shù)

關(guān)于Keccak哈希函數(shù)的完整描述參閱文獻(xiàn)[1]，在此不再詳述。為討論方便起見(jiàn)，僅描述關(guān)鍵部分。

1.1 Keccak哈希函數(shù)的海綿結(jié)構(gòu)

Keccak哈希函數(shù)采用了如圖1的海綿結(jié)構(gòu)[15]，其中M表示任意長(zhǎng)度的消息，Z表示函數(shù)的輸出，l表示函數(shù)的輸出長(zhǎng)度，r表示比特率，c表示容量，f表示置換，b=r+c表示置換寬度。

圖1 Keccak哈希函數(shù)的海綿結(jié)構(gòu)Fig.1 Sponge construction of Keccak Hash function

海綿結(jié)構(gòu)分為吸收階段和擠壓階段。在吸收階段，消息M首先進(jìn)行填充，填充后消息的長(zhǎng)度是比特率r的倍數(shù)。接著，消息分為長(zhǎng)度為r的若干消息塊。隨后，從全部為0的初始值開(kāi)始，b比特狀態(tài)的前r比特與消息塊進(jìn)行異或運(yùn)算并與后c比特共同作為置換f的原像，重復(fù)此步驟，直到處理完所有消息塊。在擠壓階段，首先輸出前r比特。隨后，在經(jīng)過(guò)置換f后可以輸出更多的r比特，重復(fù)該過(guò)程，直到獲得所需長(zhǎng)度l的所有比特位。最后輸出這l比特。

根據(jù)參數(shù)集(b,c,l)取值的不同，Keccak哈希函數(shù)有不同的版本。本文僅考慮Keccak哈希函數(shù)的置換f的寬度b=1 600的情形，此時(shí)容量c=2l，其中l(wèi)∈{224,256,384,512}，記為Keccak-l。Keccak哈希函數(shù)的填充規(guī)則形如“M10…1”，即，它首先填充單個(gè)比特“1”，后跟若干比特“0”，最后再填充單個(gè)比特“1”，填充后消息的長(zhǎng)度為r的倍數(shù)。滿足這一條件的“10…1”比特串有多個(gè)，選擇其中長(zhǎng)度最短的進(jìn)行填充。因此，最少填充2比特，最多填充r+1比特。

1.2 Keccak哈希函數(shù)中的置換f

Keccak哈希函數(shù)中的置換f的寬度共1 600 bit，表示為如圖2（a）所示的5×5個(gè)64 bit的道。每一比特都可以表示為二元域上的一個(gè)三維數(shù)組a[x][y][z]，消息串M通過(guò)M[64(5y+x)+z]=a[x][y][z]進(jìn)入三維數(shù)組進(jìn)行變換。x軸和y軸構(gòu)成的二維平面稱為“面”，如圖2（b）所示。[x]表示列的索引，[y]表示行的索引，[z]表示道的索引，[x]和[y]的取值均從0到4，[z]的取值從0到63。有時(shí)省略索引[z]、索引[y][z]或全部3個(gè)索引，這表示該條陳述適用于省略的索引中的所有值。當(dāng)某些比特被設(shè)定為未知量時(shí)，如果一個(gè)比特可以表示為關(guān)于這些未知比特的線性多項(xiàng)式，則稱這個(gè)比特是線性的，類似地，如果一個(gè)比特可以表示為關(guān)于這些未知比特的二次多項(xiàng)式，則稱這個(gè)比特是二次的。

圖2 數(shù)據(jù)狀態(tài)Fig.2 Data state

Keccak哈希函數(shù)中的置換f是迭代置換，由24輪置換R組成。每輪置換R=ι°χ°π°ρ°θ由以下5個(gè)部件組成：

在上述定義中，“⊕”表示二元域上的加法，“⊕”表示二元域上的求和，“·”表示二元域上的乘法，“RCz”表示輪常數(shù)，省略了RCz的細(xì)節(jié)，因?yàn)樗挥绊懝簟！皉[x][y]”是與道相關(guān)的旋轉(zhuǎn)常數(shù)，表示針對(duì)二維狀態(tài)a[x][y]的z軸進(jìn)行移位操作，取值如表1所示。

表1 r[x][y]的取值Table 1 Value of r[x][y]

通過(guò)對(duì)θ、ρ、π、χ和ι共5個(gè)部件的表達(dá)式進(jìn)行分析，不難發(fā)現(xiàn)部件ρ、π和ι屬于線性運(yùn)算，其輸出結(jié)果均保持線性。部件θ雖然屬于線性運(yùn)算，但未知量經(jīng)過(guò)θ會(huì)擴(kuò)散到周圍兩列，這大幅度增加了輸入部件χ的未知量個(gè)數(shù)，不利于線性化操作。若各列列和均為0或1，則經(jīng)過(guò)部件θ的狀態(tài)一定可以保持線性且未知量不擴(kuò)散，因此，在經(jīng)過(guò)部件θ前設(shè)定含未知量的各列的和均為常數(shù)是防止未知量擴(kuò)散的一個(gè)重要思想。部件χ是唯一的非線性部件，處于同一行的未知量經(jīng)過(guò)χ后會(huì)相互影響。文獻(xiàn)[8]和[10]分別給出了如下關(guān)于部件χ的兩個(gè)命題，這兩個(gè)命題在后續(xù)原像攻擊的分析中起到至關(guān)重要的作用。

命題1給定部件χ的5個(gè)輸出比特中的連續(xù)t個(gè)，可以建立至少t-1個(gè)關(guān)于輸入比特的線性方程。給定連續(xù)的輸出比特?cái)?shù)與線性方程個(gè)數(shù)的關(guān)系如表2所示。

表2 給定連續(xù)的輸出比特?cái)?shù)與方程個(gè)數(shù)的關(guān)系Table 2 Relationship between number of given continuous output bits and number of equations

命題2令初始狀態(tài)（a′）（內(nèi)部比特用a[x][y][z]表示）如圖3所示，如果：

圖3 初始狀態(tài)為(a′)的2輪置換fFig.3 2-round permutation f with initial state(a′)

則存在一組常數(shù){s[x][z]}使得當(dāng)各列和為定值{s[x][z]}時(shí)，一定能夠通過(guò)θ由狀態(tài)(a′)得到狀態(tài)(b)，進(jìn)而Keccak哈希函數(shù)中的置換f能夠以194的自由度保持2輪線性結(jié)構(gòu)。

2 4輪Keccak-256原像攻擊

4輪Keccak-256的輸出長(zhǎng)度l=256，置換f由24輪置換R組成。本文采用與文獻(xiàn)[10]一致的分析方法和相同的代數(shù)系統(tǒng)。將攻擊過(guò)程分為兩個(gè)階段，兩階段分別得到一個(gè)消息塊，它們共同構(gòu)成原像，其中第一階段受到一組新提出的中間狀態(tài)的約束，第二階段受到給定哈希值的約束，這樣每次考慮較少的約束以獲得更多的自由度，進(jìn)而有效降低復(fù)雜度。

具體來(lái)說(shuō)，如圖4所示，狀態(tài)（A）（內(nèi)部比特用e[x][y][z]表示）是第一階段的輸出狀態(tài)，也是攻擊的中間狀態(tài)，對(duì)于Keccak-256，它的容量c=512意味著最后8個(gè)道不能通過(guò)異或第二個(gè)消息塊而改變，因此為了使?fàn)顟B(tài)（B）滿足式（1）和（2），需要確保下述64+64+64+1=193個(gè)方程全部成立：

圖4 異或第二個(gè)消息塊后的狀態(tài)變化Fig.4 State change after XOR the second message

2.1 4輪Keccak-256原像攻擊第一階段

原像攻擊的第一階段同文獻(xiàn)[10]，為完整起見(jiàn)，現(xiàn)簡(jiǎn)要描述過(guò)程。該階段的輸出狀態(tài)滿足式（3），且根據(jù)填充規(guī)則還需滿足e[1][3][63]⊕1=e[1][4][63]⊕1，因此，第一階段需要滿足193+1=194個(gè)等式。在原像的所有取值中，有一半數(shù)量的取值能夠使得等式e[2][3][63]⊕1=e[2][4][63]成立，對(duì)(e[3][3][z],e[3][4][z])、(e[4][3][z],e[4][4][z])和(e[1][3][63],e[1][4][63])的情況，分析是相同的，因此，至多選取原像的2194個(gè)可能的值就能確保上述194個(gè)等式全部成立，故第一階段復(fù)雜度為2194。使得194個(gè)等式全部成立的原像即為第一個(gè)消息塊。

2.2 4輪Keccak-256原像攻擊第二階段

同文獻(xiàn)[10]構(gòu)造代數(shù)系統(tǒng)的方法，根據(jù)命題2，在精心設(shè)置第二個(gè)消息塊之后得到圖5中的初始狀態(tài)。初始狀態(tài)中深色格子為未知量，因此代數(shù)系統(tǒng)包含10×64=640個(gè)未知量。為防止第1輪和第2輪置換的部件θ引起未知量擴(kuò)散，設(shè)定含未知量的各列的和均為常數(shù)，得到5×64+2×64=448個(gè)線性方程，其中2個(gè)方程線性相關(guān)。第3輪置換中，經(jīng)過(guò)部件χ之后的比特全部變?yōu)槎蔚?，因此根?jù)命題1可以得到256個(gè)二次方程，這些二次方程是難解的，需要線性化。本文提出的線性化方法不同于文獻(xiàn)[10]，更充分地利用了各多項(xiàng)式比特之間的關(guān)系。

圖5 4輪Keccak-256原像攻擊第二階段Fig.5 Second stage of 4-round Keccak-256 preimage attack

如圖5，第3輪置換經(jīng)過(guò)部件χ之前的狀態(tài)為(a)，設(shè)其中比特為l[x][y][z]；第3輪置換經(jīng)過(guò)部件χ之后的狀態(tài)為(b)，設(shè)其中比特為q[x][y][z]；第4輪置換經(jīng)過(guò)部件θ之后的狀態(tài)為(c)，設(shè)其中比特為r[x][y][z]。將二次方程線性化的過(guò)程就是將r[x][y][z]線性化的過(guò)程。根據(jù)部件θ的表達(dá)式可得：

其中所有q[x][y][z]是二次比特。注意到：

q[x][y]=l[x][y]⊕(l[x+1][y]⊕1)·l[x+2][y]

即q[x][y][z]中只有一個(gè)二次項(xiàng)，它由l[x+1][y][z]和l[x+2][y][z]生成，因此，如果設(shè)l[x+1][y][z]或l[x+2][y][z]為常數(shù)則可以將q[x][y][z]線性化。同時(shí)，還發(fā)現(xiàn)枚舉l[x+2][y][z]的值可以將q[x][y][z]和q[x+1][y][z]線性化。

接下來(lái)以r[1][1][Z]、r[2][2][Z]和r[3][3][Z-1]為例描述線性化的過(guò)程。

如圖6所示，枚舉l[2][y][Z]的值將q[0][y][Z]和q[1][y][Z]線性化，枚舉l[4][2][Z]的值將q[2][2][Z]線性化，枚舉l[4][y][Z-1]的值將q[3][y][Z-1]和q[2][y][Z-1]線性化，由于：

圖6 4輪Keccak-256二次方程線性化過(guò)程Fig.6 Linearization processes of 4-round Keccak-256 quadratic equations

因此枚舉l[2][y][Z]、l[4][2][Z]和l[4][y][Z-1]的值之后可以將r[1][1][Z]和r[2][2][Z]線性化。再枚舉l[1][y][Z-2]和l[3][1][Z-2]的值將q[0][y][Z-2]、q[1][1][Z-2]和q[4][y][Z-2]線性化，由于：

因此r[3][3][Z-1]可以被線性化。依照上述步驟還可以將r[0][0][Z-2]、r[1][1][Z-2]、r[2][2][Z-3]、r[3][3][Z-3]、r[0][0][Z-4]……線性化，每5個(gè)線性化過(guò)程后，線性化的二次比特出現(xiàn)在面上的同一位置。表3列出了5個(gè)線性化過(guò)程中每個(gè)面上枚舉的線性多項(xiàng)式個(gè)數(shù)、線性化的二次比特?cái)?shù)以及得到的線性方程個(gè)數(shù)。5個(gè)面共枚舉29個(gè)線性多項(xiàng)式，線性化二次比特8個(gè)，得到37個(gè)線性方程。

表3 5個(gè)線性化過(guò)程中各面上的情況Table 3 Situation on each side in 5 linearization processes

不失一般性地，假設(shè)線性化的二次比特分布在第Z-K面至第Z面上，則在這個(gè)過(guò)程中不僅需要枚舉第Z-K面至第Z面的線性多項(xiàng)式的值，還需枚舉第Z-K-1面的線性多項(xiàng)式的值。因此，在代數(shù)系統(tǒng)中，如果枚舉=150個(gè)線性多項(xiàng)式，則可以將個(gè)二次比特線性化并得到個(gè)線性方程，為解該代數(shù)系統(tǒng)，再猜測(cè)640-446-190=4個(gè)線性比特的值即可。此時(shí)，系統(tǒng)包含640個(gè)未知量，446+190+4=640個(gè)線性方程，256-40=216個(gè)二次方程。該代數(shù)系統(tǒng)的解為圖5初始狀態(tài)深色格子的值，將該狀態(tài)與第一階段的輸出狀態(tài)進(jìn)行異或運(yùn)算即得到第二個(gè)消息塊，兩個(gè)消息塊共同構(gòu)成了原像。

根據(jù)文獻(xiàn)[8]，利用代數(shù)系統(tǒng)求解進(jìn)行原像攻擊的復(fù)雜度由解線性方程組的次數(shù)來(lái)衡量。為了得到這個(gè)系統(tǒng)的解，可以變換第2輪已固定的列和的值以及被枚舉的線性多項(xiàng)式的值。因此，需要枚舉2216次來(lái)確保216個(gè)二次方程全部成立，即，需要解2216次線性方程組，這一階段的復(fù)雜度為2216，它高于找到第一個(gè)消息塊的復(fù)雜度，故4輪Keccak-256原像攻擊復(fù)雜度為2216。

3 結(jié)束語(yǔ)

本文討論了基于代數(shù)系統(tǒng)求解的4輪Keccak-256原像攻擊。在已有的最好方法中，線性化過(guò)程是以兩個(gè)面為基本單位對(duì)一個(gè)面的二次比特線性化，理論復(fù)雜度為2239。本文完善了上述線性化過(guò)程，每?jī)蓚€(gè)相鄰的面都可以將一個(gè)面的二次比特線性化，更充分地利用了各線性比特之間的關(guān)系，將理論復(fù)雜度降低為2216。這種完善后的線性化方法對(duì)基于代數(shù)系統(tǒng)求解的其他具有海綿結(jié)構(gòu)的哈希函數(shù)的原像攻擊同樣具有參考意義。