两类动态密码结构抵抗不可能差分和零相关线性能力评估

动态密码的设计与分析是当前密码学领域研究的热点.本文针对类CLEFIA动态密码结构和四分组CLEFIA变换簇抵抗不可能差分和零相关线性分析的能力进行评估.当两类动态密码结构的轮函数为双射时,通过研究密码组件的可交换性质,证明了这两类动态密码结构各自置换等价于标准静态密码结构.利用建立的置换等价关系,通过构造静态密码结构不可能差分和零相关线性区分器,证明了4n轮类CLEFIA动态密码结构所有结构均存在8轮的不可能差分和零相关线性区分器,证明了4n轮四分组CLEFIA变换簇所有结构均存在9轮的不可能差分和零相关线性区分器.

零相关线性分析研究

零相关线性分析由Bogdanov和Rijmen于2012年首次提出,该方法利用分组密码算法中广泛存在的相关度为零的线性逼近来区分密码算法与随机置换.为了解决零相关线性分析所依赖的高数据复杂度的问题,Bogdanov与Wang于FSE 2012提出利用多条零相关线性逼近,以区分统计分布的方式来降低数据复杂度.为了消除新模型所依赖的强烈假设条件,Bogdanov等人于ASIACRYPT 2012提出多维零相关线性分析的模型,进一步完善了零相关线性分析模型.零相关线性分析模型的有效性,在对诸多算法,包括TEA、XTEA、CAST-256、CLEFIA、Camellia等一系列重要算法的分析中得到验证.作为新的分析方法,零相关线性分析与其它密码分析技术之间的联系也被深入研究.线性分析领域的另一个研究进展是相关密钥下线性分析模型——相关密钥不变偏差线性分析模型的提出.本文详细介绍了零相关线性分析研究背景、发展历程以及线性分析领域当前的主要进展与取得的重要结果,以及存在的一些问题.

SMS4算法的多维零相关线性分析

SMS4算法是中国无线标准中使用的分组加密算法,2012年被国家商用密码管理局确定为国家密码行业标准.作为中国官方公布的第一个商用密码算法,SMS4算法的安全性分析是当前密码学界的研究热点之一.SMS4算法是一种32轮的迭代非平衡Feistel结构的分组密码算法,其加解密过程中使用的算法完全相同,唯一的不同点就是该算法的解密密钥是由它的加密密钥进行逆序变换后得到的,因此,SMS4算法在32轮非线性迭代之后有一个反序变换.本文证明了SMS4算法存在11轮零相关线性逼近,选取了其中一类特殊的零相关线性逼近,缩小了密钥猜测空间,分析了14轮SMS4算法对多维零相关线性攻击技术的安全性.结果显示:该攻击的数据复杂度为2123.5个已知明密文,时间复杂度为2120.7次14轮SMS4加密,存储复杂度为273个SMS4分组.虽然14轮SMS4算法对多维零相关线性攻击是不免疫的,但是其数据复杂度较其它攻击方法还很高,且14轮距离目前最高攻击轮数还有较大差距,因此SMS4算法在抗多维零相关线性分析方面仍然有足够的安全边界.

对LBlock算法的多重零相关线性分析

为了降低对LBlock进行零相关线性分析所需的数据复杂度,提出了对LBlock进行多重零相关线性分析的方法,证明了14轮LBlock存在26条零相关线性逼近,并给出了其具体构造.利用26条14轮零相关线性逼近为区分器,并基于正态分布的概率计算模型对22轮LBlock进行了多重零相关线性攻击,攻击的数据复杂度约为263.45个已知明文,计算复杂度约为276.27次22轮LBlock加密,成功实施攻击的概率为0.85.结果表明,该方法有效解决了需要利用整个明文空间对LBlock进行零相关线性分析的问题.

嵌套SP网络的New-Structure系列结构的零相关线性逼近与不可能差分性质研究

分组密码的安全性分析是密码学的重要研究内容,其中不可能差分分析和零相关线性分析是密码算法安全性分析的重要方法.本文利用中间相错方法,通过对扩散层进行限制,给出了嵌套SP网络的New-Structure系列结构的零相关线性逼近.给出了New-Structure I和New-Structure IV结构中概率非零的差分传递链和相关优势非零的线性逼近传递链在结构上的一致性.此外也给出了嵌套SP网络New-Structure I、III的16/22轮不可能差分特征.最后给出在分组规模和密钥规模均为128比特时,对New-Structure I,III,IV进行21/28/22轮的不可能差分攻击和19/28/22轮的多维零相关线性逼近攻击所需要的时间复杂度和数据复杂度.本文的结果对基于New-Structure结构设计的密码算法的安全性分析提供了理论依据.

嵌套代替-扩散网络的CLEFIA结构零相关线性逼近的构造

零相关线性分析是一种新的分组密码分析方法。进行零相关线性分析首先需要构造相关系数为0的线性逼近。该文研究了嵌套代替-扩散(SP)的CLEFIA结构相关系数为0的线性逼近构造问题,给出了该结构的一类新的(4n+1)轮零相关线性逼近的构造算法。利用该方法可以给出9轮CLEFIA算法的大量零相关线性逼近。

