Zodiac密码算法的多维零相关线性分析

程 璐，魏悦川，潘晓中，李安辉

(1.武警工程大学 电子技术系,西安 710086; 2.网络与信息安全武警部队重点实验室,西安 710086)

Zodiac密码算法的多维零相关线性分析

程 璐1,2*，魏悦川1,2，潘晓中1,2，李安辉1,2

(1.武警工程大学 电子技术系,西安 710086; 2.网络与信息安全武警部队重点实验室,西安 710086)

(*通信作者电子邮箱18302972151@163.com)

分组密码算法Zodiac支持3种密钥长度，分别为Zodiac-128、Zodiac-192、Zodiac-256。利用零相关线性分析方法评估了Zodiac算法的安全性，首先根据算法的结构特性，构造了一些关于Zodiac算法的10轮零相关线性逼近，然后对16轮Zodiac-192进行了多维零相关分析。分析结果显示：攻击过程中一共恢复了19个字节的密钥，其数据复杂度约为2124.40个明密文对，计算复杂度为2181.58次16轮加密。由此可得：16轮(即全轮)192 bit密钥的Zodiac算法(Zodiac-192)对于零相关线性分析方法是不安全的。

分组密码；Zodiac密码算法；线性掩码；线性逼近；零相关线性分析

0 引言

Zodiac是分组密码算法的代表之一，由韩国专家Lee等[1]于2000年为韩国公司SoftForum所设计。Zodiac算法是典型的Feistel结构，共有16轮迭代。其明文分组长度为128 bit，密钥长度有三种128 bit、192 bit、256 bit，分别可记作Zodiac-128、Zodiac-192、Zodiac-256[12]。目前针对Zodiac的分析有不可能差分分析、积分分析和中间相遇分析等。

目前对Zodiac最好的分析结果是不可能差分分析， Shakiba等[2]利用2个13轮的不可能差分，攻击全轮Zodiac算法，时间复杂度为271.3次全轮加密，数据复杂度为271.28个选择明文；张鹏等[3]利用Zodiac的等价结构找到了两个新的9轮Square区分器，利用新的区分器攻击了全轮Zodiac，其时间复杂度为2189.5次全轮加密，数据复杂度为212.6个选择明文；孙兵等[4]构造了一个16轮的不可能差分以及一个9轮的积分区分器，并在此区分器前面增加1轮，后面增加6轮，实现对全轮Zodiac算法的积分攻击，其时间复杂度为2190次全轮加密，数据复杂度为216个选择明文；海昕等[5]利用中间相遇攻击分析Zodiac算法，找到了一个10轮的区分器，对全轮Zodiac算法进行了攻击，其时间复杂度为2105.3次全轮加密，数据复杂度为228.9个选择明文，其预计算所需要的时间复杂度为2121.9次全轮加密。

由前面的描述可以看出，为评估Zodiac算法的安全性，研究者们已经做了很多工作。然而，Zodiac对于零相关线性分析的结果还是空白。零相关线性分析方法由Bogdanov等[6]在2012年第一次提出，其最大缺陷是攻击所需数据复杂度较高。为了进一步降低数据复杂度，Bogdanov等[7]于FSE2012(International Conference on Fast Software Encryption)提出利用多条零相关线性逼近区分统计分布的理论模型，即多重零相关线性分析，但是要求多条零相关线性逼近相互独立，此假设是很难满足的。Bogdanov等[8]于ASIACRYPT2012提出多维零相关线性分析的模型，克服了多重零相关线性分析所要求的强假设条件，所需数据量和多重零相关基本相当，进一步完善了零相关线性分析模型。零相关线性分析模型的有效性，在对AES[6]、LBlock[9]、TWINE[9]、E2[10]、SMS4[11]、FOX[12]及MIBS[13]等一系列重要密码算法的分析中得到了验证，因此利用零相关线性分析来评估部分分组密码算法的安全性，是当前分组密码分析的一个热点。

本文首次利用零相关线性分析方法分析Zodiac密码算法。根据Zodiac算法结构特性，构造了10轮零相关线性逼近，之后对16轮(全轮)的Zodiac-192进行了多维零相关线性分析。整个攻击过程共恢复了19个字节的密钥，由此可得全轮Zodiac-192对于零相关线性分析方法是不安全的，而且其分析结果相比其他研究用不同方法进行攻击的部分结果有一定的优化。

1 预备知识

