Zodiac密碼算法的多維零相關(guān)線(xiàn)性分析

程 璐，魏悅川，潘曉中，李安輝

(1.武警工程大學(xué) 電子技術(shù)系,西安 710086; 2.網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室,西安 710086)

Zodiac密碼算法的多維零相關(guān)線(xiàn)性分析

程 璐1,2*，魏悅川1,2，潘曉中1,2，李安輝1,2

(1.武警工程大學(xué) 電子技術(shù)系,西安 710086; 2.網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室,西安 710086)

(*通信作者電子郵箱18302972151@163.com)

分組密碼算法Zodiac支持3種密鑰長(zhǎng)度，分別為Zodiac-128、Zodiac-192、Zodiac-256。利用零相關(guān)線(xiàn)性分析方法評(píng)估了Zodiac算法的安全性，首先根據(jù)算法的結(jié)構(gòu)特性，構(gòu)造了一些關(guān)于Zodiac算法的10輪零相關(guān)線(xiàn)性逼近，然后對(duì)16輪Zodiac-192進(jìn)行了多維零相關(guān)分析。分析結(jié)果顯示：攻擊過(guò)程中一共恢復(fù)了19個(gè)字節(jié)的密鑰，其數(shù)據(jù)復(fù)雜度約為2124.40個(gè)明密文對(duì)，計(jì)算復(fù)雜度為2181.58次16輪加密。由此可得：16輪(即全輪)192 bit密鑰的Zodiac算法(Zodiac-192)對(duì)于零相關(guān)線(xiàn)性分析方法是不安全的。

分組密碼；Zodiac密碼算法；線(xiàn)性掩碼；線(xiàn)性逼近；零相關(guān)線(xiàn)性分析

0 引言

Zodiac是分組密碼算法的代表之一，由韓國(guó)專(zhuān)家Lee等[1]于2000年為韓國(guó)公司SoftForum所設(shè)計(jì)。Zodiac算法是典型的Feistel結(jié)構(gòu)，共有16輪迭代。其明文分組長(zhǎng)度為128 bit，密鑰長(zhǎng)度有三種128 bit、192 bit、256 bit，分別可記作Zodiac-128、Zodiac-192、Zodiac-256[12]。目前針對(duì)Zodiac的分析有不可能差分分析、積分分析和中間相遇分析等。

目前對(duì)Zodiac最好的分析結(jié)果是不可能差分分析， Shakiba等[2]利用2個(gè)13輪的不可能差分，攻擊全輪Zodiac算法，時(shí)間復(fù)雜度為271.3次全輪加密，數(shù)據(jù)復(fù)雜度為271.28個(gè)選擇明文；張鵬等[3]利用Zodiac的等價(jià)結(jié)構(gòu)找到了兩個(gè)新的9輪Square區(qū)分器，利用新的區(qū)分器攻擊了全輪Zodiac，其時(shí)間復(fù)雜度為2189.5次全輪加密，數(shù)據(jù)復(fù)雜度為212.6個(gè)選擇明文；孫兵等[4]構(gòu)造了一個(gè)16輪的不可能差分以及一個(gè)9輪的積分區(qū)分器，并在此區(qū)分器前面增加1輪，后面增加6輪，實(shí)現(xiàn)對(duì)全輪Zodiac算法的積分攻擊，其時(shí)間復(fù)雜度為2190次全輪加密，數(shù)據(jù)復(fù)雜度為216個(gè)選擇明文；海昕等[5]利用中間相遇攻擊分析Zodiac算法，找到了一個(gè)10輪的區(qū)分器，對(duì)全輪Zodiac算法進(jìn)行了攻擊，其時(shí)間復(fù)雜度為2105.3次全輪加密，數(shù)據(jù)復(fù)雜度為228.9個(gè)選擇明文，其預(yù)計(jì)算所需要的時(shí)間復(fù)雜度為2121.9次全輪加密。

