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

分组密码算法的若干安全性分析方法研究近年来,随着云计算、物联网等新一代信息技术的飞速发展,各类移动终端、传感器等得到了广泛的应用,与此同时,为了提供有效的数据安全防护,轻量级分组密码得到了迅猛发展。本文主要利用二分图技术、混合整数线性规划（MixedIntegerLinearPro-gramming-MILP）方法和矩阵理论对分组密码算法标准化进程中的几个重要分组密码算法的安全性进行研究,包括2015年俄罗斯联邦政府制定的国家标准加密算法Kuznyechik和2012年被美国国家标准与技术研究院选为SHA-3（SecureHashAlgorithm3）标准的Keccak算法,以及轻量级分组密码算法Piccolo、Midori、Skinny、PRESENT、KLEIN和MIBS等,主要工作和贡献如下:（1）基于轻量级分组密码Piccolo密钥编排缺陷评估其抵抗Biclique攻击的能力。在研究Piccolo算法结构和密钥编排特点的基础上,重新评估了轻量级分组密码Piccolo算法抵抗Biclique攻击的能力,提出了针对Piccolo-80第23轮的轮密钥与最后的白化密钥存在16比特抵消的弱点构建Biclique结构,较大地降低了Biclique攻击的数据复杂度。构造了一个6轮Biclique结构,对Piccolo-80进行全轮的Biclique攻击,其数据和计算复杂度分别为2⁴⁰和2^79.22,把我们已知当前最好的Piccolo-80的Biclique攻击的复杂度由2⁴⁸降低至2⁴⁰。分别构造了5轮和7轮的Biclique结构,对Piccolo-128进行全轮的Biclique攻击,其数据复杂度分别为2⁸和2²⁴,计算复杂度分别为2^127.30和2^127.14。我们的研究结果证明了密钥编排简单的Piccolo算法对Biclique攻击技术免疫性较弱。（2）评估了轻量级分组密码Midori抵抗非平衡的Biclique攻击的能力。评估了Midori抵抗非平衡的Biclique攻击的能力,给出了自动化搜索非平衡Biclique结构的方案,提出了一个5轮4?8维的非平衡Biclique结构,基于该结构对Midori-64进行了全轮的密钥恢复攻击,数据和计算复杂度分别为2³⁶和2^126.25。利用构建的4轮8?16维的非平衡Biclique结构,对Midori-128进行了全轮的密钥恢复攻击,数据和计算复杂度分别为2⁷²和2^126.91。分析结果优于我们已知的其它单密钥分析的结果,从新的角度评估了Midori算法的安全性,展示了Biclique攻击从分析轮数上较其它分析方法的优越性,且证明了非平衡的Biclique攻击在数据和时间复杂度方面均优于平衡的Biclique攻击。（3）用自动化方法搜索分组密码概率最大、涵盖轮数最长的差分路径。在深入研究密码结构和基本运算的基础上,用线性不等式组准确刻画其非线性变换的DDT（DifferenceDistributionTable）中每个点的差分传播概率,构建基于比特级的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（SubstitutionPermutationNetwork）和Feistel两种结构类型的分组密码的结构特点,研究分组密码的线性变换层的性质,评估线性变换层抵抗不可能差分分析的能力。通过某个比特（或单元）引入差分,考虑r轮后加密算法中间状态的所有单元是否有差分,来评估加密算法的线性变换的扩散能力。根据线性变换层矩阵为正阵的最小轮数r的值,确定不可能差分路径长度的上界。给出不考虑S盒细节,输入、输出只有一个单元甚至一比特有差分的不可能差分路径长度的上界,并给出证明。该研究成果为进一步的密钥恢复攻击奠定理论基础,同时为分组密码的设计在选择密码结构轮函数和轮数上提供参考。对2015年俄罗斯国家标准加密算法进行分析,若不