Feistel-SPS結(jié)構(gòu)的反彈攻擊

董　樂(lè)　鄒　劍　吳文玲　杜　蛟（河南師范大學(xué)大數(shù)據(jù)統(tǒng)計(jì)分析與優(yōu)化控制河南省工程實(shí)驗(yàn)室新鄉(xiāng)453007）（河南師范大學(xué)數(shù)學(xué)與科學(xué)計(jì)算重點(diǎn)學(xué)科開(kāi)放實(shí)驗(yàn)室新鄉(xiāng)453007）（福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院福州350116）（中國(guó)科學(xué)院軟件研究所可信計(jì)算與信息保障實(shí)驗(yàn)室北京100190）

?

Feistel-SPS結(jié)構(gòu)的反彈攻擊

董樂(lè)*①②鄒劍③吳文玲④杜蛟①②①
①（河南師范大學(xué)大數(shù)據(jù)統(tǒng)計(jì)分析與優(yōu)化控制河南省工程實(shí)驗(yàn)室新鄉(xiāng)453007）
②（河南師范大學(xué)數(shù)學(xué)與科學(xué)計(jì)算重點(diǎn)學(xué)科開(kāi)放實(shí)驗(yàn)室新鄉(xiāng)453007）
③（福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院福州350116）
④（中國(guó)科學(xué)院軟件研究所可信計(jì)算與信息保障實(shí)驗(yàn)室北京100190）

該文給出了以Feistel結(jié)構(gòu)為主框架，以SPS（Substitu tion-Perm utation-Substitution）函數(shù)作為輪函數(shù)的Feistel-SPS結(jié)構(gòu)的反彈攻擊。通過(guò)對(duì)差分?jǐn)U散性質(zhì)的研究，得到這一結(jié)構(gòu)的6輪已知密鑰截?cái)嗖罘謪^(qū)分器，并在此區(qū)分器的基礎(chǔ)上，給出將這一結(jié)構(gòu)內(nèi)嵌入MMO（M atyas-Meyer-Oseas）和MP（M iyaguchi-Preneel）模式所得到的壓縮函數(shù)的近似碰撞攻擊。此外，還將6輪截?cái)嗖罘謪^(qū)分器擴(kuò)展，得到了7輪的截?cái)嗖罘致窂?，基于此還得到上述兩種模式下壓縮函數(shù)的7輪截?cái)嗖罘謪^(qū)分器。

反彈攻擊；Feistel結(jié)構(gòu)；SPS（Substitution-Permutation-Substitution）函數(shù)；截?cái)嗖罘謪^(qū)分器；近似碰撞

2011年，文獻(xiàn)［10］構(gòu)造了11輪Feistel-SP結(jié)構(gòu)的已知密鑰區(qū)分器，并用其構(gòu)造了這一結(jié)構(gòu)雜湊模式的近似碰撞攻擊。2012年，文獻(xiàn)［11］將這一方法用于分析以SP函數(shù)為輪函數(shù)的type-1，type-2和type-3廣義Feistel結(jié)構(gòu)。2014年，文獻(xiàn)［12］將type-1廣義Feistel結(jié)構(gòu)的結(jié)果加以改進(jìn)，次年文獻(xiàn)［13］又將type-2廣義Feistel結(jié)構(gòu)的結(jié)果加以改進(jìn)。雙SP函數(shù)提出后，文獻(xiàn)［14］比較了type-2廣義Feistel結(jié)構(gòu)下的單SP函數(shù)與雙SP函數(shù)，構(gòu)造出了含更多SP層的區(qū)分器，從而得出在反彈攻擊下雙SP函數(shù)模型更弱的結(jié)論。

本文首次對(duì)以SPS函數(shù)為輪函數(shù)的Feistel結(jié)構(gòu)（Feistel-SPS結(jié)構(gòu)）實(shí)施反彈攻擊，將適用于AES型輪函數(shù)的“非全活躍狀態(tài)的差分匹配技術(shù)”首次用于“單列SPS結(jié)構(gòu)”中，得到了6輪的已知密鑰區(qū)分器，并基于這一區(qū)分器構(gòu)造了其雜湊模式的6輪近似碰撞攻擊。然后又將這一區(qū)分器加以改進(jìn)，得到了7輪的已知密鑰區(qū)分器，并得到其壓縮函數(shù)的7輪已知密鑰區(qū)分器。

本文第2節(jié)介紹了相關(guān)的背景知識(shí)；第3節(jié)對(duì)6輪Feistel-SPS結(jié)構(gòu)進(jìn)行反彈攻擊；第4節(jié)對(duì)7輪Feistel-SPS結(jié)構(gòu)進(jìn)行反彈攻擊；第5節(jié)總結(jié)全文。

2　基本知識(shí)

2.1 Feistel-SPS結(jié)構(gòu)

