一類(lèi)廣義Feistel結(jié)構(gòu)的安全性分析

徐林杰 王春紅 彭 聰 劉麗輝

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

一類(lèi)廣義Feistel結(jié)構(gòu)的安全性分析

徐林杰 王春紅 彭 聰 劉麗輝

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

廣義Feistel結(jié)構(gòu)(以下簡(jiǎn)稱(chēng)GFS)的形式多種多樣,廣泛應(yīng)用于分組密碼設(shè)計(jì)。論文定義了一類(lèi)GFS為GFSRP,研究了整體結(jié)構(gòu)為GFSRP-SP結(jié)構(gòu)(GFSRP的F函數(shù)是SP型結(jié)構(gòu))的分組密碼的性質(zhì)?？紤]到實(shí)際應(yīng)用,論文給出一個(gè)4子塊的GFSRP-SP結(jié)構(gòu)的實(shí)例,并通過(guò)建立搜索算法,得到了更精確的活動(dòng)S盒個(gè)數(shù)的下界。結(jié)果表明,4子塊的GFSRP-SP結(jié)構(gòu)具有較好的抵抗差分攻擊與線(xiàn)性攻擊的能力,可應(yīng)用于分組密碼設(shè)計(jì)。

分組密碼; 廣義Feistel結(jié)構(gòu); 活動(dòng)S盒

Class Number TP393

1 引言

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

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

對(duì)于以上提到的GFS,這些結(jié)構(gòu)的特點(diǎn),都是一個(gè)或者若干個(gè)子塊進(jìn)入F函數(shù),然后再進(jìn)入擴(kuò)散層。擴(kuò)散層都是基于子塊位置的置亂,可以看作一個(gè)置換。值得思考的是,擴(kuò)散層是否一定是這種基于子塊位置的置亂?能否將子塊拆分成更小的單元,再將這些更小的單元位置置亂?如果這樣做,對(duì)這種結(jié)構(gòu)抵抗差分攻擊與線(xiàn)性攻擊的能力應(yīng)該怎樣評(píng)估?本文對(duì)這幾個(gè)問(wèn)題進(jìn)行了研究。

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

為方便描述,本文先引入文獻(xiàn)[10]的定義。k為偶數(shù),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函數(shù),π:({0,1}n)k→({0,1}n)k是一個(gè)子塊位置置亂、可看作是一個(gè)置換,k是子塊的個(gè)數(shù),n是一個(gè)子塊的比特長(zhǎng)度,則稱(chēng)具有這樣結(jié)構(gòu)的置換為GFSπ。GFSπ如圖1所示。

對(duì)于GFSπ,π置換的選取不同,對(duì)應(yīng)的結(jié)構(gòu)就不同。目前分組密碼設(shè)計(jì)中較為常用的是4子塊的GFS(即k=4)。于是,令k=4,當(dāng)π(Y0,Y1,Y2,Y3)=(Y1,Y2,Y3,Y0),即為4子塊的Ⅱ-型GFS,結(jié)構(gòu)如圖2所示;當(dāng)π(Y0,Y1,Y2,Y3)=(Y1,Y3,Y0,Y2),即為4子塊的Nyberg-型GFS,結(jié)構(gòu)如圖3所示。Ⅰ-型GFS不是GFSπ置換,但與Ⅰ-型GFS與Ⅱ-型GFS的結(jié)構(gòu)類(lèi)似,如圖4所示。這兩種結(jié)構(gòu),相同的是π置換一致,都是循環(huán)左移一個(gè)子塊;不同的是,單輪Ⅱ-型GFS有k/2個(gè)F函數(shù),而單輪Ⅰ-型GFS只有1個(gè)F函數(shù)。

定義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函數(shù),RP:({0,1}n/2)2×k→({0,1}n/2)k×2是一個(gè)置換。則稱(chēng)具有這樣結(jié)構(gòu)的置換為GFSRP。

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

差分攻擊與線(xiàn)性攻擊是分組算法最常用且很有效的攻擊方法。為評(píng)估一個(gè)分組密碼抵抗的這兩種攻擊的能力,通常采用估計(jì)這個(gè)分組密碼差分特征(線(xiàn)性逼近)中活動(dòng)S盒的個(gè)數(shù)的下界的方法。而活動(dòng)S盒的個(gè)數(shù)與差分分支數(shù)與線(xiàn)性分支數(shù)密切相關(guān)。