由前面的描述可以看出，為評(píng)估Zodiac算法的安全性，研究者們已經(jīng)做了很多工作。然而，Zodiac對(duì)于零相關(guān)線(xiàn)性分析的結(jié)果還是空白。零相關(guān)線(xiàn)性分析方法由Bogdanov等[6]在2012年第一次提出，其最大缺陷是攻擊所需數(shù)據(jù)復(fù)雜度較高。為了進(jìn)一步降低數(shù)據(jù)復(fù)雜度，Bogdanov等[7]于FSE2012(International Conference on Fast Software Encryption)提出利用多條零相關(guān)線(xiàn)性逼近區(qū)分統(tǒng)計(jì)分布的理論模型，即多重零相關(guān)線(xiàn)性分析，但是要求多條零相關(guān)線(xiàn)性逼近相互獨(dú)立，此假設(shè)是很難滿(mǎn)足的。Bogdanov等[8]于A(yíng)SIACRYPT2012提出多維零相關(guān)線(xiàn)性分析的模型，克服了多重零相關(guān)線(xiàn)性分析所要求的強(qiáng)假設(shè)條件，所需數(shù)據(jù)量和多重零相關(guān)基本相當(dāng)，進(jìn)一步完善了零相關(guān)線(xiàn)性分析模型。零相關(guān)線(xiàn)性分析模型的有效性，在對(duì)AES[6]、LBlock[9]、TWINE[9]、E2[10]、SMS4[11]、FOX[12]及MIBS[13]等一系列重要密碼算法的分析中得到了驗(yàn)證，因此利用零相關(guān)線(xiàn)性分析來(lái)評(píng)估部分分組密碼算法的安全性，是當(dāng)前分組密碼分析的一個(gè)熱點(diǎn)。

本文首次利用零相關(guān)線(xiàn)性分析方法分析Zodiac密碼算法。根據(jù)Zodiac算法結(jié)構(gòu)特性，構(gòu)造了10輪零相關(guān)線(xiàn)性逼近，之后對(duì)16輪(全輪)的Zodiac-192進(jìn)行了多維零相關(guān)線(xiàn)性分析。整個(gè)攻擊過(guò)程共恢復(fù)了19個(gè)字節(jié)的密鑰，由此可得全輪Zodiac-192對(duì)于零相關(guān)線(xiàn)性分析方法是不安全的，而且其分析結(jié)果相比其他研究用不同方法進(jìn)行攻擊的部分結(jié)果有一定的優(yōu)化。

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

1.1 符號(hào)說(shuō)明

1.2Zodiac算法簡(jiǎn)介

Zodiac算法的主體結(jié)構(gòu)采用Feistel結(jié)構(gòu)，共16輪迭代。在第一輪迭代之前有一個(gè)初始置換T*，在最后一輪迭代之后有一個(gè)末置換T*，并且在迭代前后分別異或于一個(gè)白化密鑰，如圖1所示，其中：K0、K17為64 bit的白化密鑰，Ki(1≤i≤16)為第i輪的輪密鑰，F(xiàn)為輪函數(shù)。本文的分析中不考慮前后兩個(gè)置換，所以不作詳細(xì)介紹。

第16輪變換與之前不同，定義為：

密文為：

C=T(L16,R16)

每一輪變換分別由密鑰加K、線(xiàn)性變換P、非線(xiàn)性變換S構(gòu)成。輪函數(shù)的定義為：F(X)=S(P(X))，其中X為64 bit，可按字節(jié)表示為X=(x0,x1,x2,x3,x4,x5,x6,x7)，P為線(xiàn)性變換，它將X=(x0,x1,x2,x3,x4,x5,x6,x7)變換為Y=(y0,y1,y2,y3,y4,y5,y6,y7)：y0=x2⊕x3⊕x4，y1=x0⊕x1，y2=x1⊕x2，y3=x2⊕x3，y4=x0⊕x6⊕x7，y5=x4⊕x5，y6=x5⊕x6，y7=x6⊕x7。

由于本文分析中沒(méi)有考慮主密鑰與輪子密鑰以及輪子密鑰之間的聯(lián)系，所以Zodiac算法的密鑰擴(kuò)展算法在此不作介紹，具體可參見(jiàn)文獻(xiàn)[1]。

圖1 Zodiac算法的加密結(jié)構(gòu)