首先給出一些符號(hào)記法：N為密碼算法的分組長(zhǎng)度；n為Feistel結(jié)構(gòu)中左半部分或右半部分比特?cái)?shù)，即n=N/2；c為S盒所包含的比特?cái)?shù)；r為輪函數(shù)中一個(gè)S盒層所含S盒的個(gè)數(shù)。

Feistel-SPS結(jié)構(gòu)如圖1所示，它采用了經(jīng)典的Feistel網(wǎng)絡(luò)作為它的結(jié)構(gòu)，而輪函數(shù)采用了SPS結(jié)構(gòu)。

圖1　 Feistel-SPS結(jié)構(gòu)的一輪

假定文中所攻擊的Feistel-SPS結(jié)構(gòu)，除子密鑰之外每一輪都是相同的，并且S盒層和P層具有“好”的密碼學(xué)特性，即輪函數(shù)中兩個(gè)S盒層的每一個(gè)S盒具有最優(yōu)的抵抗差分分析與線性分析的密碼學(xué)特性。對(duì)于差分分析來(lái)說(shuō)，它們均有最優(yōu)的差分?jǐn)U散性，即任一S盒的每一個(gè)輸入差分都有2c-1個(gè)可能的輸出差分與其對(duì)應(yīng)，這樣任意一對(duì)輸入輸出差分可以在這一S盒層達(dá)到匹配的概率就是1/2，而一旦達(dá)成匹配，有兩對(duì)輸入輸出值與其對(duì)應(yīng)；此外，輪函數(shù)中P層的分支數(shù)達(dá)到最大，即r+1。

2.2反彈攻擊

2009年，文獻(xiàn)［15］提出一種針對(duì)AES類雜湊函數(shù)的攻擊方法，這一攻擊方法的攻擊過(guò)程分為彈入部分和彈出部分，所以命名為“反彈攻擊”。反彈攻擊的最終目的是以比窮舉攻擊更低的復(fù)雜度找到滿足某一預(yù)設(shè)截?cái)嗖罘痔卣鞯囊粚?duì)值，從而得到區(qū)分器或者得到一對(duì)（近似）碰撞。

由于AES類雜湊函數(shù)的輪函數(shù)中，S盒往往具有最優(yōu)差分?jǐn)U散特點(diǎn)，而線性擴(kuò)散層則具有最大的分支數(shù)，所以對(duì)差分分析有很強(qiáng)的抵抗能力。但如果確定輸入輸出差分，也能夠在這樣的S盒處以最大（1/2）的概率實(shí)現(xiàn)差分匹配。正是利用這一點(diǎn)，反彈攻擊在彈入部分可以有效地得到許多滿足這一部分截?cái)嗖罘痔卣鞯闹怠＠眠@些值，攻擊者可以以一定的概率實(shí)施彈出攻擊，從而得到滿足整個(gè)截?cái)嗖罘致窂降闹?。本文?輪攻擊采用了傳統(tǒng)的彈入攻擊模式，而6輪攻擊則采用了非全活躍差分匹配［16］的方法進(jìn)行彈入攻擊，都取得了預(yù)期的效果。

2.3MMO模式與MP模式

設(shè)EK是一個(gè)密鑰為K的分組密碼算法，M為消息塊，H為中間鏈值，MMO模式的壓縮函數(shù)計(jì)算過(guò)程為

MP模式的壓縮函數(shù)計(jì)算過(guò)程為

本文基于6輪已知密鑰截?cái)嗖罘謪^(qū)分器，構(gòu)造了內(nèi)嵌Feistel-SPS結(jié)構(gòu)（即分組密碼KE具有這一結(jié)構(gòu)）的MMO模式和MP模式的近似碰撞。

3　 Feistel-SPS結(jié)構(gòu)的6輪反彈攻擊

本節(jié)以4r=，8c=的Feistel-SPS結(jié)構(gòu)為例，對(duì)其進(jìn)行6輪（含有12個(gè)S盒層）的反彈攻擊。

3.1攻擊概述

首先，給出攻擊中所使用的幾個(gè)符號(hào)：

0為所有字節(jié)都不活躍的字；i為有i個(gè)指定位置的字節(jié)是活躍的字，例如2表示有兩個(gè)指定位置的字節(jié)是活躍的字；F為全部字節(jié)都活躍且不能確定其差分的字。

攻擊的第1步利用反彈攻擊對(duì)Feistel-SPS結(jié)構(gòu)構(gòu)建一條6輪差分路徑，其中第3輪和第4輪為彈入部分，第1輪和第2輪為逆向彈出部分，第5輪和第6輪為正向彈出部分。整個(gè)差分路徑的差分傳播模式為

最后得到了82對(duì)滿足整個(gè)6輪差分路徑的值，以這些值構(gòu)造內(nèi)部置換采用Feistel-SPS結(jié)構(gòu)，反饋采用MMO或MP模式的壓縮函數(shù)的近似碰撞。

3.2兩輪彈入部分

