Simon量子算法攻击下的可调加密方案研究

随着量子计算机和量子计算技术的迅速发展,量子算法对密码系统安全性的威胁迫在眉睫。之前的研究表明,许多经典安全的对称密码结构或方案在基于Simon算法的量子攻击下不安全,例如3轮Feistel结构、Even-Mansour结构、CBC-MAC、GCM和OCB等方案。可调加密方案通常设计为分组密码工作模式,用于磁盘扇区加密,其结构可以分为Encrypt-MaskEncrypt(CMC、EME、EME*等)、Hash-CTR-Hash(XCB、HCTR、HCH等)和Hash-ECB-Hash(PEP、TET、HEH等)三种类型。本文利用Simon算法,对HCTR、HCH、PEP和HEH四种可调加密方案进行了分析,研究结果表明这四种可调加密方案在选择明文量子攻击下是不安全的,使用多项式次的量子问询即可得到与方案秘密值有关的周期函数的周期,进而将其和可调随机置换区分开来。对于利用Simon算法对可调加密方案的攻击,构造周期函数是关键。一般基于两种特殊形式的可调加密方案构造周期函数:一种是固定调柄,一种是变化调柄。本文用变化调柄的方法给出了对CMC和TET两种可调加密方案更简洁的量子攻击方法。通过对比分析,固定调柄和变化调柄两种不同的Simon量子攻击方式得到的周期不同,可结合得到进一步的结果。最后本文从固定调柄和变化调柄的角度对可调加密方案的一般量子攻击方法进行了总结,并给出了对基于泛哈希函数可调加密方案(Hash-CTR-Hash和Hash-ECB-Hash)的通用攻击。

基于量子Simon算法对分组密码类EM结构的密钥恢复攻击

文章基于量子Simon算法(一类经典量子周期寻找算法)的量子过程以及应用,对类EM结构进行基于量子Simon算法的密码分析,以类EM结构的加密算法为研究对象,运用量子Simon算法,构造适用于Simon算法的函数,对类EM加密结构的5轮加密过程进行密钥恢复攻击。结果显示,在密钥长度的多项式时间内,文章所提方法可以成功恢复出第五轮加密密钥,且根据此密钥可以分析出其他轮密钥。研究结果表明,在密钥长度的多项式时间内,可以找到其中一个密钥,量子条件下密钥的可恢复性说明该结构的安全轮数应当高于5轮,为未来对称密码体制的研究和发展奠定了一定的基础。

量子计算模型下PFP算法的安全性分析

量子技术的快速发展和量子计算效率的不断提高,以及Shor算法和Grover算法的出现,给传统公钥密码和对称密码的安全性造成了较大威胁。因此,基于Feistel结构设计的分组密码PFP算法,首先将轮函数的线性变换P融入Feistel结构的周期函数构造,推导得到PFP算法的4个5轮周期函数,比选择明文攻击模型下典型Feistel结构的周期函数多2轮,并通过实验验证正确性;进一步地,以其中一个5轮周期函数作为区分器,结合量子Grover算法和Simon算法,通过分析PFP密钥编排算法的特点对9、10轮PFP进行了安全性评估,得到正确密钥比特需要的时间复杂度为2^(26)、2^(38.5),需要的量子资源为193、212个量子比特,可以恢复58、77比特密钥,优于已有不可能差分分析结果。

SIMON类非线性函数的线性性质研究

SIMON算法是由美国国家安全局(NSA)在2013年推出的一簇轻量级分组密码算法,具有实现代价低、安全性能好等优点,其轮函数采用了F(x)=(x<<<a)&(x<<<b)+(x<<<c)类型的非线性函数。该文研究了移位参数(a,b,c)一般化时SIMON类算法轮函数的线性性质,解决了这类非线性函数的Walsh谱分布规律问题,证明了其相关优势只可能取到0或2^(-k),其中k∈Z且0≤k≤|2^(-1)n|,并且对于特定条件下的每一个,都存在相应的掩码对使得相关优势等于2^(-k),给出了相关优势取到2^(-1)时的充分必要条件及掩码对的计数,给出了特定条件下非平凡相关优势取到最小值时的充分必要条件与掩码对的计数。

