分组密码算法和流密码算法的安全性分析

分组密码算法和流密码算法的安全性分析当今是一个网络时代,人们的生活方式与过去相比发生了很大的变化,足不出户就可以通过网络解决衣食住行中的绝大多数需求,例如,用淘宝网购买所需、用支付宝进行日常支付、用电子银行转账等等。生活变得快捷而又方便。然而,事物都有两面性,伴随着生活的便捷而来的是财产安全和个人隐私的保障问题。这时,密码的使用就是在网络上对我们进行保护的一个关键技术点。它是类似防火墙似的存在,是一切网络活动的基石。在网络传输时一般使用的是对称加密算法来进行加密操作,如流密码算法和分组密码算法。因此,对现有的被广泛重视和使用的分组密码算法和流密码算法的安全性进行研究和分析是非常有必要的。在本文中,首先,我们针对分组密码算法建立统计积分区分器和多结构体统计积分区分器新模型,并将模型应用于实际算法中;其次,基于MILP方法首次将S盒的差分特征和线性特征考虑进不可能差分路线和零相关路线的自动化搜索中,首次给出ARX算法通用的不可能差分路线和零相关路线的自动化搜索方法,并将该方法应用于实际算法中;最后,在相关密钥场景下利用不可能差分方法给出流密码算法Lizard的安全性分析结果。具体结果如下。提出分组密码算法统计积分区分模型,并利用该模型理论破解Skipjack变种算法、给出CAST-256的最优攻击结果和IDEA的最优积分攻击结果:积分攻击是对称密码领域最强大的分析方法之一,被广泛的应用于分组密码算法的安全性分析中。它是基于概率为1的平衡特性来构建区分器。攻击者可以通过固定输入的一部分比特而遍历剩下的所有比特的可能取值,观察相应的输出值在某些比特上是否为均匀分布来区分真实算法和随机置换。为了增加积分区分器的覆盖轮数,攻击者通常会在整个明文空间的限制条件下以特定的结构来遍历更多的明文比特以使得平衡特性依然成立。然而这一要求限制了积分攻击在很多算法分析中的应用。在本文中,为降低积分分析中使用的数据复杂度,我们基于超几何分布和多项分布为算法和随机置换构造不同的概率分布来进行区分,从而构建了统计积分这一新模型。这个新模型所需要的数据量与传统的积分区分器所需的数据量相比降低了很多。利用该模型我们对Skipjack变种算法、CAST-256和IDEA算法进行改进分析。Skipjack算法是美国NSA设计并公开的首个分组密码算法。这个算法抵抗不可能差分攻击的能力较弱。为了加强Skipjack抗截断差分类攻击的能力,Knudsen等人给出了Skipjack算法的一个变种算法Skipjack-BABABABA。本文中,我们利用统计积分区分新模型首次成功破解了Skipjack的变种算法Skipjack-BABABABA。CAST-256算法是由Adams等人在SAC’97上提出的一个分组密码算法。从其提出至今,许多分析结果被陆续给出,如差分分析、线性分析、飞去来器分析和零相关线性分析等。在本文中,我们利用统计积分区分器模型来攻击CAST-256算法。首先,我们给出CAST-256算法一个29轮的攻击结果。这个攻击需要296.8个选择明文、2219.4次加密、273字节存储。通过对时间复杂度和数据复杂度之间进行折中,这个攻击也可以使用283.9个选择明文、2244.4次加密和266字节存储进行。据我们所知,这是在单密钥场景且无弱密钥假设下CAST-256算法的最优攻击结果。IDEA算法是由Lai和Massey在1991年提出的分组密码算法,现被广泛的用于多个安全应用中,如IPSec和PGP。在本文中,我们利用统计积分区分器模型来攻击IDEA算法。我们首次给出了IDEA算法的一个2.5轮的积分区分器,这个区分器是至今为止IDEA算法最长的区分器。基于这个区分器,我们成功给出了IDEA算法的一个4.5轮密钥恢复攻击结果。这个攻击需要258.5个已知明文、2120.9次加密和246.6字节存储来完成。从攻击轮数角度看,这个攻击是目前IDEA算法最优的积分攻击结果。提出多结构体统计积分区分模型,并利用该模型给出AES算法在秘密密钥下的最优积分区分结果和(类)AES算法的最优已知密钥区分攻击结果:统计积分区分模型有一定的局限性,我们仅仅考虑了使用区分器输出上的一个平衡特性。在一些场景下,积分区分器的输出处同时存在多个平衡特性;在另一些场景下,区分器需要同时使用多个数据结构体才能有效。针对前者,使用统计积分区分器模型会浪费一些积分特性;针对后者,现有的统计积分区分器不能适应于这样的场景。为了扩展统计积分区分器模型以便用于更多的场景中,我们构造了多结构体统计积分区分模型。利用该模型我们对AES在秘密密钥下的积分区分攻击进行改进,给出(类)AES算法的最优已知密钥区分攻击。AES(AdvancedEncryptionStandard)是由美国国家标准与技术研究所(NIST)发布的一个标准分组密码算法,已被广泛的应用于数据加密算法、哈希函数和认证加密方案等。研究AES的区分攻击可以帮助算法设计者和分析者来评估相关算法的安全界限。利用多结构体统计积分模型,我们给出了一个在秘密密钥和秘密S盒场景下5轮AES算法的选择密文区分攻击结果。该攻击所需的数据、时间和存储复杂度分别为2114.32个选择密文、2110次加密和233.32的存储。这个积分区分器是AES算法迄今为止在秘密密钥和秘密S盒场景下最优的积分区分结果。除此之外,我们将多结构体统计积分模型应用于AES算法的已知密钥区分器中。改进了Gilbert给出的原有结果。以242.61的时间复杂度完成对8轮AES的已知密钥区分攻击,以259.60的时间复杂度完成对全轮AES的已知密钥区分攻击。从时间复杂度的角度来看,我们给出的区分器是AES在已知密钥场景下最优的区分结果。另外,AES算法采用的宽轨道设计思想被广泛的用于哈希函数的设计中,如ISO标准哈希函数Whirlpool、国际重要的轻量级哈希函数PHOTON和SHA-3评选竞赛最后一轮的五个候选算法之的Gr(?)stl算法等。这些算法的压缩函数均采用类AES算法设计而成。哈希函数本身的安全性直接取决于内部置换的安全性,即类AES算法在已知密钥场景下的安全性。与AES算法的已知密钥区分攻击方法类似的,我们可以将多结构体统计积分模型用于类AES算法的已知密钥区分中。分别给出Whirlpool、Gr(?)stl-256和PHOTON的内部置换在已知密钥场景下最优的区分结果。提出基于MILP的不可能差分路线和零相关路线自动化搜索工具:不可能差分分析和零相关线性分析是对称密码领域有力的分析手段。现有多个用于搜索带S盒算法的不可能差分路线的自动化工具,然而这些工具往往只关注于算法的线性层性质而将S盒理想化。事实上,在现实中理想的S盒并不存在,因而在理想S盒下搜出的差分路线有可能在实际中并不存在。在本工作中,我们首次将S盒的差分特征和线性特征考虑进不可能差分路线和零相关线性路线的搜索中,提出基于MILP自动化搜索带S盒算法的不可能差分路线和零相关路线的方法。除此之外,我们首次给出针对ARX算法的通用不可能差分路线和零相关线性路线的自动化搜索方法。作为应用实例,我们将该方法应用于HIGHT、SHACAL-2、LEA、LBlock、Salsa20和Chaskey中,改进了HIGHT、SHACAL-2、LEA和LBlock算法现有的(相关密钥)不可能差分路线或零相关路线,首次给出Salsa20和Chaskey中使用的置换的不可能差分路线。相关密钥场景下Lizard算法的安全性分析:Lizard是由Hamann等人在ToSC2016上提出的一个抗生日攻击的流密码算法。算法以120比特密钥和64比特Ⅳ为输入,内部状态为121比特,输出一个至多218比特的密钥流。设计者声明该算法抗密钥恢复攻击的安全性为80比特,抗区分攻击的安全性为60比特。基于Banik等人利用碰撞对来恢复密钥的思想,在本文中,我们利用猜测复合密钥的方法在单密钥场景下直接将密钥恢复阶段增加1轮从而给出227步的攻击结果,这在单密钥场景下是Lizard算法的最优密钥恢复结果;在相关密钥场景下将攻击改进到233步,使得Lizard算法的安全冗余仅剩23步(共256步)。在相关密钥场景下,首先我们通过选择密钥差分拉