序列密码立方攻击研究进展综述

立方攻击由Dinur和Shamir在2009年欧密会上首次提出,是一种高阶差分攻击和代数攻击.经过近十余年的研究,传统立方攻击不断发展,动态立方攻击、基于可分性的立方攻击、相关立方攻击相继提出,攻击思想不断丰富,攻击技术不断改进,逐渐成为针对基于非线性反馈移位寄存器的序列密码算法的重要攻击方法.特别地,立方攻击自2009年提出以来一直是国际轻量级序列密码标准Trivium最有效的密钥恢复攻击,动态立方攻击攻破了全轮Grain-128算法,Kreyvium、Grain-128AEAD、ACORN这些基于非线性反馈移位寄存器的序列密码算法都可以用立方攻击进行有效分析.本文介绍了立方攻击的基本原理和攻击方法,综述了实验立方攻击、基于可分性立方攻击、立方集构造、动态立方攻击、相关立方攻击等方面的研究进展.

对减轮Enhanced-Bivium流密码的立方攻击

Trivium流密码是最终胜选欧洲eSTREAM项目的轻量级同步流密码之一,而Enhanced-Bivium流密码是适用于RIFD系统的Trivium流密码的简化版本,该密码设计者认为在相同的初始化轮数下Enhanced-Bivium流密码算法的安全性要高于Trivium流密码算法。通过在离线预处理阶段引入代数次数评估方法和在在线计算阶段引入基于嵌套式单项式预测的立方攻击提出了一种新的立方攻击方法。使用该方法可以将初始化464轮的Enhanced-Bivium流密码的立方攻击所需时间复杂度由2^(55)降到2^(50.3),同时利用该方法可以在时间复杂度2^(77.8)下将对Enhanced-Bivium流密码攻击成功的初始化轮数由464轮提升到601轮。另外,利用该方法在相同的时间复杂度下,将对Trivium流密码成功攻击的轮数由799轮提升至840轮,进而证明了Enhanced-Bivium流密码比Trivium流密码对立方攻击有更好的抵抗性。

立方攻击研究综述

立方攻击是一种基于高阶差分理论的新型代数攻击方法,只要输出比特能够表示成关于明文变量和密钥变量的低次多元方程,立方攻击就有可能攻破此类密码。近年来立方攻击研究迅速开展,取得了一系列重要的成果。首先介绍了立方攻击原理及其变种:非线性立方攻击、立方测试和动态立方攻击;总结了基于中间状态泄露和基于故障信息泄露的两种旁路立方攻击模型及容错机制,给出了立方攻击扩展研究内容;最后分析了已有研究的不足并预测了下一步可能的研究方向。

流密码算法Grain的立方攻击

Dinur和Shamir在2009年欧洲密码年会上提出了立方攻击的密码分析方法.Grain算法是欧洲序列密码工程eSTREAM最终入选的3个面向硬件实现的流密码算法之一,该算法密钥长度为80比特,初始向量(initialvector,简称IV)长度为64比特,算法分为初始化过程和密钥流产生过程,初始化过程空跑160拍.利用立方攻击方法对Grain算法进行了分析,在选择IV攻击条件下,若算法初始化过程空跑70拍,则可恢复15比特密钥,并找到了关于另外23比特密钥的4个线性表达式;若算法初始化过程空跑75拍,则可恢复1比特密钥.

密码算法旁路立方攻击改进与应用

立方攻击的预处理阶段复杂度随输出比特代数次数的增长呈指数级增长,寻找有效立方集合的难度也随之增加。该文对立方攻击中预处理阶段的算法做了改进,在立方集合搜索时,由随机搜索变为带目标的搜索,设计了一个新的目标搜索优化算法,优化了预处理阶段的计算复杂度,进而使离线阶段时间复杂度显著降低。将改进的立方攻击结合旁路方法应用在MIBS分组密码算法上,从旁路攻击的角度分析MIBS的算法特点,在第3轮选择了泄露位置,建立关于初始密钥和输出比特的超定的线性方程组,可以直接恢复33 bit密钥,利用二次检测恢复6 bit密钥。所需选择明文量221.64,时间复杂度225。该结果较现有结果有较大改进,恢复的密钥数增多,在线阶段的时间复杂度降低。

SIMON系列轻量级分组密码故障立方攻击

针对SIMON密码按位与&运算特性以及现有立方攻击与故障攻击的不足,给出一种故障立方攻击方法.根据线性和二次多项式数量确定候选故障注入轮;利用差分特征表确定故障注入的具体位置;利用离线阶段求得的大量低次多项式,恢复部分轮密钥,并结合密钥猜测攻击恢复全轮密钥.结果表明:对SIMON32/64进行故障立方攻击,需要平均注入故障69次,计算复杂度为247.91,优于现有立方攻击;相比于差分故障攻击,采用故障立方攻击方法确定故障位置更有效,故障模型更易实现,且整个攻击过程具有自动化程度高的特点.该方法可为核心运算次数较低的轻量级分组密码提供借鉴.

