多SP輪函數對廣義Feistel結構安全性影響分析

王田麗，黃 坤

(華北水利水電大學數學與信息科學學院，河南鄭州450046)

0 引言

廣義Feistel結構是由鄭玉良等人于1989年的美洲密碼年會上提出的一系列算法結構.Lesamnta［1］是進入NIST舉辦的SHA-3競賽第一輪的56個雜湊函數之一，它采用了比較流行的Type-1廣義 Feistel［2］結構的變體.2010 年，Bouillaguet等人對其給出了一個20輪的積分區分器［3］.2009年，Mendel等人介紹了一種分析雜湊函數的新技術，稱為反彈攻擊［4］.在2011年的 FSE會議上，Sasaki等人將這一技術用于Feistel-SP結構的算法，給出了11輪已知密鑰區分器［5］.后來，Sasaki等人又將復雜度加以改進，并應用于Camellia［6］.但這種技術對廣義Feistel結構進行攻擊的結果如何，現在還不明晰.筆者從多SP輪函數的角度出發，分析這種設計會給安全性帶來什么樣的影響.

1 基礎知識

1.1 Type-1廣義Feistel結構和Lesamnta簡介

Type-1廣義Feistel結構的狀態有四個字，而Lesamnta的壓縮函數利用分組密碼和MMO結構，整個Lesamnta雜湊函數采用MD結構.對于Lesamnta-256雜湊函數，消息填充之后長度是256比特的整數倍，并被分成256比特大小的塊M1‖M2‖…‖MN.記壓縮函數為 CF:{0，1}256×{0，1}256→{0，1}256，它按照下列方式進行迭代:

初始狀態記為H0.最后的HN即為消息M的雜湊值.中間的分組密碼EK為4分支的Type-1廣義Feistel結構.首先，中間鏈值Hi-1進入密鑰生成算法，生成每一輪的64比特子密鑰kj，其中0≤j≤31.狀態中 4 個 64 比特的字我們用 Wj，Xj，Yj，Zj來表示，則EK的輸出按照下列方式計算:

輪函數F包含4個運算:輪密鑰加、字節代換、行移位層、列混淆層.攻擊是在已知密鑰狀態下，在這里忽略密鑰擴展算法，細節參考文獻［1］.

1.2 反彈攻擊

反彈攻擊［4］是Mendel等人提出的一種針對雜湊函數的分析方法.它從兩個狀態出發，選擇截斷差分，在中間某S盒層構造匹配，再分別向前向后構造截斷差分路徑，故命名為反彈攻擊.此類攻擊的方法與傳統的差分攻擊有所不同，其關鍵點之一在于研究S盒層的匹配性質.

2 多SP輪函數Type-1廣義Feistel結構安全性

利用三輪匹配技術，對兩輪擴散(AES類)的SP輪函數的Type-1廣義Feistel結構進行分析.

情形1:兩輪擴散的雙SP結構.如果函數采用雙SP結構，并且兩輪達到全擴散，則可以采用如圖1的彈入結構進行攻擊.圖中0表示不活躍的字，F表示全活躍的字，H表示經過 P(或者P-1)達到全活躍的字.首先在#A處取一個活躍狀態，此狀態經過一個P擴散后全活躍，同樣在#B處選擇一個活躍狀態，經過一個P-1擴散后全活躍，兩個狀態進行3輪匹配，如圖1中粗線所示.而#A沿虛線運算經過一個逆SP層，然后異或輪子密鑰，在第二輪異或常數，在第五輪異或輪子密鑰，再進行雙SP運算，如果設定第二輪的常數等于第一輪與第五輪輪密鑰的異或，則可保證在第五輪異或的時候將差分消除，得到一個非活躍字.

彈出部分是概率為1的，具體每一輪的差分字特征見表1.彈出部分一共11輪，故攻擊一共有16輪.

圖1 Type-1雙SP結構彈入攻擊部分Fig.1 Inbound phase for Type-1 double SP constructure

表1 Type-1雙SP結構與三SP結構彈出攻擊部分Tab.1 Outbound phase for Type-1 double SP constructur and three SP structure

圖2 Type-1三SP結構彈入攻擊部分Fig.2 Inbound phase for Type-1 three SP constructure

情形2:2輪擴散的三SP結構.這種輪函數使用了3輪的SP結構，這樣看起來會使得擴散更加充分，但是總的攻擊仍然可以達到16輪.如圖2所示，其彈出部分見表1.

其它情形:由上述兩種情形可以看到，即使再增加輪數，對攻擊彈入部分的影響也只是將彈入五輪之后的第二個字變為F，這樣會將正向彈出部分輪數變為3輪，總的攻擊輪數變為13輪.

3 Lesamnta-256的截斷差分區分器

3.1 彈入部分