這一部分將構(gòu)建截?cái)嗖罘痔卣飨唷皩?duì)稱”的兩個(gè)彈入輪，并最終找到一對(duì)滿足差分傳播模式的值。

如圖2所示，具體的攻擊過(guò)程為：

步驟1選擇#A處4個(gè)字節(jié)中的前2個(gè)作為活躍字節(jié)，并確定這2個(gè)活躍字節(jié)的差分。

步驟2選擇#B處4個(gè)字節(jié)中的前3個(gè)作為活躍字節(jié)，并將其前2個(gè)活躍字節(jié)的差分設(shè)定為與#A處前2個(gè)字節(jié)差分相同，第3個(gè)字節(jié)的差分暫不確定（圖3中淺灰色的字節(jié)）。

步驟3現(xiàn)在連接此輪輪函數(shù)的輸入輸出差分，并確定滿足這一差分路徑的值，具體如下（如圖3所示）：

圖2　兩輪彈入部分

圖3　輪函數(shù)差分匹配部分

（1）對(duì)#A，#B處的每一個(gè)確定差分的活躍字節(jié)，遍歷其所有28個(gè)值，進(jìn)行S盒與逆向S盒的計(jì)算，然后將這些值和其對(duì)應(yīng)的輸出差分同時(shí)存儲(chǔ)在一個(gè)表中，并以輸出差分進(jìn)行索引。最后共可得到4個(gè)這樣的表。

（2）從狀態(tài)#A1的第1個(gè)字節(jié)開(kāi)始，從#A的第1個(gè)字節(jié)通過(guò)S盒層之后的所有可能的輸出差分中選擇一個(gè)，作為#A1的第1個(gè)字節(jié)的差分。

（3）此時(shí)，在P層的輸入狀態(tài)中，1個(gè)活躍字節(jié)的差分確定，另有2個(gè)非活躍字節(jié)差分也確定（零差分），加上輸出P層的輸出狀態(tài)中有1個(gè)非活躍字節(jié)，這樣，P層的輸入輸出狀態(tài)共有4個(gè)字節(jié)的差分是確定的。用解方程組的方式計(jì)算出另外4個(gè)活躍字節(jié)的差分。

（4）在#A與#A1的第2個(gè)字節(jié)之間謀求差分匹配，同時(shí)在#B與#B1的前兩個(gè)字節(jié)之間謀求差分匹配，全部匹配的概率為2-3，所以可以在選擇#A1第1個(gè)字節(jié)的23個(gè)差分（第（2）步）之后期望找到這3個(gè)字節(jié)差分的全匹配。注意到#A與#A1的第1個(gè)字節(jié)的差分總是可以匹配的，此時(shí)得到了4個(gè)活躍字節(jié)之間的差分匹配，從而可以確定它們所對(duì)應(yīng)的值。由于一個(gè)字節(jié)的差分匹配有兩對(duì)值與其對(duì)應(yīng)，所以共得到24對(duì)滿足差分路徑的值。

（5）從這些值中選擇一個(gè)，在P層建立值之間的連接，這里將使用非活躍字節(jié)值的自由度。利用解方程的方式，由已經(jīng)確定的#B1中兩個(gè)活躍字節(jié)（圖3中深灰色字節(jié)）的值，計(jì)算#A1中兩個(gè)非活躍字節(jié)的值，使P層的輸入輸出值不產(chǎn)生矛盾；同樣，由已經(jīng)確定的#A1中第2個(gè)活躍字節(jié)的值，計(jì)算#B1中唯一一個(gè)非活躍字節(jié)的值，使P層的輸入輸出值不產(chǎn)生矛盾。

（6）最后，利用#A1的整個(gè)狀態(tài)值，計(jì)算#B1中淺灰色字節(jié)的值（其差分在第（3）步已經(jīng)確定），并計(jì)算與其對(duì)應(yīng)的#B中的第3個(gè)字節(jié)的差分和值。注意這里#B處的第3個(gè)字節(jié)是唯一不可預(yù)設(shè)差分的字節(jié)，也就是說(shuō)最后這一字節(jié)的差分是無(wú)法控制的。

（7）取遍#A1第1個(gè)字節(jié)差分的所有27情況，每一種情況都進(jìn)行第（2）步-第（6）步的迭代。注意到在第（4）步中，每選擇#A第1個(gè)字節(jié)處的一個(gè)差分，平均可以得到兩對(duì)滿足差分路徑的值，而取每一個(gè)值都可以得到一個(gè)#B的第3個(gè)字節(jié)的差分和其對(duì)應(yīng)的一對(duì)值，所以最后可以得到#B的第3個(gè)字節(jié)的28個(gè)差分，將此差分與其對(duì)應(yīng)的#A，#B處的值存儲(chǔ)在一個(gè)表中，用此差分作為索引。