分组密码结构抗Simon量子算法攻击研究

本文首先对Simon量子算法作出了进一步研究,证明了Simon承诺中存在周期的随机函数具有唯一周期的概率接近1.随后总结了对常见分组密码结构进行Simon量子算法攻击的一般性步骤,指出对Feistel结构及其扩展结构应用Simon算法时,只需要中间的轮函数为置换,就可以构造出完全满足Simon承诺的周期函数.同时修正了Dong等人对RC6算法结构攻击中的错误,并且对三轮MISTY-L和MISTY-R进行了区分攻击.最后论证了在选择明文攻击下,三轮Lai-Massey结构能够抵抗Simon量子算法攻击.

Simon算法对SIMON密码的密钥恢复攻击

近年来,随着量子技术被应用到密码算法的安全性分析中,经典密码算法的安全性受到了极大的威胁.将Simon量子算法应用到SIMON密码的分析之中,成功构造一个周期函数,将3轮SIMON密码与随机置换区分开.随后对该周期函数满足Simon问题条件的参数进行估计,找到且证明其存在一个上界,从而计算出SIMON32/48/64这3类密码对应参数的上界值.最后通过分别构造加密和解密过程相应的区分器,对6轮SIMON密码进行了密钥恢复攻击,得到了4个轮密钥,并给出了该攻击的时间复杂度.

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

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

SIMON算法的差分—线性密码分析

差分分析和线性分析是目前分组密码算法攻击中较常见的两种方法,差分—线性分析是基于这两种方法建立的一种分析方法,近年来受到密码学界的广泛关注。SIMON算法是一种重要的轻量级密码算法,文章主要对SIMON 32/64和SIMON 48进行差分—线性分析,分别构造13轮差分—线性区分器,基于区分器分别进行16轮密钥恢复攻击,数据复杂度分别为2^(26)和2^(42),时间复杂度分别为2^(40.59)和2^(61.59),增加了SIMON算法的安全性评估维度,丰富了差分—线性分析的实际案例。

一种高性能多模式可配置SIMON加密电路设计

文章设计了一种用于物联网(Internet of Things,IoT)安全的多模式SIMON轻量级数据加密电路,采用Verilog HDL描述。为保证IoT场景多样化的加密性能需求,设计实现了支持输出反馈(output feedback,OFB)及计数器(CTR)分组迭代方式且分组和密钥长度可变的SIMON算法加密电路。整个电路利用数据路径复用方法减小硬件开销并基于现场可编程门阵列(field programmable gate array,FPGA)平台进行验证。测试结果表明,仅支持10种配置的加密电路最大频率为350 MHz,消耗245个Slices,最大吞吐率为658.8 Mb/s,在扩展OFB和CTR后,消耗Slices仅提升19.6%。

SIMON密码算法线性路径的成功概率计算

分组密码是现代密码学的重要组成部分,其设计与分析是信息安全领域中的热点问题.2013年美国国家安全局(National Security Agency,简写为NSA)提出了轻量级分组密码SIMON和SPECK算法.针对SIMON算法的线性分析,本文分别针对其3、7和10轮的线性路径的成功概率进行了详细的计算,为SIMON算法的线性分析提供理论指导和借鉴.

代数次数的求解算法及其在SIMON-like算法中的应用

