【作者】 崔霆；

【导师】 金晨辉；

【作者基本信息】 解放军信息工程大学 ， 密码学， 2013， 博士

【摘要】 不可能差分分析是针对分组密码的一种重要分析方法,该分析技术的关键在于给出分组密码算法最长的不可能差分区分器。不可能差分区分器的长度也是衡量分组密码抵抗不可能差分分析的一个重要标准。本文致力于分组密码整体结构不可能差分区分器的构造方法研究,主要工作如下：1.对SP结构的不可能差分性质进行了研究,首次提出并证明了SP结构不可能差分区分器存在的充要条件,进而给出了搜索SP结构全部不可能差分区分器的方法,因此能够找到SP结构最长的不可能差分区分器。作为特例,证明了AES算法至多存在4轮的不可能差分区分器；并证明了如果P盒采用MDS矩阵设计,则SP结构不存在超过2轮的不可能差分区分器。本文对评价SP结构抗不可能差分分析的能力具有参考价值。2.对常见的广义Feistel结构的不可能差分性质进行了研究,给出了嵌套SP/SPS结构的m分组广义Skipjack结构、CAST256结构和广义MARS结构迄今为止最长的不可能差分区分器。较之前人结论,使上述三个结构的不可能差分对应的长度比现有结果增加了2轮、m-1轮和m-1轮；分析了New-Structure I-IV结构的不可能差分性质,首次给出了这些结构的14轮、无限轮、16轮和19轮不可能差分区分器,从而丰富了常见的广义Feistel结构的安全性分析的结论。3.提出了构造一般广义Feistel结构不可能差分区分器的解标签方法。该方法对广义Feistel结构的具体结构和轮函数的具体结构没有限制,以多个常见的嵌套SP结构的广义Feistel结构为例,找出的不可能差分区分器的长度均长于已知的最佳结果。最后通过证明密码结构之间存在差分-线性相似关系,将解标签方法扩展到解决分组密码结构的零相关线性逼近的搜索问题。4.分析了Inscrypt2009年会提出的VGF2结构的安全性,指出任意轮VGF2结构均存在概率为1的差分路径,并给出了任意轮VGF2结构的不可能差分区分器,进而提出了对满轮VGF2算法的唯密文攻击方法,能够在不求解密钥的前提下实时获得明文的一半比特。本文以264次MAC运算和0.392的成功率,找到了基于256比特VGF2算法的类CBC消息认证码的消息碰撞,并以2128次MAC运算和1的成功率进行了泛伪造攻击。5.研究了类FOX结构的不可能差分特性,首次证明了类FOX结构存在着不依赖于轮函数和线性正形置换具体结构的新的4轮不可能差分,并在轮函数设计为SP结构时,给出了类FOX结构的5轮不可能差分的构造。更多还原

【Abstract】 Impossible differential cryptanalysis is one of the most powerful attacks against blockcipher, and the key step of this cryptanalysis is to find out the longest impossible differentials.The length of impossible differentials can also be treated as a measurement against impossibledifferential cryptanalysis. This paper works on constructing impossible differentials for blockcipher structures, and our main contribution includes:1. This paper studies the impossible differential property for SP structures. For the first time,we provide a necessary and sufficient condition of the existence of impossible differentials in SPstructure, then we provide a method to search out all impossible differentials in SPN, by whichwe can find the longest impossible differentials in SP structure. As a special example, we provethat impossible diffentials in AES can not exceed4rounds, and we prove that if the SP structureemploies MDS matrix as the P layer, we can never find impossible differentials longer than2rounds. This paper is helpful in measuring the immunity against impossible cryptanalysis for SPstructure.2. We study on the impossible differential properties for some popular generalized Feistelstructures. We provide the longest impossible differentials for m-dataline Skipjack-likestructure, CAST256-like structure and MARS-like structure. Compare with the existed results,our results improve2, m1and m1rounds for each structure respectively. Besides, westudy on the impossible differential properties for New-Structure I~IV, and we provide14rounds, infinite rounds,16rounds and19rounds impossible differentials for these structuresrepectively. Our investigation enriches the security results of generalized Feistel structures.3We propose the solution-tag method to find impossible differentials of generalized Feistelstructures. This method has no restrict on neither the overall structure nor the round function,compare with traditional methods, we can find longer impossible differentials of somewell-known block cipher structures with SP round functions. Later, we point that there exsitsdifferential-linear conjugation relationships between overall structures, by this property, thesolution-tag method can be used to find zero-corollaries for some block cipher structures.4. We analyze the security of VGF2structure, which was proposed in Inscrypt2009, wepointed that there exists1-probability differential in arbitrary rounds VGF2, also we proved thatthere exists impossible differential for arbitrary rounds VGF2. Sequentially, we launch areal-time ciphertext-only attack on the full round block cipher VGF2, this attack can obtain halfbits of the plaintext without calculate the key. And we further find a collision for VGF2-basedCBC-like MAC within264MAC operations and successful rate reaches0.392. We also launcha universal forgery attack on VGF2-based CBC-like MAC, in the attack, we need2128times MAC operations and the successful rate reaches1.5. This paper investigates impossible properties of FOX-like structure. And prove that thereexist new4rounds impossible differentials in FOX-like structure, which do not depend on thestrength of the round function or the orthomorphic permutation. Also, we provide the method forfinding5rounds impossible differentials in FOX-like structure with SP-based round function.更多还原