分组密码算法的若干安全性分析方法研究

摘要

近年来，随着云计算、物联网等新一代信息技术的飞速发展，各类移动终端、传感器等得到了广泛的应用，与此同时，为了提供有效的数据安全防护，轻量级分组密码得到了迅猛发展。本文主要利用二分图技术、混合整数线性规划（Mixed Integer Linear Pro-gramming-MILP）方法和矩阵理论对分组密码算法标准化进程中的几个重要分组密码算法的安全性进行研究，包括2015年俄罗斯联邦政府制定的国家标准加密算法Kuznyechik和2012年被美国国家标准与技术研究院选为SHA-3（Secure Hash Algorithm3）标准的Keccak算法，以及轻量级分组密码算法Piccolo、Midori、Skinny、PRESENT、KLEIN和MIBS等，主要工作和贡献如下： (1)基于轻量级分组密码Piccolo密钥编排缺陷评估其抵抗Biclique攻击的能力。 在研究Piccolo算法结构和密钥编排特点的基础上，重新评估了轻量级分组密码Piccolo算法抵抗Biclique攻击的能力，提出了针对Piccolo-80第23轮的轮密钥与最后的白化密钥存在16比特抵消的弱点构建Biclique结构，较大地降低了Biclique攻击的数据复杂度。构造了一个6轮Biclique结构，对Piccolo-80进行全轮的Biclique攻击，其数据和计算复杂度分别为240和279.22，把我们已知当前最好的Piccolo-80的Biclique攻击的复杂度由248降低至240。 分别构造了5轮和7轮的Biclique结构，对Piccolo-128进行全轮的Biclique攻击，其数据复杂度分别为28和224，计算复杂度分别为2127.30和2127.14。我们的研究结果证明了密钥编排简单的Piccolo算法对Biclique攻击技术免疫性较弱。 (2)评估了轻量级分组密码Midori抵抗非平衡的Biclique攻击的能力。 评估了Midori抵抗非平衡的Biclique攻击的能力，给出了自动化搜索非平衡Biclique结构的方案，提出了一个5轮4?8维的非平衡Biclique结构，基于该结构对Midori-64进行了全轮的密钥恢复攻击，数据和计算复杂度分别为236和2126.25。利用构建的4轮8×16维的非平衡Biclique结构，对Midori-128进行了全轮的密钥恢复攻击，数据和计算复杂度分别为272和2126.91。分析结果优于我们已知的其它单密钥分析的结果，从新的角度评估了Midori算法的安全性，展示了Biclique攻击从分析轮数上较其它分析方法的优越性，且证明了非平衡的Biclique攻击在数据和时间复杂度方面均优于平衡的Biclique攻击。 (3)用自动化方法搜索分组密码概率最大、涵盖轮数最长的差分路径。 在深入研究密码结构和基本运算的基础上，用线性不等式组准确刻画其非线性变换的DDT(Difference Distribution Table)中每个点的差分传播概率，构建基于比特级的MILP模型，自动化搜索概率最大涵盖轮数最长的单密钥下的差分路径。 通过精确刻画分组密码Midori的内部结构，构建了基于MILP的自动化搜索差分区分器模型，得到Midori-64的10轮差分路径，同时利用其S盒性质和线性层特点，向前延伸1轮，得到Midori-64的11轮差分路径。同时得到两条6轮SKINNY-64-64概率分别为2-48和2-60的差分路径，一条13轮SKINNY-64-128概率为2-124的差分路径，两条18轮SKINNY-64-192概率分别为2-188和2-190的差分路径。 对Keccak-f[400]构建了基于比特级的MILP模型，设置2个活跃比特在同一列，满足了第一轮θ操作不扩散的限制，求得起始2比特有差分的3/4/5轮的差分路径。深入研究PRESENT的S盒性质和线性层的缺陷，发现一条概率为2-18的4轮一循环的差分特征，基于此构造了16和17轮概率分别为2-72和2-76的差分路径。 (4)用矩阵理论研究线性层扩散性质并给出两种密码结构最长不可能差分路径的上界。 利用矩阵理论，分析SPN（Substitution Permutation Network）和Feistel两种结构类型的分组密码的结构特点，研究分组密码的线性变换层的性质，评估线性变换层抵抗不可能差分分析的能力。通过某个比特（或单元）引入差分，考虑r轮后加密算法中间状态的所有单元是否有差分，来评估加密算法的线性变换的扩散能力。根据线性变换层矩阵为正阵的最小轮数r的值，确定不可能差分路径长度的上界。给出不考虑S盒细节，输入、输出只有一个单元甚至一比特有差分的不可能差分路径长度的上界，并给出证明。该研究成果为进一步的密钥恢复攻击奠定理论基础，同时为分组密码的设计在选择密码结构轮函数和轮数上提供参考。 对2015年俄罗斯国家标准加密算法进行分析，若不考虑S盒细节，得出Kuznyechik不存在任何3轮的不可能差分路径的结论。同时给出了几个其它分组密码算法的不可能差分路径长度的上界，除非考虑S盒细节，否则KLEIN/Midori-64/MIBS不存在任何的5/7/9轮的不可能差分路径。

目录

声明

主要符号对照表

第1章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

分组密码Piccolo的安全性分析

分组密码Midori的安全性分析

用自动化方法搜索分组密码的概率最大、涵盖轮数最长的差分路径

1.3 论文主要研究内容及创新点

1.4 论文组织结构

第2章 分组密码及其分析方法简介

2.1 分组密码算法简介

2.2 分组密码的分析方法

2.3 本章小结

第3章Piccolo算法的Biclique分析

3.1 Piccolo算法简介

3.2 Piccolo算法的相关分析

3.3 Biclique攻击的原理

Biclique分析方法的提出

Biclique结构定义

Biclique技术的攻击原理

Biclique攻击的一般步骤

3.4 对Piccolo-80全轮的Biclique攻击

3.5 对Piccolo-128全轮的Biclique攻击

3.6 改进Piccolo-128全轮的Biclique攻击

3.7本章小结

第4章 Midori算法的非平衡的Biclique分析

4.1 Midori算法简介

4.2 Midori算法的相关分析

4.3 对Midori-64全轮的非平衡的Biclique攻击

4.4 对Midori-128全轮的非平衡的Biclique攻击

4.5 本章小结

第5章 分组密码差分区分器的自动化分析方法

5.1 基于MILP的区分器研究现状

5.2 构建差分扩散的MILP模型

5.3 Midori-64的建模及实验结果

5.4 Skinny-64的建模及实验结果

5.5 PRESENT-80的建模及实验结果

5.6 Keccak-f[400]的建模及实验结果

5.7 本章小结

第6章 几个分组密码的最长不可能差分路径的上界

6.1 不可能差分分析原理

6.2 几个相关的概念

6.3 SPN结构密码算法的不可能差分路径

6.3.1 不可能差分路径长度的上界

6.3.2 分析加密算法Kuznyechik

6.3.3 分析加密算法KLEIN

6.3.4 分析加密算法Midori-64

6.4 SP型轮函数的Feistel结构的不可能差分路径

6.4.1 不可能差分路径长度的上界

6.4.2 分析加密算法MIBS

6.5 本章小结

第7章 总结与展望

7.1 总结

7.2 展望

参考文献

攻读博士学位期间取得的成果及参与的课题

致谢