Cryptoanalysis And Construction Of Chaotic Hash Functions

Chaotic cryptography is a new interdisciplinary field combining cryptography and nonlinear science. Over the last two decades, the scope of chaotic cryptography has vastly extended, from stream cipher and block cipher in the early period, to include hash function, pubic-key cipher, digital watermark and image hiding, etc., and many chaotic cryptographic algorithms and protocols have been proposed so far. Chaotic hash function is a major branch of chaotic cryptography, which has become a research hotspot in recent years, and also a new application of chaos theory in the field of cryptography.In this thesis, research on chaotic hash function focuses on the following two aspects:firstly, analyzes the security of previously proposed chaotic hash schemes and poses new attacks; secondly, designs new chaotic hash scheme with stronger security properties and higher efficiency. The main contributions of this thesis are given as follows:Chapter2analyzes the security of a one-way hash function construction based on spatiotemporal chaos, proposed by Ren et al. in2009. A new kind of differential attack named "arithmetic differential attack", is introduced to construct two kinds of differential paths in the round function of Ren's scheme. Based on these differential paths, a simple forgery attack can be devised, where the valid MAC of a random256-bit message can be calculated, without knowledge of the secret key, from eight related256-bit messages and their intermediate hash values. Furthermore, some preliminary advice on how to improve the Ren's scheme is given.Chapter3analyzes the security of two parallel keyed hash schemes proposed by Xiao et al., separately in2008and2009, where one is based on chaotic maps, and the other is based on chaotic neural network. The security leak of the underlying parallel structure is revealed through differential cryptanalysis, and two kinds of forgery attacks are devised, where the valid MAC of a random message can be calculated from related messages and their MACs, without knowledge of the secret key. In addition, a class of weak-keys in both schemes is discussed, where keys are considered as weak-keys in the sense that they turn the chaotic orbit of PWLCM into fixed point. With these weak keys, different messages will have identical MACs, in other words, MAC collision happens at this case.In order to overcome the weaknesses of the two parallel keyed hash schemes, three different schemes were proposed, i.e., an improved parallel hash scheme based on chaotic maps proposed by Xiao et al. in2009, an improved parallel hash scheme based on chaotic neural network proposed by Huang et al. in2011, and a parallel hash scheme based coupled map lattices proposed by Wang et al. in2011. The security of these three proposals is analyzed, and their weaknesses are identified. The forgery attacks on Xiao's improved scheme and on Wang's improved scheme are presented, respectively. Moreover, a provable secure parallel structure, which is inspired by the PMAC algorithm, is proposed to remedy these security flaws.Chapter4analyzes the security of a one-way hash function construction based on chaotic map network, proposed by Yang et al. in2009. It is found that the chaotic round function of Yang's scheme can be translated into a set of systems of linear equations by applying algebraic analysis, and hence a key-recovery attack is devised based on these equations. Preliminary advice on how to improve the original scheme is also discussed.In Chapter5, the cryptanalysis results available so far are summarized, and the root causes of the security vulnerabilities are analyzed. Then a new chaotic hash function is proposed, which combines the advantages of both chaotic system and conventional hash function. The proposed hash scheme follows HAIFA structure with internal wide-pipe design strategy, which does not suffer from the known generic attacks that work on the M-D construction. The compression function in-use is based on chaotic iteration, and includes some classic design elements form traditional hash function as well. A statistical evaluation methodology developed by NESSIE project is introduced for the performance analysis, which includes three well-known cryptologic measures for diffusion property:the degrees of completeness, of avalanche effect and of strict avalanche criterion. Theoretical analysis and numeric simulation show that the proposed algorithm avoids all known security pitfalls of chaotic hash function, and achieves fast hashing speed as well.