Collisions, a secure hash function killer (MD5, SHA1, SHA2)

The trouble with the use of MD5 in digital signatures recently uncovered by Sotirov et al. is common to other hash functions.

NIST has been discouraging people to use MD5 and even SHA 1 since many years ago. A good account of this was posted by Dustin Trammell here.

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.

 

del.icio.us Tags: authentication,hash functions,collisions,MD5,SHA1,encryption

Advertisement