Design Of Hash Function Based On Analysis Of Block Cipher

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.