Hashing it Out
Earlier this year, NIST (National Institute of Standards and Technology),announced that they will be hosting an open competition to decide on anew secure cryptographic hash standard. Cryptographic hash functionsare a fundamental part of cryptography and computer security. Acryptographic hash function takes an input and returns a (practically)unique output, providing applications in authentication, encryption anddigital signatures.
The most commonly used hash functions right now have been aroundsince the mid-nineties and are beginning to show some serious cracks.One of the basic requirements of a cryptographic hash functions is thatit must be very hard to find two inputs that map to the same output.When two such inputs are found it is called a collision, and collisionsare a really bad thing for hash functions. The Message Digest 5 (MD5)algorithm was created in 1991 by Ron Rivest and is still in common usedespite some very serious cryptanalytic attacks that have made findingMD5 collisions relatively easy. The Secure Hash Algorithm-1 (SHA-1) wascreated by the NSA and is the current secure hash standard, but recentattacks have shown that finding a SHA-1 collision is on the verge offeasibility and many expect the first SHA-1 collision to be foundwithin the year. Finding a collision is not the end of the line for acryptographic hash function, it is more like a death sentence. Althoughmany applications of hash functions can still work if collisions arefound, having a weakness against collisions indicates that there arefundamental flaws in the algorithm and that more weaknesses are rightaround the corner.
The solution initially proposed by NIST was to phase out SHA-1 andto start using the so-called SHA-2 family of hash functions that haveproven resistant to attacks for now. The problem with the SHA-2 hashesis that they are based on the same decade-old designs as thesoon-to-be-insecure SHA-1 algorithm. Moreover, the documentation aboutthe design decisions made in SHA-2 is still classified, so it isunknown what sort of modern attacks the algorithms are designed toresist. Considering that multiple advances have been made in the fieldof secure hash functions since the SHA algorithms were created, it wastime for a change. To find a new hash standard, NIST decided to have acontest to let the greatest cryptographic minds in the public worldsink their teeth into the problem. This route has proved fruitfulbefore: a previous contest to replace the outdated Digital EncryptionStandard (DES) resulted in the very successful choice of Rijndael asthe new Advanced Encryption Standard (AES). Hopefully the competitionfor designing a new cryptographic hash standard will achieve a similarlevel of success.
By the end of the year, NIST will have finalized the minimumacceptability requirements, submission requirements, and evaluationcriteria for candidate hash functions. Submissions will be due in thefall of 2008, so if you have a good idea for a secure hash function,get working!