代數系統求解4輪Keccak-256原像攻擊的完善

裴君翎，陳魯生

南開大學 數學科學學院，天津 300071

Keccak哈希函數[1]由比利時密碼學家Bertoni等領銜設計，于2008年成為了美國國家標準技術研究所（NIST）開展的第三代安全哈希算法（SHA-3）競賽[2]的候選作品，于2012年贏得了該競賽，隨后，美國國家標準技術研究所于2015年將其標準化為第三代安全哈希函數。自公開發布以來，Keccak哈希函數接受了深入的安全分析，包括傳統的安全概念，如抗碰撞攻擊、抗原像攻擊、立方攻擊[3]、零和區分器[4]以及在消息認證碼[5]、流密碼和認證密碼模式下的安全性。

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

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

求解代數系統是目前Keccak哈希函數原像攻擊的最有效方法之一，在構造代數系統時，降低系統的次數是攻擊成功的關鍵。本文討論4輪Keccak-256的原像攻擊，對文獻[13]的線性化過程進行了完善，將更多的非線性比特位線性化，理論復雜度由2239降低為2216。

1 Keccak哈希函數

關于Keccak哈希函數的完整描述參閱文獻[1]，在此不再詳述。為討論方便起見，僅描述關鍵部分。

1.1 Keccak哈希函數的海綿結構

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

圖1 Keccak哈希函數的海綿結構Fig.1 Sponge construction of Keccak Hash function

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

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

1.2 Keccak哈希函數中的置換f

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

圖2 數據狀態Fig.2 Data state

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

在上述定義中，“⊕”表示二元域上的加法，“⊕”表示二元域上的求和，“·”表示二元域上的乘法，“RCz”表示輪常數，省略了RCz的細節，因為它不影響攻擊?！皉[x][y]”是與道相關的旋轉常數，表示針對二維狀態a[x][y]的z軸進行移位操作，取值如表1所示。

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

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

命題1給定部件χ的5個輸出比特中的連續t個，可以建立至少t-1個關于輸入比特的線性方程。給定連續的輸出比特數與線性方程個數的關系如表2所示。

表2 給定連續的輸出比特數與方程個數的關系Table 2 Relationship between number of given continuous output bits and number of equations

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

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

則存在一組常數{s[x][z]}使得當各列和為定值{s[x][z]}時，一定能夠通過θ由狀態(a′)得到狀態(b)，進而Keccak哈希函數中的置換f能夠以194的自由度保持2輪線性結構。

2 4輪Keccak-256原像攻擊

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

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

圖4 異或第二個消息塊后的狀態變化Fig.4 State change after XOR the second message

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

原像攻擊的第一階段同文獻[10]，為完整起見，現簡要描述過程。該階段的輸出狀態滿足式（3），且根據填充規則還需滿足e[1][3][63]⊕1=e[1][4][63]⊕1，因此，第一階段需要滿足193+1=194個等式。在原像的所有取值中，有一半數量的取值能夠使得等式e[2][3][63]⊕1=e[2][4][63]成立，對(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個可能的值就能確保上述194個等式全部成立，故第一階段復雜度為2194。使得194個等式全部成立的原像即為第一個消息塊。

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

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

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

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

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

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

即q[x][y][z]中只有一個二次項，它由l[x+1][y][z]和l[x+2][y][z]生成，因此，如果設l[x+1][y][z]或l[x+2][y][z]為常數則可以將q[x][y][z]線性化。同時，還發現枚舉l[x+2][y][z]的值可以將q[x][y][z]和q[x+1][y][z]線性化。

接下來以r[1][1][Z]、r[2][2][Z]和r[3][3][Z-1]為例描述線性化的過程。

如圖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二次方程線性化過程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個線性化過程后，線性化的二次比特出現在面上的同一位置。表3列出了5個線性化過程中每個面上枚舉的線性多項式個數、線性化的二次比特數以及得到的線性方程個數。5個面共枚舉29個線性多項式，線性化二次比特8個，得到37個線性方程。

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

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

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

3 結束語

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