Feistel-SP結(jié)構(gòu)迭代差分的自動(dòng)化搜索*

李艷俊，方 波,2，毛 明,2

(1.西安電子科技大學(xué)通信工程學(xué)院，陜西 西安 710071；2.北京電子科技學(xué)院,北京 100070)

Feistel-SP結(jié)構(gòu)迭代差分的自動(dòng)化搜索*

李艷俊1，方 波1,2，毛 明1,2

(1.西安電子科技大學(xué)通信工程學(xué)院，陜西 西安 710071；2.北京電子科技學(xué)院,北京 100070)

基于新的符號(hào)差分表示方法提出了一種自動(dòng)化搜索技術(shù)，可以搜索出典型Feistel-SP結(jié)構(gòu)的分組密碼的最優(yōu)迭代差分模式，選擇合適的迭代差分模式可以遍歷出所有最優(yōu)的迭代差分路徑，不僅大大降低計(jì)算復(fù)雜性，還能通過迭代差分模式構(gòu)造出多輪最優(yōu)差分路徑。以輕量級(jí)分組密碼MIBS為例，應(yīng)用自動(dòng)化搜索工具，給出了MIBS的3輪、4輪最優(yōu)迭代差分路徑，概率分別為2-20、2-26，并搜索出所有滿足條件的最優(yōu)迭代差分路徑。

Feistel-SP;MIBS;自動(dòng)化搜索;符號(hào)差分;迭代差分

1 引言

Feistel網(wǎng)絡(luò)結(jié)構(gòu)[1]是由Feistel H設(shè)計(jì)的，它是設(shè)計(jì)分組密碼的典型結(jié)構(gòu)，其優(yōu)點(diǎn)是加密和解密過程相同或者相似，使得加密和解密速度快，非常有利于軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)。SP[2]網(wǎng)絡(luò)結(jié)構(gòu)是除了Feistel網(wǎng)絡(luò)結(jié)構(gòu)之外的另一種典型結(jié)構(gòu)，SARER、SHARK等著名密碼算法都采用此結(jié)構(gòu)。在此結(jié)構(gòu)的每一輪的輪輸入首先作用于一個(gè)由子密鑰控制的可逆函數(shù)S(非線性變換)，然后再作用于一個(gè)置換P(或一個(gè)可逆的線性變換)。S一般被稱為混淆層，主要起混淆作用，P一般被稱為擴(kuò)散層，主要起擴(kuò)散作用。很多著名的分組密碼算法都是基于這兩種結(jié)構(gòu)設(shè)計(jì)的，F(xiàn)eisetl-SP結(jié)構(gòu)是指將Feistel、SP相結(jié)合而形成的一種混合結(jié)構(gòu)，典型密碼算法有MIBS[3], E2[4]和Camellia[5]等。

2009年，文獻(xiàn)[3]提出一種新的分組密碼算法MIBS，整體采用Feistel結(jié)構(gòu)，輪函數(shù)為SP結(jié)構(gòu)，以4 bit為一個(gè)單位輸入，它的分組長(zhǎng)度為64 bit，密鑰長(zhǎng)度為64 bit和80 bit兩個(gè)版本，輪數(shù)為32輪，可以應(yīng)用到資源受限的微型計(jì)算設(shè)備上。由于密鑰生成對(duì)差分分析沒有影響，我們只需要考慮算法的差分特征。本文提出了一種新的符號(hào)差分表示方法，基于這種符號(hào)表示方法進(jìn)而給出了一種自動(dòng)化搜索技術(shù)，使用自動(dòng)化搜索工具，我們搜索出3、4輪的最優(yōu)迭代差分概率,并給出了多條迭代差分路徑。第2節(jié)介紹了MIBS分組密碼算法組成和性質(zhì)，第3節(jié)介紹了差分傳播系統(tǒng)，重點(diǎn)說明了差分基本性質(zhì)和新的差分表示法，第4節(jié)給出了3、4輪的自動(dòng)化搜索算法，第5節(jié)對(duì)本文工作進(jìn)行了總結(jié)。

2 MIBS分組密碼

