文档介绍：Zodiac
128算法的多维零相关线性分析
 
 
程璐
摘 要 分组密码算法Zodiac支持3种密钥长度，分别为Zodiac-128、Zodiac-192、Zodiac-256。该文首次利用零相关线性分析方法评估了Zodiac算法的安全性，首先根据算法的结构特性，构造了一些关于Zodiac算法的10轮零相关线性逼近，然后对14轮Zodiac-128进行了多维零相关分析。其结果显示：攻击过程中一共恢复了10个字节的密钥，，。由此可得：14轮128比特密钥的Zodiac算法（Zodiac-128）对于零相关线性分析方法是不安全的。
【关键词】分组密码 Zodiac密码算法 线性掩码 线性逼近 零相关线性分析
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作多维零相关线性分析，分析过程中不考虑初始置换和末置换以及白化密钥的影响。
攻击过程
（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