Feistel-SPS結構的反彈攻擊

董　樂　鄒　劍　吳文玲　杜　蛟（河南師范大學大數據統計分析與優化控制河南省工程實驗室新鄉453007）（河南師范大學數學與科學計算重點學科開放實驗室新鄉453007）（福州大學數學與計算機科學學院福州350116）（中國科學院軟件研究所可信計算與信息保障實驗室北京100190）

?

Feistel-SPS結構的反彈攻擊

董樂*①②鄒劍③吳文玲④杜蛟①②①
①（河南師范大學大數據統計分析與優化控制河南省工程實驗室新鄉453007）
②（河南師范大學數學與科學計算重點學科開放實驗室新鄉453007）
③（福州大學數學與計算機科學學院福州350116）
④（中國科學院軟件研究所可信計算與信息保障實驗室北京100190）

該文給出了以Feistel結構為主框架，以SPS（Substitu tion-Perm utation-Substitution）函數作為輪函數的Feistel-SPS結構的反彈攻擊。通過對差分擴散性質的研究，得到這一結構的6輪已知密鑰截斷差分區分器，并在此區分器的基礎上，給出將這一結構內嵌入MMO（M atyas-Meyer-Oseas）和MP（M iyaguchi-Preneel）模式所得到的壓縮函數的近似碰撞攻擊。此外，還將6輪截斷差分區分器擴展，得到了7輪的截斷差分路徑，基于此還得到上述兩種模式下壓縮函數的7輪截斷差分區分器。

反彈攻擊；Feistel結構；SPS（Substitution-Permutation-Substitution）函數；截斷差分區分器；近似碰撞

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

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

本文第2節介紹了相關的背景知識；第3節對6輪Feistel-SPS結構進行反彈攻擊；第4節對7輪Feistel-SPS結構進行反彈攻擊；第5節總結全文。

2　基本知識

2.1 Feistel-SPS結構

首先給出一些符號記法：N為密碼算法的分組長度；n為Feistel結構中左半部分或右半部分比特數，即n=N/2；c為S盒所包含的比特數；r為輪函數中一個S盒層所含S盒的個數。

Feistel-SPS結構如圖1所示，它采用了經典的Feistel網絡作為它的結構，而輪函數采用了SPS結構。

圖1　 Feistel-SPS結構的一輪

假定文中所攻擊的Feistel-SPS結構，除子密鑰之外每一輪都是相同的，并且S盒層和P層具有“好”的密碼學特性，即輪函數中兩個S盒層的每一個S盒具有最優的抵抗差分分析與線性分析的密碼學特性。對于差分分析來說，它們均有最優的差分擴散性，即任一S盒的每一個輸入差分都有2c-1個可能的輸出差分與其對應，這樣任意一對輸入輸出差分可以在這一S盒層達到匹配的概率就是1/2，而一旦達成匹配，有兩對輸入輸出值與其對應；此外，輪函數中P層的分支數達到最大，即r+1。

2.2反彈攻擊

2009年，文獻［15］提出一種針對AES類雜湊函數的攻擊方法，這一攻擊方法的攻擊過程分為彈入部分和彈出部分，所以命名為“反彈攻擊”。反彈攻擊的最終目的是以比窮舉攻擊更低的復雜度找到滿足某一預設截斷差分特征的一對值，從而得到區分器或者得到一對（近似）碰撞。

由于AES類雜湊函數的輪函數中，S盒往往具有最優差分擴散特點，而線性擴散層則具有最大的分支數，所以對差分分析有很強的抵抗能力。但如果確定輸入輸出差分，也能夠在這樣的S盒處以最大（1/2）的概率實現差分匹配。正是利用這一點，反彈攻擊在彈入部分可以有效地得到許多滿足這一部分截斷差分特征的值。利用這些值，攻擊者可以以一定的概率實施彈出攻擊，從而得到滿足整個截斷差分路徑的值。本文的7輪攻擊采用了傳統的彈入攻擊模式，而6輪攻擊則采用了非全活躍差分匹配［16］的方法進行彈入攻擊，都取得了預期的效果。

2.3MMO模式與MP模式

設EK是一個密鑰為K的分組密碼算法，M為消息塊，H為中間鏈值，MMO模式的壓縮函數計算過程為

MP模式的壓縮函數計算過程為

本文基于6輪已知密鑰截斷差分區分器，構造了內嵌Feistel-SPS結構（即分組密碼KE具有這一結構）的MMO模式和MP模式的近似碰撞。

3　 Feistel-SPS結構的6輪反彈攻擊

本節以4r=，8c=的Feistel-SPS結構為例，對其進行6輪（含有12個S盒層）的反彈攻擊。

3.1攻擊概述

首先，給出攻擊中所使用的幾個符號：

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

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

最后得到了82對滿足整個6輪差分路徑的值，以這些值構造內部置換采用Feistel-SPS結構，反饋采用MMO或MP模式的壓縮函數的近似碰撞。

3.2兩輪彈入部分

這一部分將構建截斷差分特征相“對稱”的兩個彈入輪，并最終找到一對滿足差分傳播模式的值。

如圖2所示，具體的攻擊過程為：

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

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

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

圖2　兩輪彈入部分

圖3　輪函數差分匹配部分

（1）對#A，#B處的每一個確定差分的活躍字節，遍歷其所有28個值，進行S盒與逆向S盒的計算，然后將這些值和其對應的輸出差分同時存儲在一個表中，并以輸出差分進行索引。最后共可得到4個這樣的表。

（2）從狀態#A1的第1個字節開始，從#A的第1個字節通過S盒層之后的所有可能的輸出差分中選擇一個，作為#A1的第1個字節的差分。

