【作者】 魏悦川；

【导师】 李超；

【作者基本信息】 国防科学技术大学 ， 军队指挥学， 2011， 博士

【摘要】 分组密码是密码学的重要分支.数据加密标准DES的破译与高级加密标准AES的选用对分组密码算法的设计理论与分析理论产生了巨大推动.近几年来,在欧洲序列密码标准的征集活动ECRYPT计划和美国Hash函数标准的征集活动SHA3计划中,越来越多的序列密码和Hash函数都采用了分组密码的设计思想.分组密码设计理论的日渐成熟,对分组密码的分析提出了新的挑战,与此同时,设计理论也亟需新的分析结果来获得更大发展.本文研究了分组密码的不可能差分分析、相关密钥分析、积分分析和差分故障攻击的基本原理,利用这些分析方法对Feistel型密码、修正的Lai-Messay型密码、SPN型密码等算法进行有效地分析,获得了一些新的结果.本文的第一部分利用不可能差分分析方法对Feistel结构与Lai-Messay结构的分组密码进行有效分析.得到了以下几方面的结果:(1)研究了具有SP型轮函数和SPS型轮函数,并且线性层P定义在F2n×n上的Feistel结构.这两种结构在当前非常流行,代表密码为欧洲分组密码标准Camellia和AES候选算法E2.已知结果表明,当轮函数为双射时,Feistel密码存在5轮不可能差分.利用中间相遇法,本文得到了SP型轮函数Feistel密码存在6/7/8轮不可能差分的充分条件: P⊕P?1中汉明重量大于1的列对应着某些6轮不可能差分;通过统计P和P?1在某些特定位置上1的个数可以确定某些7轮不可能差分,通过计算P的某个子矩阵的秩,可以判断8轮不可能差分.我们设计了两个P置换,使用该P置换的Feistel-SP结构不存在上述8轮不可能差分,并且分支数达到最大.SPS型轮函数Feistel密码的6轮不可能差分也可以通过计算P的某个子矩阵的秩来确定.这些结果表明,当设计Feistel密码组件时,为使其能够抵抗不可能差分分析,应该慎重地选择线性层.(2)找到了AES候选算法E2密码的一组6轮不可能差分,对已知结果改进了一轮.基于新的6轮不可能差分,评估了E2密码抵抗不可能差分分析的能力,结果显示不包含初始变换和末端变换的7轮E2-128/192/256和8轮E2-256对不可能差分分析是不免疫的.(3)对修正Lai-Messay结构的FOX系列密码进行研究,结合线性层的性质,找到了FOX的4轮不可能差分,基于这些4轮不可能差分,利用空间-时间权衡技术,给出了对5/6/7轮FOX64以及5轮FOX128的分析结果.本文的第二部分研究相关密钥模型下分组密码的安全性.得到了以下两个结果:(1)研究了SPN结构的分组密码Crypton对相关密钥不可能差分分析的免疫性.通过分析Crypton密码的密钥扩展算法,构造了Crypton的6轮相关密钥不可能差分区分器,利用该区分器,结合线性层的性质,给出了对9轮256比特密钥的Crypton的攻击结果,该攻击可以恢复出Crypton的第9轮的全部密钥字节。(2)研究了韩国Hash标准HAS-160在加密模式下的安全性,HAS-160加密模式可以看作一个具有512比特密钥、160比特明文的分组密码,以前最优的分析结果是基于一个71轮的概率为2?304的相关密钥矩形区分器,通过更细致地研究HAS-160的性质,并引入比特固定技术,本文构造了一个概率为2?290的72轮相关密钥矩形区分器,利用这一区分器,对HAS-160的全部80轮给出了两个攻击方案,改进了已有的分析结果.本文的第三部分研究积分区分器的构造.首先,利用Z’aba基于比特的积分思想,构造了具有256比特分组长度的Rijndael密码新的3轮积分区分器,该区分器只需要32个选择明文,与传统的Square区分器需要256个选择明文相比,明文量大大减少了.其次,利用高阶差分的理论,将密文看作关于明文的布尔函数,利用布尔函数的代数次数理论研究了积分区分器的构造与证明,分别以Rijndael密码和Present密码为例,将基于字节的积分方法与基于比特的积分方法统一到代数次数上来,丰富了积分攻击的理论.最后给出了6轮SMS4结构代数次数的一个上界,该上界远小于理想分组密码的代数次数.本文的第四部分提出了对欧洲标准SHACAL-2密码的差分故障攻击,SHACAL-2密码为广义Feistel结构,通过研究算法的迭代结构,采用面向字的故障诱导模型,在倒数第二轮诱导故障,结合差分分析技术,可以恢复出算法的轮密钥.在PC机上的模拟结果显示,恢复出一个32比特的轮密钥平均需要8个随机错误,结合密钥扩展算法,完全恢复出512比特密钥大约需要128个错误密文.该结果显示了硬件故障对SHACAL-2算法的安全性具有很大潜在危险.更多还原