步驟4選擇#D處4個(gè)字節(jié)中的前兩個(gè)作為活躍字節(jié)，并將這兩個(gè)活躍字節(jié)的差分設(shè)定為與#A處前兩個(gè)字節(jié)差分相同。

步驟5選擇#C處4個(gè)字節(jié)中的前3個(gè)作為活躍字節(jié)，并將其前兩個(gè)活躍字節(jié)的差分設(shè)定為與#B處前兩個(gè)字節(jié)差分相同，第3個(gè)字節(jié)的差分同樣暫不確定。

步驟6利用與步驟3類似的方法，將這一輪函數(shù)的輸入輸出差分連接起來(lái)，并確定滿足這一差分路徑的值。最后也得到#C的第3個(gè)字節(jié)的82個(gè)差分，同樣將此差分與其對(duì)應(yīng)的#A，#B處的值存儲(chǔ)在一個(gè)表中，用此差分作為索引。

步驟7對(duì)#B處和#C處的第3個(gè)字節(jié)的差分進(jìn)行中間相遇攻擊（前兩個(gè)字節(jié)的差分已經(jīng)設(shè)定為相同）。在步驟3和步驟6，兩處的第3字節(jié)均有82個(gè)差分，所以共有88162 2=2×個(gè)差分對(duì)，兩差分相同的概率為所以期望找到個(gè)單字節(jié)碰撞。

步驟8對(duì)于每一個(gè)碰撞，均有#B和#C處的差分相同，這樣第1彈入輪與第2彈入輪的差分就可以成功連接；而且#A與#D處的差分相同，這樣第2彈入輪右側(cè)異或運(yùn)算的結(jié)果為一個(gè)零差分狀態(tài)。

至此，找到了28對(duì)滿足這兩輪差分路徑的值。

這一部分的復(fù)雜度分析如下：首先步驟1、步驟2的復(fù)雜度可以忽略。在步驟3中，（1）中構(gòu)造4個(gè)表需用去4×28=210次S盒或逆向S盒的計(jì)算，和210字節(jié)的存儲(chǔ)；（2）-（5）中的解方程和查表運(yùn)算的復(fù)雜度均可忽略；在（6）中，需要計(jì)算淺灰色字節(jié)的值與差分，然后存儲(chǔ)，所以進(jìn)行兩次S盒的計(jì)算和一個(gè)字節(jié)存儲(chǔ)；而（7）中進(jìn)行27次（2）中-（6）中的迭代，每次迭代只有（6）中產(chǎn)生時(shí)間復(fù)雜度與存儲(chǔ)消耗，所以共需2×27=28次S盒計(jì)算和27字節(jié)的存儲(chǔ)。至此，步驟3的計(jì)算復(fù)雜度約為4×28=210次S盒或逆向S盒的計(jì)算，存儲(chǔ)約為210字節(jié)。步驟4-步驟6的計(jì)算復(fù)雜度與前3步相同，并且與前3步獨(dú)立計(jì)算，所以共需約2×210=211次S盒計(jì)算和211字節(jié)的存儲(chǔ)。步驟7利用查表進(jìn)行的中間相遇攻擊的復(fù)雜度可以忽略。

綜上所述，兩輪的彈入部分共需約2×210=211次S盒計(jì)算和211字節(jié)的存儲(chǔ)，相當(dāng)于25.4次6輪運(yùn)算和28的全狀態(tài)存儲(chǔ)。

3.3彈出部分

在兩輪彈入部分的前后各加兩輪，得到共涉及6輪的反彈攻擊，即兩彈入輪為第3，4輪，其前面有兩輪逆向彈出部分，后面有兩輪正向彈出部分，這兩部分概率都為1。逆向與正向彈出部分分別如圖4和圖5所示。

圖4　 6輪攻擊的逆向彈出部分

圖5　 6輪攻擊的正向彈出部分

值得注意的是，6輪差分路徑的輸入（2，F(xiàn)）與輸出（3，F(xiàn)）的左半部分的前兩個(gè)字節(jié)的差分是相同的。而在彈入部分共得到28對(duì)滿足差分模式（2，0）→（3，2）→（0，3）的值，所以最后也可以得到28對(duì)滿足6輪差分路徑的值。而進(jìn)行28次彈出部分攻擊的復(fù)雜度為29次4輪計(jì)算，約為28.4次6輪計(jì)算。

3.4攻擊擴(kuò)展到所有參數(shù)

