2007One-way Hash function construction based on iterating a chaotic map

One-way Hash function construction based on iterating a chaotic map

Yong Wang1,2

1School of Computer Science and Engineering, Chongqing University, Chongqing, 400044, PRChina

wangyong_cqu@https://www.sodocs.net/doc/024067334.html,

Degang Yang1,3

3School of Mathematics and Computer Science, Chongqng Normal University,

40047, PR China

ydg42@https://www.sodocs.net/doc/024067334.html,

Maokang Du2

2 School of Economy and Management,

Chongqing University of Posts and

Telecommunications, 400065,China

exceldu@https://www.sodocs.net/doc/024067334.html,

Huaqian Yang1,4

4Department of Computer and Modern Education, Chongqing Education College, Chongqing 400067, PR China

yhq_cq@https://www.sodocs.net/doc/024067334.html,

Abstract

An algorithm for one-way Hash function construction based on iterating a chaotic map is proposed. The total chaotic space is divided into some subspace based on the density distribution function of the chaotic map. Each subspace is associated with a unique bit in a bit sequence. The value of the chaotic map is dynamically decided by the last-time value and the corresponding message bit in different positions. When the chaotic value is in one subspace, changes the corresponding bit. Finally, the bit sequence is used as the Hash value. Theoretical analysis and computer simulation indicate that the algorithm can resist statistical attack, birthday attack and meet-in-the-middle attack and satisfy all performance requirement of Hash function in an efficient and flexible manner. It is practicable and reliable, with high potential to be adopted for E-commerce.

1. Introduction

Hash function is a basic technique for information security and plays an important role in modern cryptography. The conventional Hash functions, such as MD5, SHA, are realized through the complicated method based on logical XOR operation or multi-round iteration of some available cipher. However, recent work on collision frequencies reveals many undiscovered flaws in the well-known methods MD5, SHA1, and RIPEMD [1, 2]. How to design secure Hash functions, therefore, attracts more and more attentions.

Chaos-based Hash functions as a novel developing directions in construction of Hash function has been exploited [3-7]. Based on Baptista’s method [8], Wong developed a hashing scheme in [6], which is built on the number of iterations of one-dimensional (1-D) logistic map needed to reach the region corresponding to the character, along with a look-up table updated dynamically. Xiao, etc. proposed an algorithm for One-way Hash function construction based on the chaotic map with changeable-parameter[3]. Zhang, etc. presented a method for One-way Hash function construction based on spatiotemporal chaos[5]. These hashing schemes can be considered as producing Hash value by iterating a chaotic map. In this paper, an algorithm for one-way Hash function construction is proposed, which producing Hash value by iterating a chaotic map, too. Simulation results show that performance of our scheme is better than those of existing algorithms based on iterating a chaotic map. It is practicable and reliable, which is a good choice for data integrity or authentication.

The remaining of the paper is organized as follows. The algorithm of Hash function is proposed in section 2. The performance of Hash function is analyzed and compared with that of other algorithms in section 3. Finally, conclusions are drawn in section 4.

2. The hashing scheme

2.1 Analysis of the logistic map

In our hashing scheme, the logistic map is employed as the chaotic map:

2007 International Conference on Computational Intelligence and Security Workshops

2

112n n x x +=? , ( -1≤ x n ≤1 ) (1) The density distribution function of Eq.(1) is described below [10]

()x ρ=

(2) distributed map. According to Eq.(2), we divide the whole phase space [-1,1] into 2n subintervals. Defines T i (i ＝0, 1, ... ,2n -1) as the i th subinterval, and T i =[t i , t i+1), 21

cos()i i t π?=?. It can be easily proved that the

count of x in each subinterval is the same, i.e., the probability of the chaotic orbit entering each subinterval is equal when iterating the logistic map.

2.2 Algorithm of Hash function

The detailed algorithm of Hash function is described as follows:

(1) Divides interval [-1, 1] into 128 subintervals according to the method in section 2.1. Defines a 128-bit sequence h and h i ( i = 0, 1, ... ,127 ) is the i th bit of h . Initializes h = { 01, 23, 45, 67, 89, AB, CD, EF, FE, DC, BA, 98, 76, 54, 32, 10}, where h is expressed in hexadecimal format.

(2) Arbitrarily choose a value in interval [-1, 1] as the initial value x 0 of Eq.(1). To avoid the transient effect, iterates the logistic map for 50 times.

(3) Defines x, A j as the current state value of logistic map and ASCII number of the j th byte in the message m , respectively. For each byte of m , the same operations are done as follows:

Step 1. Modifies x according to Eq.(3):

x = p *x +(1-p )*(A j / 255 - 0.8) (3) where p is the proportion coefficient, which can be arbitrarily value in interval (0,1);.

