分组密码算法的不可能差分分析

发布时间：2020-07-20 13:45

【摘要】：分组密码算法属于对称密码算法,将明文消息分割为固定长度分组进行加解密运算。分组加密具有实现简单、加解密速率快的优点,是密码体制的重要组成部分。典型的分组密码算法如DES和AES是美国政府的标准加密算法,其应用领域从邮件加密到转账交易,与生活息息相关。对分组密码算法进行安全性分析能够评估算法的优缺点,保证密码算法的合理应用,非常具有现实意义。不可能差分分析由Knudsen和Biham分别独立提出,属于差分分析技术的变种,利用数据的差分传播特性对密码算法进行安全性评估,是分组密码算法安全性分析的重要方法之一。与经典差分分析技术中利用高概率差分进行密钥恢复不同,不可能差分分析依靠不可能出现,即概率为0的差分来过滤错误的候选密钥,因为利用正确密钥对数据加密不会出现这样的差分。本文以不可能差分分析为主要技术手段,对几个重要的分组密码算法进行了分析,包括两个部分:第一部分属于不可能差分分析技术的经典应用,对ASIACRYPT 2016算法Simpira进行了研究,结合大S盒技术和算法采用的广义Feistel结构特点,寻找到Simpira算法4分支版本的首个9轮不可能差分区分器,给出了算法的首个分析结果;第二部分通过分析密钥编排方案对差分传播特性的影响,提出一种可以由单密钥不可能差分推导更长轮相关密钥不可能差分的自动化搜索方法,这也是首个针对相关密钥不可能差分的自动化搜索方案,利用此方法,对FSE2017接收算法QARMA-64、CAESAR竞赛胜出方案Deoxys的内置可调分组密码算法Deoxys-BC-256和CAESAR竞赛第二轮入选方案Joltik内置可调分组密码算法Joltik-BC-128进行了分析,相较已有工作,给出了算法的更精确安全评估结果,具有国际水平。两个工作结果均发表于 Science China Information Sciences。· Simpira v2的单密钥不可能差分分析密码置换函数Simpira由Shay Gueron和Nicky Mouha设计,采用AES轮函数作为唯一基础组件,支持128×b比特输入,其中b为任意正整数,用Simpira-b表示输入分支数目为b的算法版本。当b = 1时,Simpira-1可以被看作轮密钥为确定值的12轮AES算法;当b≥2时,Simpira-b是一个F函数由两个AES轮函数构成的广义Feistel结构。根据设计者推荐,Simpira可以作为Even-Mansour结构的置换函数构造成为一个没有轮密钥的分组密码算法,算法的分组长度与密钥长度均为128× b 比特。Simpira的多分支结构充分考虑了密码学界和工业界对AES算法的研究进展。继2001年Rijndael算法被美国国家标准与技术研究院(NIST)选为高级加密标准(AES)以来,如何更高效的实现AES算法是密码工作者最关注的问题之一。许多芯片公司例如Intel、AMD和ARM都相继研发了适用于各自处理器的AES算法实现指令,大大减少了数据处理时的资源开销。但是,由于AES利用8比特S盒作为非线性层,高延迟无法避免的成为了算法的运算效率瓶颈。利用AES-GCM模式运行AES加密指令是当今比较有效的解决方案。在这种模式下,数据分组互相独立,对加密指令进行流水线操作,从而可以提高吞吐量,弥补了算法高延迟的缺点。Simpira的设计灵感便是从这种独立加密、并行计算的工作模式中获得。此外,利用AES轮函数作为基础组件可以充分利用已有的AES算法实现指令;F函数的安全性也直接依赖于两轮AES算法的安全性。Simpira v2是在Simpira v1基础上改进的正式发布版本,发表于国际密码学会议ASIACRYPT 2016。本文对输入为512比特的Simpira v2版本,即Simpira-4进行研究。通过对结构特点进行分析,我们发现了 Simpira-4的首个9轮不可能差分区分器。考虑到Simpira-4和Even-Mansour结构的安全声明,我们利用短轮不可能差分对Simpira-4作为置换函数在Even-Mansour下构造的分组密码进行了安全性分析:利用8条6轮不可能差分路线,对7轮算法进行了攻击,恢复了 256比特密钥,数据复杂度为257,时间复杂度为257;利用10条7轮不可能差分,通过对不可能差分前扩1轮或后扩1轮,攻击了8轮算法并可以恢复所有512比特密钥,攻击的数据复杂度为2170,时间复杂度为2170。这是Simpira v2的首个分析结果。·相关密钥不可能差分分析在相关密钥分析模型中,敌手可以获取密码算法在不同密钥作用下的运算结果,虽然他不能得知不同密钥的具体值,但可以知道甚至控制这些密钥之间的某些数学关系。这种分析方法可以与其他密码分析方法相结合对密码算法进行分析,并且取得了很多有价值的攻击结果,例如全轮AES-192、AES-256的理论破解便是得益于相关密钥分析与飞去来器分析(Boomerang)的结合运用。但是,由于相关密钥模型赋予了敌手对密钥比特的控制能力,密码学界一直认为这种假设条件过强,更倾向于将其归为一种理想模型。随着可调分组密码算法和TWEAKEY框架概念的提出,这种模型的现实意义才重新引起了学界重视。在可调分组密码中,调柄比特可以公开。此外,为了保证算法在各种资源受限环境中的高效计算,调柄编排所需要资源开销应该尽可能小,为了满足这一要求,可调分组密码设计者往往采用非常简单的密钥编排方案。在TWEAKEY框架中,使用调柄密钥来统一看待调柄比特和密钥比特,只要保证调柄密钥的总长度一定,密钥长度和调柄长度可以任意变化。公开的调柄比特使得不同调柄密钥之间的数学关系更容易被发现;在TWEAKEY框架下,敌手则可以根据攻击的复杂度需求选择相应的密钥比特长度。因此,可调分组密码在相关密钥模型下更容易遭受攻击。相关密钥不可能差分分析是相关密钥模型和不可能差分分析技术的巧妙结合,与其他分析方法类似,对算法进行相关密钥不可能差分分析的前提是寻找到有效的相关密钥不可能差分区分器。在本文中,通过分析不同调柄/密钥编排方案对算法内部差分传播特性的影响,我们给出一种基于MILP技术的相关调柄/密钥不可能差分自动化搜索方案。当满足一定条件时,该搜索方案可以利用单密钥不可能差分进行更长轮相关调柄/密钥不可能差分的推导。据我们所知,这是首个可以进行相关密钥不可能差分自动化搜索的方案。本文以三种具有代表性的可调分组密码算法为例,介绍了相关调柄/密钥不可能差分区分器的搜索过程并进行了密钥恢复攻击:1.QARMA-64 QARMA-64是由Roberto Avanzi设计的轻量级可调分组密码,发表于国际密码学会议FSE 2017,已被ARM公司采用作为实现指针认证功能的标准算法。算法采用代替-置换网络(SPN)结构,包括14个轮函数和一个中间结构,其中中间结构由两个轮函数和一个称作Pseudo-Reflector的结构组成。密钥长度为128比特,调柄和分组长度均为64比特。在本文中,结合算法轮密钥相等和其轮函数结构的特点,相关调柄/密钥差分可以完全由调柄比特差分构造。通过将密钥差分设为0,我们搜索到算法的7轮相关调柄不可能差分区分器并基于此区分器攻击了 11轮算法。相较于之前的结果,将攻击轮数提高了 1轮,攻击的数据复杂度为261,时间复杂度为264.4。2.Deoxys-BC-256 Deoxys-BC-256为CAESAR认证加密竞赛胜出方案Deoxys的内置可调分组密码算法,采用TWEAKEY框架,调柄密钥为256比特,分组长度为128比特,采用SPN结构,轮函数与AES轮函数相同,属于类AES算法。本文中,结合Deoxys-BC-256调柄密钥编排方案的特点,通过对3.5轮单密钥不可能差分后扩两轮,我们得到了一条6轮相关调柄密钥不可能差分,并基于此差分对Deoxys-BC-256进行了超文本攻击。当密钥长度大于174比特,调柄长度小于82比特时,我们的方法可以攻击10轮算法(共14轮)。攻击的数据复杂度为2135,时间复杂度为2173.1。在密钥比特为192比特时,之前的结果只能攻击9轮算法,比本文中结果少1轮。3.Joltik-BC-128Joltik-BC-128是CAESAR竞赛第二轮入选方案Joltik的内置可调分组密码算法。算法的调柄密钥长度为128比特,分组长度为64比特,采用SPN结构,由24个轮函数组成,同样采用了类AES结构设计。本文中我们利用6轮相关调柄密钥不可能差分分析了算法的10轮安全性,攻击的数据复杂度为271,时间复杂度为2109.5。这是Joltik-BC的首个分析结果,相较设计者给出的分析结果,我们将分析轮数提高了两轮。以上结果足以作为本文中相关调柄/密钥不可能差分搜索方案有效性的证明。在终端体积不断缩小,密钥编排偏向轻量化设计的趋势下,相关密钥模型将在密码算法安全评估工作中扮演越来越重要的角色,相信我们的相关调柄/密钥不可能差分自动化搜索方案会成为分析算法安全性的有效工具。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TN918.1
【图文】：