1.3 多維零相關(guān)線(xiàn)性分析方法

Cf(α,β)=Corx(β·f(x)⊕α·x)= 2Prx(β·f(x)⊕α·x=0)-1

若Cf(α,β)=0，則稱(chēng)該線(xiàn)性逼近是零相關(guān)線(xiàn)性逼近。

多維零相關(guān)線(xiàn)性分析[8]方法選取l=2m個(gè)零相關(guān)線(xiàn)性逼近，并且這些線(xiàn)性逼近由m條相互獨(dú)立的線(xiàn)性逼近通過(guò)線(xiàn)性關(guān)系擴(kuò)展。不妨記作為(ai→bi)i=0,1,…，m-1。攻擊者選擇N對(duì)明密文對(duì)，并建立計(jì)數(shù)器N[z]，其中z是mbit長(zhǎng)的字符串。通過(guò)在線(xiàn)性逼近前后加輪，窮舉部分子密鑰并部分加解密所選取的明密文對(duì)，得到線(xiàn)性掩碼首尾對(duì)應(yīng)的中間狀態(tài)，為了方便記作(p′,c′)[12]。然后，對(duì)于選擇的每一個(gè)明密文對(duì)經(jīng)過(guò)部分加解密得到(p′,c′)，通過(guò)式(1)得到z的值：

z=(z[0],z[1],…，z[m-1])=(a0·p′⊕b0·c′,a1·p′⊕b1·c′，…，am-1·p′⊕bm-1·c′)

(1)

更新相應(yīng)的計(jì)數(shù)器N[z]。然后，計(jì)算統(tǒng)計(jì)量T：

(2)

(3)

其中：n是分組長(zhǎng)度；z1-α、z1-β為標(biāo)準(zhǔn)正態(tài)分布的分位數(shù)。對(duì)此方法更完整詳細(xì)的描述請(qǐng)參考文獻(xiàn)[8]。

2 Zodiac算法10輪零相關(guān)線(xiàn)性逼近

本文主要通過(guò)以下的方式來(lái)構(gòu)造零相關(guān)線(xiàn)性逼近：在相關(guān)系數(shù)非零條件下線(xiàn)性掩碼從前和從后兩個(gè)方向向中間傳播，最后在中間某個(gè)位置相遇，并且產(chǎn)生相關(guān)系數(shù)為零的矛盾狀態(tài)。在非零相關(guān)系數(shù)條件下線(xiàn)性掩碼在分組密碼各組件中有如下傳播規(guī)律。

根據(jù)命題1，能夠推導(dǎo)出在非零相關(guān)系數(shù)條件下線(xiàn)性掩碼在分組密碼各組件中的傳播規(guī)律。

引理1[14]異或運(yùn)算。如果h(x1,x2)=x1⊕x2，那么C(β°h(x1,x2),α1°x1⊕α2°x2)≠0，當(dāng)且僅當(dāng)β=α1=α2。

引理2[14]分支操作。如果h(x)=(x,x)，那么C((β1,β2)°h(x),α°x)≠0，當(dāng)且僅當(dāng)α=β1⊕β2。

引理3[14]可逆F操作。如果φ(x)為可逆函數(shù)，則C(β°φ(x),α°x)≠0，當(dāng)且僅當(dāng)α與β均為零或者均不為零。

利用這些規(guī)律，可以得到Zodiac的10輪零相關(guān)線(xiàn)性逼近。

設(shè)a和h分別是8 bit長(zhǎng)的非零字符串，則(000a000000000000)→(00000000000000h0)是r輪到r+9輪的10輪零相關(guān)線(xiàn)性逼近。

證明 如圖2所示，圖中設(shè)定“0”表示零掩碼；b、ci、di、ei、f、gi、li(0≤i≤7)表示非零掩碼；“?”表示不確定是零或非零的掩碼。從加密方向，若第r輪的輸入掩碼為(000a000000000000)，向加密方向經(jīng)過(guò)5輪迭代，在非零相關(guān)系數(shù)條件下第r+4輪左側(cè)輸出掩碼為(0c2(c2⊕c3)(c3⊕a)0000)⊕(????e0000)，則其第8個(gè)字節(jié)為0掩碼；若第r+9輪的輸出掩碼為(00000000000000h0)，向解密方向經(jīng)過(guò)5輪迭代，在非零相關(guān)系數(shù)條件下第r+5輪右側(cè)輸入掩碼為l4000??(l4⊕l6⊕f)l4，則其第8個(gè)字節(jié)為非0掩碼，與第r+4輪的狀態(tài)相矛盾。

