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 H that maps an arbitrary length message M to a fixed length message digest MD is a collision-free hash function if:

1. It is a one-way hash function.

2. It is hard to find two distinct messages (M', M) that hash to the same result H(M')=H(M).

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.

 

Advertisements

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

  1. Pingback: driveling about MD5; SSL in javascript, over websockets | Peter's ruminations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: