基于MILP的相关密钥差分分析安全评估算法改进

近年来,基于混合整数线性规划(MILP)的密码分析方法在对称密码的安全性分析中发挥了重要作用. Zhou等人在FSE 2020上提出了结合分治法,大幅度提高基于MILP的差分和线性特征搜索方法效率.本文将Zhou等人的方法扩展到相关密钥差分特征搜索,提出了一种更高效的基于MILP的相关密钥差分分析安全评估新算法.应用新算法评估了PRESENT-80/128抵抗相关密钥差分分析的安全性,得到了高达15轮的最小活跃S盒数量和高达12轮的最优相关密钥差分特征,并由此得到了迄今最紧的PRESENT-80/128抵抗相关密钥差分分析安全界.找到了一条概率为2^(-62)的15轮PRESENT-80相关密钥差分特征,和一条概率为2-60的16轮PRESENT-128相关密钥差分特征,是目前对于PRESENT-80/128轮数最长的相关密钥差分特征.

对简化版LBLock算法的相关密钥不可能差分攻击

LBLOCK是吴文玲等人于2011年设计的一种轻量级密码算法。该文利用一个特殊的相关密钥差分特征,对19轮的LBlock算法进行了相关密钥不可能差分攻击,攻击的计算复杂度为70.0O(2),所需要的数据量为264。进一步,提出了一种针对21轮LBlock的相关密钥不可能差分攻击,计算复杂度为71.5O(2),数据量为263。

对混沌序列密码的相关密钥攻击

该文首次提出了对混沌序列密码的相关密钥攻击方法。该方法将线性密码分析的思想与对混沌密码的分割攻击方法相结合,利用多个相关密钥产生的乱数序列对混沌密码实施分割攻击,从而大大提高了分割攻击方法的效率,克服了当混沌密码吻合度分布泄漏的信息较小或密钥规模较大时,分割攻击方法难以将攻击方案的计算复杂性降低在可实现范围内的局限。作为例子,该文实现了对具有64bit密钥的ZLL混沌密码的相关密钥攻击,在主频为2．5GHz的Pentium 4-PC机上,整个攻击时间平均为154s,成功率为0．96。

对轻量级密码算法MIBS的相关密钥不可能差分攻击

研究了轻量级分组密码算法MIBS抵抗相关密钥不可能差分的能力。利用MIBS-80密钥编排算法的性质,给出了一个密钥差分特征,并结合特殊明密文对的选取,构造了一个10轮不可能差分。在此不可能差分特征上进行扩展,对14轮的MIBS-80进行了攻击,并给出了复杂度分析。此攻击的结果需要的数据复杂度为254和时间复杂度为256。

相关密钥Square攻击AES-192

利用AES-192子密钥间的内在关系,完全确定了在特定相关密钥差分下的前8轮子密钥的所有确切的差分值,结合Asiacrypt’2010中的密钥桥技术可以确定部分初始密钥,从而发现AES-192的密钥编排方案存在一定缺陷。利用该缺陷,给出了一个相关密钥Square攻击7轮和8轮AES-192的新方法。新方法攻击8轮AES-192仅需244.5选择明文,244.5存储,以及2183.5的8轮AES-192加密。结合部分和技术进一步降低了攻击的计算复杂度。

对低轮AES-256的相关密钥-不可能差分密码分析(英文)

研究AES-256抵抗相关密钥-不可能差分密码分析的能力.首先给出相关密钥的差分,该差分可以扩展到8轮(甚至更多轮)子密钥差分;然后构造出一个5.5轮的相关密钥不可能差分特征.最后,给出一个对7轮AES-256的攻击和4个对8轮AES-256的攻击.

LBlock算法的相关密钥-不可能差分攻击

该文研究了LBlock分组密码算法在相关密钥-不可能差分条件下的安全性.利用子密钥生成算法的差分信息泄漏规律,构造了多条低重量子密钥差分链,给出了15轮相关密钥-不可能差分区分器.通过扩展区分器,给出了23轮和24轮LBlock算法的相关密钥-不可能差分攻击方法.攻击所需的数据复杂度分别为2^(65.2)和2^(65.6)个选择明文,计算复杂度分别为2^(66.2)次23轮LBlock算法加密和2^(66.6)次24轮LBlock算法加密,存储复杂度分别为2^(61.2)和2^(77.2)字节存储空间.与已有结果相比,首次将针对LBlock算法的攻击扩展到了23轮和24轮.

对完整轮数ARIRANG加密模式的相关密钥矩形攻击

