January 25, 2007

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

At 8:22 PM -0500 1/23/07, Ivan KrstiÁ wrote:
> Perry E. Metzger wrote:
>> http://www.csrc.nist.gov/pki/HashWorkshop/index.html
> I'm completely unfamiliar with the way NIST operates, but I've been
> wondering for years why they haven't organized this competition already.
> Do we have a list veteran who can shed some light on why it took them
> this long? My curiosity demands to know.

At the Second Hash Workshop this summer, NIST explained this a bit. (There were a bunch of regulars from this list there who can correct me if I'm wrong.)

First, there is SHA-2 (SHA-256, -384, and -512). Nearly everyone thinks they are good enough unless there is an unexpected attack. So NIST was not hot to create something that competes with this.

More important, however, is the lack of sureness in the community that we know what will make a good hash function, much less one that is better than SHA-2. See for much more on that.

Also, remember that we don't know much about the design of SHA-2. In fact, unless the NSA tells the world a whole lot more, it will not be able to compete in the NIST competition due to requirement B1 in the proposal.

At the end of the workshop, there were at least two camps: those who wanted a competition in case Wang-esque attacks degrade SHA-2, and those who didn't want a competition until we knew more about how to judge it because we don't know enough now. Some of the Big Names In Crypto are in the second group. It looks like NIST sided with the first group, but it will be interesting if the folks in the second group are vocal during the coming few years.

--Paul Hoffman, Director
--VPN Consortium

Posted by: Seen on crypto group at January 25, 2007 02:22 PM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.