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算法，时间复杂度为2^71.3次全轮加密，数据复杂度为2^71.28个选择明文；张鹏等^[3]利用Zodiac的等价结构找到了两个新的9轮Square区分器，利用新的区分器攻击了全轮Zodiac，其时间复杂度为2^189.5次全轮加密，数据复杂度为2^12.6个选择明文；孙兵等^[4]构造了一个16轮的不可能差分以及一个9轮的积分区分器，并在此区分器前面增加1轮，后面增加6轮，实现对全轮Zodiac算法的积分攻击，其时间复杂度为2¹⁹⁰次全轮加密，数据复杂度为2¹⁶个选择明文；海昕等^[5]利用中间相遇攻击分析Zodiac算法，找到了一个10轮的区分器，对全轮Zodiac算法进行了攻击，其时间复杂度为2^105.3次全轮加密，数据复杂度为2^28.9个选择明文，其预计算所需要的时间复杂度为2^121.9次全轮加密。

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

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

1 预备知识 1.1 符号说明

‖：表示两个比特串的连接；⊕：异或运算；$ \circ $：表示两个比特串的内积； M：矩阵；M^T：矩阵的转置；L_i(1≤i≤16) 表示第i轮输入左半64 bit，L_i^j(0≤j≤7) 表示其第j+1个字节；R_i表示第i轮输入右半64 bit，R_i^j表示其第j+1个字节；K_i^j(0≤j≤7) 表示第i轮密钥的第j+1个字节。

1.2 Zodiac算法简介

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

设算法的明文输入为P=(L, R)∈($ \mathbb{F}$₂⁶⁴)²，第i轮的输入和输出分别为(L_i－1, R_i－1)和(L_i, R_i)，则(L₀, R₀)=T(P)⊕(K₀, 0)。Zodiac算法第1到第15轮变换是相同的，定义为：