对SHA-3计划候选算法ARIRANG采用的分组密码组件进行了安全性分析,利用初始密钥的一个线性变换和轮函数的全1差分特征,给出了一个完整40轮ARIRANG加密模式的相关密钥矩形攻击,该攻击是第一个对ARIRANG加密模式的密码分析结果。攻击结果表明:ARIRANG加密模式作为分组密码是不抵抗相关密钥矩形攻击的。

对基于NLFSR分组密码KTANTAN32的相关密钥中间相遇代数攻击

本文分析了KTANTAN32的代数学弱点.使用相关密钥中间相遇攻击,用代数推导的方法得到了在240轮之后所使用某些密钥的一元线性方程,解这些方程便可迅速逐比特恢复相应密钥.因只须一对相关密钥和2个明密文,即可恢复部分密钥比特,攻击的时间复杂度和空间复杂度都可以忽略不计.分析表明KTANTAN32是一个很弱的算法.同时也说明使用NLFSR和线性密钥编排是KTANTAN32的致命弱点,为抵抗相关密钥中间相遇攻击,设计者应在密钥编排中加入非线性因素.

42轮SHACAL-2新的相关密钥矩形攻击

利用SHACAL-2密码算法轮变换的特点,构造了一个新型的34轮区分器。基于该区分器和部分密钥分别猜测的技术,针对40轮、42轮简化SHACAL-2分别给出了新的攻击方法。研究结果表明:利用2个相关密钥,对40轮SHACAL-2进行相关密钥矩形攻击其数据复杂度约为2235选择明文数据量,计算复杂度约为2432.6次加密;而对42轮SHACAL-2进行相关密钥矩形攻击其数据复杂度约为2235选择明文数据量,计算复杂度约为2472.6次加密。与已有的结果相比较,这些新分析所需的数据复杂度和计算复杂度均有明显的降低。

LBlock算法的相关密钥不可能差分分析

LBlock算法是2011年提出的轻量级分组密码,适用于资源受限的环境.目前,关于LBlock最好的分析结果为基于14轮不可能差分路径和15轮的相关密钥不可能差分路径,攻击的最高轮数为22轮.为研究LBlock算法抵抗不可能差分性质,结合密钥扩展算法的特点和轮函数本身的结构,构造了新的4条15轮相关密钥不可能差分路径.将15轮差分路径向前扩展4轮、向后扩展3轮,分析了22轮LBlock算法.在已有的相关密钥不可能差分攻击的基础上,深入研究了轮函数中S盒的特点,使用2类相关密钥不可能差分路径.基于部分密钥分别猜测技术降低计算量,分析22轮LBlock所需数据量为261个明文,计算量为259.58次22轮加密.

Cobra-H64/128算法的相关密钥-差分攻击

本文研究了Cobra-H64/128分组密码算法在相关密钥-差分攻击下的安全性.针对Cobra-H64算法,利用新构造的相关密钥-差分路径和CP逆变换存在的信息泄露规律给出攻击算法1,恢复出了全部128bit密钥,相应的计算复杂度为2^40.5次Cobra-H64算法加密,数据复杂度为2^40.5个选择明文,存储复杂度为2^22bit,成功率约为1;针对Cobra-H128算法,利用新构造的相关密钥-差分路径给出攻击算法2,恢复出了全部256bit密钥,相应的计算复杂度为2^76次Cobra-H128算法加密,数据复杂度为2^76个选择明文,存储复杂度为2^16.2bit.分析结果表明,Cobra-H64/128算法在相关密钥-差分攻击条件下是不安全的.

对完整轮数ARIRANG加密模式的新的相关密钥矩形攻击

针对ARIRANG加密模式,利用相关密钥矩形攻击的方法对其安全性进行了重新评估。首先找到了一些新的38轮和39轮的高概率相关密钥矩形区分器,然后在此基础上将区分器进行改进,改进的主要思想是:利用模减差分和异或差分的混合表示方式代替原先的异或差分,同时在区分器的输出中选择一个差分集合代替原先单一的差分。基于以上各种新的高概率区分器,对全轮ARIRANG加密模式进行了攻击,其结果优于以往的攻击结果。其中最好的攻击结果为:攻击全轮的ARIRANG-256加密模式所需的数据复杂度和时间复杂度分别为2220.79和2155.60。

CIKS-128分组算法的相关密钥-差分攻击