前面所述的反彈攻擊可以看作是對(duì)一個(gè)分組密碼或者一個(gè)雜湊函數(shù)的內(nèi)部置換構(gòu)造了一個(gè)（已知密鑰）區(qū)分器。由彈入與彈出攻擊的過(guò)程可知，彈入部分的復(fù)雜度為2c-2.6，彈出部分的復(fù)雜度為2c+0.4，所以總體的復(fù)雜度約等于2c+0.4，得到了2c對(duì)滿足輸入差分模式為（r/2，F(xiàn)），輸出差分模式為（（r/2）+1，F(xiàn)）的值，其中輸入差分模式的左半部分有r/2個(gè)差分為零的字節(jié)，另外r/2個(gè)差分為預(yù)設(shè)值的字節(jié)，輸出差分模式的左半部分有r/2-1個(gè)差分為零的字節(jié)，另外r/2個(gè)差分為預(yù)設(shè)值的字節(jié)，所以只有一個(gè)字節(jié)的差分是不確定的。按照生日攻擊的復(fù)雜度，得到2c對(duì)滿足此輸入輸出差分的值需要2（n-c）/2×2c的復(fù)雜度。所以，攻擊有效需要滿足條件2c+0.4<2（n-c）/2×2c，即c

3.5兩種壓縮函數(shù)模式的近似碰撞攻擊

當(dāng)某些壓縮函數(shù)的內(nèi)部置換采用Feistel-SPS結(jié)構(gòu)，其反饋采用MMO或MP模式的時(shí)候，這一攻擊還可以用來(lái)構(gòu)造近似碰撞。注意到，區(qū)分器的輸入差分模式（r/2，F(xiàn)）和輸出差分模式（（r/2）+1，F(xiàn)）中，左半部分有（/2）r-byte的差分是對(duì)應(yīng)相同的，這樣經(jīng)過(guò)輸入與輸出的異或運(yùn)算，可以將（/2）r-by te的差分消去，最后得到的壓縮函數(shù)的輸出具有差分模式（1，F(xiàn)），即得到了（）n c--bit的近似碰撞。而上節(jié)共得到了2c對(duì)滿足6輪差分路徑的值，則最后可以得到2c個(gè)近似碰撞，依概率可以期望得到n-bit的近似碰撞，即半個(gè)狀態(tài)的碰撞。

4　 Feistel-SPS結(jié)構(gòu)的7輪反彈攻擊

4.1攻擊概述

本節(jié)以8r=，8c=的Feistel-SPS結(jié)構(gòu)為例，利用反彈攻擊構(gòu)造一條7輪的截?cái)嗖罘致窂?。在整個(gè)7輪的反彈攻擊中，彈入部分有3輪，在這3輪彈入部分的基礎(chǔ)之上，前面加上兩個(gè)逆向彈出輪，后面加上兩個(gè)正向彈出輪，構(gòu)成整個(gè)7輪差分路徑。7輪截?cái)嗖罘帜Ｊ娇梢员硎緸?/p>

在這里，X是某一中間確定的全活躍字差分，M是某一提前給定的全活躍字差分。

根據(jù)這一路徑的性質(zhì)：將輸入差分與輸出差分異或，所得狀態(tài)的左半部分為提前給定的全活躍字差分M。以7輪的Feistel-SPS結(jié)構(gòu)作為內(nèi)部置換，外部以MMO或MP模式作為反饋結(jié)構(gòu)構(gòu)造壓縮函數(shù)，其輸出的一半為某一提前設(shè)定的全活躍字差分。

4.2 3輪彈入部分

3輪彈入部分的截?cái)嗖罘致窂綖?/p>

如圖6所示，攻擊的詳細(xì)過(guò)程為：

步驟1對(duì)輪函數(shù)中第2個(gè)S盒層的所有S盒建立“差分分布表”。

步驟2設(shè)定#B處的差分為提前給定的差分M。

圖6　 7輪攻擊的彈入部分

步驟3在#A處選擇1個(gè)字節(jié)作為活躍字節(jié)（不妨選擇第1個(gè)字節(jié)），則#A處的差分模式為1。隨機(jī)選擇#A處活躍字節(jié)的差分值得Δ#A，計(jì)算，然后通過(guò)查表在圖6中“匹配1”處檢查P（Δ#A）和Δ#B是否能在這里的S盒層建立匹配。由于每個(gè)字節(jié)差分匹配的概率為1/2，所以期望選擇28個(gè)#A處活躍字節(jié)的差分值可以在“匹配1”處找到一個(gè)匹配。而由于每一個(gè)匹配的字節(jié)都有兩對(duì)值滿足匹配的輸入輸出差分，所以這里共有28對(duì)值滿足#A處到#B處的差分特征。

步驟4從這28對(duì)值中選擇一個(gè)，由處計(jì)算逆向S盒，再異或子密鑰k4，得第2彈入輪左半部分狀態(tài)的差分和值，這樣就確定了處和處的差分，而其值暫時(shí)不確定。

（1）注意到#G是全活躍的，對(duì)于#G的每一個(gè)字節(jié)，遍歷其全部的28個(gè)值，對(duì)每個(gè)值計(jì)算至#H處，檢查其對(duì)應(yīng)的差分是否與#H處對(duì)應(yīng)字節(jié)的差分相等，若相等存儲(chǔ)其對(duì)應(yīng)的#G處和#H處的值。