（3）此時，在P層的輸入狀態中，1個活躍字節的差分確定，另有2個非活躍字節差分也確定（零差分），加上輸出P層的輸出狀態中有1個非活躍字節，這樣，P層的輸入輸出狀態共有4個字節的差分是確定的。用解方程組的方式計算出另外4個活躍字節的差分。

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

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

（6）最后，利用#A1的整個狀態值，計算#B1中淺灰色字節的值（其差分在第（3）步已經確定），并計算與其對應的#B中的第3個字節的差分和值。注意這里#B處的第3個字節是唯一不可預設差分的字節，也就是說最后這一字節的差分是無法控制的。

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

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

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

步驟6利用與步驟3類似的方法，將這一輪函數的輸入輸出差分連接起來，并確定滿足這一差分路徑的值。最后也得到#C的第3個字節的82個差分，同樣將此差分與其對應的#A，#B處的值存儲在一個表中，用此差分作為索引。

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

步驟8對于每一個碰撞，均有#B和#C處的差分相同，這樣第1彈入輪與第2彈入輪的差分就可以成功連接；而且#A與#D處的差分相同，這樣第2彈入輪右側異或運算的結果為一個零差分狀態。

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

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

綜上所述，兩輪的彈入部分共需約2×210=211次S盒計算和211字節的存儲，相當于25.4次6輪運算和28的全狀態存儲。

3.3彈出部分

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

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

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

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

3.4攻擊擴展到所有參數

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

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

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

4　 Feistel-SPS結構的7輪反彈攻擊

4.1攻擊概述

本節以8r=，8c=的Feistel-SPS結構為例，利用反彈攻擊構造一條7輪的截斷差分路徑。在整個7輪的反彈攻擊中，彈入部分有3輪，在這3輪彈入部分的基礎之上，前面加上兩個逆向彈出輪，后面加上兩個正向彈出輪，構成整個7輪差分路徑。7輪截斷差分模式可以表示為

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

根據這一路徑的性質：將輸入差分與輸出差分異或，所得狀態的左半部分為提前給定的全活躍字差分M。以7輪的Feistel-SPS結構作為內部置換，外部以MMO或MP模式作為反饋結構構造壓縮函數，其輸出的一半為某一提前設定的全活躍字差分。

4.2 3輪彈入部分

3輪彈入部分的截斷差分路徑為

如圖6所示，攻擊的詳細過程為：

步驟1對輪函數中第2個S盒層的所有S盒建立“差分分布表”。

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

圖6　 7輪攻擊的彈入部分

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

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

（1）注意到#G是全活躍的，對于#G的每一個字節，遍歷其全部的28個值，對每個值計算至#H處，檢查其對應的差分是否與#H處對應字節的差分相等，若相等存儲其對應的#G處和#H處的值。

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

圖7　字節級差分匹配部分

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

步驟6記錄下匹配上的差分所對應的值，計算出所對應的整個彈入部分輸入與輸出的值。

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

4.3彈出部分

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

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

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

4.4 7輪區分器

4.3節利用反彈構造一條7輪的差分路徑，并找到了滿足這一路徑的一對值。由彈入與彈出攻擊的過程可知，當r≠c+1時，彈入部分的復雜度約為2max（3c-r，2c-1）-2.8，彈出部分的復雜度為1，所以總體的復雜度約等于2max（3c-r，2c-1）-2.8；當r=c+1時，彈入部分的復雜度約為24c-4.8，彈出部分的復雜度為1，所以總體的復雜度約等于24c-4.8。最后得到一對滿足輸入差分模式為（X，F），輸出差分模式為（X⊕M，F）的值。輸入差分與輸出差分的異或為某一個提前預設的全活躍差分M，按照生日攻擊的復雜度，得到一對滿足此輸入輸出差分的值需要2rc/2的復雜度。所以，攻擊有效需要滿足條件

常見參數的Feistel-SPS設計除4r=，8c=之外都滿足這一條件。

當某些壓縮函數的內部置換采用Feistel-SPS結構，其反饋采用MMO或MP模式的時候，這一攻擊可以作為碰撞攻擊或者近似碰撞攻擊的一部分。前面構造的7輪區分器的輸入差分模式為（X，F），輸出差分模式為（X⊕M，F），它們異或之后的差分模式為（M，F），即左半部分是一個預設的全活躍差分。

5　結束語

本文給出了針對Feistel-SPS結構的反彈攻擊，這一攻擊根據一個6輪的截斷差分區分器得到了其壓縮函數模式的6輪近似碰撞攻擊。將這一結果擴展，得到了此結構的7輪截斷差分區分器，并進一步得到了其壓縮函數的7輪截斷差分區分器。這是Feistel-SPS結構的首個反彈攻擊結果，它顯示了在此攻擊下這一結構既不比Feistel-SP結構強，也不比Feistel-SPSP結構弱的特性。表1給出本文結果與類似結構結果的比較，為密碼算法設計者提供了素材，使其可以在更深層地理解這些結構的基礎上做出選擇。

［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.

董樂：男，1980年生，博士，副教授，研究方向為分組密碼與雜湊函數的分析等.

鄒劍：男，1985年生，博士，講師，研究方向為雜湊函數的設計與分析等.

吳文玲：女，1966年生，博士，研究員，博士生導師，研究方向為分組密碼的設計與分析、雜湊函數的研究與應用等.

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，Fuzhou University，Fuzhou 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　引言

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

TN918.4

A

1009-5896（2016）08-1928-07

10.11999/JEIT 151255

2015-11-09；改回日期：2016-04-08；網絡出版：2016-06-24

董樂dongle127@163.com

國家自然科學基金（61402154，U 1404601，11471104，11171093），河南省高?？萍紕撔聢F隊支持計劃（14IRTSTHN023）