轮函数

逦＾；＋１逡逑图３．１：邋Ｓｉｍｐｉｒａ－４的轮函数逡逑图３．１中给出了邋Ｓｉｍｐｉｍ－４轮函数的具体结构，函数状态的计算规则可以描逡逑述为：逡逑Ｓ＾＋１邋＝邋Ｓｌ？Ｆ２ｉ＋１Ａ（Ｓ＾），逡逑Ｓ｝＋ｉ邋＝邋ｓｆ，逡逑Ｓｆ＋１邋＝邋Ｓｆ？Ｆ２ｉ＋２Ａ（Ｓｆ），逡逑Ｈ逡逑其中邋０邋ｓ邋ｉ邋￥邋１４。逡逑注意到当轮数不为４的倍数时，函数的最后输出状态需要进行一个简单的逡逑置换以保证输入输出顺序的一致性。逡逑在Ｓｉｍｐｉｒａ使用的Ｆｅｉｓｔｅｌ结构轮函数中，ｊＰ函数可以表不为＝邋ｉ＾，其逡逑中６是输入分组中子块的数量，ｃ是一个计数器来标记＾函数所在的轮数，从逡逑１开始计数。Ｆ函数由两轮ＡＥＳ轮函数构成，两个密钥加操作与ＡＥＳ轮函数逡逑不同

分组密码算法的不可能差分分析

图３．２：大Ｓ盒逡逑

差分,不可能

图３．４：邋Ｓｉｍｐｉｒａ－４的６轮不可能差分逡逑

【参考文献】