一類廣義Feistel結構的安全性分析

徐林杰 王春紅 彭 聰 劉麗輝

(中國船舶重工集團公司第七二二研究所 武漢 430079)

一類廣義Feistel結構的安全性分析

徐林杰 王春紅 彭 聰 劉麗輝

(中國船舶重工集團公司第七二二研究所 武漢 430079)

廣義Feistel結構(以下簡稱GFS)的形式多種多樣,廣泛應用于分組密碼設計。論文定義了一類GFS為GFSRP,研究了整體結構為GFSRP-SP結構(GFSRP的F函數是SP型結構)的分組密碼的性質。考慮到實際應用,論文給出一個4子塊的GFSRP-SP結構的實例,并通過建立搜索算法,得到了更精確的活動S盒個數的下界。結果表明,4子塊的GFSRP-SP結構具有較好的抵抗差分攻擊與線性攻擊的能力,可應用于分組密碼設計。

分組密碼; 廣義Feistel結構; 活動S盒

Class Number TP393

1 引言

整體結構作為分組密碼的重要特征,對分組密碼的實現效率與安全性都有非常大的影響。國內外公開的分組密碼最為常見的整體結構是SPN結構和Feistel結構。廣義Feistel結構(以下簡稱GFS)是Feistel結構的一種推廣,同樣具有Feistel結構加解密相似的特點。Feistel結構將輸入分組分為2個子塊,而GFS將輸入分組分為k(k>2)個子塊。這樣做,一方面使得F函數的規模小,更好設計;另一方面使得軟硬件實現代價更低。廣義Feistel結構的形式多種多樣,如Ⅰ-型[1]GFS、Ⅱ-型[1]GFS、Nyberg-型[2]GFS等。整體結構采用GFS的分組密碼設計,較為常見的是將輸入分組分為四個子塊,如SMS4[3]、CAST-256[4]、CLEFIA[5]等。

對整體結構的安全性研究,一直是密碼學領域的研究熱點。設計安全的分組密碼,一定要評估該密碼抵抗差分攻擊與線性攻擊的能力,目前常用的評估方法是估計活動S盒個數的下界[5]。對SPN結構和Feistel結構,通常采用理論證明的方法[6～7],而對于GFS,由于其形式多種多樣,分析方法也不盡相同。文獻[8]利用理論證明的方法研究了SMS4算法結構的活動S盒個數的下界,文獻[5]采用建立搜索算法的方式研究了CLEFIA算法的活動S盒個數的下界,同樣的方法,文獻[9]對文獻[5]的方法加以改進,研究了Ⅰ-型、Ⅱ-型和Nyberg-型GFS活動S盒的個數的下界。

對于以上提到的GFS,這些結構的特點,都是一個或者若干個子塊進入F函數,然后再進入擴散層。擴散層都是基于子塊位置的置亂,可以看作一個置換。值得思考的是,擴散層是否一定是這種基于子塊位置的置亂?能否將子塊拆分成更小的單元,再將這些更小的單元位置置亂?如果這樣做,對這種結構抵抗差分攻擊與線性攻擊的能力應該怎樣評估?本文對這幾個問題進行了研究。

2 基礎知識

為方便描述,本文先引入文獻[10]的定義。k為偶數,k子塊的GFSπ是({0,1}n)k上的置換,定義如下:

定義1[10]:(X0,X1,…,Xk-1)→π(X0,F0(X0)⊕X1,X2,F1(X2)⊕X3,…,F(k-2)/2(Xk-2)⊕Xk-1)

其中,Fi:{0,1}n→{0,1}n是F函數,π:({0,1}n)k→({0,1}n)k是一個子塊位置置亂、可看作是一個置換,k是子塊的個數,n是一個子塊的比特長度,則稱具有這樣結構的置換為GFSπ。GFSπ如圖1所示。

對于GFSπ,π置換的選取不同,對應的結構就不同。目前分組密碼設計中較為常用的是4子塊的GFS(即k=4)。于是,令k=4,當π(Y0,Y1,Y2,Y3)=(Y1,Y2,Y3,Y0),即為4子塊的Ⅱ-型GFS,結構如圖2所示;當π(Y0,Y1,Y2,Y3)=(Y1,Y3,Y0,Y2),即為4子塊的Nyberg-型GFS,結構如圖3所示。Ⅰ-型GFS不是GFSπ置換,但與Ⅰ-型GFS與Ⅱ-型GFS的結構類似,如圖4所示。這兩種結構,相同的是π置換一致,都是循環左移一個子塊;不同的是,單輪Ⅱ-型GFS有k/2個F函數,而單輪Ⅰ-型GFS只有1個F函數。

定義2:(X0,X1,…,Xk-1)→RP(X0,F0(X0)⊕X1,X2,F1(X2)⊕X3,…,F(k-2)/2(Xk-2)⊕Xk-1)。

其中,Fi:{0,1}→{0,1}n是F函數,RP:({0,1}n/2)2×k→({0,1}n/2)k×2是一個置換。則稱具有這樣結構的置換為GFSRP。