代数次数作为布尔函数重要的密码学指标,在密码算法的设计与分析中有着重要的应用.主要研究布尔函数代数次数的求解及其在分组密码SIMON-like算法中的应用.首先,在利用真值表求解代数正规型算法的基础上建立了基于CUDA的并行求解架构,协同利用CPU和GPU的计算资源,极大地缩短了求解代数次数的时间,在较短的时间内求解了SIMON32算法和SIMECK32算法任意轮数的代数正规型和代数次数;其次,在Cube攻击理论的基础上,根据代数次数和超多项式取值之间的关系,设计了估计代数次数的概率算法,估计了一般SIMON-like算法布尔函数的代数次数;最后,从布尔函数代数次数的角度出发,给出了SIMON-like算法在选择不同循环移位参数表现的差异性,进而给出循环移位参数的选取依据.实验结果表明,SIMON算法在原始参数下,达到最大代数次数所需的轮数最短,原始参数具有更高的安全性.

基于Simon-wong刚体算法的风力机风速仪测风准确性研究

为了对风力机风速仪测量风速的准确性进行分析,本文以风速仪修正试验数据为基础,采用三维流场计算方法对其进行研究,并在数值研究中,加入风速仪计算模型,同时采用Simon-wong刚体算法解决风速仪在数值模拟中的被动响应问题。通过对试验数据和模拟结果对比分析后可知:风力机在运行状态下,风速仪测量风速与实际来流之间存在偏差,且最大偏差出现在风力机额定转速附近;与一般定常计算模拟相比,加入风速仪计算模型后,风速仪模拟测量风速最大误差由6.4%降为2.89%,模拟结果更为准确;风速仪在风速测量中,自身也存在测量风速极差,且极差随着来流风速的增加而变大。

基于Simon量子算法的密钥认证分析研究

针对密钥认证过程中存在的攻击影响认证效果的情况,提出基于Simon量子算法的密钥认证分析研究.首先对Simon量子算法的运算规则以及对应的密钥设计方式进行分析,在此基础上,根据Simon量子算法,通过寄存器转换,进行密钥认证过程中的周期计算,并将这种周期特性应用到密钥认证过程的询问程序中,以此实现密钥准确认证.实验结果表明,所提方法的密钥准确认证概率始终在90%以上,计算耗时稳定在10s以内,并在面临安全攻击时能够保持较高的认证准确率,实现了信息安全保障.

Simon量子算法在对称密码分析中的应用浅析

量子算法给对称密码体制的安全性带来了巨大挑战。Simon量子算法受益于量子算法的并行性,其快速寻找函数周期的性质被用来构造区分攻击、密钥恢复攻击、滑动攻击、量子伪造攻击等多种攻击形式。对于不同的分组密码结构,应用Simon量子算法做密码分析,取得的攻击结果不尽相同。结合Simon量子算法在对称密码分析中的攻击特点,探索其在对称密码分析中的重要应用,给出了几种提升对称密码抗量子攻击能力的方法。

轻量级分组密码Piccolo的量子密码分析

根据Piccolo算法RP置换的结构特点,提出3轮量子区分器,并用Grover meets Simon算法进行6轮量子密钥恢复攻击。分析结果表明,该攻击可恢复密钥56 bit,时间复杂度为2^(28),共需量子比特数为464;当攻击轮数大于6轮时,时间复杂度为2^(28+16(r-6)),降至Grover量子暴力搜索的1/2^(68)。与传统差分和线性分析相比,所提攻击方法时间复杂度更低,且较Grover暴力搜索的时间复杂度大幅降低,为后续轻量级分组密码的量子攻击的研究奠定了基础。

基于周期性质的新型密钥恢复攻击方法