对简化版KeeLoq算法的中间相遇-立方攻击

利用立方攻击密码分析方法对简化版(64圈)的KeeLoq算法进行分析,寻找关于15bit密钥的线性方程组;结合穷举攻击,以O(221.2)的复杂度恢复所有64bit密钥;利用所得线性方程组,结合中间相遇技术将攻击圈数增加到96圈,从而实现了以O(251.3)的复杂度恢复所有密钥.

立方攻击成功率分析

在一般随机布尔函数及布尔函数的代数次数或代数标准型项数受限情况下,从理论上分析了立方攻击的成功概率,对立方攻击密码分析方法提供了理论支持。理论结果与对流密码算法Trivium及Grain v1的实验结果是相吻合的。

轻量级分组密码LED旁路立方攻击研究

对CHES 2011会议上提出的轻量级分组密码LED进行旁路立方攻击研究。提出一种基于贪心策略的小立方体搜索方法,利用该方法确定了单比特泄露模型和汉明重泄露模型的泄露位;基于两种模型对LED密码进行旁路立方攻击,并对其攻击结果进行比较。仿真结果表明,基于单比特模型进行立方攻击,可将密钥搜索空间降低到28~211;基于汉明重模型,对第2、3轮的攻击可分别将密钥搜索空间降低到248、223。对两种模型比较发现,汉明重模型的多项式次数更高,立方大小分布更加集中。

对简化版MORUS算法的改进动态立方攻击

MORUS算法是Wu等人设计的认证加密算法,现已进入CAESAR竞赛的第三轮.动态立方攻击是Dinur等人2011年提出的针对迭代型序列密码的分析方法.提出了一种改进的动态立方攻击方法,优化了动态立方攻击的立方集合的选取规则,提出了优先猜测关键值并恢复相应的关键秘密信息的方法,据此给出了成功率更高的秘密信息恢复方法.利用该方法分析了初始化5步的简化版MORUS算法,最终以O(295.05)的复杂度恢复所有128比特密钥,攻击的成功率大于92%.

二次检测立方攻击改进与实现

对二次检测立方攻击预处理阶段的提取二次表达式的算法进行了改进以优化攻击效率。将秘密变量的变化引入攻击中,使得攻击模型更加灵活;同时,利用时空折中的思想,通过存储常数项和一次项的计算结果,有效降低二次项的计算量。将改进的方法应用于简化版的PRESENT算法和Trivium算法上,攻击效率有显著提高。

KATAN族密码的立方攻击和积分攻击

为了重新评估KATAN族密码抵抗立方攻击和积分攻击的安全性,利用无未知集合三子集可分性结合混合整数线性规划(MILP)搜索工具,恢复了更长轮数的超级多项式并且搜索得到了积分区分器,进而对KATAN族密码进行了立方攻击和积分攻击.具体来说,针对KATAN32,给出了102轮和95轮的立方攻击,时间复杂度分别是2^(79)和2^(71);针对KATAN48,给出了85轮和77轮的立方攻击,时间复杂度分别是2^(79)和2^(65.6);针对KATAN64,给出了73轮的立方攻击,时间复杂度为2^(79).将KATAN32/48/64的已有最好的立方攻击结果分别提升了12/35/43轮.当超级多项式退化为常数,便得到了积分区分器.因此,所提算法也可以搜索积分区分器.针对KATAN32/48/64的积分区分器分别可达到101轮、84轮、73轮,从而可以对125/100/81轮的KATAN32/48/64进行积分攻击,时间复杂度分别为2^(79).3/2^(79).2/2^(79).1.结果表明,针对超过102/85/73轮的KATAN32/48/64并不存在有效的立方攻击结果,超过125/100/81轮的KATAN32/48/64也不存在有效的积分攻击结果.

改进的基于可分属性的立方攻击

针对基于可分属性的立方攻击,提出了一种改进的单项式枚举算法,该算法相较于之前的算法,能够将更多的不存在于超级多项式中的单项式排除,从而改进的立方攻击所需要的时间复杂得到降低。通过对初始化5拍MORUS-640-128算法的分析,验证了改进的单项式枚举算法的有效性,并将改进的单项式枚举算法用于初始化6拍MORUS-640-128算法的分析,得到的攻击时间复杂度较之前的分析结果有明显的降低。

Trivium算法的立方攻击

针对Trivium算法的立方攻击中恢复超级多项式表达式时遇到的模型求解费时问题,提出了一种快速方法,该方法结合了Delaune等人的有向图建模方法以及胡凯等人的模型分解方法。初始化845轮的Trivium算法的攻击实验结果表明,相比于公开结果,恢复超级多项式表达式的模型求解时间由约3周下降至约1周。

