14-07-2012, 10:22 AM
Chaotic cryptographic hash function
[attachment=27603]
Introduction
Hash function is a special kind of one-way function which can be classified into two categories known as un keyed hash function which specifies a single input parameter called message and a it Keyed hash function, whose specification involves two distinct inputs, a message and a secret key. In this chapter we propose a keyed hash function based on chaotic functions of logistic and the tent maps.
Many chaotic hash functions have been proposed in the literature. One of the latest ones is by Wong et al which we take as our basis for comparison. Earlier Wong had proposed a hash function based on the dynamic table look up algorithm which was a modification of Baptista’s algorithm. It was shown that this algorithm needs to be improved. Wong et al propose a chaotic map network which also has a chaining mechanism to take care of the last bit security requirements. This method achieves the ideal diffusion of above 50% and the minimum changed bit number which measures confusion to be nearly 45%. We propose a hash function which achieves performs comparable. We also analyze the time complexity of our algorithm.
The recent investigations on the collision frequencies reveal many undiscovered flaws in well-known methods such as MD5, SHA1 and RIPEMD. Preneel et al, have studied the construction of single- block- length hash functions and pointed out that the hash function is insecure since a collision could be found with only about 2^m/2 operations dude to the birthday attack, where m is block size
Chaos based cryptographic hash function
A hash function h maps an arbitrary bit string to a bit string of length n and should be easy to compute. Further a secure hash function is required to have the following properties:
Irreversibility- Given h and an input x, it are computationally infeasible to find an input which hashes to a specific output. i.e... Given a y to find a pre- image x such that h(x) =y.
Second – preimage resistance – it is computationally infeasible to find another input, to find a 2nd pre image x’≠ x such that h(x)=h(x’)
Collision resistance – it is hard to find any two distant inputs x, x’ which hash to the same output, i.e., such that h(x) = h (x’).
Types of collisions and attacks
As the set of possible message digests is much smaller than the set of input messages which can be potentially infinite, collisions are always possible. This intrinsic weakness introduces at least two kinds of potential attacks, known as impersonation and substitution.
Impersonation
An imposter injects a message together with an authentication code, (x,a), into the communication channel, hoping that it is considered as authentic and accepted by the receiver.
Substitution
An imposter tampers a message (x,a) in the channel, and modifies it into (x’,a’), where x≠x’, hoping that it is accepted by the receiver.
Therefore, the security of a Message Digest (MD) is highly dependent on the difficulty in identifying collisions. For a birthday attack, based on the birthday paradox in, it can be proven that the number of random hashes to achieve collision with a probability of 0.5 is approximately equal to 2^n/2 for MD of n-bit length. Therefore, the length of MD is built to be at least 128 bit long or even higher to counter birthday attacks.
Apart from the birthday attack, the reliability of MD schemes also rely on the complexity of analyzing the iterative compression function. Some weaknesses of MD4 are observed and the collision were found by identifying two messages with similar contents that generate the same MD.Based on these findings, a collision search attack is described. For MD5, yet an improved version of MD4, a kind of pseudo- collision has also been reported, and collision cases are obtained. Similarly, some weaknesses and the collision search attacks of the SHA-[41], SHA –1[42] and RIPEMD [43] have also been identified. Based on the security criteria of hash function stated above it is observed that chaotic map can probably be good candidate for a hash function, because of its following properties
Sensitive Dependence on initial conditions: A chaos based hash function can be highly sensitive to a small change in any given message and hence is more likely to produce different hash values for messages with small difference in content.
Mixing: A tiny difference between two messages can be diffused and change the resultant MD totally.
Sensitivity to system parameters: these parameters can be user specified so that the hash value can be used directly as a MAC.
The basic objective of a cryptographic hash function is to generate a fixed length MD from a message with arbitrary length. The design of the hash function is shown in the figure
[attachment=27603]
Introduction
Hash function is a special kind of one-way function which can be classified into two categories known as un keyed hash function which specifies a single input parameter called message and a it Keyed hash function, whose specification involves two distinct inputs, a message and a secret key. In this chapter we propose a keyed hash function based on chaotic functions of logistic and the tent maps.
Many chaotic hash functions have been proposed in the literature. One of the latest ones is by Wong et al which we take as our basis for comparison. Earlier Wong had proposed a hash function based on the dynamic table look up algorithm which was a modification of Baptista’s algorithm. It was shown that this algorithm needs to be improved. Wong et al propose a chaotic map network which also has a chaining mechanism to take care of the last bit security requirements. This method achieves the ideal diffusion of above 50% and the minimum changed bit number which measures confusion to be nearly 45%. We propose a hash function which achieves performs comparable. We also analyze the time complexity of our algorithm.
The recent investigations on the collision frequencies reveal many undiscovered flaws in well-known methods such as MD5, SHA1 and RIPEMD. Preneel et al, have studied the construction of single- block- length hash functions and pointed out that the hash function is insecure since a collision could be found with only about 2^m/2 operations dude to the birthday attack, where m is block size
Chaos based cryptographic hash function
A hash function h maps an arbitrary bit string to a bit string of length n and should be easy to compute. Further a secure hash function is required to have the following properties:
Irreversibility- Given h and an input x, it are computationally infeasible to find an input which hashes to a specific output. i.e... Given a y to find a pre- image x such that h(x) =y.
Second – preimage resistance – it is computationally infeasible to find another input, to find a 2nd pre image x’≠ x such that h(x)=h(x’)
Collision resistance – it is hard to find any two distant inputs x, x’ which hash to the same output, i.e., such that h(x) = h (x’).
Types of collisions and attacks
As the set of possible message digests is much smaller than the set of input messages which can be potentially infinite, collisions are always possible. This intrinsic weakness introduces at least two kinds of potential attacks, known as impersonation and substitution.
Impersonation
An imposter injects a message together with an authentication code, (x,a), into the communication channel, hoping that it is considered as authentic and accepted by the receiver.
Substitution
An imposter tampers a message (x,a) in the channel, and modifies it into (x’,a’), where x≠x’, hoping that it is accepted by the receiver.
Therefore, the security of a Message Digest (MD) is highly dependent on the difficulty in identifying collisions. For a birthday attack, based on the birthday paradox in, it can be proven that the number of random hashes to achieve collision with a probability of 0.5 is approximately equal to 2^n/2 for MD of n-bit length. Therefore, the length of MD is built to be at least 128 bit long or even higher to counter birthday attacks.
Apart from the birthday attack, the reliability of MD schemes also rely on the complexity of analyzing the iterative compression function. Some weaknesses of MD4 are observed and the collision were found by identifying two messages with similar contents that generate the same MD.Based on these findings, a collision search attack is described. For MD5, yet an improved version of MD4, a kind of pseudo- collision has also been reported, and collision cases are obtained. Similarly, some weaknesses and the collision search attacks of the SHA-[41], SHA –1[42] and RIPEMD [43] have also been identified. Based on the security criteria of hash function stated above it is observed that chaotic map can probably be good candidate for a hash function, because of its following properties
Sensitive Dependence on initial conditions: A chaos based hash function can be highly sensitive to a small change in any given message and hence is more likely to produce different hash values for messages with small difference in content.
Mixing: A tiny difference between two messages can be diffused and change the resultant MD totally.
Sensitivity to system parameters: these parameters can be user specified so that the hash value can be used directly as a MAC.
The basic objective of a cryptographic hash function is to generate a fixed length MD from a message with arbitrary length. The design of the hash function is shown in the figure