MIBS整體結(jié)構(gòu)是Feistel結(jié)構(gòu)，輪函數(shù)是SPN(Secret Private Network)型，該算法是以4 bit為單位(半字節(jié))，由密鑰加、S盒替換、M置換和變換層T組成。為了方便描述，我們把線性變換M和T統(tǒng)稱為P置換，MIBS的輪函數(shù)的具體表達(dá)式為：

F[K]=P′S′σ[K]

其中，σ[K]是密鑰異或運(yùn)算。

其具體結(jié)構(gòu)如圖1所示。

Figure 1 Structure of round function

MIBS的字節(jié)替代是由8個(gè)相同的S盒組成，S盒是4×4規(guī)模大小，每個(gè)S盒的最大差分概率是2-2：

F輪函數(shù)的線性變換由M置換層、T變換層組成、M置換層表達(dá)式如下：

T變換表映射如表1所示。

Table 1 T transformation

M-T組成的P矩陣及其逆矩陣可以寫成為：

3 差分傳播系統(tǒng)

3.1 預(yù)備知識(shí)

為了更好地研究MIBS迭代差分模式,首先我們對(duì)差分傳播模式進(jìn)行說明,引進(jìn)如下表示方法：ΔXA、ΔYA分別表示A輪的輸入差分和輸出差分，ΔZA、ΔVZA分別表示A輪S盒的輸出差分和P逆置換的輸出差分，他們之間的關(guān)系為ΔZA=S(ΔXA),ΔYA=P(ΔZA)。這里，ΔX=(Δ1,…,Δx2),Δx1表示第i個(gè)S盒的差分。

定義1 輪函數(shù)F的一對(duì)輸入(x,x′),若該輸入對(duì)導(dǎo)致某個(gè)S盒的輸入差分非零，則稱輸入對(duì)(輸入差分)導(dǎo)致該S盒活躍，或者稱S盒針對(duì)輸入對(duì)(輸入差分)是活躍的，簡(jiǎn)稱該S盒是差分活躍S盒。

上述定義說明輸入差分非0,輸出差分非0；輸入差分為0，輸出差分為0。

定義2[6]SPN輪函數(shù)中，差分分支數(shù)定義如下：

其中，P是擴(kuò)散層，△X是輸入差分。

定義3[6]若一條i輪差分特征ω=(β0,β1,…,βi)滿足β0=βi，這稱ω是一條i輪迭代差分特征，若ω是迭代差分特征，則它自身可進(jìn)行級(jí)聯(lián)。

定義4[7]如果特征滿足如下條件:

([Φ],[I]),ΔYm,…,ΔYm′,([J],[Φ])

且中間不包含交換特征，其中[Φ]表示全0比特，[I]和[J]為任意差分，稱為m′-m+1輪迭代差分特征。

定義5[7]n輪迭代差分中概率p最大的特征稱為最優(yōu)差分特征，如果它是k輪導(dǎo)出的，稱n輪差分特征的最優(yōu)迭代差分特征為k輪。同樣k輪迭代特征中概率p最大的迭代差分特征稱為k輪最優(yōu)迭代差分特征。

定義6 符號(hào)差分以Sign表示，如果輸入為0，經(jīng)過符號(hào)差分輸出為0，如果輸入不為0，經(jīng)過符號(hào)差分輸出為1。

如Sign(X1,…,Xn)=(A1,…,An),當(dāng)Xi為0時(shí)，Ai為0,當(dāng)Xi不為0時(shí)，Ai為1。

定理1[8]輪函數(shù)是SPN型的Feistel結(jié)構(gòu)密碼沒有兩輪迭代差分特征。

上述定理說明Feistel-SP沒有兩輪迭代差分特征，本文搜索了3、4輪的迭代差分特征。

3.2 差分模式表示法

經(jīng)過觀察，第i-1輪的輸出差分對(duì)是第i輪的輸入差分對(duì)，要使第i輪輸入的活躍S盒個(gè)數(shù)最少，考慮P置換的性質(zhì)可以推測(cè)到輸入的非零差分之間存在著一定的等價(jià)關(guān)系?；谶@種思想我們采用具有內(nèi)部關(guān)系的符號(hào)差分來表示具體的輸入差分值，這種表示方式改進(jìn)了以往的符號(hào)差分表示方法[7](輸入差分不為零時(shí)用1表示，輸出差分為零時(shí)用0表示)。使用這種具有一定內(nèi)部關(guān)系的迭代差分模式去搜索迭代差分特征，可以大大降低計(jì)算復(fù)雜性。