迭代立方攻击及其应用

由于种种原因,实际分析中立方攻击通常无法找到相当数量的密钥比特线性表达式,基于迭代的思想,提出了一种迭代立方攻击方法。将其应用于55轮KATAN32算法,实验结果表明较之前的方法,该方法具有更小的数据复杂度和计算复杂度,攻击效果明显。

Subterranean-SAE 算法的条件立方攻击

美国国家标准与技术研究院(NIST)于2018年开始征集轻量级认证加密和哈希算法标准,其中Subterranean 2.0密码套件是晋级到第二轮的32个候选算法之一.Subterranean-SAE是Subterranean 2.0密码套件中的一种认证加密工作模式.2019年,刘富康等人对4轮空白轮(4 blank rounds)的Subterranean-SAE算法进行了基于条件立方的密钥恢复攻击,此攻击有效的前提假设是:当条件变量满足条件时输出代数次数为64,否则为65.但刘富康等人并没有验证该假设是否成立.借助三子集可分性理论,本文首次提出了在初始状态未知场景下评估输出代数次数的新技术,并将该技术成功应用于4轮空白轮Subterranean-SAE算法.实验结果表明,4轮空白轮Subterranean-SAE算法32个输出比特的代数次数上界为63,因此刘富康等人的密钥恢复攻击实际为区分攻击.进一步,本文提出降低立方维数、扩展立方变量选取范围的策略,并成功改进了Subterranean-SAE算法条件立方的搜索方法.利用此方法我们共搜索到24组33维立方并以此构造条件立方攻击,攻击的数据和时间复杂度分别为2^{41.8}和2^{124}.本文的条件立方攻击能够通过实验验证其有效性,并且能够正确恢复128比特密钥.在nonce不重用场景下,这是首次实现4轮缩减轮数Subterranean-SAE算法的全密钥恢复攻击.值得注意的是,本文缩减轮数的攻击并不会对Subterranean-SAE算法构成实质安全性威胁,但有助于加深对其安全性的理解.

简化版分组密码KATAN32的相关密钥立方攻击

立方攻击是一种针对序列密码的分析技术,最近这一技术获得了新的发展,引入集合可分性的概念,建立数学模型,然后用数学软件求解。展现了立方攻击强大的分析能力。分组密码KATAN32是由一个线性反馈移位寄存器和两个非线性反馈移位寄存器设计的。分组密码KATAN32被认为是序列密码,联合使用带可分性的立方攻击和相关密钥攻击,得到了127轮的分组密码KATAN32的5个密钥比特的信息。

立方攻击研究进展

立方攻击是一种新型的代数分析方法,刚提出时对密码算法的分析效果并不理想。但是在引入多重集合可分性、可分路径的概念之后,立方攻击的过程转化为求解混合整数线性规划问题,再使用数学软件进行计算,大大提高了其分析能力。梳理了立方攻击的技术脉络,论述了其最新进展,给出了立方攻击亟待解决的研究问题,这将有助于掌握立方攻击的最新技术,便于开展对分组密码、序列密码和哈希函数等密码算法的分析工作。

MIBS密码旁路立方体攻击

研究密码MIBS安全性评估问题。基于单比特泄露模型,假定攻击者可以获取加密中间状态的1比特信息泄露。预处理阶段,随机生成不同选择明文和密钥进行极大项和超多项式提取;在线分析阶段,利用超多项式和加密输出中间状态信息泄露构建关于密钥变量的低次方程组,经方程组求解恢复密钥。结果表明:针对MIBS加密第1轮输出的第5比特泄露,26.39个选择明文分析将MIBS-64密钥搜索空间降低至240。经暴力破解可最终恢复64位MIBS完整密钥。改进方法对其它分组密码旁路立方体攻击研究具有一定借鉴意义。

EPCBC密码旁路立方体攻击

将立方体分析和旁路攻击结合,基于8位汉明重泄露模型,对CANS 2011会议上提出的轻量级分组密码EPCBC抗旁路立方体攻击安全性进行评估。在黑盒攻击场景下,攻击者按照一定规则生成立方体和超多项式,利用不同立方体生成不同选择明文,通过计算这些选择明文在加密过程某比特的高阶差分,判断该立方体对应的超多项式是否合法。对不同分组长度的EPCBC密码进行了黑盒旁路立方体攻击实验,结果表明:未经防护的EPCBC密码易遭受黑盒旁路立方体攻击;如果攻击者能够精确获取加密过程汉明重信息泄露,利用提取出的立方体和超多项式,372个选择明文可恢复EPCBC(48,96)的48比特密钥,将其主密钥搜索空间降低到248;610个选择明文可恢复EPCBC(96,96)的全部96比特主密钥。文中方法对其他分组密码黑盒旁路立方体攻击研究具有一定的借鉴意义。