Feistel結(jié)構(gòu)差分活動(dòng)S盒的搜索算法*

明亞運(yùn),祝世雄,曹云飛

(保密通信重點(diǎn)實(shí)驗(yàn)室,四川成都610041)

Feistel結(jié)構(gòu)差分活動(dòng)S盒的搜索算法*

明亞運(yùn),祝世雄,曹云飛

(保密通信重點(diǎn)實(shí)驗(yàn)室,四川成都610041)

為了設(shè)計(jì)安全的分組密碼算法,評(píng)估算法抵抗差分分析和線性分析的能力至關(guān)重要。目前一個(gè)比較實(shí)際的方法就是計(jì)算分組算法活動(dòng)S盒的最小數(shù)目,或者最小數(shù)目的下界。2004年Shirai等人在FSE會(huì)議上提出了一種基于漢明重量針對(duì)Feistel結(jié)構(gòu)的估計(jì)差分活動(dòng)S盒數(shù)量下界的算法。本文指出了此算法的不足,并基于一種特殊的剪枝策略,對(duì)原算法提出了一個(gè)改進(jìn)方案,將算法提升到實(shí)際應(yīng)用水平。

Feistel結(jié)構(gòu) 差分分析 活動(dòng)S盒

0 引 言

分組密碼由于具有容易被標(biāo)準(zhǔn)化和易于實(shí)現(xiàn)同步的優(yōu)點(diǎn),在信息安全領(lǐng)域得到了廣泛的應(yīng)用。在分組密碼的標(biāo)準(zhǔn)化過程中,密碼算法的安全性成為衡量算法好壞的重要指標(biāo)之一。分組密碼分析方法中最知名的莫過于Biham與Shamir提出的差分分析[1]和Matsui提出的線性分析[2],這是已知的攻擊分組密碼算法最有力的途徑。對(duì)于一個(gè)密碼設(shè)計(jì)者來說,評(píng)估分組密碼算法的安全性,應(yīng)該首先重點(diǎn)考慮其抵抗差分分析和線性分析的能力。目前一個(gè)有效的方法即是計(jì)算分組密碼算法的活動(dòng)S盒的數(shù)量。

目前主要有兩類方法來計(jì)算差分(線性)活動(dòng)S盒的最小數(shù)或者最小數(shù)的下界。一是理論證明,此種方法能夠解決較小輪數(shù)的計(jì)數(shù)問題。首先提出Feistel結(jié)構(gòu)的活動(dòng)S盒下界理論計(jì)算的是Kanda[3],主要是基于分支數(shù)的理論推導(dǎo)證明,后由Wang等人[4]優(yōu)化。吳文玲等人[5]分析了CAST256結(jié)構(gòu)并得到了8輪和16輪的活動(dòng)S盒的下界。對(duì)于CLEFIA和SMS4結(jié)構(gòu)的活動(dòng)S盒的下界分別由Shibutani[6]和Wang等人[7]做了研究。

如果要解決較大輪數(shù)甚至完整算法的活動(dòng)S盒計(jì)數(shù)問題,則需要利用第二種方法,即是建立搜索算法。通過對(duì)Matsui[8]的算法的改進(jìn),Aoki等人[9]給出了一種有效地輸出Feistel結(jié)構(gòu)活動(dòng)S盒最小數(shù)的下界的算法。Shirai等人[10,11,12]采用了一些有效的搜索算法對(duì)Feistel、CAST256、GFS安全性做出了評(píng)估。同時(shí)值得一提的是,Wu[13]、Mouha[14]等人采用線性規(guī)劃方法計(jì)算活動(dòng)S盒數(shù)量也取得了不錯(cuò)的效果。

在文獻(xiàn)[10]中,Shirai等人針對(duì)套嵌SP型輪函數(shù)的Feistel結(jié)構(gòu),提出一種基于漢明重量的活動(dòng)S盒搜索算法。此算法采用窮盡搜索法,數(shù)據(jù)復(fù)雜度高,離實(shí)際使用有較大差距。

1 相關(guān)定義

定義1有非零輸入的S盒就叫做活動(dòng)S盒。

定義2令x=(x1,…,xn)∈()n,x的漢明重量wh(x)定義為

定義3令θ:是一個(gè)變換,x=(x1,…,xn)∈()n,則稱B(θ)=(wh(x)+wh(θ(x)))為θ的分支數(shù)。

分支數(shù)的概念和差分密碼分析及線性密碼分析緊密相關(guān),本文后面將利用它給出活動(dòng)S盒數(shù)目的界。下面定義θ的差分分支數(shù)Bd:

其中x、x*為變換θ的兩個(gè)輸入,x⊕x*為變換θ的輸入差分,θ(x)⊕θ(x*)為變換θ的輸出差分。

定義4SP型F函數(shù)定義如下:令n為雙射S盒的輸入比特寬,m為F函數(shù)中所使用S盒的數(shù)量,在F函數(shù)中

(1)mn比特的輪密鑰ki∈()m和數(shù)據(jù)X∈()m異或:W=X⊕ki。此過程為加密鑰。

