Zodiac—128算法的多维零相关线性分析

程璐

摘 要 分组密码算法Zodiac支持3种密钥长度，分别为Zodiac-128、Zodiac-192、Zodiac-256。该文首次利用零相关线性分析方法评估了Zodiac算法的安全性，首先根据算法的结构特性，构造了一些关于Zodiac算法的10轮零相关线性逼近，然后对14轮Zodiac-128进行了多维零相关分析。其结果显示：攻击过程中一共恢复了10个字节的密钥，大体需要2123.04個明密文对，计算复杂度为2109.19次14轮加密。由此可得：14轮128比特密钥的Zodiac算法（Zodiac-128）对于零相关线性分析方法是不安全的。

【关键词】分组密码 Zodiac密码算法 线性掩码 线性逼近 零相关线性分析

1 预备知识

1.1 Zodiac算法简介

Zodiac算法的主体结构采用Feistel结构，共16轮迭代。在第一轮迭代之前有一个初始置换T，在最后一轮迭代之后有一个末置换T，并且在迭代前后分别异或于一个白化密钥，其中：K0，K17为64bit的白化密钥，为第i轮的轮密钥，F为轮函数。每一轮变换分别由密钥加K、线性变换P、非线性变换S构成。轮函数的定义为：，其中X为64bit，可按字节表示为，P为线性变换，S为非线性变换。

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

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

证明 设定"0"表示零掩码；表示非零掩码；"？"表示不确定是零或非零的掩码。从加密方向，若第r轮的输入掩码为，向加密方向经过5轮迭代，在非零相关系数条件下第r+4轮左侧输出掩码为，则其第8个字节为0掩码；若第r+9轮的输出掩码为，向解密方向经过5轮，在非零相关系数条件下第r+5轮右侧输入掩码为，则其第8个字节为非0掩码，与第r+4轮的状态相矛盾。证毕。

3 14轮Zodiac-128的多维零相关分析

本章主要利用构造的10轮（第3轮-第12轮）零相关线性逼近，并且往前扩展2轮往后扩展2轮，对14轮Zodiac-128作多维零相关线性分析，分析过程中不考虑初始置换和末置换以及白化密钥的影响。

3.1 攻击过程

（1）首先，取，则x0共有280种状态，对每一种状态建立一个48bit计数器，且全部初始化为零。收集N个明文及对应的密文，并计算这些明密文对中满足每个状态的对数，相应的计数器加1，此步骤大致需要N次内存读取。

（2）取，则x1共有264种状态，对每一种状态建立一个16bit计数器，且全部初始化为零。穷举24bit轮子密钥，计算并更新；；然后累加计数器。此步骤大致需要次内存访问。

（3）取，则x2共有248种状态，对每一种状态建立一个16bit计数器，且全部初始化为零。穷举16bit轮子密钥，计算并更新，然后累加计数器。此步骤大致需要次内存访问。

（4）取，则x3共有232种状态，对每一种状态建立一个16bit计数器，且全部初始化为零。穷举24bit轮子密钥，计算并更新；，然后累加计数器。此步骤大致需要次内存访问。

（5）取，则x4共有216种状态，对每一种状态建立一个16bit计数器，且全部初始化为零。穷举16bit轮子密钥，计算并更新，然后累加计数器。此步骤大致需要次内存访问。

（6）是16bit向量，为每一个可能的建立一个16bit计数器，且全部初始化为零。对于16个长度为16bit的基础向量，即1是第i+1个比特为1，其他比特为0的向量。计算，，并且计算，然后累加计数器。根据式（2），计算统计量T。

（7）如果，则所猜测的轮子密钥可能为正确密钥，穷尽搜索所有可能的正确密钥。

4 结语

本文主要评估了Zodiac密码算法关于多维零相关线性分析方法的安全性。首先利用Zodiac算法结构特点，构造了10轮零相关线性逼近，之后对14轮的Zodiac-128进行了多维零相关线性分析。整个攻击过程中共恢复了10个字节的密钥，所以，14轮Zodiac-128对多维零相关线性分析是不安全的。进一步的研究方向就是通过分析算法的结构特点、密钥扩展算法等来降低其数据复杂度。

参考文献

[1]LEE C，JUN K，and JUNG M，et al.Zodiac version1.0（revised） architecture and specification Standardization Workshop on Information Security Technology， Korean Contribution on MP18033，ISO/IEC JTC1/SC27 N2563，2000.http：//www.kisa.or.k ndex.html.

[2]BOGDANOV A，RIJMEN V.Linear hulls with correlation zero and linear cryptanalysis of block ciphers [J].Designs，Codes and Cryptography，2014，70（03）：369-383.

[3]BOGDANOV A，WANG M.Zero correlation linear cryptanalysis with reduced data complexity[C].FSE 2012， Washington，DC，USA，2012：29-48.

[4]BOGDANOV A，LEANDER G，NYBERG K，et al.Integral and multidimensional linear distinguishers with correlation zero [C]// Proceedings of the ASIACRYPT 2012，Beijing， China，2012：244-261.

作者单位

武警工程大学 陕西省西安市 710086endprint