Design And Analysis Of The Hash Functions

Cryptographic hash functions play a fundamental role in modern cryptography. Hash functions occur as components in various cryptographic applications (e.g. protection of pass-phrases, protocols for payment, broadcast authentication etc). They are used to compress messages of arbitrary length to fixed length hash values which are also called message digests, digital fingerprints, message integrity check codes, manipulation detection codes etc. A primary motivation for cryptographic hash functions is that they serve as compact representative images of input messages, which they can uniquely identify. For example, the MD5 hash value "607364dea1d44b43e9898437b6d7e223" can be looked on as the "fingerprint" to represent this dissertation title "Research on design and analysis of cryptographic hash functions" uniquely. Changing the title, even by a single letter, most of the digits in the hash value will be changed. We change the first capital to a small letter; the corresponding hash value is "5cea4844e982080b258cfl44853603ec".In recents years, a flood of cryptanalytic results washed away most of the practical hash functions. The collection of new secure cryptographic hash algorithm from all over the world, by National Institute of Standards and Technology, is on view. Hash function has become a hotspot field in the cryptographic world. We start our work under this interesting background. We do main research on the analysis of known hash functions and the design of new collision resistant hash function; meanwhile, we do research on the target collision resistant hash functions. The main contributions of this dissertation are summarized as follows:1) We gived 7 collision modular differential path for MD4. Finding a feasible differential path is the key step of the modular differential attack, and it is also the most difficult step. Since most of the practical hash functions are designed based on MD4, the research on MD4 is very important and necessary. Moreover, when given message differential arbitrarily, we gived the arithmetic idea of how to search for the collision of MD4 including the given message differential by using computer.2) We presented a collision attack on the hash function NaSHA for the output sizes 384-bit and 512-bit. This attack is based on the the weakness in the generate course of the state words and the fact that the quasigroup operation used in the compression function is only determined by partial state words. Its time complexity is about 2¹²⁸ with negligible memory. NaSHA is a family of hash functions submitted by Markovski and Mileva as a SHA-3 candidate. This is currently by far the best known cryptanalysis result on this SHA-3 candidate.3) To improve the security of the iterative hash function, we proposed an enhanced iterative construction, called CMD construction. This construction can maintain the collision resistance of the compression function. The analysis results show that it can resist the attacks on the Merkle-Damg(?)rd construction, including the second preimage attack and the herding attack.4) We designed a new compression function, called Crazy, to construct secure and efficient iterated hash function. Crazy has the design goals to be resistant against known attacks and under the Merkle-Damg(?)rd iterative structure, its performance should be better than that of SHA-256. The main and novel features of Crazy are that, using step function to do message expansion such that message modification is harder than before; to intensify the attack complexity, initial values are introduced to help message expansion; difference diffusion in the step function is so fast that message value can be completely diffused to all the registers after two steps; expansion word does not operate on any register directly, so difference is harder than before. We conjecture that Crazy is securing against known attacks on compression functions based on our analysis up to now. Combining Crazy with Merkle-Damg(?)rd iterative structure, we construct a hash function. Experiments show that this new hash function is about 50% faster that that of SHA-256 in software.5) We researched on the secure requirements of the randomized construction (?)(M)= H^c(r|H^c(M(?)r)), gived the requirements of the underlying compression function when this construction is TCR/eTCR, and compared it with RMX. The compare results are that both (?) and RMX are comparative in security and efficiency when they are TCR, while (?) is more secure than RMX when they are eTCR. Moreover, we enhanced the randomized hash-then-sign diagram from two aspects. One is that the random salt used in the signature should be decided by the signer and the message provider together. Neither the signer nor the message provider can know the random salt before; the other is that after signing process, the signature should be sent back to the message provider firstly, and then the signature should be handed out by the message provider. By doing so, if one wants to make a success forgery, he has to find the second preimage of the target message, instead of a collision.6) Using enhanced randomized hash-then-sign diagram and millionaires' problem, we proposed two donation monitor schemes to make the donation process believable and controllable. In these two schemes, the charity is monitored by all the donators. It is impossible for the charity to deduct the donation arbitrarily. More over, the schemes can also protect the charity against the donators who have evil intentions.