分析研究了CIKS-128分组密码算法在相关密钥-差分攻击下的安全性.利用DDP结构和非线性函数的差分信息泄漏规律构造了一条高概率相关密钥-差分特征,并给出攻击算法,恢复出了192bit密钥;在此基础上,对剩余64bit密钥进行穷举攻击,恢复出了算法的全部256bit密钥.攻击所需的计算复杂度为277次CIKS-128算法加密,数据复杂度为277个相关密钥-选择明文,存储复杂度为225.4字节存储空间.分析结果表明,CIKS-128算法在相关密钥-差分攻击条件下是不安全的.

Eagle-128算法的相关密钥-矩形攻击

该文利用高次DDO(Data Dependent Operations)结构的差分重量平衡性和SPN结构的高概率差分对构造了Eagle-128分组密码算法的两条5轮相关密钥-差分特征,通过连接两条5轮特征构造了完全轮相关密钥-矩形区分器,并对算法进行了相关密钥-矩形攻击,恢复出了Eagle-128算法的64 bit密钥。攻击所需的数据复杂度为281.5个相关密钥-选择明文,计算复杂度为2106.7次Eagle-128算法加密,存储复杂度为250 Byte存储空间,成功率约为0.954。分析结果表明,Eagle-128算法在相关密钥-矩形攻击条件下的有效密钥长度为192 bit。

LBlock算法的相关密钥不可能飞来去器分析

研究了相关密钥不可能飞来去器分析方法及轻量级分组密码算法LBlock在该分析方法下的安全性。将不可能飞来去器分析方法和相关密钥分析方法相结合,针对22轮LBlock给出了新的攻击。构造了15轮的相关密钥不可能飞来去器区分器,通过向前扩展3轮,向后扩展4轮,成功攻击了22轮LBlock。该攻击的数据复杂度仅为2^(51.3)个明文,计算复杂度为2^(71.54)次22轮加密。与已有结果相比,攻击的数据复杂度和计算复杂度均有明显下降。

轻量级分组密码算法ESF的相关密钥不可能差分分析

八阵图算法(ESF)是一种具有广义Feistel结构的轻量级分组密码算法,可用在物联网环境下保护射频识别(RFID)标签等资源受限的环境中,目前对该算法的安全性研究主要为不可能差分分析。该文通过深入研究S盒的特点并结合ESF密钥扩展算法的性质,研究了ESF抵抗相关密钥不可能差分攻击的能力。通过构造11轮相关密钥不可能差分区分器,在此基础上前后各扩展2轮,成功攻击15轮ESF算法。该攻击的时间复杂度为2^(40.5)次15轮加密,数据复杂度为2^(61.5)个选择明文,恢复密钥比特数为40 bit。与现有结果相比,攻击轮数提高的情况下,时间复杂度降低,数据复杂度也较为理想。

TWINE算法的相关密钥不可能飞来去器攻击

为了评估轻量级分组密码算法TWINE的安全性,利用相关密钥不可能飞来去器的方法对其进行了分析。构造了由16轮和17轮两条路径组成的相关密钥不可能飞来去器区分器,并将16轮和17轮的路径向前扩展4轮、向后分别扩展3轮和2轮,完成对23轮TWINE密码算法(80 bit密钥)的攻击。实验结果表明,该攻击的数据复杂度为262. 05个明文,时间复杂度为270.49次23轮加密,与现有算法相比有明显优势。

ESF算法的相关密钥不可能差分分析

ESF算法是一种具有广义Feistel结构的32轮迭代型轻量级分组密码。为研究ESF算法抵抗不可能差分攻击的能力,首次对ESF算法进行相关密钥不可能差分分析,结合密钥扩展算法的特点和轮函数本身的结构,构造了两条10轮相关密钥不可能差分路径。将一条10轮的相关密钥不可能差分路径向前向后分别扩展1轮和2轮,分析了13轮ESF算法,数据复杂度是260次选择明文对,计算量是223次13轮加密,可恢复18bit密钥。将另一条10轮的相关密钥不可能差分路径向前向后都扩展2轮,分析了14轮ESF算法,数据复杂度是262选择明文对,计算复杂度是243.95次14轮加密,可恢复37bit密钥。

减轮GOST2的相关密钥差分攻击

2015年,文献[1]提出GOST的改进版本GOST2,该版本使GOST2便于硬件实现,且抵抗相关密钥攻击能力更强。给出GOST216轮概率为1的相关密钥差分区分器,计算S盒平均差分分布概率,建立概率为1.75×2-7的GOST221轮相关密钥截断差分特征,恢复GOST2第5~27轮中的64比特密钥。此外,还给出GOST2的第26~28轮相关密钥截断差分特征及概率。