定義3:一個(gè)差分特征中,如果S盒的輸入差分不為零,則稱(chēng)此S盒是差分活動(dòng)的;一個(gè)線(xiàn)性逼近中,如果一些輸入和輸出比特被涉及,則稱(chēng)此S盒是線(xiàn)性活動(dòng)的。

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

類(lèi)似地定義差分分支數(shù)與線(xiàn)性分支數(shù)的定義:

其中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是有效線(xiàn)性逼近。上標(biāo)t表示向量或矩陣的轉(zhuǎn)置。

P的差分分支數(shù)與線(xiàn)性分支數(shù)的最大值為m+1。當(dāng)變換P的差分分支數(shù)與線(xiàn)性分支數(shù)的均達(dá)到最大,則稱(chēng)P為最優(yōu)擴(kuò)散映射,其對(duì)應(yīng)的矩陣M是m階MDS矩陣。

3 GFSRP-SP結(jié)構(gòu)的安全性分析

3.1 GFSRP-SP結(jié)構(gòu)的性質(zhì)

當(dāng)R輪GFSRP-SP至少存在一個(gè)非零輸入差分,顯然有如下性質(zhì)。

性質(zhì)1:任意連續(xù)2輪k子塊的GFSRP-SP結(jié)構(gòu),至少有1個(gè)F函數(shù)有差分活動(dòng)S盒。

這個(gè)性質(zhì)是由于GFSRP-SP結(jié)構(gòu)的可逆性。如果連續(xù)2輪加密的k個(gè)F函數(shù)均沒(méi)有活動(dòng)S盒,即沒(méi)有非零的輸入差分,則意味著這兩輪加密之前的兩輪的k個(gè)F函數(shù)均沒(méi)有非零輸入差分。同樣的,這兩輪加密之后的k個(gè)F函數(shù)也沒(méi)有非零輸入差分,以此類(lèi)推目標(biāo)結(jié)構(gòu)不存在非零的輸入差分,這與R輪GFSRP-SP結(jié)構(gòu)至少存在一個(gè)非零輸入差的前提條件相矛盾。

而由GFSRP-SP結(jié)構(gòu)的定義,結(jié)合差分分支數(shù)的定義不難有如下性質(zhì)。

性質(zhì)2:任意連續(xù)3輪GFSRP-SP結(jié)構(gòu)加密,其差分活動(dòng)S盒個(gè)數(shù)有如下特點(diǎn)。

性質(zhì)1考慮了連續(xù)兩輪輸入差分的關(guān)系,性質(zhì)2考慮了連續(xù)三輪輸入差分的關(guān)系。顯然任意R(R≥3)輪GFSRP-SP結(jié)構(gòu)迭代都要滿(mǎn)足這兩個(gè)性質(zhì)。

3.2 搜索算法

對(duì)于一個(gè)分組密碼,一般有兩種方式統(tǒng)計(jì)活動(dòng)S盒的個(gè)數(shù)。一種是理論證明的方式,一種是建立搜索算法的方式。理論證明得到的結(jié)果一般比較粗略,而針對(duì)算法結(jié)構(gòu)建立搜索算法的方式往往時(shí)間消耗與資源消耗都比較大。于是,結(jié)合這兩種方式,文獻(xiàn)[9]提出了如下的搜索算法。

輸入:R(輪數(shù)),STR(R輪算法結(jié)構(gòu))

輸出:STR的活動(dòng)S盒個(gè)數(shù)

步驟1:設(shè)定全局變量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,并檢測(cè)算法結(jié)構(gòu)是否滿(mǎn)足所有的限定條件,若滿(mǎn)足,則進(jìn)行如下步驟;

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

調(diào)用Func(x+1,r);

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

令z是一個(gè)滿(mǎn)足x=NFz的整數(shù),

調(diào)用Func(x+1,r)。

NFi是STR的前i輪F函數(shù)的個(gè)數(shù)。

3.3 4子塊GFSRP-SP結(jié)構(gòu)的差分(線(xiàn)性)活動(dòng)S盒個(gè)數(shù)的下界