1.1 符号说明

1.2Zodiac算法简介

Zodiac算法的主体结构采用Feistel结构，共16轮迭代。在第一轮迭代之前有一个初始置换T*，在最后一轮迭代之后有一个末置换T*，并且在迭代前后分别异或于一个白化密钥，如图1所示，其中：K0、K17为64 bit的白化密钥，Ki(1≤i≤16)为第i轮的轮密钥，F为轮函数。本文的分析中不考虑前后两个置换，所以不作详细介绍。

第16轮变换与之前不同，定义为：

密文为：

C=T(L16,R16)

每一轮变换分别由密钥加K、线性变换P、非线性变换S构成。轮函数的定义为：F(X)=S(P(X))，其中X为64 bit，可按字节表示为X=(x0,x1,x2,x3,x4,x5,x6,x7)，P为线性变换，它将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。

由于本文分析中没有考虑主密钥与轮子密钥以及轮子密钥之间的联系，所以Zodiac算法的密钥扩展算法在此不作介绍，具体可参见文献[1]。

图1 Zodiac算法的加密结构

1.3 多维零相关线性分析方法

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

若Cf(α,β)=0，则称该线性逼近是零相关线性逼近。

多维零相关线性分析[8]方法选取l=2m个零相关线性逼近，并且这些线性逼近由m条相互独立的线性逼近通过线性关系扩展。不妨记作为(ai→bi)i=0,1,…，m-1。攻击者选择N对明密文对，并建立计数器N[z]，其中z是mbit长的字符串。通过在线性逼近前后加轮，穷举部分子密钥并部分加解密所选取的明密文对，得到线性掩码首尾对应的中间状态，为了方便记作(p′,c′)[12]。然后，对于选择的每一个明密文对经过部分加解密得到(p′,c′)，通过式(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)

更新相应的计数器N[z]。然后，计算统计量T：

(2)

(3)

其中：n是分组长度；z1-α、z1-β为标准正态分布的分位数。对此方法更完整详细的描述请参考文献[8]。

2 Zodiac算法10轮零相关线性逼近

本文主要通过以下的方式来构造零相关线性逼近：在相关系数非零条件下线性掩码从前和从后两个方向向中间传播，最后在中间某个位置相遇，并且产生相关系数为零的矛盾状态。在非零相关系数条件下线性掩码在分组密码各组件中有如下传播规律。

根据命题1，能够推导出在非零相关系数条件下线性掩码在分组密码各组件中的传播规律。

引理1[14]异或运算。如果h(x1,x2)=x1⊕x2，那么C(β∘h(x1,x2),α1∘x1⊕α2∘x2)≠0，当且仅当β=α1=α2。

引理2[14]分支操作。如果h(x)=(x,x)，那么C((β1,β2)∘h(x),α∘x)≠0，当且仅当α=β1⊕β2。

引理3[14]可逆F操作。如果φ(x)为可逆函数，则C(β∘φ(x),α∘x)≠0，当且仅当α与β均为零或者均不为零。

利用这些规律，可以得到Zodiac的10轮零相关线性逼近。

设a和h分别是8 bit长的非零字符串，则(000a000000000000)→(00000000000000h0)是r轮到r+9轮的10轮零相关线性逼近。

证明 如图2所示，图中设定“0”表示零掩码；b、ci、di、ei、f、gi、li(0≤i≤7)表示非零掩码；“?”表示不确定是零或非零的掩码。从加密方向，若第r轮的输入掩码为(000a000000000000)，向加密方向经过5轮迭代，在非零相关系数条件下第r+4轮左侧输出掩码为(0c2(c2⊕c3)(c3⊕a)0000)⊕(????e0000)，则其第8个字节为0掩码；若第r+9轮的输出掩码为(00000000000000h0)，向解密方向经过5轮迭代，在非零相关系数条件下第r+5轮右侧输入掩码为l4000??(l4⊕l6⊕f)l4，则其第8个字节为非0掩码，与第r+4轮的状态相矛盾。

证毕。

3 16轮Zodiac-192的多维零相关分析

本章主要利用图2中构造的10轮(第4轮～第13轮)零相关线性逼近，并且往前扩展3轮往后扩展3轮，对16轮Zodiac-192作多维零相关线性分析，分析过程中不考虑初始置换和末置换以及白化密钥的影响，如图3所示。在图3中，部分加解密所涉及到的状态字节用“*”标记，其他无关字节则用来“0”标记。Lout、Rout分别表示异或白化密钥K17之前第16轮左侧的64bit输出及右侧64bit输出。

