【作者】 多磊；

【导师】 冯克勤； 李超；

【作者基本信息】 国防科学技术大学 ， 应用数学， 2007， 博士

【摘要】 分组密码和Hash函数是对称密码学领域的两个重要分支,分组密码在数据加密和MAC等领域有着广泛的应用,Hash函数在电子签名、消息认证、防否认等领域有着广泛应用。早在上个世纪九十年代,人们意识到分组密码标准DES已不能满足高速发展的信息时代的加密需求,1997年NIST(美国国家标准与技术研究所)启动了AES(高级加密标准)计划,并最终选用Rijndael作为新一轮加密算法标准。继美国征集AES活动之后,欧洲在2000年启动了NESSIE计划。伴随着AES计划和NESSIE计划的实施,分组密码研究从一种经验设计走向理论设计的道路,分组密码理论得到飞速发展。相比之下人们对在用的Hash函数安全性估计过于乐观,相关研究比较滞后。2004年底山东大学王小云教授和她的工作团队给出了MD5和SHA1算法的碰撞攻击,国际上也陆续推出了系列攻击,给在用的Hash函数带来了重创。Hash函数已成为密码学领域一个热门话题。NIST决定在2008年启动高级Hash函数算法征集活动-AHS计划,预计5年时间。如何设计、分析和评价Hash函数,以及如何给出一个可证明安全的Hash函数等问题将贯穿于整个活动。Hash函数研究深度远远不及分组密码,能否将分组密码理论用于专用Hash函数的设计中,已成为一个热点话题。大多Hash函数均是通过迭代结构对压缩函数进行迭代而实现的。Hash函数设计包括迭代结构的设计和压缩函数的设计两部分。本文目标是设计一个新的Hash函数,这要求对当前分组密码和Hash函数设计原理和攻击方法有充分的认识。本文最终给出了一个Hash函数,命名为Dolly。在该算法设计中,我们给出了一个新的迭代结构FHash,新的压缩函数结构FL-结构和新的压缩函数算法。我们构造的压缩函数同时也是一个加密分组长度为256比特,密钥长度为512比特的分组密码,同时给出了一个不可逆的密钥扩展算法。本文的主要创新成果如下:(1)给出Camellia密码四个等价结构,提出Camellia密码的变种Square攻击,同时改进了Yeom等在FSE2002上给出的Square攻击的界。Camellia相关攻击结果是当时最有效的攻击方法,被日本当年的信息安全年报引用。CRYPTREC关于Camellia算法的2006年年度报告中仍然引用我们的结论作为该算法的安全现状。(2)发现Camellia算法P置换与S盒变换的特殊联系,在特殊明文条件下,P置换导致几个S盒的模加相互抵消。根据这一特性,给出了新的变种Square攻击,将Camellia攻击结果再次改进,这一结果是目前对Camellia算法的最好攻击结果,该结果收录在ICICS2007。(3)引入有向图理论和Game-Based proof方法,将基于分组密码构造的64种压缩函数方案归为四类,并给出了每一类的抗原像、次原像和碰撞攻击的界。这种归类比Black、Rogaway和Shrimpton在Crypto2002上给出的三种分类更加精确,并改进了BRS给出的抗碰撞和原像攻击的界。同时给出了基于固定点多碰撞中碰撞个数、算法复杂度与消息长度之间的关系。(4)我们发现Merkle-Damgard结构迭代过程中不一定能够继承压缩函数的分布特性,并举例说明了这一现象的存在,其中一个几乎均匀分布的函数在Merkle-Damgard迭代结构下,生成的新函数分布上界为1,完全不符合几乎均匀分布。我们进一步证明迭代后函数分布特性与压缩函数分布特性和迭代次数有关,最坏情况下,迭代次数与分布的界构成指数关系。同时给出了其它几个结构的分布特性。我们发现Merkle-Damgard结构下基于分组密码构造压缩函数的64种方案的概率分布特性,只有四个方案的概率分布与迭代次数无关,但这四种方案均是不抗原像攻击的,该结论在文献[87]中给出。(5)Bellare等在AsiaCrypt2006上给出了EMD结构,第一个直接继承压缩函数抗碰撞攻击特性、伪随机预言机(该性质称为indifferentiability)特性和伪随机函数特性的迭代结构,使Hash函数安全性问题归结到压缩函数的安全性问题上。我们认为均匀分布也是一非常重要的性质需要继承。令人遗憾的是EMD结构无法满足这一特性。我们给出了一个新的结构(定义为ECM结构),它满足EMD所有特性且继承了压缩函数分布特性,并给出了详细证明,该结果收录在Indocrypt2007。(6)对Feistel结构进行变形,给出了一个满足单向性要求的压缩函数结构FL-结构,并给出一个Hash迭代结构FHash,同时给出了FL-结构和FHash安全性的形式化证明,在此基础上构造了一个新的Hash函数Dolly。Dolly算法采用了AES的扩散准则,因此继承了AES算法的抗线性和差分攻击特性,同时我们给出了一个不可逆的密钥扩展算法,尽可能地增强了压缩函数的抗碰撞特性。Dolly中的压缩函数轮函数和密钥扩展算法还有待更深入的分析和评价。更多还原

