KATAN算法相关密钥的条件差分分析

摘要

KATAN密码算法是以非线性反馈移位寄存器为基础的分组密码算法，最初发表在CHES2009上。KATAN系列分组密码算法分为三类:KATAN32，KATAN48和KATAN64。这三个算法使用相同的密钥生成算法，密钥长度均为80比特，加密轮数都是254轮，并且使用相同的非线性函数。在KATAN系列算法中，除了算法主体使用非线性反馈移位寄存器外，254轮的轮计数器使用的是8级的线性反馈移位寄存器，而密钥生成算法是采用80级的线性反馈移位寄存器，将80比特密钥置入移存器，反馈多项式为80级的本原多项式，每轮80级移位寄存器运动两拍，来获得每轮对应的两比特子密钥。
　　本论文主要利用了KATAN算法的密钥生成算法的特性，思路如下:
　　第一步，搜索一条密钥差分路线，从而确定主密钥的密钥差分b，使得在r轮之后的尽量长的轮数，密钥不引入差分。
　　第二步，从r轮处逆推，通过控制明文和密钥的相关条件，来确定明文分组的明文差分a，使得密钥引入的差分b可以被明文差分抵消。这将确定一条明文的高概率的差分路线。
　　第三步，在逆推过程中，确定第二步中差分特征需要满足的条件。从而得到一个有效明文的样本空间和一些明文与密钥的关系约束条件。对于KATAN32来说，正是通过这些控制条件可以使前62轮的差分以1的概率通过，之后差分进行扩散时，可以使差分优势保持到更长的轮数。
　　第四步，由明文和密钥的约束条件得到的有效明文的样本空间进行差分路线搜索测试，寻找密文差分中，差分优势可以被检测到的最长的轮数。
　　第五步，通过测试之后若干轮的轮子密钥对最长差分路径的概率分布是否影响，来增加攻击轮数，获得更多的子密钥。
　　因为KATAN系列算法的密钥生成算法是相同的，都是将80比特主密钥置入80级的线性反馈移位寄存器，线性反馈移位寄存器的反馈多项式为80级的本原多项式，这样，线性反馈移位寄存器产生的序列为小m序列，周期为280-1，没有长度大于80的游程，长度为80的‘1’游程有且仅有1个，长度为79的‘0’游程的个数有且仅有1个，长度为k的游程总数为280-k个，其中‘0’游程和‘1’游程各占一半。因为每一轮加密使用的密钥为两比特，这样我们可以利用唯一的一个长度为79的‘0’游程来控制密钥差分在39轮之内不出现差分，进而寻找更长的高概率差分路径，找到路径后，我们测试差分路径之后的若干轮的轮子密钥是否对最长差分路径的概率产生影响，回推来验证最长路径的差分优势。对于KATAN32算法，我们由连续79个‘0’和1个‘1’确定的80比特移存器密钥差分状态进行逆推，逆推得到密钥差分，逆推22轮时，得到的密钥差分为[6，14，25，44]，由确定的密钥差分，控制条件得到的明文差分为[6，9，19]。
　　本论文对以移位寄存器为基础并且密钥扩展算法为LFSR的分组密码的相关密钥的差分分析有积极的借鉴意义，是KATAN系列算法相关密钥差分分析的最好结果。论文完成了以下改进工作:
　　1、目前，KATAN32算法相关密钥的差分攻击的国际最好结果的攻击轮数为120轮，本文通过测试最长高概率差分路线之后若干轮的轮子密钥将KATAN32的攻击轮数从120轮增加到158轮;
　　2、目前，KATAN48算法相关密钥的差分攻击的国际最好结果的攻击轮数为103轮，本文通过测试最长高概率差分路线之后若干轮的轮子密钥将KATAN48的攻击轮数从103轮增加到140轮;
　　3、目前，KATAN64算法相关密钥的差分攻击的国际最好结果的攻击轮数为90轮，本文通过测试最长高概率差分路线之后若干轮的轮子密钥将KATAN64的攻击轮数从90轮增加到126轮。

目录

声明

摘要

符号说明

第一章 引言

1．1 密码学及分组密码算法简介

1．2 课题研究意义及结果

1．3 论文组织结构

第二章 KATAN系列算法介绍及安全性分析

2．1 KATAN系列算法介绍

2．2 KATAN算法安全性分析

第三章 相关密钥的差分分析简介

3．1 相关密钥攻击和差分分析的基本原理

3．2 基于NLFSR的密码算法的条件差分分析

3．2．1 以NLFSR为基础的密码算法

3．2．2 约束条件及其分类

第四章 KATAN相关密钥的条件差分分析

4．1 KATAN32相关密钥的条件差分分析

4．1．1 KATAN32条件差分路径搜索

4．1．2 KATAN32尾部猜测密钥回推

4．1．3 KATAN32尾部猜测密钥复杂度分析

4．2 KATAN48相关密钥的条件差分分析

4．2．1 KATAN48条件差分路径搜索

4．2．2 KATAN48尾部猜测密钥回推

4．2．3 KATAN48尾部猜测密钥复杂度分析

4．3 KATAN64相关密钥的条件差分分析

4．3．1 KATAN64条件差分路径搜索

4．3．2 KATAN64尾部猜测密钥回推

4．3．3 KATAN64尾部猜测密钥复杂度分析

第五章 研究结论与展望

参考文献

附录 每轮IR的值

致谢