文獻[10]指出,為了達到最優擴散效果,GFSπ的π置換應具有這樣的特點:任意一個奇數的輸入子塊都應映射為偶數的輸出子塊。同樣,為了使GFSRP具有較好的擴散效果,本文對RP置換做出相同要求,即RP置換的奇數的輸入子塊Y2i+1都應映射為偶數的輸出子塊Z2j,可表示為:RP(Y0,Y1,Y2,…,Yk-1)=(Z0,Z1,Z2,…,Zk-1),Z2j∈{Y1,Y3,…,Yk-2},0≤j≤k/2-1。與GFSπ一致的是,GFSRP也將每個分組分為k個子塊;不同的是,GFSπ的π置換使k個子塊的位置置亂,而GFSRP的RP置換將每個子塊平均分為兩個更小的單元,然后這2k個單元位置置亂。圖5即為4子塊的GFSRP的結構示意圖。選用文獻[11]中的置換作為RP置換,如圖6所示。

差分攻擊與線性攻擊是分組算法最常用且很有效的攻擊方法。為評估一個分組密碼抵抗的這兩種攻擊的能力,通常采用估計這個分組密碼差分特征(線性逼近)中活動S盒的個數的下界的方法。而活動S盒的個數與差分分支數與線性分支數密切相關。

定義3:一個差分特征中,如果S盒的輸入差分不為零,則稱此S盒是差分活動的;一個線性逼近中,如果一些輸入和輸出比特被涉及,則稱此S盒是線性活動的。

為P的分支數。其中wb(x)表示非零xi(1≤i≤m)的個數,稱為x的包重量。

類似地定義差分分支數與線性分支數的定義:

其中c(x·αt,P(x)·βt)=2×Pr(x·αt,P(x)·βt)-1,x·αt是矩陣乘。c(x·αt,P(x)·βt)≠0意味著α·x=β·y是有效線性逼近。上標t表示向量或矩陣的轉置。

P的差分分支數與線性分支數的最大值為m+1。當變換P的差分分支數與線性分支數的均達到最大,則稱P為最優擴散映射,其對應的矩陣M是m階MDS矩陣。

3 GFSRP-SP結構的安全性分析

3.1 GFSRP-SP結構的性質

當R輪GFSRP-SP至少存在一個非零輸入差分,顯然有如下性質。

性質1:任意連續2輪k子塊的GFSRP-SP結構,至少有1個F函數有差分活動S盒。

這個性質是由于GFSRP-SP結構的可逆性。如果連續2輪加密的k個F函數均沒有活動S盒,即沒有非零的輸入差分,則意味著這兩輪加密之前的兩輪的k個F函數均沒有非零輸入差分。同樣的,這兩輪加密之后的k個F函數也沒有非零輸入差分,以此類推目標結構不存在非零的輸入差分,這與R輪GFSRP-SP結構至少存在一個非零輸入差的前提條件相矛盾。

而由GFSRP-SP結構的定義,結合差分分支數的定義不難有如下性質。

性質2:任意連續3輪GFSRP-SP結構加密,其差分活動S盒個數有如下特點。

性質1考慮了連續兩輪輸入差分的關系,性質2考慮了連續三輪輸入差分的關系。顯然任意R(R≥3)輪GFSRP-SP結構迭代都要滿足這兩個性質。

3.2 搜索算法

對于一個分組密碼,一般有兩種方式統計活動S盒的個數。一種是理論證明的方式,一種是建立搜索算法的方式。理論證明得到的結果一般比較粗略,而針對算法結構建立搜索算法的方式往往時間消耗與資源消耗都比較大。于是,結合這兩種方式,文獻[9]提出了如下的搜索算法。

輸入:R(輪數),STR(R輪算法結構)

輸出:STR的活動S盒個數

步驟1:設定全局變量LBi=∞(1≤i≤R);

步驟2:fori=1 toR

Func(1,i);

步驟3:輸出LBR;

其中,Func(x,r)如下:

步驟4:ifx=NFr+1

步驟5:ifx≠NFr+1

forj=0 tom

令Dx=j,并檢測算法結構是否滿足所有的限定條件,若滿足,則進行如下步驟;

步驟5.1:ifx?{NFk|1≤k≤r-1}

調用Func(x+1,r);

步驟5.2:ifx∈{NFk|1≤k≤r-1}

令z是一個滿足x=NFz的整數,

調用Func(x+1,r)。

NFi是STR的前i輪F函數的個數。

3.3 4子塊GFSRP-SP結構的差分(線性)活動S盒個數的下界

令m=4,P為最優擴散映射(即令Bd=5),以性質1與性質2為搜索條件,使用3.1節的搜索算法可以搜索4子塊的GFSRP-SP的差分活動S盒個數的下界。由于P是最優擴散映射,差分分支數與線性分支數均為5,因此搜索算法中的限制條件相似,使得差分活動S盒個數的下界與線性活動S盒個數的下界相同,以下統稱活動S盒。活動S盒的搜索結果如表1所示。

表1 性質結果