本文提出了如下具有差分內(nèi)部關(guān)系的符號(hào)差分來搜索多輪最優(yōu)的迭代差分模式。當(dāng)輸入活躍S盒個(gè)數(shù)為1、2、3時(shí)，內(nèi)部關(guān)系比較簡(jiǎn)單。主要對(duì)輸入為4個(gè)活躍S盒的情況進(jìn)行說明，如表2所示，例如：當(dāng)有4個(gè)活躍S盒時(shí),考慮它們內(nèi)部經(jīng)過線性變換后的關(guān)系，我們定義1111表示4個(gè)差分都相等,經(jīng)過P變換后,可以確定四種情況(1、2、3、4個(gè)差分進(jìn)行異或)，當(dāng)1、2個(gè)差分進(jìn)行異或時(shí)，輸出是唯一的(用“-”表示，對(duì)于其他情況也是一樣)，當(dāng)3個(gè)異或時(shí)結(jié)果為1,當(dāng)4個(gè)異或時(shí)結(jié)果為0。同樣，如1112表示當(dāng)1、2個(gè)差分進(jìn)行異或時(shí)，結(jié)果唯一，任取3個(gè)異或時(shí)符號(hào)差分為1、4個(gè)差分異或時(shí)符號(hào)差分也為1，下面也用相同的方法表述。

Table 2 Differential representation

注:1、2、3、4、7表示它們內(nèi)部關(guān)系的符號(hào)差分，1、2、3存在關(guān)系式：1⊕2=3，4、7不存在內(nèi)部的關(guān)系，這樣就能把輸入為4個(gè)活躍S盒的所有情況表示出來。

4 高概率自動(dòng)化差分模式算法

本文借鑒符號(hào)差分的思想,考慮S盒性質(zhì)。算法的核心思想是比較經(jīng)過P置換或P逆置換后S盒兩端對(duì)應(yīng)零元位置是否相等(零元位置經(jīng)過線性變換后具有唯一性),來過濾不滿足的差分模式。下面給出了3、4輪算法的偽代碼，我們搜索出MIBS的3、4輪最優(yōu)迭代差分模式，進(jìn)而給出迭代差分路徑。

4.1 3輪迭代差分特征

Feistel-SP結(jié)構(gòu)3輪迭代差分特征滿足如下形式：

([Φ],[ΔX])

A:[ΔY]←[ΔX]

B:[ΔX]←[ΔY]

([ΔY]，[Φ])

Feistel-SP3輪迭代差分結(jié)構(gòu)如圖2所示。

Figure 2 Differential structure of 3 round iteration

建立等式：

Sign(P-1(Δy))=

Sign(Δx)Sign(P-1(Δx))=Sign(Δy)

其具有對(duì)稱性，利用這種性質(zhì)我們?cè)O(shè)計(jì)了3輪迭代差分算法。

Feistel-SP結(jié)構(gòu)3輪迭代模式算法偽代碼如下：

1.差分變量ΔX、ΔY，聯(lián)系關(guān)系為：Sign(P-1(Δy))=Sign(Δx),Sign(P-1(Δx))=Sign(Δy);

3. For選取輸入差分ΔX的一種情況 do

4. For選取輸出差分ΔY的一種情況 do

5. 分別對(duì)ΔX、ΔY求線性變換逆變變換存入臨時(shí)變量TempX、TempY;

6. if(Sign(TempX)==Sign(ΔY)&&Sign(TempY)==Sign(ΔY)) Then

7. 找出最小活躍S盒個(gè)數(shù)，把滿足條件的差分變量ΔX、ΔY存儲(chǔ)起來，計(jì)數(shù)器加1;

8.Continue

