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

分组密码算法和流密码算法的安全性分析当今是一个网络时代,人们的生活方式与过去相比发生了很大的变化,足不出户就可以通过网络解决衣食住行中的绝大多数需求,例如,用淘宝网购买所需、用支付宝进行日常支付、用电子银行转账等等。生活变得快捷而又方便。然而,事物都有两面性,伴随着生活的便捷而来的是财产安全和个人隐私的保障问题。这时,密码的使用就是在网络上对我们进行保护的一个关键技术点。它是类似防火墙似的存在,是一切网络活动的基石。在网络传输时一般使用的是对称加密算法来进行加密操作,如流密码算法和分组密码算法。因此,对现有的被广泛重视和使用的分组密码算法和流密码算法的安全性进行研究和分析是非常有必要的。在本文中,首先,我们针对分组密码算法建立统计积分区分器和多结构体统计积分区分器新模型,并将模型应用于实际算法中;其次,基于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)是由美国国家标准与技术研究所(NIS