Step 2. Iterates Eq.(1) only once and obtains the subinterval T k where x is in. Then changes the k th bit of sequence h according to Eq.(4):

h k = h k +1 mod 2 (4) Does the iterating and changing operations in Step 2 for 32 times.

Does the operations included in Step 1 & 2, increasing j from 1 to n , where n is the byte size of the message m . Then does the operations again, decreasing j from n to 1.

(4) Finally, uses the 128-bit sequence h as the Hash value of the message m .

From the algorithm above, we know that x is dynamically decided by the last-time value and the corresponding ASCII value of message in different positions. So different messages result in different chaotic orbits, and finally different Hash values.

Owing to the special division of interval [-1, 1], the probability of the chaotic orbit entering each subinterval is equal, which guarantees the balance between 0 and 1 in Hash value. Moreover, due to making full use of properties of chaos, such as mixing, ergodicity and sensitive dependence on initial conditions, totally different orbit can be obtained even a bit is changed in the message.

3. Performance analysis

3.1 Hash result of messages

We use the proposed algorithm to do Hash simulation under the following five kinds of condition (here x 0 = 0.1234567 and p = 0.8 ):

Condition 1: The original message is “Cryptographic hash functions play a fundamental role in modern cryptography. While related to conventional hash functions commonly used in non-cryptographic computer applications – in both cases, larger domains are mapped to smaller ranges – they differ in several important aspects. Our focus is restricted to cryptographic hash functions (hereafter, simply hash functions), and in particular to their use for data integrity and message authentication.”

Condition 2: Changes the first Character C in the original message into D .

Condition 3: Changes the word functions in the original message into function .

Condition 4: Changes full stop at the end of the original message into comma.

Condition 5: Adds a blank space to the end of the original message.

The corresponding Hash values in hexadecimal format are:

Condition 1: F228601205EAD7A6ECF7768F6210DB81 Condition 2: A738C153CDCF89EEDE53C1AF2ADD0A Condition 3: F4572C049FA54123C6FB3DCB174E78C5 Condition 4: 558AD25C9C6C64E9C195F922AE04C7EC Condition 5: B484C73B017B85AE9B1DA796D8D7A9F7 The simulation result indicates that any least difference of the message will cause huge changes in the final Hash value.

3.2 Statistic analysis of diffusion and confusion

Confusion and diffusion are two basic design criteria for encryption algorithms, including Hash functions. For the Hash value in binary format, each bit is only 1 or 0. So the ideal diffusion effect should be that any tiny changes in initial conditions lead to the 50% changing probability of each bit. Usually, four statistics are defined as follows :

Mean changed bit number: 1

1N

i

B B

N

?

=

∑

Mean changed probability: (/128)100%P B ?

=×

Standard variance of the changed bit number:

B ?=

Standard variance:

100%P ?= where N is the total number of test and B i is the number of changed bits in the i th test.

We have performed the following diffusion and confusion test: A paragraph of message is randomly chosen and Hash value is generated. Then a bit in the message is randomly selected and toggled and a new Hash value is generated. Finally two Hash values are compared.

This kind of test is performed N times, and the corresponding distribution of changed bit number is shown as Fig. 1, where N = 2048.

Fig. 1. Distribution of changed bit number

Through the tests with N = 256, 512, 1024, 2048, respectively, the corresponding data are listed in Table 1. Based on the analysis of the data in Table 1, we can draw the conclusion: the mean changed bit number B ?

and the mean changed probability P are both very close to the ideal value 64 bit and 50%. ΔB and ΔP are very little, which indicates the capability for diffusion and confusion is very stable.

3.3. Analysis of collision resistance and birthday attacks resistance

3.3.1. Birthday attack. Collision resistance and birthday attack are similar in idea. They are essentially a probability problem that two random input data are found such that they are hashed to the same output. In our proposed algorithm, the probability of the chaotic orbit entering each subinterval is equal, which guarantees the uniform distribution of Hash value. Thus, for birthday-attack, the length of hash value determines the security of cryptosystem. Here the hash value is 128-bit. The attack difficulty is 26

4. This keeps the scheme secure against this kind of attack.

3.3.2 Meet-in-the-middle attack. Meet-in-the-middle attack seeks collisions on intermediate results (i.e., chaining variables) rather than the overall hash-result [9]. In our scheme, the sequence h and the state value of logistic map, namely x , can be seen as the intermediate results. The 32-times iterations of chaotic map and the operation of changing bits in sequence h can be considered as round function. Supposes 'j A is a meet-in-the-meddle collision of A j . According Eq.(3), the two initial values of round function are different. After iterations, we can get different state values. The changed bits in sequence h are different, too. Meanwhile, great changes can be taken between the two final state values of logistic map. So 'j A is not a collision. That is to say, it is impossible to find a meet-in-the-middle collision in the floating point domain. Thus our scheme can resist this kind of attack.