(2)W分成m份的n比特?cái)?shù)據(jù),輸入到對(duì)應(yīng)n個(gè)S盒S1、S2、…、Sn。

(3)S盒輸出的數(shù)據(jù)記作Z∈()m,通過一個(gè)在上的m×m矩陣M變換:Y=MZ。

本文所研究的對(duì)象即是SP型輪函數(shù)的Feistel結(jié)構(gòu),如圖1所示。

圖1 套嵌SP輪函數(shù)的Feistel結(jié)構(gòu)Fig.1 Feistel structure with SP round function

2 算法介紹

Feistel結(jié)構(gòu)差分模型見圖2。

圖2 Feistel結(jié)構(gòu)扭正圖(4輪)Fig.2 Untwist form of Feistel structure(4 rounds)

令Δxi(i=0,1,2,3,…)代表各輪的差分,根據(jù)Feistel結(jié)構(gòu)的扭正圖,我們可以得到如圖3所示的結(jié)構(gòu),并得到各輪差分之間有如下關(guān)系:

圖3 扭正圖細(xì)節(jié)Fig.3 Details of Untwist form of Feistel structure

令W1為wh(Δxi+Δxi+2j),可以得到下面的不等式,

另一方面,我們令W2為wh(),如果至少存在一個(gè)wh(Δxj)非零,那么有如下不等式

如果所有的漢明重量wh(Δxj)都為0,那么W2的值為0。在下面的搜索算法中,對(duì)于某一個(gè)漢明重量組合,比較W1與W2的值,如果二者的取值范圍沒有重合,那么說明此漢明重量組合是不合理的,不應(yīng)當(dāng)計(jì)入到活動(dòng)S盒的下界的目標(biāo)組合中去。

以下算法基于漢明重量,可以輸出一個(gè)R輪活動(dòng)S盒數(shù)量的下界:

1)令L=∞。

2)任意一個(gè)對(duì)δx0,δx1,…,δxR+1漢明重量為0, 1,2,3,…,m的組合(不妨設(shè)m=8,共9R+2種可能):

(1)從i=2到R+1,做如下操作

從j=2到j(luò)≤i,j=j+2,做如下操作

A.檢驗(yàn)所給的漢明重量組合是否滿足條件。

B.如果檢測(cè)通過則繼續(xù),否則跳出流程。

(2)如果所有的檢測(cè)皆通過,計(jì)算在此路徑中所有活動(dòng)S盒的數(shù)量A。如果A＜L,則設(shè)置L=A。

3.輸出L,作為R輪活動(dòng)S盒數(shù)量的下界。

此算法采用窮盡搜索法,數(shù)據(jù)復(fù)雜度高,我們的實(shí)驗(yàn)表明當(dāng)m=8,Bd=9時(shí)搜索12輪的Feistel結(jié)構(gòu)的活動(dòng)S盒下界所需的時(shí)間已經(jīng)超過一天,離實(shí)際使用存在很大差距。

3 改進(jìn)方案

根據(jù)文獻(xiàn)[12]剪枝方法,可將算法優(yōu)化如下,可以輸出一個(gè)R輪活動(dòng)S盒數(shù)量的下界:

1)令LR=∞。

2)從i=1到R,調(diào)用函數(shù)Func(i)。Func(y)定義為:

(1)如果y=R+1,做如下操作

如果L＞。

(2)如果y≠R+1,從j=0到j(luò)≤m,執(zhí)行如下操作:令δxy=j。如果,則執(zhí)行以下操作:

(3)檢驗(yàn)所給的漢明重量組合是否滿足條件。如果檢測(cè)通過,則轉(zhuǎn)到Func(y+1)。

3)輸出L,作為R輪活動(dòng)S盒數(shù)量的下界。

4 方案分析

改進(jìn)的方案充分利用了較小輪數(shù)的下界的結(jié)果,即是,如果前y輪活動(dòng)S盒的數(shù)量與剩下R-y輪的活動(dòng)S盒的下界的總和已經(jīng)超過目前得到的R輪活動(dòng)S盒數(shù)量下界的結(jié)果,那此搜索再進(jìn)行下去也無(wú)法得到一個(gè)更優(yōu)的結(jié)果。此種提前跳出的剪枝策略大大降低了算法的計(jì)算復(fù)雜度,實(shí)驗(yàn)表明,當(dāng)m=8,Bd=9時(shí)搜索30輪的Feistel結(jié)構(gòu)的活動(dòng)S盒下界所需的時(shí)間僅需幾秒。以m=8,Bd=9為例,可得如結(jié)果,見表1。

表1 實(shí)驗(yàn)結(jié)果Table 1 Experiment results

5 結(jié) 語(yǔ)

借助于計(jì)算機(jī),構(gòu)造一個(gè)普適性較好的分組密碼實(shí)際安全性分析工具在分組密碼設(shè)計(jì)工作中非常必要,科研人員可以通過此工具對(duì)密碼算法進(jìn)行可行性論證和改進(jìn),使算法設(shè)計(jì)等實(shí)際工作更加快速高效,并對(duì)可重構(gòu)密碼安全性分析提供重要理論支持。Feistel結(jié)構(gòu)差分活動(dòng)S盒搜索算法的應(yīng)用,可以作為分組密碼實(shí)際安全性分析工具的重要功能之一,后續(xù)進(jìn)一步研究將算法拓展到SMS4、MISTY、L-M等結(jié)構(gòu)。