【Abstract】 Block cipher is an important branch of cryptology. The brokenness of data encryptionstandard(DES)andthelaunchofadvancedencryptionstandard(AES)havegreatlypromotedboth the theories of design and analysis of block cipher. In recent years, from the ECRYPTproject of Europe to SHA-3 project of America, more and more stream ciphers and Hashfunctions were designed based on the idea of block cipher. The design theory of block ciphercomes mature gradually, which proposes more challenge of cryptanalysis. New cryptanaly-sis results can also promote the design theory. This thesis investigates several cryptanalyticmethods, including impossible differential cryptanalysis, related-key cryptanalysis, integralcryptanalysis, differential fault analysis and so on. By using these methods, we analyze Feis-tel cipher, Modified Lai-Messay cipher, SPN cipher etc. efficiently and get some new resultson cryptanalysis.In the first part, impossible differential cryptanalysis on Feistel cipher and modifiedLai-Messay cipher is studied. The main contents and fruits of this part are as follows:(1) Feistel ciphers with SP and SPS round functions are discussed, where the lineartransformation P is defined over F2n×n. The typical ciphers employing the two structuresare European standard Camellia and AES candidate E2. Known result shows that there arealways 5-round impossible differentials of a Feistel cipher with bijective round function. Byusing the method of“miss in the middle”, we find some sufficient conditions for impossi-ble differentials of Feistel-SP ciphers with 6/7/8 rounds, i.e. any column of P⊕P?1 whoseHamming weight is greater than 1 corresponds to some 6-round impossible differentials forFeistel ciphers with SP round functions. The existence of some 7-round impossible differ-entials can be determined by counting the times that 1 appears at some special positions of PandP?1. Some8-roundimpossibledifferentialscanbefoundbycomputingtherankofsomesub-matrix of P. We also present two linear transformations, by employing which, Feistel-SP structure has no 8-round impossible differentials mentioned above. For Feistel cipherswith SPS round functions, by determining the rank of some sub-matrix of P, 6-round im-possible differentials can be found. These results tell us that when designing a Feistel cipherwith SP or SPS round function where the diffusion layer is selected from Fn2×n, the lin-ear transformation should be chosen carefully to make the cipher secure against impossible differential cryptanalysis.(2) For an AES candidate E2, a series of impossible differentials are discovered, whichimproves the former results by one round. We also evaluate the security of E2 against im-possible differential cryptanalysis. The results show that tweaked E2-128/192/256 reducedto 7 rounds and tweaked E2-256 reduced to 8 rounds are not immune to this cryptanalysis.(3) Impossible differential cryptanalysis on FOX, a block cipher with a modified Lai-Messay structure, is studied. Combining properties of the structure and diffusion layer, wepresent some 4-round impossible differentials, based on which we can perform attacks onFOX with reduced rounds and improve the former cryptanalysis results.In the second part, the thesis studies the security of block cipher under the related-keymodel. The main contents and fruits of this part are as follows:(1) We target an SPN cipher Crypton firstly. By analyzing the key schedule of Cryptonand diffusion layer, some 6-round related-key impossible differential distinguishers are con-structed, based on which we perform a 9-round attack on Crypton with 256 bits key for thefirst time. The attack can recover all the bytes of the 9th round key.(2) We aim to re-evaluate the security of HAS-160 in encryption mode—a block cipherwith 512 bits key size and 160 bits plaintext size. Previous attack was based on a 71-roundrelated-key distinguisher with a probability of 2?304. By investigating some delicate proper-tiesofHAS-160andusingabit-fixingtechnique,wepresenta72-roundrelated-keyrectangledistinguisher with a probability of 2?290. Two key recovery attacks on the encryption modeof the full 80-round HAS-160 are performed, which improve the former results.The third part discusses the construction of integral distinguisher, which is used forperforming integral attack. Firstly, by using Z’aba’s idea of bit-pattern based integral, weconstruct a new 3-round distinguisher of Rijndael with 256 bit block length. Comparingwith the Square distinguisher which needs 256 chosen plaintexts, this new one only needs32 chosen plaintexts. Secondly, if we treat the ciphertext as the boolean function respectto plaintext bits, the integral distinguisher can be constructed or proved using the theory ofalgebraic degree. Take Rijndael and Present as examples, we unify byte-oriented integralmethod and bit-oriented integral method in a new way. Finally, we bounded the algebraicdegree of 6-round SMS4 structure, which turns out to be a bad degree.In the last part, we proposed differential fault attack on European standard algorithmSHACAL-2, which employs an unbalanced Feistel structure. By observing the iterate struc- ture, using word-oriented fault model, as well as combining the technique of differentialcryptanalysis, the subkey of SHACAL-2 can be recovered. PC simulation shows that, 8faulty ciphertexts can recover a 32-bit subkey on average, and 128 faulty ciphertexts areneeded to recover all the 512 bit keys if consider the key schedule. The attack indicates thatfaults on hardware greatly threat the security of SHACAL-2.更多还原