【作者】 李雷波；

【导师】 王小云；

【作者基本信息】 山东大学 ， 信息安全， 2014， 博士

【摘要】 分组密码是加解密双方用同一密钥进行加密和解密运算的密码算法,是保障数据机密性与完整性的重要技术。分组密码的安全性分析有利于发现算法中存在的不足,以确保算法在实际应用中的安全,并指导新的算法设计。上世纪末,随着美国AES计划[1]、欧洲NESSIE计划[2]和日本CRYPTREC计划[3]的相继实施,对相应标准密码算法的安全性分析被国际密码学者广泛关注,极大地推动了分组密码分析与设计工作的发展。本文主要对三个国际标准分组密码算法AES、Camellia和CLEFIA的安全性进行分析,提出一些有意义的密码学性质,并与国际上最前沿的分析结果相比得到最优的结果。1、分组密码AES的安全性分析分组密码Rijndael是由两位比利时密码学者Daemen和Rijmen于1997年设计,并于2000年10月被美国国家标准和技术研究所(NIST)公布为高级加密标准AES (Advanced Encryption Standard)。之后,AES被CRYPTREC工程和NESSIE工程推荐,并由国际标准化组织(ISO)选定为国际标准ISO/IEC18033-3。AES的分组长度为128比特,采用SPN结构,密钥长度有128比特、192比特和256比特三个版本,本文分别用AES-128、AES-192与AES-256表示。AES的中间相遇攻击是由Demirci和Selcuk于2008年FSE会议上提出[7],他们利用4轮AES区分器给出了7轮AES-192和8轮AES-256的分析结果。在2010年亚密会上,Dunkelman, Keller和Shamir提出了差分列举技术思想和Multiset技术,有效的减少了Demirci和Selquk攻击的存储和时间复杂度。同时,利用数据/时间/存储折衷技术给出了7轮AES-128的中间相遇分析结果。在2013年欧密会上,Derbez, Fouque和Jean利用Hash函数分析中的反弹(Rebound)技术,极大减少了Dunkelman等人攻击的时间和存储复杂度。并构造了5轮AES-256区分器,给出了9轮AES-256的分析结果。本文主要考虑单密钥模式下,对AES-192/256的中间相遇攻击。我们提出了一种改进中间相遇攻击的新方法——基于密钥的中间状态过滤,并利用此方法构造了5轮AES-192区分器,结合数据/时间/存储折衷完成了对9轮AES-192的中间相遇攻击。我们的攻击延续了Dunkelman等人所提出的差分列举的思想,但不同的是,我们利用中间状态的密钥关系,用有序数列代替Multiset来获取更多的信息量,以减少攻击的复杂度。这是除Biclique方法之外[10],首次对9轮AES-192的分析结果。同时,我们利用攻击中预计算与在线阶段的密钥关系,将整个攻击分割为一系列的子攻击,每个子攻击都是相互独立的。当所有的子攻击工作于串行模式的时候,相应的存储空间可以重复使用。利用此方法,我们降低了整个攻击的存储复杂度。对于9轮AES-256,与2013年欧密会的结果[9]相比,存储复杂度降低了232,但数据复杂度和时间复杂度不受影响。2、分组密码Camellia的安全性分析分组密码算法Camellia由日本NTT和三菱公司于2000年设计,其分组长度为128比特,密钥长度有128比特、192比特和256比特三个版本。Camellia被CRYPTREC工程推荐为日本的e-government算法,也是NESSIE工程最终选取的算法之一,并且由国际标准化组织(ISO)选定为国际标准ISO/IEC18033-3。本文研究了Camellia算法的不可能差分分析和中间相遇攻击。首先,我们给出了带FL/FL-1层Camellia算法的7轮不可能差分特征。利用该不可能差分特征,我们分析了不带白化密钥的10轮Camellia-128,以及带白化密钥的10轮Camellia-192和11轮Camellia-256算法。同时,我们给出了在3/4弱密钥空间里,带FL/FL-1层的7轮不可能差分特征。之后利用该特征给出了弱密钥条件下、10/11/12轮Camellia-128/192/256的不可能差分分析。在此基础上,我们提出了复合攻击的思想：即利用每次失败的攻击来推出2比特的密钥条件,经过a次攻击,推出2×a比特密钥信息。从而,将弱密钥条件下的攻击转化为对全密钥空间的攻击。除此之外,我们还给出了中间14轮Camellia-256和12轮Camellia-192的分析结果。其次,结合2010年亚密会上Dunkelman等人所提出的差分列举思想和Mulitset技术,我们给出了7轮Camellia-192的中间相遇性质。并以此构造了12轮Camellia-192的中间相遇攻击,复杂度比当前最优结果快大约28倍。此外,我们给出了8轮Camellia-256的中间相遇性质,并以此构造了带两个FL/FL-1层的13轮Camellia-256的中间相遇攻击,据我们所知,这是第一个对首轮开始13轮Camellia-256的分析结果。我们同样给出了不带白化密钥的14轮Camellia-256的分析结果。3、分组密码CLEFIA的安全性分析CLEFIA是由索尼公司(Sony Corporation)于2007年设计,2012年被ISO/IEC29192-2选举为轻量级分组密码算法标准,2013年被日本CRYP-TREC项目推荐为e-Government建议算法。CLEFIA采用四路广义Fesitel结构,分组长度为128比特,密钥长度有128比特、192比特和256比特三个版本。本文给出了一个10轮的CLEFIA截断差分特征,并给出了13轮CLEFIA-128的分析结果。之后,结合Isobe等人提出的函数归约技术,我们给出了14/15轮CLEFIA-192/256的分析结果。复杂度比当前最优结果快大约240倍。最后,结合轮函数的密钥关系,我们给出了14轮CLEFIA-128的分析结果,据我们所知,这是第一个对14轮CLEFIA-128的分析结果。更多还原