令m=4,P為最優(yōu)擴(kuò)散映射(即令Bd=5),以性質(zhì)1與性質(zhì)2為搜索條件,使用3.1節(jié)的搜索算法可以搜索4子塊的GFSRP-SP的差分活動(dòng)S盒個(gè)數(shù)的下界。由于P是最優(yōu)擴(kuò)散映射,差分分支數(shù)與線(xiàn)性分支數(shù)均為5,因此搜索算法中的限制條件相似,使得差分活動(dòng)S盒個(gè)數(shù)的下界與線(xiàn)性活動(dòng)S盒個(gè)數(shù)的下界相同,以下統(tǒng)稱(chēng)活動(dòng)S盒。活動(dòng)S盒的搜索結(jié)果如表1所示。

表1 性質(zhì)結(jié)果

需要注意的是,GFSRP的擴(kuò)散層不同于Ⅰ-型GFS、Ⅱ-型GFS、Nyberg-型GFS的擴(kuò)散層。GFSRP的擴(kuò)散層將每個(gè)子塊平均分為兩個(gè)更小的單元,RP置換是這些單元的位置置亂。因此GFSRP的性質(zhì)應(yīng)與RP置換的特點(diǎn)密切相關(guān)。以本文定義的RP置換,研究4子塊的GFSRP-SP結(jié)構(gòu)的差分(線(xiàn)性)活動(dòng)S盒個(gè)數(shù)的下界。

更進(jìn)一步地,有:

于是,根據(jù)以上的搜索算法,滿(mǎn)足性質(zhì)1～性質(zhì)5時(shí),有以下的搜索結(jié)果。

表2 搜索結(jié)果

3.4 對(duì)比與分析

當(dāng)F函數(shù)為SP結(jié)構(gòu)時(shí),通過(guò)使用搜索算法,本文對(duì)比了4子塊的Nyberg-型GFS、Ⅰ-型GFS、Ⅱ-型GFS與GFSRP的R輪活動(dòng)S盒個(gè)數(shù)的下界。這四種結(jié)構(gòu)中,均限定m=4,k=4,并且Bd=5。簡(jiǎn)稱(chēng)這三種結(jié)構(gòu)為Nyberg、Ⅰ-型、Ⅱ-型,評(píng)估結(jié)果如表3所示。根據(jù)結(jié)果可以發(fā)現(xiàn):GFSRP的擴(kuò)散效果雖然不如Ⅱ-型GFS,但是明顯好于Ⅰ-型GFS與Nyberg-型GFS。

表3 對(duì)比結(jié)果

4 結(jié)語(yǔ)

不同于常見(jiàn)的GFS的擴(kuò)散層都是基于子塊位置的置亂的結(jié)構(gòu)特點(diǎn),本文定義了一類(lèi)GFS為GFSRP。該結(jié)構(gòu)將子塊拆分成更小的單元,再將這些更小的單元位置置亂。目前還沒(méi)有國(guó)內(nèi)外公開(kāi)的分組密碼使用GFSRP-SP結(jié)構(gòu),也沒(méi)有GFSRP-SP結(jié)構(gòu)安全性研究的文獻(xiàn)。本文采與Feistel-SP結(jié)構(gòu)相似的方法,研究了GFSRP-SP結(jié)構(gòu)的性質(zhì)。

特別地,考慮到實(shí)際應(yīng)用,針對(duì)本文定義的4子塊GFSRP-SP的結(jié)構(gòu)特點(diǎn),通過(guò)建立搜索算法,得到了更精確的活動(dòng)S盒個(gè)數(shù)的下界。對(duì)于本文定義的4子塊的GFSRP-SP結(jié)構(gòu),當(dāng)P變換差分(線(xiàn)性)分支數(shù)為5,S盒的差分(線(xiàn)性)概率為2～6,則對(duì)于分組長(zhǎng)度為128比特的GFSRP-SP結(jié)構(gòu)分組密碼,14輪迭代后,沒(méi)有有效的差分(線(xiàn)性)特征,具有足夠抵抗差分攻擊與線(xiàn)性攻擊的能力,具有實(shí)際應(yīng)用價(jià)值。

[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] 國(guó)家密碼管理局公告第7號(hào)[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] 吳文玲,賀也平.一類(lèi)廣義Feistel密碼的安全性評(píng)估[J].電子與信息學(xué)報(bào),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日

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

TP393

10.3969/j.issn.1672-9730.2017.02.014