需要注意的是,GFSRP的擴散層不同于Ⅰ-型GFS、Ⅱ-型GFS、Nyberg-型GFS的擴散層。GFSRP的擴散層將每個子塊平均分為兩個更小的單元,RP置換是這些單元的位置置亂。因此GFSRP的性質應與RP置換的特點密切相關。以本文定義的RP置換,研究4子塊的GFSRP-SP結構的差分(線性)活動S盒個數的下界。

更進一步地,有:

于是,根據以上的搜索算法,滿足性質1～性質5時,有以下的搜索結果。

表2 搜索結果

3.4 對比與分析

當F函數為SP結構時,通過使用搜索算法,本文對比了4子塊的Nyberg-型GFS、Ⅰ-型GFS、Ⅱ-型GFS與GFSRP的R輪活動S盒個數的下界。這四種結構中,均限定m=4,k=4,并且Bd=5。簡稱這三種結構為Nyberg、Ⅰ-型、Ⅱ-型,評估結果如表3所示。根據結果可以發現:GFSRP的擴散效果雖然不如Ⅱ-型GFS,但是明顯好于Ⅰ-型GFS與Nyberg-型GFS。

表3 對比結果

4 結語

不同于常見的GFS的擴散層都是基于子塊位置的置亂的結構特點,本文定義了一類GFS為GFSRP。該結構將子塊拆分成更小的單元,再將這些更小的單元位置置亂。目前還沒有國內外公開的分組密碼使用GFSRP-SP結構,也沒有GFSRP-SP結構安全性研究的文獻。本文采與Feistel-SP結構相似的方法,研究了GFSRP-SP結構的性質。

特別地,考慮到實際應用,針對本文定義的4子塊GFSRP-SP的結構特點,通過建立搜索算法,得到了更精確的活動S盒個數的下界。對于本文定義的4子塊的GFSRP-SP結構,當P變換差分(線性)分支數為5,S盒的差分(線性)概率為2～6,則對于分組長度為128比特的GFSRP-SP結構分組密碼,14輪迭代后,沒有有效的差分(線性)特征,具有足夠抵抗差分攻擊與線性攻擊的能力,具有實際應用價值。

[1] Y. Zheng, T. Matsumoto, H. Imai. On the construction of block ciphers probably secure and not relying on any unproved hypotheses[C]//Proc. Crypto’89, ed. G. Brassard, LNCS,1989,435:461-480.

[2] K. Nyberg. Generalized Feistel network[C]//Proc. Asiacrypt’96, ed. K. Kim and T. Mastsumoto, LNCS,1996,1163:91-104.

[3] 國家密碼管理局公告第7號[EB/OL]. http://www.oscca.gov.cm,2006-01.

[4] ADAMS C. The CAST-256 encryption algorithm[J]. Computer Science & Communications Dictionary,2001,81(4):864-894.

[5] Shirai, T., Shibutani, K., Akishita, T., et al. The 128-bit Blockcipher CLEFIA[C]//Biryukov, A. (ed.) FSE 2007. LNCS, Springer, Heidelberg,2007,4593:181-195.

[6] J. Daemen, V. Rijmen. The Design of Rijndael[M]. Heidelberg: Springer,2002.

[7] Kanda M. Practical Security Evaluation against Differential and Linear Cryptanalyes for Feistel Ciphers with SPN round function[C]//SAC 2000. Heidelberg: Springer,2001:324-338.

[8] 吳文玲,賀也平.一類廣義Feistel密碼的安全性評估[J].電子與信息學報,2002,24(9):1177-1184.

[9] Shirai T., Araki K. On Generalized Feistel Structures Using the Diffusion Switching Mechanism[J]. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.,2008,E91-A(8):2120-2129.

[10] Tomoyasu Suzaki, Kazuhiko Minematsu. Improving the Generalized Feistel[C]//FSE 2010, LNCS 6147,2010:19-39.

[11] Shibutani, K., Isobe, T., Hiwatari, H., et al. Piccolo: An Ultra-Lightweight Blockcipher[C]//CHES 2011, LNCS 6917,2011:342-357.

Security Analysis on A Class of Generalized Feistel Structure

XU Linjie WANG Chunhong PENG Cong LIU Lihui

(No. 722 Research Institute of CSIC, Wuhan 430079)

The generalized Feistel structure (GFS) which is extensively applied in block cipher designing has kinds of forms. In this paper, a novel form of GFS is defined as GFSRP, and the character of this structure which F function is SP type either been studied. To practical application, a search algorithm is established to find lower bounds of number of active S-boxes for 4-subblocks GFSRP-SP which showed in this paper. The obtained result shows that 4-subblocks GFSRP-SP structure has good immunity against differential attack and linear attack, and can be applied in bock cipher design.

block cipher, generalized Feistel structure, active S-boxes

2016年8月12日,

2016年9月16日

徐林杰,男,碩士研究生,工程師,研究方向:通信安全。王春紅,女,碩士研究生,高級工程師,研究方向:信息安全。彭聰,男,碩士研究生,工程師,研究方向:通信安全。劉麗輝,女,碩士研究生,工程師,研究方向:信息安全。

TP393

10.3969/j.issn.1672-9730.2017.02.014