證畢。

3 16輪Zodiac-192的多維零相關(guān)分析

本章主要利用圖2中構(gòu)造的10輪(第4輪～第13輪)零相關(guān)線(xiàn)性逼近，并且往前擴(kuò)展3輪往后擴(kuò)展3輪，對(duì)16輪Zodiac-192作多維零相關(guān)線(xiàn)性分析，分析過(guò)程中不考慮初始置換和末置換以及白化密鑰的影響，如圖3所示。在圖3中，部分加解密所涉及到的狀態(tài)字節(jié)用“*”標(biāo)記，其他無(wú)關(guān)字節(jié)則用來(lái)“0”標(biāo)記。Lout、Rout分別表示異或白化密鑰K17之前第16輪左側(cè)的64bit輸出及右側(cè)64bit輸出。

3.1 攻擊過(guò)程

圖2 Zodiac的10輪零相關(guān)線(xiàn)性逼近

圖3 Zodiac的16輪零相關(guān)線(xiàn)性分析

8)z是16 bit字符串，為每一個(gè)可能的z建立一個(gè)24 bit計(jì)數(shù)器N[z]，且全部初始化為零。對(duì)于16個(gè)長(zhǎng)度為16 bit的zi(第i+1個(gè)比特為1、其他比特為0)。計(jì)算z[i]=zi·x6(0≤i≤15)，并且計(jì)算z，然后累加計(jì)數(shù)器N[z]+=N6[x6]。根據(jù)式(2)，計(jì)算統(tǒng)計(jì)量T。

9)如果T≤τ，則所猜測(cè)的輪子密鑰可能為正確密鑰，窮盡搜索所有可能的正確密鑰。

3.2 攻擊復(fù)雜度

在攻擊過(guò)程中，一共恢復(fù)了19個(gè)字節(jié)的密鑰，設(shè)α=2-2.7，β=2-152，則z1-α≈1，z1-β≈13.9。又因?yàn)閚=128，l=216，則由式(3)可得大體需要2124.40個(gè)明密文對(duì)。判斷的臨界值為τ≈215.89。在本文中，假設(shè)訪(fǎng)問(wèn)一次內(nèi)存的代價(jià)大約是一輪Zodiac-192加密，由于步驟5)～7)的復(fù)雜度占計(jì)算復(fù)雜度的主要部分，而它們的復(fù)雜度之和不超過(guò)2184×3×1/16≈2181.58次16輪加密。存儲(chǔ)復(fù)雜度計(jì)算主要集中于步驟1)，大約需要2121.58個(gè)字節(jié)。所以完成全輪的Zodiac-192攻擊需要得到數(shù)據(jù)復(fù)雜度為2124.40，計(jì)算復(fù)雜度為2181.58，沒(méi)有預(yù)計(jì)算復(fù)雜度。本文方法與其他攻擊方法的復(fù)雜度對(duì)比如表1所示。由表1的對(duì)比結(jié)果可知，目前對(duì)Zodiac算法最好的攻擊結(jié)果是不可能差分攻擊，而本文的零相關(guān)線(xiàn)性分析與Square攻擊和積分攻擊相比，在時(shí)間復(fù)雜度上有明顯優(yōu)化，與中間相遇攻擊相比，該方法不需要預(yù)計(jì)算復(fù)雜度。

表1 不同攻擊方法的復(fù)雜度對(duì)比

4 結(jié)語(yǔ)