（2）對(duì)于#H處每一個(gè)字節(jié)存儲(chǔ)值的每一個(gè)組合，計(jì)算#E處值，并計(jì)算其通過(guò)S盒層之后所對(duì)應(yīng)的差分是否等于前面已確定的#F處第1個(gè)字節(jié)的差分，如果相等則成功地在“匹配2”處建立了差分匹配。利用同樣的方法建立#C的活躍字節(jié)與#D的活躍字節(jié)的差分匹配。

圖7　字節(jié)級(jí)差分匹配部分

（3）如果不能同時(shí)找到#C與#D處、#E與#F處活躍字節(jié)的差分匹配，則需要從#C與#E處的27種差分中再選擇，進(jìn)行（1）-（2）步中的計(jì)算，直到找到#C與#D處、#E與#F處活躍字節(jié)的差分匹配為止。

步驟6記錄下匹配上的差分所對(duì)應(yīng)的值，計(jì)算出所對(duì)應(yīng)的整個(gè)彈入部分輸入與輸出的值。

這樣就找到了一對(duì)滿足彈入部分3輪差分特征的值，這一部分的復(fù)雜度分析如下：在步驟1建立差分分布表共需28×28×8=219次S盒計(jì)算。步驟2-步驟3查表的復(fù)雜度可忽略不計(jì)。步驟4需要1次逆向S盒的計(jì)算。在步驟5的（1）中，每個(gè)字節(jié)的差分匹配上的概率為2-8，即需要28的復(fù)雜度建立一個(gè)匹配，所以每個(gè)字節(jié)的28對(duì)值可以期望找到1個(gè)匹配，這1個(gè)匹配的值可以有兩種配對(duì)情況，故8個(gè)字節(jié)共有28對(duì)值滿足#G到#H處的差分，得到這28對(duì)值共需28×2×8=212次S盒計(jì)算；在步驟5的（2）中，在#C和#D處、#E和#F處建立差分匹配需要216的復(fù)雜度，這需要將步驟5的（1）中迭代216-8=28次，每次迭代在步驟5的（1）中需212次S盒計(jì)算，故共需212+8=220次S盒計(jì)算，與此相比，步驟5的（2）中計(jì)算量可忽略不計(jì)。所以彈入部分共需要219+1+220≈220次S盒計(jì)算，相當(dāng)于220-4/7≈213.2次7輪Feistel-SPS函數(shù)計(jì)算，而存儲(chǔ)基本上等于保存“差分分布表”所需的空間，即28×2/2=215的全狀態(tài)存儲(chǔ)。

4.3彈出部分

在3輪彈入部分的前面和后面各加上兩輪，可以得到共有4輪組成的彈出部分，這一部分的概率為1，其細(xì)節(jié)如圖8和圖9所示。其原理與3.3節(jié)的6輪反彈攻擊類似，只是這一次只有一對(duì)值參與彈出運(yùn)算，最后得到一對(duì)滿足整個(gè)7輪差分路徑的值。這對(duì)值在明文部分的差分為（X，F(xiàn)），在密文部分的差分為，這里M是一個(gè)提前預(yù)設(shè)好的8個(gè)字節(jié)全活躍差分。

圖8　 7輪攻擊的逆向彈出部分

圖9　 7輪攻擊的正向彈出部分

4.4 7輪區(qū)分器

4.3節(jié)利用反彈構(gòu)造一條7輪的差分路徑，并找到了滿足這一路徑的一對(duì)值。由彈入與彈出攻擊的過(guò)程可知，當(dāng)r≠c+1時(shí)，彈入部分的復(fù)雜度約為2max（3c-r，2c-1）-2.8，彈出部分的復(fù)雜度為1，所以總體的復(fù)雜度約等于2max（3c-r，2c-1）-2.8；當(dāng)r=c+1時(shí)，彈入部分的復(fù)雜度約為24c-4.8，彈出部分的復(fù)雜度為1，所以總體的復(fù)雜度約等于24c-4.8。最后得到一對(duì)滿足輸入差分模式為（X，F(xiàn)），輸出差分模式為（X⊕M，F(xiàn)）的值。輸入差分與輸出差分的異或?yàn)槟骋粋€(gè)提前預(yù)設(shè)的全活躍差分M，按照生日攻擊的復(fù)雜度，得到一對(duì)滿足此輸入輸出差分的值需要2rc/2的復(fù)雜度。所以，攻擊有效需要滿足條件

常見(jiàn)參數(shù)的Feistel-SPS設(shè)計(jì)除4r=，8c=之外都滿足這一條件。

當(dāng)某些壓縮函數(shù)的內(nèi)部置換采用Feistel-SPS結(jié)構(gòu)，其反饋采用MMO或MP模式的時(shí)候，這一攻擊可以作為碰撞攻擊或者近似碰撞攻擊的一部分。前面構(gòu)造的7輪區(qū)分器的輸入差分模式為（X，F(xiàn)），輸出差分模式為（X⊕M，F(xiàn)），它們異或之后的差分模式為（M，F(xiàn)），即左半部分是一個(gè)預(yù)設(shè)的全活躍差分。

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

