多SP輪函數(shù)對(duì)廣義Feistel結(jié)構(gòu)安全性影響分析

王田麗，黃 坤

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

0 引言

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

1 基礎(chǔ)知識(shí)

1.1 Type-1廣義Feistel結(jié)構(gòu)和Lesamnta簡(jiǎn)介

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

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

輪函數(shù)F包含4個(gè)運(yùn)算:輪密鑰加、字節(jié)代換、行移位層、列混淆層.攻擊是在已知密鑰狀態(tài)下，在這里忽略密鑰擴(kuò)展算法，細(xì)節(jié)參考文獻(xiàn)［1］.

1.2 反彈攻擊

反彈攻擊［4］是Mendel等人提出的一種針對(duì)雜湊函數(shù)的分析方法.它從兩個(gè)狀態(tài)出發(fā)，選擇截?cái)嗖罘?，在中間某S盒層構(gòu)造匹配，再分別向前向后構(gòu)造截?cái)嗖罘致窂?，故命名為反彈攻?此類(lèi)攻擊的方法與傳統(tǒng)的差分攻擊有所不同，其關(guān)鍵點(diǎn)之一在于研究S盒層的匹配性質(zhì).

2 多SP輪函數(shù)Type-1廣義Feistel結(jié)構(gòu)安全性

利用三輪匹配技術(shù)，對(duì)兩輪擴(kuò)散(AES類(lèi))的SP輪函數(shù)的Type-1廣義Feistel結(jié)構(gòu)進(jìn)行分析.

情形1:兩輪擴(kuò)散的雙SP結(jié)構(gòu).如果函數(shù)采用雙SP結(jié)構(gòu)，并且兩輪達(dá)到全擴(kuò)散，則可以采用如圖1的彈入結(jié)構(gòu)進(jìn)行攻擊.圖中0表示不活躍的字，F(xiàn)表示全活躍的字，H表示經(jīng)過(guò) P(或者P-1)達(dá)到全活躍的字.首先在#A處取一個(gè)活躍狀態(tài)，此狀態(tài)經(jīng)過(guò)一個(gè)P擴(kuò)散后全活躍，同樣在#B處選擇一個(gè)活躍狀態(tài)，經(jīng)過(guò)一個(gè)P-1擴(kuò)散后全活躍，兩個(gè)狀態(tài)進(jìn)行3輪匹配，如圖1中粗線所示.而#A沿虛線運(yùn)算經(jīng)過(guò)一個(gè)逆SP層，然后異或輪子密鑰，在第二輪異或常數(shù)，在第五輪異或輪子密鑰，再進(jìn)行雙SP運(yùn)算，如果設(shè)定第二輪的常數(shù)等于第一輪與第五輪輪密鑰的異或，則可保證在第五輪異或的時(shí)候?qū)⒉罘窒玫揭粋€(gè)非活躍字.

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

圖1 Type-1雙SP結(jié)構(gòu)彈入攻擊部分Fig.1 Inbound phase for Type-1 double SP constructure

表1 Type-1雙SP結(jié)構(gòu)與三SP結(jié)構(gòu)彈出攻擊部分Tab.1 Outbound phase for Type-1 double SP constructur and three SP structure

圖2 Type-1三SP結(jié)構(gòu)彈入攻擊部分Fig.2 Inbound phase for Type-1 three SP constructure

情形2:2輪擴(kuò)散的三SP結(jié)構(gòu).這種輪函數(shù)使用了3輪的SP結(jié)構(gòu)，這樣看起來(lái)會(huì)使得擴(kuò)散更加充分，但是總的攻擊仍然可以達(dá)到16輪.如圖2所示，其彈出部分見(jiàn)表1.

其它情形:由上述兩種情形可以看到，即使再增加輪數(shù)，對(duì)攻擊彈入部分的影響也只是將彈入五輪之后的第二個(gè)字變?yōu)镕，這樣會(huì)將正向彈出部分輪數(shù)變?yōu)?輪，總的攻擊輪數(shù)變?yōu)?3輪.

3 Lesamnta-256的截?cái)嗖罘謪^(qū)分器

3.1 彈入部分

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

圖3 彈入部分Fig.3 Inbound phase

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

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

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

步驟5:(消除輪)我們發(fā)現(xiàn)，第4大輪輸出的最后一個(gè)字，和第5大輪F函數(shù)的輸出都是由同樣的截?cái)嗖罘帜Ｊ缴傻?而且，狀態(tài)#1的差分與第5大輪第一個(gè)狀態(tài)的差分相同，值相差一個(gè)常數(shù).記第2大輪的F函數(shù)的輸出為，則相差的常數(shù)可以表示為

通過(guò)上述步驟，我們得到了一條包含5大輪的差分路徑.此路徑的時(shí)間復(fù)雜度由兩部分組成:建8個(gè)表的時(shí)間復(fù)雜度和中間匹配的時(shí)間復(fù)雜度.共用218.6次S盒的計(jì)算的時(shí)間，和218個(gè)“兩字節(jié)”的存儲(chǔ).

3.2 彈出部分

事實(shí)上，彈出部分可以分為兩個(gè)部分:正向彈出部分和逆向彈出部分.共有19輪，具體細(xì)節(jié)見(jiàn)表2.

表2 19輪截?cái)嗖罘致窂絋ab.2 19-round truncated differential path

3.3 與理想置換進(jìn)行區(qū)分

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

4 結(jié)論

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

［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，F(xiàn)LORIAN 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.