本文主要評(píng)估了Zodiac密碼算法關(guān)于多維零相關(guān)線(xiàn)性分析方法的安全性。首先利用Zodiac算法結(jié)構(gòu)特點(diǎn)，構(gòu)造了10輪零相關(guān)線(xiàn)性逼近，然后對(duì)16輪(全輪)的Zodiac-192進(jìn)行了多維零相關(guān)線(xiàn)性分析。整個(gè)攻擊過(guò)程中共恢復(fù)了19個(gè)字節(jié)的密鑰，所以，16輪Zodiac-192對(duì)多維零相關(guān)線(xiàn)性分析是不安全的。通過(guò)與其他攻擊方法對(duì)比可以得出，本文方法在時(shí)間復(fù)雜度方面優(yōu)于Square攻擊和積分攻擊，與中間相遇攻擊比較，本文方法沒(méi)有預(yù)計(jì)算復(fù)雜度。但本文方法的數(shù)據(jù)復(fù)雜度明顯高于其他方法，進(jìn)一步研究將考慮通過(guò)分析算法的結(jié)構(gòu)特點(diǎn)、密鑰擴(kuò)展算法等來(lái)降低其數(shù)據(jù)復(fù)雜度。

)

[1]LEEC,JUNK,JUNGM,etal.Zodiacversion1.0 (revised)architectureandspecificationStandardizationWorkshoponInformationSecurityTechnology,KoreanContributiononMP18033,ISO/IECJTC1/SC27N2563, 2000[EB/OL]. [2016- 11- 20].http://www.kisa.or.kr/seed/index.html.

[2]SHAKIBAM,DAKHILALIANM,MALAH.AnimprovedimpossibledifferentialcryptanalysisofZodiac[J].JournalofSystemsandSoftware, 2010, 83(4): 702-709.

[3] 張鵬，李瑞林，李超.Zodiac算法新的Square攻擊[J].電子與信息學(xué)報(bào),2010,32(11):2790-2794.(ZHANGP,LIRL,LIC.NewsquareattackonZodiac[J].JournalofElectronics&InformationTechnology, 2010, 32(11): 2790-2794.)

[4] 孫兵，張鵬，李超.Zodiac算法的不可能差分和積分攻擊[J].軟件學(xué)報(bào)，2011,22(8):1911-1917.(SUNB,ZHANGP,LIC.ImpossibledifferentialandintegralcryptanalysisofZodiac[J].JournalofSoftware, 2011, 22(8): 1911-1917.)

[5] 海昕,唐學(xué)海,李超.對(duì)Zodiac算法的中間相遇攻擊[J].電子與信息學(xué)報(bào),2012,34(9):2259-2262.(HAIX,TANGXH,LIC.Themeet-in-the-middleattacksonZodiac[J].JournalofElectronics&InformationTechnology, 2012, 34(9): 2259-2262.)

[6]BOGDANOVA,RIJMENV.Linearhullswithcorrelationzeroandlinearcryptanalysisofblockciphers[J].Designs,CodesandCryptography, 2014, 70(3): 369-383.

[7]BOGDANOVA,WANGMQ.Zerocorrelationlinearcryptanalysiswithreduceddatacomplexity[C]//FSE’12:Proceedingsofthe19thinternationalconferenceonFastSoftwareEncryption.Berlin:Springer, 2012: 29-48.

[8]BOGDANOVA,LEANDERG,NYBERGK,etal.Integralandmultidimensionallineardistinguisherswithcorrelationzero[C]//ASIACRYPT’12:Proceedingsofthe18thInternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Berlin:Springer, 2012: 244-261.

[9] WANG Y F, WU W L. Improved multidimensional zero-correlation linear cryptanalysis and applications to LBlock and TWINE [C]// ACISP 2014: Proceedings of the 19th Australasian Conference on Information Security and Privacy, LNCS 8544. Berlin: Springer: 2014: 1-16.

[10] WEN L, WANG M Q, BOGDANOV A. Multidimensional zero-correlation linear cryptanalysis of E2 [C]// AFRICACRYPT 2014: Proceedings of the 7th International Conference on Cryptology in Africa, LNCS 8469. Berlin: Springer, 2014: 147-164.