【Abstract】 Block ciphers and hash functions are two important branches in symmetric cryptology. Block ciphers play important roles in data encryption. Hash functions are widely used in digital signature schemes, message authentication and integrity checking.In the early 1990s, people realized that DES (Data Encryption Standard) was not suitable for data encryption requirements of the rapidly developing information era. In 1997 NIST (National Institute for Standards and Technology) published an open call for the Advanced Encryption Standard (AES). Rijndael by Rijmen and Daemen was selected as the AES to succeed DES. In 2000, the European Community started the NESSIE project. Studies made during these processes led to important theoretical advances in the public knowledge on the design and analysis of block ciphers.Comparatively, research on hash functions lagged behind due to over-optimistic attitude on the security of the MD family hash functions. In 2004, Wang and her team members gave collision attacks on some of MD family hash functions. Subsequently more weakness have been found on MD families. Hash functions are now a hotspot in the area of cryptography, a trend that will endure for five or six years as NIST has decided to hold new hash algorithm competition (AHS project). Topics related to design, analysis and evaluation of hash functions (including with provable security) will be discussed in the competition. Since there are plenty of good results in block ciphers, many cryptographers have been considering designing a hash function following block cipher theory.Most hash functions are based upon iterated compression functions, design of which includes compression function design and iterated structure design. The goal of this paper is to give a new hash algorithm, which requires good understanding and analysis on the theory of block cipher and hash function. The thesis concludes with a new hash function algorithm called Dolly, in which the compression function follows the block cipher design idea of using S-boxes transformation to achieve nonlinear transformation and the iterated structure is a modified structure of Merkle-Damg(a|°)rd construction to prevent some known weaknesses in it.The contributions of this paper are as follows.(1) Four equivalent structures of Camellia are founded, based on which a variant Square attack on Camellia is presented. We also improve the square attack bound given by Yeom et.al and the collision attack bound given by Wu et. al. Our results were the best results on Camellia and were cited by Japanese CRYPTREC 2005 annual reports. CRYPTREC 2006 annual report on Camellia still cited our results as the current security status of the cipher. (2) A new relationship between the P permutation and S-boxes are discovered in Camellia, which results in the cancellation of S-boxes during P permutation transformation. Based on such property, a new variant square attack is proposed and the attack results on Camellia again improved. Both our new results on 128 bit and 256 bit keys are the best attack results on Camellia. This result is accepted by ICICS2007.(3) Digraph theory and Game-Based proof method are applied in security analysis of Merkle-Damg(a|°)rd construction, then PGV schemes are divided into four groups and the bounds of preimage, second preimage and collision attack are given. Our results improve the classification and attacking bounds given by Black, Rogaway and Shrimpton.(4) The Merkle-Damg(a|°)rd construction can not guarantee good distribution properties of its compression function being inherited during the iteration. The distribution bound of Merkle-Damg(a|°)rd construction with MD-strengthening may reach 1, even if its compression function has a good distribution bound, where the bound is not only related to the distribution bound of compression function, but also to the length of message being hashed. We prove that, in the worst case, the distribution bound of construction will increase exponentially to the message length.(5) The EMD (Enveloped Merkle-Damg(a|°)rd ) transformation, which was proposed by Bellare et. al at AsiaCrypt2006, was the first structure to satisfy collision resistance preservation, pseudo random oracle preservation (Indifferentiability) and pseudo random function preservation. We think that, the almost uniformly distribution preserving is also an important property for a structure. However, EMD is not a structure of almost uniform distribution preservation. Then, we recommend a new structure called ECM construction satisfying collision resistance preservation, pseudo random oracle preservation (Indifferentiability) and pseudo random function preservation and almost uniformly distribution preservation. The proofs are also presented. This result is accepted by Indocrypt 2007.(6) A variant Feistel structure called FL-construction, which is a one way structure, and a new hash iterated hash structure FHash are presented. The security proofs of FHash and FL-construction are given based on heuristic proof method. We design a new hash function, which is named Dolly, its round function inherit that of Rijndael. And our new hash function has a not invertible key schedule algorithm.更多还原