3.3.3 Test of Collision. According Wong's method [6], we perform the following test to do quantitative analysis on collision resistance: Calculating the distance between two hash values, whose messages are only one bit different and the number of ASCII characters with the same value at the same location in the Hash value.

This kind of collision test is performed 2048 times. The maximum, mean, minimum values of distance and mean/character are 2098, 1323, 663 ,82.70 respectively. The distribution of the number of ASCII characters with the same value at the same location in the Hash value is given in Fig. 4. Notice that the maximum number of equal character is only 2 and the collision is very low. Correspondingly, the maximum number of equal character of [5] is calculated and the Xiao's result is directly obtained from [3]. Their maximum numbers of equal character are both 3. The results show that our scheme is slightly better.

Table 1: The statistical performance of our algorithm N = 256 512 1024 2048

B ?

63.94 64.17 64.01 63.90 P (%) 49.96 50.14 50.01 49.93

ΔB

5.47 5.62 5.52 5.64 ΔP (%)

4.28 4.40 4.32 4.41

Fig. 4. Distribution of the number of ASCII characters with the same value at the same location in the Hash

value

3.4. Flexibility

Although our proposed algorithm aims at unkeyed Hash function, it also can be used to construct keyed Hash function by simply treating x0 and the initial values of bit sequence as secrete keys.

Through simply modifying the number of subintervals and the size of bit sequence, the length of the final Hash value will be easily changed. For example, we can get 256-bit Hash value by dividing interval [-1, 1] into 256 subintervals and using a 256-bit sequence. Compared with the conventional Hash algorithm such as MD5 with fixed 128-bit length, the proposed algorithm can adapt to the actual demand better.

4. Conclusion

In this paper, an algorithm for one-way hash function construction based on iterating a chaotic map is investigated. The phase space of the chaotic logistic map is divided into some subspace based on the density distribution function, which guarantees that the probability of chaotic orbit entering each subinterval is equal. The Hash value is obtained by iterating the logistic map. Owing to making full use of properties of chaos, such as ergodicity, nonlinearity and mixing, the scheme can satisfy all the performance requirements of Hash function in an efficient and flexible manner and has a better performance than other schemes based on iterating a chaos maps. Theoretical analysis and computer simulation indicate that our algorithm can resist statistical attack, birthday attack and meet-in- the-middle attack and has enough security.

5 Acknowledgements

The work described in this paper was supported by the Foundation of Chongqing Education Committee (No.KJ070503, KJ070509), and the Natural Science Foundation of Chongqing University of Posts and Telecommunications (No.A2006-41, A2007-26).

6 References

[1] X. Wang, D. Feng, X. Lai, H. Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", Rump Session of Crypto'04 E-print, 2004

[2] X. Wang, X. Lai, D. Feng etc., "Cryptanalysis of the Hash Functions MD4 and RIPEMD", in: Proceedings of Eurocrypt'05, Springer, Aarhus, Denmark, 2005, pp. 1-18.

[3] D. Xiao, X. F. Liao, S. J. Deng , "One-way Hash function construction based on the chaotic map with changeable-parameter" , Chaos Solitons & Fractals , ELSEVIER, Vol.24, Issue 1, 2005.4, pp 65-71.

[4] X. Yi , "Hash function based on chaotic tent Maps", IEEE Transactions on Circuits and Systems II, Vol.52, 2005, 6, pp 354-357.

[5] H. Zhang, X.F.Wang, Z.H.Li, D.H. Liu , "One way Hash function construction based on spatiotemporal chaos" , Acta Physica Sinica, Vol. 54, 2005, 9, pp 4006-4011. (in Chinese)

[6] K.W. Wong , "A combined chaotic cryptographic and hashing scheme" , Physics letters A , ELSEVIER, Vol. 307, Issues 5-6, 2003,2, pp 292-298.

[7] J.S. Zhang, X. M. Wang, W. F. Zhang, "Chaotic keyed hash function based on feedforward-feedback nonlinear digital filter", Physics letters A, ELSEVIER, Vol. 362, Issues 5-6, 2007, 3, pp 439-448

[8] M.S. Baptista, "Cryptography with chaos", Physics letters A, ELSEVIER, Vol. 240, Issues 1-2, 1998, 3, pp 50-54.

[9] A. Menezes, P. van Oorschot, S. Vanstone , Handbook of Applied Cryptography , CRC press , 1996.

[10] S. L. Ulam and J. von Neumann, "On combination of stochastic and deterministic processes", Bull. Math. Soc., Vol. 53, 1947, pp1120-1135