[11] 馬猛,趙亞群,劉慶聰,等.SMS4算法的多維零相關(guān)線(xiàn)性分析[J].密碼學(xué)報(bào)，2015,2(5)：458-466.(MA M, ZHAO Y Q, LIU Q C, et al. Multidimensional zero-correlation linear cryptanalysis on SMS4 algorithm [J]. Journal of Cryptologic Research, 2015, 2(5): 458-466.)

[12] 伊文壇,陳少真.FOX密碼的多維零相關(guān)線(xiàn)性分析[J].密碼學(xué)報(bào)，2015,2(1):27-39.(YI W T, CHEN S Z. Multidimensional zero-correlation linear attacks on FOX block cipher [J]. Journal of Cryptologic Research, 2015, 2(1): 27-39.)

[13] 伊文壇,魯林真,陳少真.輕量級(jí)密碼算法 MIBS 的零相關(guān)和積分分析[J].電子與信息學(xué)報(bào),2016,38(4):819-826.(YI W T, LU L Z, CHEN S Z. Integral and zero-correlation linear cryptanalysis of lightweight block cipher MIBS [J]. Journal of Electronics & Information Technology, 2016, 38(4): 819-826.)

[14] 王美琴,溫隆.零相關(guān)線(xiàn)性分析研究[J].密碼學(xué)報(bào),2014,1(3):296-310.(WANG M Q, WEN L. Research on zero-correlation linear cryptanalysis [J]. Journal of Cryptologic Research, 2014, 1(3): 296-310.)

This work is partially supported by the National Natural Science Foundation of China (61202492，61572521), the Foundation of Science and Technology on Information Assurance Laboratory (KJ- 15- 010), the Natural Science Foundation of Shaanxi Province (2016JQ6030).

CHENG Lu, born in 1992, M. S. candidate. His research interests include information security, cryptology.

WEI Yuechuan, born in 1982, Ph. D., associate professor. Her research interests include cryptology.

PAN Xiaozhong, born in 1964, M. S., professor. His research interests include information security.

LI Anhui, born in 1993, M. S. candidate. His research interests include information security, complex network.

Multidimensional zero-correlation linear cryptanalysis on Zodiac cipher algorithm

CHENG Lu1,2*, WEI Yuechuan1,2, PAN Xiaozhong1,2, LI Anhui1,2

(1.DepartmentofElectronicTechnology,EngineeringCollegeoftheArmedPoliceForce,Xi’anShaanxi710086,China； 2.KeyLaboratoryofNetwork&InformationSecurityundertheChineseArmedPoliceForce,Xi’anShaanxi710086,China)

Zodiac is a block cipher algorithm and it supports 3 master key lengths which are called Zodiac-128, Zodiac-192 and Zodiac-256. The security of Zodiac algorithm was evaluated by using zero-correlation linear cryptanalysis. Firstly, 10-round zero-correlation linear approximations of Zodiac algorithm were constructed according to the structural characteristics of the algorithm. Then, the multidimensional zero-correlation linear cryptanalysis on 16-round Zodiac-192 was conducted. The analysis results show that 19-byte keys were restored totally in the process of attack, the data complexity was about 2124.40known ciphertexts and the computational complexity was 2181.58encryptions of 16-round. Thus the Zodiac-192 algorithm with the 192-bit key of 16 rounds (full rounds) is not immune to the zero-correlation linear cryptanalysis.

block cipher; Zodiac cipher algorithm; linear mask; linear approximation; zero-correlation linear cryptanalysis

2016- 12- 12;

2017- 02- 26。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61202492，61572521)；信息保障技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(KJ- 15- 010)；陜西省自然科學(xué)基金資助項(xiàng)目(2016JQ6030)。

程璐(1992—)，男，河北衡水人，碩士研究生，主要研究方向：信息安全、密碼學(xué)； 魏悅川(1982—)，女，天津人，副教授，博士，主要研究方向：密碼學(xué)； 潘曉中(1964—)，男，陜西西安人，教授，碩士，主要研究方向：信息安全； 李安輝(1993—)，男，湖南常德人，碩士研究生，主要研究方向：信息安全、復(fù)雜網(wǎng)絡(luò)。

1001- 9081(2017)06- 1605- 04

10.11772/j.issn.1001- 9081.2017.06.1605

TP309.2

A