步驟1:(正向起始)選擇并固定狀態#4的兩個灰色字節的差分，此差分線性地傳播至狀態#5，使得狀態#5中有4個字節差分不為0.由于此狀態第1行的每一個字節與其右下方的字節進入同一個超級S盒，將這兩個字節看做一個整體，取遍其216個值，每個值均可以獨立地計算至狀態#9，然后存儲在一個表中.這樣，由狀態#5至狀態#9可以建立4個這樣的表，每一個的大小為216.

圖3 彈入部分Fig.3 Inbound phase

步驟2:(逆向起始)相似地，在狀態#12選擇并固定4個灰色字節的差分，在狀態#11取遍每一個超級S盒的輸入的值，在狀態#9建立4個大小為216的表.值得注意的是，在狀態#9，由狀態#5開始建立的每一個表都對應第1行的一個字節和它左下方的一個字節，由狀態#11開始的每一個表都對應一列的兩個字節.為了區別，我們從左到右記正向的四個表為 l1，l2，l3，l4，逆向的四個表記

步驟3:(匹配輪)狀態#9左下角字節差分為0，取定此字節的值.這樣，相當于給集合限定了216個條件，而集合中包含216個元素，我們期望在其中找到一個滿足條件.這樣，狀態#9和狀態#10的第一行的兩個字節的差分和值就都確定了.而隨著狀態#9左上角字節的差分和值的確定，相當于給集合l1限定了216個條件，我們同樣期望有一個元素滿足條件.而集合l1涉及的另一個字節為#9右下角的字節，所以這一字節的差分和值也確定了.這樣，我們對集合限定了216個條件，我們期望從此集合中得到一個元素滿足條件.按照同樣的方法，我們可以確定剩下的字節的差分和值.狀態#9中第1行的第2個字節是最后確定的元素.但是，我們發現此字節的差分為零，這樣就在最后多出了28個條件.開始選擇狀態中左下角的元素值時，也有28個選擇.這樣，我們便以28的時間復雜度達到了匹配.

步驟4:(正向逆向彈出)找到匹配之后，狀態#4逆向傳播到狀態#1，狀態#12正向傳播到狀態#14.

步驟5:(消除輪)我們發現，第4大輪輸出的最后一個字，和第5大輪F函數的輸出都是由同樣的截斷差分模式生成的.而且，狀態#1的差分與第5大輪第一個狀態的差分相同，值相差一個常數.記第2大輪的F函數的輸出為，則相差的常數可以表示為

通過上述步驟，我們得到了一條包含5大輪的差分路徑.此路徑的時間復雜度由兩部分組成:建8個表的時間復雜度和中間匹配的時間復雜度.共用218.6次S盒的計算的時間，和218個“兩字節”的存儲.

3.2 彈出部分

事實上，彈出部分可以分為兩個部分:正向彈出部分和逆向彈出部分.共有19輪，具體細節見表2.

表2 19輪截斷差分路徑Tab.2 19-round truncated differential path

3.3 與理想置換進行區分

用218.6次S盒的計算的時間，218個“兩字節”的存儲，構造了一條輸入輸出均有2224種可能差分的差分路徑.我們的攻擊為19輪，每輪有24次的S盒計算，故時間復雜度為218.6/19×24=29.8.而狀態含32個字節，故存儲為218/32=213.而一個理想置換，如果找到具有同樣差分模式的兩個輸入/輸出的話，需要232/2=216的計算復雜度.所以，此區分器可以將19輪的Lesamnta置換與理想函數有效區分.

4 結論

得到了Type-1廣義Feistel-SPSP結構的16輪已知密鑰區分器，Type-1廣義Feistel-SPSPSP結構的16輪已知密鑰區分器.并證明了即使輪函數使用更多的SP迭代，也可以構造至少13輪的已知密鑰區分器.還將這一方法應用與雜湊函數Lesamnta，如何通過其構造碰撞或者近似碰撞值得進一步研究.

［1］SHOICHI H，HIDENORI K，HIROTAKA Y.SHA-3 Proposal:Lesamnta［EB/OL］.http://ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf.

［2］ZHENG Yu-liang，MATSUMOTO T，IMAI H.On the construction of block ciphers provably secure and not relying on any unproved hypotheses［C］//Proceeding of CRYPTO.Santa Barbara，USA，1989:461-480.

［3］CHARLES B，ORR D，GA?TAN L P.Attacks on hash functions nased on generalized feistel:application to reduced-round lesamnta and SHAvite-3512［C］//Proceeding of Selected Areas in Cryptography.Waterloo，Ontario，Canada，2010:18-35.

［4］MARIO L，FLORIAN M，CHRISTIAN R，et al.Rebound distinguishers:results on the full whirlpool compression function［C］//Proceeding of ASIACRYPT.Tokyo，Japan.2009:126-143.

［5］SASAKI Y.Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool［C］//Proceeding of Fast Software Encryption.Lyngby，Denmark.2011:378-396.

［6］SASAKI Y，EMAMI S，HONG D，et al.Improved known-key distinguishers on feistel-SP ciphers and application to camellia［C］//Proceeding of Information Security and Privacy.Wollongong，NSW，Australia.2012:87-100.