$ \left\{ {\begin{array}{*{20}{l}} {{L_i} = F({L_{i-1}} \oplus {K_i}) \oplus {R_{i-1}}}\\ {{R_i} = {L_{i-1}}} \end{array}} \right.;\;\;\;\;1 \le i \le 15 $

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

$ \left\{ \begin{array}{l} {L_{16}} = {L_{15}} \oplus {K_{17}}\\ {R_{16}} = F({L_{15}} \oplus {K_{15}}) \oplus {R_{15}} \end{array} \right. $

密文为：

C=T(L₁₆, R₁₆)

每一轮变换分别由密钥加K、线性变换P、非线性变换S构成。轮函数的定义为：F(X)=S(P(X))，其中X为64 bit，可按字节表示为X=(x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇)，P为线性变换，它将X=(x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇)变换为Y=(y₀, y₁, y₂, y₃, y₄, y₅, y₆, y₇)：y₀=x₂⊕x₃⊕x₄，y₁=x₀⊕x₁，y₂=x₁⊕x₂，y₃=x₂⊕x₃，y₄=x₀⊕x₆⊕x₇，y₅=x₄⊕x₅，y₆=x₅⊕x₆，y₇=x₆⊕x₇。

S为非线性变换，将Y=(y₀, y₁, y₂, y₃, y₄, y₅, y₆, y₇)变换为Z=(z₀, z₁, z₂, z₃, z₄, z₅, z₆, z₇)：z₀=S₁(y₀)，z₁=S₂(y₁)，z₂=S₁(y₂)，z₃=S₂(y₃)，z₄=S₁(y₄)，z₅=S₂(y₅)，z₆=S₁(y₆)，z₇=S₂(y₇)。其中S₁和S₂均是$\mathbb{F} $₂⁸→ $\mathbb{F} $₂⁸的非线性变换(S盒)。

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

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

对于给定的 n bit长的输入掩码α和输出掩码β以及$ \mathbb{F}$₂ⁿ上的函数f，定义相应的线性逼近为($ (\alpha \xrightarrow{f}\beta )$)，可简记为(α→β)^[12]。该线性逼近的相关系数定义为：

C_f(α, β)=Cor_x(β·f(x)⊕α·x)=2Pr_x(β·f(x)⊕α·x=0)－1

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

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

$ \begin{gathered} z = (z[0],z[1], \cdots ,z[m - 1]) = \hfill \\ ({a_0} \cdot p' \oplus {b_0} \cdot c',{a_1} \cdot p' \oplus {b_1} \cdot c' \cdots {a_{m - 1}} \cdot p' \oplus {b_{m - 1}} \cdot c') \hfill \\ \end{gathered} $

(1)

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

$ T = \sum\limits_{z = 0}^{2m- 1} {\frac{{{{(N[z] - N{2^{ - {\text{m}}}})}^2}}}{{N{2^{ - {\text{m}}}}(1 - {2^{ - m}})}}} \approx N{2^m}\sum\limits_{z = 0}^{{2^m} - 1} {(\frac{{N[z]}}{N} -\frac{1}{{{2^m}}})} $

(2)

若所猜测的密钥为正确密钥，则统计量T服从期望为${\mu _0} = (l-1)\frac{{{2^n}-N}}{{{2^n}-1}} $、方差为$ \sigma _0^2 = 2(l-1){(\frac{{{2^n}-N}}{{{2^n}-1}})^2}$的正态分布。若猜测的密钥为错误密钥，则统计量T服从期望为μ₁=l－1、方差为σ₁²=2(l－1) 的正态分布。此处定义把正确密钥当作错误密钥的概率为α，把错误密钥当作正确密钥的概率为β，其判定条件为T≤τ，其中τ=μ₀+σ₀z_1－α=μ₁－σ₀z_1－β，则攻击所需要的明密文对可由式(3) 计算，大体为：

$ N = \frac{{({2^n}-1)({z_{1-\alpha }} + {z_{1-\beta }})}}{{\sqrt {(l - 1)/2} + {z_{1 - \alpha }}}} + 1 $

(3)

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

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

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

命题1^[6]   线性映射的线性逼近相关度。对线性映射h(x)=M·x，若α=M^T·β, 则C_{α, β}^h=1：若α≠M^T·β，则C_{α, β}^h=0。

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

引理1^[14]   异或运算。如果h(x₁, x₂)=x₁⊕x₂，那么C(β$ \circ $h(x₁, x₂), α₁$ \circ $x₁⊕α₂$ \circ $x₂)≠0，当且仅当β=α₁=α₂。

引理2^[14]   分支操作。如果h(x)=(x, x)，那么C((β₁, β₂)$ \circ $h(x), α$ \circ $x)≠0，当且仅当α=β₁⊕β₂。

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

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

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

证明  如图 2所示，图中设定“0”表示零掩码；b、c_i、d_i、e_i、f、g_i、l_i(0≤i≤7) 表示非零掩码；“?”表示不确定是零或非零的掩码。从加密方向，若第r轮的输入掩码为(000a000000000000)，向加密方向经过5轮迭代，在非零相关系数条件下第r+4轮左侧输出掩码为(0c₂(c₂⊕c₃)(c₃⊕a)0000)⊕(????e₀000)，则其第8个字节为0掩码；若第r+9轮的输出掩码为(00000000000000h0)，向解密方向经过5轮迭代，在非零相关系数条件下第r+5轮右侧输入掩码为l₄000??(l₄⊕l₆⊕f)l₄，则其第8个字节为非0掩码，与第r+4轮的状态相矛盾。

证毕。

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

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

3.1 攻击过程

1) 首先， 取x₀=L₁^{0, 1, 2, 3}‖R₁^{1, 2, 3}‖L_out^{0, 4, 5, 6, 7}‖R_out^{4, 5, 6}，则x₀共有2¹²⁰种状态，对每一种状态建立一个24 bit计数器N₀[x₀]，且全部初始化为零。收集N个明文及对应的密文，并计算这些明密文对中满足每个状态的对数，相应的计数器N₀[x₀]加1，此步骤大致需要N次内存读取。

2) 取x₁=L₁^{2, 3}‖L₂¹‖L₂²‖L₂³‖L_out^{0, 4, 5, 6, 7}‖R_out^{4, 5, 6}，则x₁共有2¹⁰⁴种状态，对每一种状态建立一个24 bit计数器N₁[x₁]，且全部初始化为零。穷举32 bit轮子密钥K₁^{0, 1, 2, 3}，计算并更新：L₂¹=S[(L₁⁰⊕K₁⁰)⊕(L₁¹⊕K₁¹)]⊕R₁¹；L₂²=S[(L₁¹⊕K₁¹)⊕(L₁²⊕K₁²)]⊕R₁²；L₂³=S[(L₁²⊕K₁²)⊕(L₁³⊕K₁³)]⊕R₁³。然后累加计数器N₁[x₁]+=N₀[x₀]。此步骤大致需要2¹²⁰×2³²次内存访问。