本文給出了針對(duì)Feistel-SPS結(jié)構(gòu)的反彈攻擊，這一攻擊根據(jù)一個(gè)6輪的截?cái)嗖罘謪^(qū)分器得到了其壓縮函數(shù)模式的6輪近似碰撞攻擊。將這一結(jié)果擴(kuò)展，得到了此結(jié)構(gòu)的7輪截?cái)嗖罘謪^(qū)分器，并進(jìn)一步得到了其壓縮函數(shù)的7輪截?cái)嗖罘謪^(qū)分器。這是Feistel-SPS結(jié)構(gòu)的首個(gè)反彈攻擊結(jié)果，它顯示了在此攻擊下這一結(jié)構(gòu)既不比Feistel-SP結(jié)構(gòu)強(qiáng)，也不比Feistel-SPSP結(jié)構(gòu)弱的特性。表1給出本文結(jié)果與類似結(jié)構(gòu)結(jié)果的比較，為密碼算法設(shè)計(jì)者提供了素材，使其可以在更深層地理解這些結(jié)構(gòu)的基礎(chǔ)上做出選擇。

［1］U.S.Departm ent of Comm erce and National Institute of Standards and Technology.FIPS PUB 46-3［S］.1999.

［2］WU Wenling and ZHANG Lei.LBlock:a lightweight b lock cipher［C］.9th International Conference on Applied Cryptography and Network Security-ACNS 2011，Nerja，Spain，2011:327-344.doi:10.1007/978-3-642-21554-4_19.

［3］BOGDANOV A and SHIBUTANI K.Double SP-functions: enhanced generalized Feistel networks［C］.16th Australasian Conference on Information Security and Privacy-ACISP 2011，Melbourne，Australia，2011:106-119.doi:10.1007/978-3-642-22497-3_8.

［4］SH IBUTAN IK，ISOBE T，H IWATAR IH，et al.Piccolo:an ultra-lightweight blockcipher［C］.13th International W orkshop on Cryptographic Hardware and Em bedded System s-CHES 2011，Nara，Japan，2011:342-357.doi: 10.1007/978-3-642-23951-9_23.

［5］KNUDSEN L R and RIJMEN V.Known-key distinguishers for some block ciphers［C］.13th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2007，Kuching，Malaysia，2007: 315-324.doi:10.1007/978-3-540-76900-2_19.

［6］BLONDEAU C，PEYRIN T，and WANG L.Known-key distinguisher on full PRESENT［C］.35th Annual Cryptology Conference on Advances in Cryp tology-CRYPTO 2015，Santa Barbara，USA，2015:455-474.doi:10.1007/978-3-662-47989-6_22.

［7］ANDREEVA E，BOGDANOV A，and MENNINK B. Towards understanding the known-key security of block ciphers［C］.20th International Workshop on Fast Software Encryption-FSE 2013，Singapore，2013:348-366.doi:10.1007 /978-3-662-43933-3_18.

［8］ZHA Daren，WU Shuang，and WANG Qiongxiao.Im proved known-key distinguisher on round-reduced 3D block cipher［J］. Chinese Journal of Electronics，2015，24（1）:199-204.doi: 10.1049/cje.2015.01.033.

［9］AOK I K.A property for full CLEFIA-128 detected by a m idd letext distinguisher under the known-key setting［J］. IEICE Transactions on Fundam entals of Electron ics，Communications and Computer Sciences，2014，97（1）: 292-297.doi:10.1587/transfun.E97.A.292.

［10］SASAKI Y and YASUDA K.Known-key distinguishers on 11-round Feistel and collision attackson itshashingmodes［C］. 18th International Workshop on Fast Software Encryption-FSE 2011，Lyngby，Denmark，2011:397-415.doi:10.1007/ 978-3-642-21702-9_23.

［11］HYUNGCHUL K，DEUKJO H，DUKJAE M，et al. Known-key attacks on generalized Feistel schemes w ith SP round function［J］.IEICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2012，95（9）:1550-1560.doi:10.1587/transfun.E 95.A.1550.

［12］DONG Le，WU W en ling，WU Shuang，et al.Known-key distinguishers on type-1 Feistel schem e and near-collision attacks on its hashing modes［J］.Frontiers of Computer Science，2014，8（3）:513-525.doi:10.1007/s11704-014-2412-7.

［13］DONG Le，WANG Yanling，WU Wenling，et al.Known-key distinguishers on 15-round 4-branch type-2 generalised Feistel networks w ith single substitution-permutation functions and near-collision attacks on its hashing modes［J］. IET Information Security，2015，9（5）:277-283.doi:10.1049/ iet-ifs.2014.0402.