以MIBS算法為例，基于上述算法我們搜索出所有的3輪迭代差分模式,遍歷所有的迭代差分模式，搜索出3輪最優(yōu)迭代差分特征，其最小活躍S盒個(gè)數(shù)為8，概率為2-20。下面列舉了部分最優(yōu)迭代差分模式和最優(yōu)迭代差分路徑數(shù)據(jù)。如表3和表4所示。

Table 3 Optimal differential mode for 3 rounds iteration

Table 4 Optimal differential path for 3 rounds iteration

4.2 4輪迭代差分模式特征

Feistel-SP結(jié)構(gòu)4輪迭代差分特征滿足如下形式：

A:([0]，[ΔX])

B:[ΔY]←[ΔX]

C:[ΔX⊕ΔX′]←[ΔY]

D:[ΔY]←[ΔX′]

([ΔX′],[0])

Feistel-SP4輪迭代差分結(jié)構(gòu)如圖3所示。

Figure 3 Differential structure of 4 round iteration

從特征B、D可以看出,Sign(ΔX)=Sign(ΔX′),且ΔX⊕ΔX′≠0,否則C輪的概率為0,我們發(fā)現(xiàn)4輪迭代特征中不可能只有一個(gè)活躍S盒,在此基礎(chǔ)上構(gòu)造出了4輪迭代差分模式的自動(dòng)化搜索算法，進(jìn)而搜索出概率最高的迭代差分特征。

Feistel-SP結(jié)構(gòu)4輪迭代模式算法偽代碼如下：

1.差分變量ΔX、ΔX′、ΔZ，聯(lián)系關(guān)系為：Sign(ΔX′)=Sign(ΔZ);

3. For選取輸入差分ΔX的一種情況 do

4. For選取輸出差分ΔX′的一種情況 do

5. 分別對(duì)ΔX、ΔX′求線性變換逆變變換存入臨時(shí)變量Temp_X、Temp_X′;

6.Z求線性正變換輸出為ΔY;

7.if(Sign(Temp_X)==Sign(ΔY)&&Sign(Temp_X′)==Sign(ΔY)) Then

8. 找出最小活躍S盒個(gè)數(shù)，把滿足條件的差分變量ΔX、ΔX′、ΔZ存儲(chǔ)起來，計(jì)數(shù)器加1;

9.Continue

同樣以MIBS算法為例，我們搜索出所有的4輪迭代差分模式,得到4輪最優(yōu)迭代差分特征，其最小活躍S盒個(gè)數(shù)為11，概率為2-26。下面列舉了部分最優(yōu)迭代差分模式和最優(yōu)迭代差分路徑數(shù)據(jù)。表5為最優(yōu)的迭代差分模式，表6為最優(yōu)的迭代路徑。

Table 5 Optimal differential mode for 4 rounds iteration

Table 6 Optimal differential path for 4 rounds iteration

5 結(jié)束語

本文提出了一種新的符號(hào)差分表示法，在此基礎(chǔ)上構(gòu)建了自動(dòng)化搜索工具，應(yīng)用于搜索MIBS分組密碼的迭代差分模式，其方法對(duì)于其他總體結(jié)構(gòu)是Feistel結(jié)構(gòu)、輪函數(shù)是SP結(jié)構(gòu)的分組密碼也是適用的，例如Camellia和E2[9]等。對(duì)于Feistel-SP結(jié)構(gòu)的分組密碼，我們只要替換輪函數(shù)的線性部分，自動(dòng)化搜索機(jī)就能找到3、4輪最優(yōu)迭代差分模式和迭代差分特征。應(yīng)用本文提出的自動(dòng)化搜索技術(shù)，不僅能重新發(fā)現(xiàn)在字節(jié)上、比特位上的最大差分概率，還能找到其他未知的結(jié)果。這種攻擊方法給算法的設(shè)計(jì)帶來更多的啟發(fā)，不僅有利于提升分組密碼抵御差分分析的能力，而且有利于抵御其他攻擊的分析方法。

為了能更好地完善自動(dòng)化搜索工具，下一步工作我們會(huì)尋找Feistel-SP結(jié)構(gòu)更加普遍的關(guān)系式，以便尋找出更多輪的最優(yōu)迭代差分模式和迭代差分特征。

