应用MILP方法搜索基于分离特性的算法积分区分器

摘要

2015年的欧密会上，密码学者Todo将传统的积分分析进行推广，提出了分离特性的概念。由于分离特性可以更加明确地刻画介于“活跃”和“零和”之间的隐含性质，所以可以应用在使用了非双射、比特级或低次数部件的分组密码算法的分析中。同年的美密会上，Todo考虑S盒为公开函数，首次在理论上成功地分析了MISTY1的全轮算法。FSE2016，日本学者Todo和Morri提出比特级分离特性，更细致地利用了算法的内部结构。之后，Sun和Wang将S盒的代数标准型和分离特性的定义相结合，提出了借助表的比特级分离特性。2016年的亚密会中，Xiang等将混合整数线性规划的思想应用到比特级分离特性的搜索中。Sun等通过刻画复杂线性层和模加运算中比特级分离特性的传递模型，分析了比特级分离特性在SPN算法和ARX类算法分析中的适用性，使得该方法能够分析更为广泛的分组密码算法。
　　本文主要研究了三种密码算法在比特级分离特性分析下的安全程度。根据己知的发表文献，本文首次研究了Kuznyechik和Chaskey算法的分离特性，找到了轮数均为4的积分区分器。对于SPARX算法，其作者在设计之初就进行了分离特性分析。本文采用了比特级分离特性进行分析，得到了与设计文档一致的分析结果，表明在比特级别上考虑分离特性不一定能够改进分析结果。Kuznyechik算法为SPN结构，S盒为8比特的替换，线性层为有限域上的乘法。Chaskey和SPARX为ARX算法，由模加、循环移位和轮密钥异或组成。本文通过分析比特级分离特性在这些算法模块之间的传递方式，利用混合线性整数规划搜索积分区分器。此外，对于Serpent、PRESENT和Noekeon等算法的已有较好积分区分器，本文通过综合分析算法的结构模块和密钥生成方案进行了密钥恢复分析，分别攻击了12轮、9轮和7轮的相应算法。

目录

声明

摘要

符号说明

第一章 引言

§1．1 分组密码算法简介

§1．2 积分分析介绍及其研究现状

§1．3 论文工作和内容安排

第二章 积分分析

§2．1 积分分析和分离特性简介

§2．2 比特级分离特性的传递规则

§2．3 模型化复杂的线性层

§2．4 模加

第三章 Kuznyechik算法的积分分析

§3．1 Kuznyechik算法简介

§3．2 Kuznyechik的安全性分析

§3．3 Kuznyechik的积分区分器

第四章 Chaskey算法的积分分析

§4．1 Chaskey算法简介

§4．2 Chaskey算法的安全性分析

§4．3 Chaskey算法的积分区分器

第五章 SPARX算法的积分分析

§5．1 SPARX算法简介

§5．2 SPARX算法的分离特性

5．2．1 SPARX-64的分离特性

5．2．2 SPARX-128的分离特性

第六章 一些比特级分组密码算法的密钥恢复攻击

§6．1 PRESENT的密钥恢复攻击

§6．2 Serpent的密钥恢复攻击

§6．3 Noekeon的密钥恢复攻击

第七章 结论

参考文献

致谢