针对Feistel, Misty与Type-1/2型广义Feistel等结构,创新性地将Simon算法的周期性质与生日攻击思想相结合,提出一种新型传统密钥恢复攻击.与Simon算法可以在多项式时间内恢复周期值不同,在传统计算环境下至少需要生日攻击界才能恢复出对应的周期值.利用所提方法,可以在O (2n/4)的选择明文和密文条件下,以O(23n/4)的时间复杂度恢复出5轮Feistel-F结构的密钥,对应的存储复杂度为O(2n/4).上述结果比Isobe和Shibutani的工作结果多扩展1轮,并且所需的存储复杂度也更少.对于Feistel-FK结构,构造7轮密钥恢复攻击.此外,还将上述方法应用于构造Misty结构和Type-1/2型广义Feistel结构的密钥恢复攻击.对于不同的Misty密码方案,分别给出5轮Misty L-F和Misty R-F结构的密钥恢复攻击,以及6轮Misty L-KF/FK和Misty R-KF/FK结构的密钥恢复攻击.对于d分支Type-1型广义Feistel结构,给出d2轮的密钥恢复攻击.当d≥6时,对于d分支Type-2型广义Feistel结构的新型密钥恢复攻击轮数会优于现有密钥恢复攻击轮数.

SIMECK32/64算法的不可能差分分析

对分组密码SIMECK32/64算法抗不可能差分分析的能力进行研究,利用中间相遇技术,构造该算法的11轮不可能差分路径。采用向前解密4轮以及向后加密4轮进行19轮不可能差分分析攻击。分析结果表明,该路径只需要猜测29 bit子密钥,并且与零相关线性分析相比,针对SIMECK32/64算法的不可能差分攻击的分析复杂度大幅减小。

SMS4-like结构以及NBC算法的量子算法攻击研究

本文利用Simon量子算法和Grover搜索算法首次给出对SMS4-like结构,和作为改进的第二类广义Feistel结构的代表算法之一的NBC算法的量子算法攻击.对SMS4给出6轮量子区分器,进行10轮量子密钥恢复攻击;首次对SMS4-like结构给出(2d-2)轮量子区分器,进行(3d-2)轮量子密钥恢复攻击.对NBC-128给出6轮量子区分器,进行11轮量子密钥恢复攻击;对NBC-256给出10轮量子区分器,进行16轮量子密钥恢复攻击.

MARS-like Feistel 结构的量子攻击

本文首次给出了对MARS-like结构的量子算法攻击.通过利用Simon算法,借助周期函数f构建量子区分器,结合Grover搜索算法进行量子密钥恢复攻击.在量子选择明文条件下,对四分支MARS-like结构,我们在4轮量子区分器附加4轮进行8轮量子密钥恢复攻击;对d分支MARS-like结构,我们在d轮量子区分器附加d轮进行2d轮量子密钥恢复攻击.在量子选择密文条件下,对四分支MARS-like结构,我们在5轮量子区分器附加4轮进行9轮量子密钥恢复攻击;对d分支MARS-like结构,我们在d+1轮量子区分器附加d轮进行2d+1轮量子密钥恢复攻击.

若干广义非平衡Feistel结构的量子分析研究

分组密码结构对密码算法的安全性有着非常重要的作用.随着量子计算的发展,以Simon算法、Grover算法等为代表的量子搜索算法,广泛应用于分组密码安全性研究领域,并产生了一定的威胁.本文首次研究了对5种广义非平衡Feistel结构的量子攻击,对n-cell结构构造了n+1轮量子区分器;对New Structure Ⅰ/Ⅲ/Ⅳ结构分别构造了6轮/9轮/5轮量子区分器;对FBC-like结构构造了3轮量子区分器,并利用Simon算法对这5种分组密码结构进行了量子区分攻击.进一步,将Simon算法和Grover算法相结合对n-cell结构、New Structure Ⅰ/Ⅲ/Ⅳ结构和FBC-like结构进行了量子密钥恢复攻击,并分析了攻击的时间复杂度.攻击r>n+1轮n-cell结构的时间复杂度为O(2^((r-n-1)k/2));攻击r>6/14/9轮New Structure Ⅰ/Ⅲ/Ⅳ结构的时间复杂度分别为O(2^((r-6)k/2))/O(2^([2k+(r-14)k]/2))/O(2^([2k+(r-9)k]/2));攻击r>5轮FBC-like结构的时间复杂度为O(2^([3k+(r-5)·2k]/2)).结果表明这些攻击的效果均优于使用Grover算法进行穷举攻击.