3) 取x₂=L₂³‖L₃²‖L₃³‖L_out^{0, 4, 5, 6, 7}‖R_out^{4, 5, 6}，则x₂共有2⁸⁸种状态，对每一种状态建立一个24 bit计数器N₂[x₂]，且全部初始化为零。穷举24 bit轮子密钥K₂^{1, 2, 3}，计算并更新：L₃²=S[(L₂¹⊕K₂¹)⊕(L₂²⊕K₂²)]⊕L₁²；L₃³=S[(L₂²⊕K₂²)⊕(L₂³⊕K₂³)]⊕L₁³。然后累加计数器N₂[x₂]+=N₁[x₁]。此步骤大致需要2¹⁰⁴×2³²×2²⁴次内存访问。

4) 取x₃=L₄³‖L_out^{0, 4, 5, 6, 7}‖R_out^{4, 5, 6}，则x₃共有2⁷²种状态，对每一种状态建立一个24 bit计数器N₃[x₃]，且全部初始化为零。穷举16 bit轮子密钥K₃^{2, 3}，计算并更新L₄³=S[(L₃²⊕K₃²)⊕(L₃³⊕K₃³)]⊕L₂³，然后累加计数器N₃[x₃]+=N₂[x₂]。此步骤大致需要2⁸⁸×2⁵⁶×2¹⁶次内存访问。

5) 取x₄=L₄³‖L₁₅⁴‖L₁₅⁵‖L₁₅⁶‖L_out^{5, 6}，则x₄共有2⁴⁸种状态，对每一种状态建立一个24 bit计数器N₄[x₄]，且全部初始化为零。穷举40 bit轮子密钥K₁₆^{0, 4, 5, 6, 7}，计算并更新：L₁₅⁴=S[(L_out⁰⊕K₁₆⁰)⊕(L_out⁶⊕K₁₆⁶)⊕(L_out⁷⊕K₁₆⁷)]⊕R_out⁴；L₁₅⁵=S[(L_out⁴⊕K₁₆⁴)⊕(L_out⁵⊕K₁₆⁵)]⊕R_out⁵；L₁₅⁶=S[(L_out⁵⊕K₁₆⁵)⊕(L_out⁶⊕K₁₆⁶)]⊕R_out⁶，然后累加计数器N₄[x₄]+=N₃[x₃]。此步骤大致需要2⁷²×2⁷²×2⁴⁰次内存访问。

6) 取x₅=L₄³‖L₁₅⁶‖L₁₄⁵‖L₁₄⁶，则x₅共有2³²种状态，对每一种状态建立一个24 bit计数器N₅[x₅]，且全部初始化为零。穷举24 bit轮子密钥K₁₅^{4, 5, 6}，计算并更新L₁₄⁵=S[(L₁₅⁴⊕K₁₅⁴)⊕(L₁₅⁵⊕K₁₅⁵)]⊕L_out⁵；L₁₄⁶=S[(L₁₅⁵⊕K₁₅⁵)⊕(L₁₅⁶⊕K₁₅⁶)]⊕L_out⁶，然后累加计数器N₅[x₅]+=N₄[x₄]。此步骤大致需要2⁴⁸×2¹¹²×2²⁴次内存访问。

7) 取x₆=L₄³‖R₁₄⁶，则x₆共有2¹⁶种状态，对每一种状态建立一个24 bit计数器N₆[x₆]，且全部初始化为零。穷举16 bit轮子密钥K₁₄^{5, 6}，计算并更新R₁₄⁶=S[(L₁₄⁵⊕K₁₄⁵)⊕(L₁₄⁶⊕K₁₄⁶)]⊕L₁₅⁶，然后累加计数器N₆[x₆]+=N₅[x₅]。此步骤大体需要2³²×2¹³⁶×2¹⁶次内存访问。

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

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

3.2 攻击复杂度

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

4 结语

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