Zodiac算法的多重零相关线性分析

首次从零相关线性分析的角度评价了Zodiac算法的安全性,构造出两类不同的14轮零相关线性逼近,结合快速傅立叶变换(FFT)技术对全轮Zodiac算法进行了多重零相关线性分析,成功恢复出64-bit轮子密钥信息。结果显示:完整16轮Zodiac-128/192/256算法的多重零相关线性攻击的数据复杂度为2^(123.3)个已知明文,时间复杂度大约为2^(120.3)次16轮Zodiac算法加密,攻击的成功率约为0.85。

MISTY结构的不可能差分和零相关线性

不可能差分分析和零相关线性分析是目前分组密码安全性分析方法中常用的两种分析方法.针对分组密码设计中常用的一种结构——MISTY结构,研究了MISTY结构的不可能差分和零相关线性.首先,给出了MISTY结构的对偶结构,然后从密码结构的角度出发,从理论上证明了MISTY结构的结构不可能差分和结构零相关线性最长轮数均为4轮.最后,当考虑MISTY结构中轮函数的具体细节时,给出了MISTY结构存在5/6轮不可能差分和零相关线性的充分条件.所得结果不仅对设计具有MISTY结构的分组密码具有一定的指导意义,同时对分析该类密码的安全性提供了具体的研究方法.

对PICO和RECTANGLE的零相关线性分析

混合整数线性规划是一种解决优化问题的常用方法.2012年,Mouha等人首次将该方法应用于密码算法的安全性评估,成功实现了对活跃S盒数下界的求解.PICO和RECTANGLE均为SPN型结构的轻量级分组密码算法,目前对于这两种算法的零相关线性分析研究尚待完善.本文首先针对PICO算法的零相关线性逼近问题,建立基于混合整数线性规划的模型并进行路径搜索,找到大量7轮PICO算法的零相关线性逼近,优于设计者给出的4轮零相关线性逼近.进一步地,通过构造7轮多维零相关线性区分器,对含白化密钥的10轮PICO算法进行密钥恢复攻击.该攻击能够恢复共50比特轮子密钥,其时间复杂度为2^(68.7)次10轮PICO加密,数据复杂度为2^(63.3)个已知明文,存储复杂度为2^(42.3)字节.最后,本文针对RECTANGLE算法的零相关线性逼近问题,采用类似方法进行搜索,同时借助算法本身的传播性质,找到了208条8轮RECTANGLE的零相关线性逼近,并给出了11轮RECTANGLE的零相关线性攻击.该攻击可恢复共44比特轮子密钥,其数据复杂度为2^(63)个已知明文,时间复杂度为2^(107)次11轮RECTANGLE加密运算.

对轻量级密码算法MIBS的零相关线性分析

研究了轻量级分组密码算法MIBS-80抵抗零相关线性分析的能力。结合MIBS-80算法轮函数嵌套SP的Feistel结构特点,给出了8轮零相关线性逼近,并对12轮MIBS-80进行零相关线性分析。攻击所需存储复杂度为258.49,时间复杂度为270,数据复杂度为262.1。

Zodiac密码算法的多维零相关线性分析

分组密码算法Zodiac支持3种密钥长度,分别为Zodiac-128、Zodiac-192、Zodiac-256。利用零相关线性分析方法评估了Zodiac算法的安全性,首先根据算法的结构特性,构造了一些关于Zodiac算法的10轮零相关线性逼近,然后对16轮Zodiac-192进行了多维零相关分析。分析结果显示:攻击过程中一共恢复了19个字节的密钥,其数据复杂度约为2^(124.40)个明密文对,计算复杂度为2^(181.58)次16轮加密。由此可得:16轮(即全轮)192 bit密钥的Zodiac算法(Zodiac-192)对于零相关线性分析方法是不安全的。

TEA型算法零相关线性逼近的研究

通过对TEA型ARX模型各个环节线性掩码传播规律的分析,对该类算法零相关线性逼近进行了研究。证明了该类算法最长零相关线性逼近与圈函数中的左移、右移位数和分组长度这3类参数之间的关系,并给出了最大轮数零相关线性逼近的计数。

多维零相关线性分析模型的改进及在23轮LBlock-s算法中的应用

基于相关性为零的线性逼近的多维零相关线性密码分析是目前最重要的分组密码分析手段之一.该文主要对多维零相关线性分析模型的密钥恢复阶段进行了深入的研究,通过定义等价密钥的距离来刻画等价密钥在压缩表达式中的位置关系,进一步约简区分器候选集合同时优化密钥猜测顺序,从而改进了原有的多维零相关线性分析的攻击模型.改进的模型首先找到所有最长的多维零相关线性区分器,然后利用密钥编排算法求得密钥恢复阶段所涉及的独立猜测密钥量,以此筛选区分器候选集合.最后,根据等价密钥的距离对候选区分器进行再次筛选,同时得到相应的密钥猜测顺序.LBlock-s算法是CAESAR竞赛中所提交的认证加密算法LAC的核心分组算法.与Lblock算法不同,LBlock-s采用具有更快混淆速度的密钥编排算法.基于改进的优化模型,该文分析了该算法抵抗多维零相关线性攻击的能力.研究表明,攻击23轮LBlock-s算法所需的数据复杂度为2^(62.3)个选择明文,时间复杂度为2^(73.75)次23轮LBlock-s加密,存储复杂度为2^(56)字节.这是目前针对LBlock-s算法的最优攻击结果.