【Abstract】 The block cipher plays an important role in cryptography, which is the core tech-nique of providing confidentiality and integrity protections in secure communication. It belongs to the symmetric-key ciphers that use the same key to encrypt and decrypt. Cryptanalysis of block ciphers can not only ensure their security application in practice by discovering the weakness of them, but also guide the design of new block ciphers. In previous years, with the competition of AES by NIST, the process of NESSIE and the CRYPTREC project, the security analysis of international standard ciphers has attracted a great amount of attentions from worldwide cryptology researchers, that greatly promoted the analysis and design of block ciphers.This thesis focus on the cryptanalysis of three international standard ciphers AES, Camellia and CLEFIA. We also propose some interesting properties of ciphers and get the best results of attack compared with the previous works.1. Cryptanalysis of9-Round AES-192/256The block cipher Rijndael was designed by Daemen and Rijmen in1997, and was selected as the Advanced Encryption Standard (AES) in2001by NIST. AES was also selected as an e-government recommended cipher by CRYPTREC in2002, NESSIE block cipher portfolio in2003and international standard by ISO/TEC18033-3in2005. It is a Substitution-Permutation Network (SPN) with variable key length of128,192,256, which are denoted as AES-128, AES-192and AES-256, respectively.The meet-in-the-middle (MITM) attack on AES was introduced by Demirci and Selcuk at FSE2008to improve the collision attack proposed by Gilbert and Minier. They constructed a4-round distinguisher to attack the7-round AES-192and8-round AES-256. At ASIACRYPT2010, Dunkelman, Keller and Shamir ex-ploited the differential enumeration and multiset ideas for MITM attack to reduce the high memory complexity in Demirci and Selcuk attack. Then combined with the data/time/memory tradeoff, they get the result of attack on7-round AES-128. Further-more, Derbez, Fouque and Jean presented a significant improvement of Dunkelman et al.’s attack at EUROCRYPT2013. Using the rebound-like idea, they gave the most efficient attacks on7-round AES-128and8-round AES-192/256. Besides, they introduced a5-round distinguisher to analyse9-round AES-256.In this paper, we focuse on key-recovery attacks on9-round AES-192and AES-256under single-key model with the framework of the meet-in-the-middle attack. A new technique named key-dependent sieve is introduced to further reduce the size of lookup table of the attack. We construct a5-round distinguisher and attack the9-round AES-192with2121chosen plaintexts,2187.59-round encryptions and2185128-bit words of memory. If the attack starts from the third round, the complexities would be further reduced by a factor of16. Moreover, we show that the whole attack is able to be sorted into a series of sub-attacks by using of the shared key information in the online and offline phases. That supports us to reduce the memory complexity of the attack without any cost of the data and time complexities, since we can perform the attack in streaming mode by working on each sub-attack independently and releasing the memories afterwards. For9-round attacks on AES-192and AES-256, the memory complexities are reduced by28and232times, respectively.2. Cryptanalysis of Reduced-Round CamelliaThe block cipher Camellia is a128-bit block cipher with variable key length of128,192and256, which are denoted as Camellia-128, Camellia-192and Camellia-256, respectively. Camellia was proposed by NTT and Mitsubishi in2000, and was selected as an e-government recommended cipher by CRYPTREC in2002, NESSIE block cipher portfolio in2003and international standard by ISO/IEC18033-3in 2005. In this paper, we study the security analysis of reduced-round Camellia with the methods of impossible differential attack and meet-in-the-middle attack.Firstly, we introduce a7-round impossible differential of Camellia including FL/FL-1layer. Utilizing impossible differential attack,10-round Camellia-128is breakable with2118.5chosen plaintexts and2123.510round encryptions. Moreover, the results of attack on10-round Camellia-192and11-round Camellia-256can also be improved. Further, we introduce a7-round impossible differentials of Camellia for weak keys, which can be used to attack the reduced-round Camellia under weak-key setting. The weak keys that work for the impossible differential take3/4of the whole key space, therefore, we can further get rid of the weak-key assumption and leverage the attacks to all keys by utilizing a method that is called the multiplied method. As a result, for the whole key space,10-round Camellia-128,11-round Camellia-192and12-round Camellia-256can be attacked with about2120,2184and2240encryptions, re-spectively. In addition, we are able to extend the attacks to12-round Camellia-192and14-round Camellia-256which include two FL/FL-1layers, provided that the attacks do not have to be started from the first round.Secondly, combined with the differential enumeration technique proposed by Dunkelman et al. at ASIACRYPT2010and other sophisticated techniques, we pro-pose a new7-round MITM property for Camellia-192and mount a12-round attack with2113chosen plaintexts,2180encryptions and2154128-bit memories. Furthermore, we present an8-round property of Camellia and achieve13-round attack on Camellia-256with2113chosen plaintexts,2232.7encryptions and2227128-bit memories. We also give a result of attack on14-round Camellia-256without whitening keys. To the best our knowledge, there are the most efficient results of cryptanalysis of reduced-round Camellia-192/256.3. Cryptanalysis of Reduced-Round CLEFIACLEFIA is a128-bit block cipher with variable key length of128,192and256, which are denoted as CLEFIA-128, CLEFIA-192and CLEFIA-256, respectively. It was proposed by Sony Corporation in2007,and was selected as an international standard by ISO/IEC29192-2in2011and e-Government recommended cipher by CRYPTREC project in2013.In this paper, taking advantage of the property of diffusion layer, we introduce a10-round truncated differential characteristic of CLEFIA, and give the key recovery at-tacks on13-round CLEFIA-128. Furthermore, we gave the attacks on14/15-round CLEFIA-192/256by applying the function reduction technique. More interest-ing, combined with the key schedule, we achieve an attack on14-round CLEFIA-128. Compared with the best results of previous attacks, we present the most efficient crypt-analysis of reduced-round CLEFIA.更多还原