［14］SASAKI Y.Double-sp is weaker than single-sp:rebound attacks on Feistel ciphers w ith several rounds［C］.13th International Conference on Progress in Cryptology-INDOCRYPT 2012，Kolkata，India，2012:265-282.doi: 10.1007/978-3-642-34931-7_16.

［15］MENDEL F，RECHBERGER C，SCHL?FFER M，etal.The rebound attack:cryptanalysis of reduced W hirlpool and Gr?stl［C］.16th International Workshop on Fast Software Encryption-FSE 2009，Leuven，Belgium，2009:260-276.doi: 10.1007/978-3-642-03317-9_16.

［16］SASAKIY，LIY，WANG L，etal.Non-full-active Super-Sbox analysis:applications to ECHO and Gr?stl［C］.16th International Conference on Advances in Cryptology-ASIACRYPT 2010，Singapore，2010:38-55.doi:10.1007/ 978-3-642-17373-8_3.

董樂(lè)：男，1980年生，博士，副教授，研究方向?yàn)榉纸M密碼與雜湊函數(shù)的分析等.

鄒劍：男，1985年生，博士，講師，研究方向?yàn)殡s湊函數(shù)的設(shè)計(jì)與分析等.

吳文玲：女，1966年生，博士，研究員，博士生導(dǎo)師，研究方向?yàn)榉纸M密碼的設(shè)計(jì)與分析、雜湊函數(shù)的研究與應(yīng)用等.

Rebound Attack on the Feistel-SPS Structure

DONG Le①②ZOU Jian③WUWenling④DU Jiao①②①（Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control，Henan Normal University，Xinxiang 453007，China）
②（Mathematics and Scientific Computing Key-Disciplines Laboratory，Henan NormalUniversity，Xinxiang 453007，China）③（College ofM athematics and Computer Science，F(xiàn)uzhou University，F(xiàn)uzhou 350116，China）
④（Trust Computing and Information Assurance Laboratory，Institute ofSoftware，Chinese Academy ofSciences，Beijing 100190，China）

This paper shows the rebound attack on the Feistel-SPS structure，which has the Feistel network with a Substitu tion-Perm utation-Substitu tion（SPS）round function.A 6-round known-key truncated differential distinguisher is obtained by studying the d iffusion properties of differences.Based on the distinguisher，a nearcollision attack on the com pression functions of this structure embedding the Matyas-M eyer-Oseas（MMO）and M iyaguchi-Preneel（MP）modes is given.Besides，the 6-round distinguisher is extended and a 7-round truncated differential path is constructed to get a 7-round truncated differential distinguisher of the com pression function for the twomodesmentioned before.

Rebound attack；Feistel structure；Substitution-Permutation-Substitution（SPS）function；Truncated differential d istinguisher；Near-collision

1　引言

在眾多現(xiàn)有的攻擊技術(shù)面前，設(shè)計(jì)新的安全的對(duì)稱密碼算法并非易事，所以許多設(shè)計(jì)者更傾向于用一些已被理論證明或者已被時(shí)間證明的組件去“組裝”一個(gè)新的密碼算法。常見(jiàn)的組件有“算法結(jié)構(gòu)”和“輪函數(shù)結(jié)構(gòu)”。包括分組密碼算法DES［1］和LBlock［2］在內(nèi)的許多算法都采用了（廣義）Feistel結(jié)構(gòu)；而大量輪函數(shù)采用了SP（Substitution-Permutation）結(jié)構(gòu)。2011年，文獻(xiàn)［3］提出了采用“雙SP函數(shù)”作為輪函數(shù)的構(gòu)想。然而，也有一些密碼算法采用所謂的SPS（Substitution-Permutation-Substitution）函數(shù)作為輪函數(shù)，例如輕量級(jí)分組密碼算法Piccolo［4］，而針對(duì)這種SPS結(jié)構(gòu)進(jìn)行的分析相對(duì)缺乏。另一方面，文獻(xiàn)［5］提出已知密鑰區(qū)分器的概念來(lái)刻畫(huà)密碼算法或密碼結(jié)構(gòu)的非偽隨機(jī)性，此后出現(xiàn)了許多針對(duì)不同算法或結(jié)構(gòu)的已知密鑰區(qū)分器［69］-。

s:National Natu ral Science Foundation of China（61402154，U 1404601，11471104，11171093），Program for Innovative Research Team（in Science and Technology）in University of Henan Province（14IRTSTHN 023）

表1　 3種結(jié)構(gòu)的攻擊結(jié)果比較

TN918.4

A

1009-5896（2016）08-1928-07

10.11999/JEIT 151255

2015-11-09；改回日期：2016-04-08；網(wǎng)絡(luò)出版：2016-06-24

董樂(lè)dongle127@163.com

國(guó)家自然科學(xué)基金（61402154，U 1404601，11471104，11171093），河南省高校科技創(chuàng)新團(tuán)隊(duì)支持計(jì)劃（14IRTSTHN023）