[1]FeistelH,WANotz,SmithJL.Somecryptographictechniquesformachine-to-machinedatacommunications[J].ProceedingoftheIEEE, 1975, 63(11):1545-1554.

[2]KandaM.PracticalsecurityevaluationagainstdifferentialandlinearcryptanalysesforfeistelcipherswithSPNroundfunction[C]∥ProcofSAC’00,2001:324-338.

[3]IzadiMI,SadeghiyanB,SadeghianS,etal.MIBS:Anewlightweightblockcipher[C]∥Procofthe8thInternationalConference,CANS’09, 2009:334-348.

[4]KandaM,MoriaiS,AokiK,etal.E2-Anew128-bitblockcipher[J].IEICETransactionsonFundamentalsofElectronics,CommunicationsandComputerSciences, 2000,E83-A(1):48-59.

[5]AokiK,IchikawaT,KandaM,etal.Camellia:A128-bitblockciphersuitableformultipleplatforms-designandanalysis[C]∥ProcofSAC’00, 2001:39-56.

[6]LiChao,SunBing,LiRui-lin.Attackmethodsandcaseanalysisofblockcipher[M].Beijing,SciencePublishingHouse, 2010.(inChinese)

[7]MatsuiM.LinearcryptanalysismethodforDEScipher[C]∥ProcofWorkshopontheTheoryandApplicationofCrytographicTechniquesonAdvancesinCryptology, 1994:386-397.

[8]LiChao,ShenJing.Differentialandlineariterativecharacteristicofcamellia[J].ChineseofJournalElectronics, 2005,33(8):1345-1348.(inChinese)

[9]NTT-NipponTelegraphandTelephoneCorporation.E2:Effcientencryptionalgorithm[EB/OL].[2013-05-13].http://info.isl.ntt.co.jp/e2.

附中文參考文獻(xiàn)：

[6] 李超,孫兵,李瑞林.分組密碼的攻擊方法與實(shí)例分析[M].北京, 科學(xué)出版社,2010.

[8] 李超, 沈靜.Camellia的差分和線性迭代特征[J].電子學(xué)報(bào),2005,33(8):1345-1348.

LI Yan-jun,born in 1979,PhD,lecturer,her research interest includes design and analysis of block cipher.

方波(1989-),男，浙江杭州人，碩士生，研究方向?yàn)榉纸M密碼的自動(dòng)化搜索技術(shù)。E-mail:bluepooh@126.com

FANG Bo,born in 1989,MS candidate,his research interest includes automated searching of block cipher.

Automated search of iterative differential mode with feistel-SP structure

LI Yan-jun1,FANG Bo1,2,MAO Ming1,2

(1.School of Telecommunications Engineering,Xidian University,Xi’an 710071;2.Beijing Electronic Science and Technology Institute,Beijing 100070,China)

Based on a new symbol differential representation,an automated search technique is presented,which can search out the optimal iterative differential mode of the block cipher with Feistel-SP structure.Selection of an appropriate mode can help find out all of the best iterative differential paths.The proposed method can not only greatly reduce the computational complexity,but also construct several rounds of optimal differential paths and find other unknown results. Based on the lightweight block cipher MIBS with automated search tools,the third and fourth optimaliterative differential paths of MIBS are found out, and the probabilities are 2-20and 2-26respectively.In addition,all the optimal iterative differential paths that meet the conditions are searched out.

Feistel-SP;MIBS;automated search;symbol differential;iterative differential

1007-130X(2015)03-0466-05

2013-11-18;

2014-03-01基金項(xiàng)目：中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(1201120703，YQNJ1003)

TP393.84

A

10.3969/j.issn.1007-130X.2015.03.009

李艷俊(1979-),女，山西晉城人，博士，講師，研究方向?yàn)榉纸M密碼設(shè)計(jì)與分析。E-mail:Lyj@besti.edu.cn

通信地址：100070 北京市豐臺(tái)區(qū)富豐路7號(hào)北京電子科技學(xué)院

Address:Beijing Electronic Science and Technology Institute,7 Fufeng Rd,Fengtai District,Beijing 100070,P.R.China