3.1 攻击过程

图2 Zodiac的10轮零相关线性逼近

图3 Zodiac的16轮零相关线性分析

8)z是16 bit字符串，为每一个可能的z建立一个24 bit计数器N[z]，且全部初始化为零。对于16个长度为16 bit的zi(第i+1个比特为1、其他比特为0)。计算z[i]=zi·x6(0≤i≤15)，并且计算z，然后累加计数器N[z]+=N6[x6]。根据式(2)，计算统计量T。

9)如果T≤τ，则所猜测的轮子密钥可能为正确密钥，穷尽搜索所有可能的正确密钥。

3.2 攻击复杂度

在攻击过程中，一共恢复了19个字节的密钥，设α=2-2.7，β=2-152，则z1-α≈1，z1-β≈13.9。又因为n=128，l=216，则由式(3)可得大体需要2124.40个明密文对。判断的临界值为τ≈215.89。在本文中，假设访问一次内存的代价大约是一轮Zodiac-192加密，由于步骤5)～7)的复杂度占计算复杂度的主要部分，而它们的复杂度之和不超过2184×3×1/16≈2181.58次16轮加密。存储复杂度计算主要集中于步骤1)，大约需要2121.58个字节。所以完成全轮的Zodiac-192攻击需要得到数据复杂度为2124.40，计算复杂度为2181.58，没有预计算复杂度。本文方法与其他攻击方法的复杂度对比如表1所示。由表1的对比结果可知，目前对Zodiac算法最好的攻击结果是不可能差分攻击，而本文的零相关线性分析与Square攻击和积分攻击相比，在时间复杂度上有明显优化，与中间相遇攻击相比，该方法不需要预计算复杂度。

表1 不同攻击方法的复杂度对比

4 结语

本文主要评估了Zodiac密码算法关于多维零相关线性分析方法的安全性。首先利用Zodiac算法结构特点，构造了10轮零相关线性逼近，然后对16轮(全轮)的Zodiac-192进行了多维零相关线性分析。整个攻击过程中共恢复了19个字节的密钥，所以，16轮Zodiac-192对多维零相关线性分析是不安全的。通过与其他攻击方法对比可以得出，本文方法在时间复杂度方面优于Square攻击和积分攻击，与中间相遇攻击比较，本文方法没有预计算复杂度。但本文方法的数据复杂度明显高于其他方法，进一步研究将考虑通过分析算法的结构特点、密钥扩展算法等来降低其数据复杂度。

)

[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].电子与信息学报,2010,32(11):2790-2794.(ZHANGP,LIRL,LIC.NewsquareattackonZodiac[J].JournalofElectronics&InformationTechnology, 2010, 32(11): 2790-2794.)

[4] 孙兵，张鹏，李超.Zodiac算法的不可能差分和积分攻击[J].软件学报，2011,22(8):1911-1917.(SUNB,ZHANGP,LIC.ImpossibledifferentialandintegralcryptanalysisofZodiac[J].JournalofSoftware, 2011, 22(8): 1911-1917.)

[5] 海昕,唐学海,李超.对Zodiac算法的中间相遇攻击[J].电子与信息学报,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算法的多维零相关线性分析[J].密码学报，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密码的多维零相关线性分析[J].密码学报，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] 伊文坛,鲁林真,陈少真.轻量级密码算法 MIBS 的零相关和积分分析[J].电子与信息学报,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] 王美琴,温隆.零相关线性分析研究[J].密码学报,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。 基金项目:国家自然科学基金资助项目(61202492，61572521)；信息保障技术国家重点实验室开放基金(KJ- 15- 010)；陕西省自然科学基金资助项目(2016JQ6030)。

程璐(1992—)，男，河北衡水人，硕士研究生，主要研究方向：信息安全、密码学； 魏悦川(1982—)，女，天津人，副教授，博士，主要研究方向：密码学； 潘晓中(1964—)，男，陕西西安人，教授，硕士，主要研究方向：信息安全； 李安辉(1993—)，男，湖南常德人，硕士研究生，主要研究方向：信息安全、复杂网络。

1001- 9081(2017)06- 1605- 04

10.11772/j.issn.1001- 9081.2017.06.1605

TP309.2

A