自动化搜索ARX分组密码不可能差分与零相关线性闭包

首先,构造了ARX分组密码差分特征及线性掩码的传播方程;然后,利用SAT求解器求解传播方程并且判定该传播系统是否为有效传播;最后,遍历差分特征及线性掩码自动化搜索不可能差分及零相关线性闭包。利用该算法搜索TEA、XTEA和SIMON的不可能差分与零相关线性闭包,并得到TEA、XTEA及SIMON族分组密码的最优不可能差分与零相关线性闭包。此外,利用差分以及线性分布表,该算法能有效搜索基于S盒分组密码的不可能差分及零相关线性闭包。

Zodiac-128算法的多维零相关线性分析

分组密码算法Zodiac支持3种密钥长度,分别为Zodiac-128、Zodiac-192、Zodiac-256。该文首次利用零相关线性分析方法评估了Zodiac算法的安全性,首先根据算法的结构特性,构造了一些关于Zodiac算法的10轮零相关线性逼近,然后对14轮Zodiac-128进行了多维零相关分析。其结果显示:攻击过程中一共恢复了10个字节的密钥,大体需要2123.04个明密文对,计算复杂度为2109.19次14轮加密。由此可得:14轮128比特密钥的Zodiac算法(Zodiac-128)对于零相关线性分析方法是不安全的。

Fox密码的多维零相关线性分析

Fox密码算法是由欧洲学者Junod和Vaudenay是基于Mediacrypt公司的实际需求而设计的系列分组密码.由于在各种平台上的性能表现良好,该算法在许多安全产品中取代了IDEA算法,成为欧洲应用最普遍的密码算法之一.本文首先关注了Fox密码的零相关线性逼近问题,构造出一些关于Fox密码的4轮零相关线性逼近;然后利用合适的线性逼近,结合部分和技术,分析了减缩轮Fox密码针对多维零相关分析技术的安全性,并且成功地恢复部分轮子密钥信息.结果显示:攻击对5轮Fox-64的计算复杂度大约是260.9次5轮Fox加密,对6轮Fox-64分析大约需要2119.4次6轮Fox加密.额外添加1轮并穷举轮子密钥,结果显示零相关分析方法对7轮Fox密码轮子密钥恢复依然有效.本文是第一个关于Fox密码零相关线性分析的结果.

Midori算法的多维零相关线性分析

利用零相关线性分析方法评估Midori64算法的安全性。利用"中间相错"的方法构造了Midori64的6轮零相关线性逼近,在此基础上,对10轮Midori64进行了密钥恢复攻击。该攻击过程的数据复杂度约为262.4个明密文对,计算复杂度为279.35次10轮加密运算。结果表明缩减至10轮的Midori64算法对于零相关线性分析方法是不免疫的。

分组密码Midori128的多维零相关线性分析

为了评估轻量级分组密码算法Midori128的安全性，对Midori128算法进行了多维零相关线性分析。首先利用“中间相错”的方法构造了Midori128的6轮零相关线性逼近，然后基于所构造的6轮零相关线性逼近，对10轮Midori128进行了密钥恢复攻击。该攻击过程的数据复杂度约为2地。∞个明密文对，计算复杂度为2^120.68次10轮加密运算。结果表明，缩减至10轮的Midori128算法对于零相关线性分析方法是不免疫的。

TWINE密码算法的多维零相关线性分析

TWINE密码算法的分组长度为64bit,支持2种密钥长度,分别为TWINE-80和TWINE-128,本文的研究对象为TWINE-128。本文构造了一个与TWINE算法等价的传统的双分支Feistel结构。利用此结构特性,首先构造了算法的14轮零相关线性逼近,之后对24轮的TWINE-128进行了多维零相关线性分析。攻击过程的数据复杂度约为262.1个明密文对,计算复杂度为2107.1次24轮加密。由此可得,缩减轮数(24轮)的TWINE-128对于零相关线性分析方法是不安全的。

SIMON不可能差分及零相关路径自动化搜索算法

对于分组密码,不可能差分和零相关线性分析都是很重要的分析手段.通过研究非线性组件与(AND)的性质,首先得到用于刻画SIMON轮函数差分及线性传播特性的约束式,再基于布尔可满足约束问题(SAT),提出一种普适性不可能差分和零相关路径自动化搜索算法,并利用该算法搜索得到SIMON更多的不可能差分及零相关路径.除用于自动化搜索外,该算法还可判断特定的差分对(掩码对)是否能构成一条有效不可能差分和零相关路径.此外,基于该算法,从抵抗不可能差分攻击的角度出发,给出SIMON轮函数设计中循环移位常数的选取依据.