Financial Cryptography

NIST Competition to create new Hash algorithm

Buzzing around the cryptosphere for the last few years has been the name that hashes fear: Wang. The allegedly mild and timid Professor Wang has destroyed all hashes up to SHA1 itself (prior posts in FC) and even that bulwark of western cryptography has wobbled at her attack. Here's a somewhat stylised and inaccurate portrait published in China

Now, NIST have announced:

Due to recent attacks on the SHA-1 hash function specified in FIPS 180-2 , Secure Hash Standard, NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES). Two workshops (see menu at left) have been held to assess the status of the NIST-approved hash functions, to discuss possible near- and long-term options, and to discuss hash function research in preparation for launching such a competition. In addition, NIST has published its policy on the use of the current hash functions, and has proposed a tentative timeline for the competition.

As a first step in initiating the competition, NIST is publishing draft minimum acceptability requirements, submission requirements, and evaluation criteria [Federal Register Notice (January 23, 2007)] for candidate hash algorithms, and public comment is requested.

Let the party begin! You have until 3Q 2008 to submit your design. If the AES experience is anything to go by, that's not a lot of time.

What's all this about then? Some background. When these oriental broadsides first started lobbying in, many thought a crypto competition would be just the shot. The AES competition, to develop a new secret key cipher, was one of the greatest cryptological parties of the late 90s. Everyone and his dog submitted an algorithm; my buddies in the Cryptix group provided the Java framework.

The winner, Rijndael, is now standardised as AES for Advanced Encryption Standard, and it is stronger for its world-wide scrutiny (but note that I stuck my neck out and predicted a shock ...).

When it came to hashes, however, NIST instead contracted for the creation of extensions to SHA1. These are SHA256, SHA512, etc, algorithms released around the same time as the AES competition.

Longer, bigger, better, or so they claimed. NIST knew their hashes:

• Hash algorithms don't exactly collapse when challenged, as they are part of wider systems;
• the breaks were only effective against unpredicted collisions, that is, we cannot attack an existing hash.
• Even if you find a break, it is still not clear how to exploit it for money.
• We (in higher layers of FC) simply don't need the hash to be as strong as a castle, whereas we absolutely need the encryption algorithm to be as strong and stronger even than any castle.

Fair enough! On the one hand, NIST stuck with the aged MD4 design and expanded it. Economically sensible. But on the other hand, Prof Wang continued her work undaunted, and the foundations kept getting weaker. Although there is no "big problem" with industry, there is a "big problem" with the theory of cryptography, and that's embarrassing.

What does this mean for the rest of us, those who are users cryptography? Well, hash agility is here to stay. What that means is that your designs and protocols need to be able to shift: first to SHA256, etc, and then later on to NewSHA. This has fairly nasty implications all through software and within security itself; something I encapsulate within a hypothesis (#1): The One True Crypto Suite. I'll have to write that up some time.

Beyond pain for software developers, it represents excitement for cryptologers, no more.

And, because you read this blog, let's close with this comment from the timeline:

A tentative timeline for developing the new hash functions was presented, and discussed at length, at the Second Cryptographic Hash Workshop held on August 24-25, 2006 at UCSB. At the workshop, there seemed to be a pretty strong sense that, although the general theory and understanding of hash functions leaves a lot to be desired, and is not as good as our understanding of block ciphers when NIST started the AES competition, it's still better to get on with the competition, rather than to keep refining our understanding to identify the precise selection criteria for the competition. Based on this public feedback, NIST has decided to start the process sooner, and has adjusted the timeline accordingly.

That's the spirit!

Posted by iang at January 25, 2007 03:18 PM | TrackBack