Collisions, a secure hash function killer (MD5, SHA1, SHA2)
February 21, 2009 2 Comments
The trouble with the use of MD5 in digital signatures recently uncovered by Sotirov et al. is common to other hash functions.
Because the output of a hash function is of a fixed length, usually smaller that the input, there will necessarily be collisions. The collision-free property for hash is thus defined by:
A function that maps an arbitrary length message to a fixed length message digest is a collision-free hash function if:
1. It is a one-way hash function.
2. It is hard to find two distinct messages that hash to the same result .
Cryptographers talk about “relatively collision free” hash functions. A good hash function should be designed with the Avalanche Criterion in mind.
The Avalanche Criterion (AC) is used in the analysis of S-boxes or substitution boxes. S-boxes take a string as input and produce an encoded string as output.
The avalanche criterion requires that if any one bit of the input to an S-box is changed, about half of the bits that are output by the S-box should change their values. Therefore, even if collisions are unavoidable, there is no way to generate two strings with the same hash value other than brute force.