[1] Biham E.,Shamir A.Differential Cryptanalysis of DES-like Cryptosystems[J].Journal of Cryptology,1991,4 (01):3-72.

[2] Matsui M.Linear Cryptanalysis Method for DES Cipher [C]//EUROCRYPT'1993,Heidelberg:Springer.1994: 386-397.

[3] Kanda M.Practical Security Evaluation against Differential and Linear Cryptanalyses for Feistel Ciphers with SPN round function[C]//Selected Areas in Cryptography' 2000.Heidelberg:Springer.2001:324-338.

[4] Wang N.,Jin C.Security Evaluation against Differential and Linear Cryptanalyses for Feistel Ciphers[J].Frontiers of Computer Science in China,2009.3(4).494-502.

[5] Wu W.,Zhang W.,Lin D.On the Security of Generalized Feistel Scheme with SP Round Function[J].International Journal of Network Security.2006.3(3).215-224.

[6] Shibutani K.On the Diffusion of Generalized Feistel Structures Regarding Differential and Linear Cryptanalysis[C]//Selected Areas in Cryptography'2010.Heidelberg:Springer.2011:211-228.

[7] Wang M.,Liu J.,Wang X.The upper bounds on differential characteristics in block cipher SMS4[DB/OL]. (2010-03-25)[2014-08-10].http://eprint.iacr.org/ 2010/155.pdf.

[8] Matsui M.:Differential Path Search of the Block Cipher E2[C]//International Superconductive Electronics Conference'1999.[s.l.]:[s.n.].1999:57-64.

[9] Aoki K.,Ichikawa T.,Kanda M.,et al.Camellia:A 128-bit Block Cipher Suitable for Multiple Platforms-Design and Analysis[C]//Selected Areas in Cryptography' 2000.Heidelberg:Springer.2001:39-56.

[10] Shirai T.,Shibutani K.Improving immunity of Feistel ciphers against differential cryptanalysis by using multiple MDS matrices[C]//Fast Software Encryption' 2004.[s.l.]:Springer.2004:260-278.

[11] Shirai,T.,Shibutani,K.:On Feistel Structures Using a Diffusion Switching Mechanism[C]//Fast Software Encryption'2006.Heidelberg:Springer.2006:41-56.

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

[13] Mouha N.,Wang Q.,Gu D.,Preneel B.Differential and linear cryptanalysis using mixed-integer linear programming[C]//7th International Conference on Information Security and Cryptology.Beijing:Springer. 2012:57-76.

[14] Wu S.,Wang M.Security evaluation against differential cryptanalysis for block Cipher structures[DB/OL]. (2011-10-06)[2014-08-10].http://eprint.iacr. org/2011/551.pdf.

MING Ya-yun(1989-),male,graduate student,mainly engaged in the design and analysis of block cipher.

祝世雄(1965—),男,碩士,研究員,主要研究方向?yàn)槊艽a學(xué);

ZHU Shi-xiong(1965-),male,M.Sci.,research fellow, mainly engaged in cryptography.

曹云飛(1971—),男,碩士,高級(jí)工程師,主要研究方向?yàn)槊艽a學(xué)。

CAO Yun-fei(1971-),male,M.Sci.,senior engineer, mainly engaged in cryptography.

Search Algorithm for Differential Active S-boxes of Feistel Structure

MING Ya-yun,ZHU Shi-xiong,CAO Yun-fei
(Science and Technology on Communication Security Laboratory,Chengdu Sichuan 610041,China)

In order to design secure block ciphers,the ability of evaluation algorithm to resist differential cryptanalysis and linear cryptanalysis is of utmost importance.Currently,a relatively practical measure is to calculate the minimum quantity of differential active S-boxes,or the lower bound of the minimum quantity.In 2004,Shirai et al.proposed a search algorithm to estimate the lower bound of active S-boxes quantity of Feistel based on hamming weight at FSE conference.This paper points out the flaw of this proposed search algorithm,and based on a special branch cutting strategy,puts forward an improved scheme is introduced to upgrade the algorithm to a practical application level.

feistel;differential cryptanalysis;active S-boxes

TN918

A

1002-0802(2014)10-1207-04

10.3969/j.issn.1002-0802.2014.10.020

明亞運(yùn)(1989—),男,碩士研究生,主要研究方向?yàn)榉纸M密碼的設(shè)計(jì)與分析;

2014-08-01;

2014-09-10 Received date：2014-08-01;Revised date：2014-09-10

國(guó)家自然科學(xué)基金(No.61309034);四川青年基金資助項(xiàng)目(No.2014JQ0055)

Foundation Item:National Natural Science Fundation of China(No.61309034);Sichuan Provincial Youth Science Fund(No.2014JQ0055)