Review of  the
NIST SHA-3 Round One Conference,
KU, Leuven, Belguim
2/25/09-2/28/09

Review by Hilarie Orman and Richard Schroeppel
3/15/09

Where would you find "Blue Midnight Wish", "ECHO", "ECOH", "Luffa", "Skein", "Sandstorm", and "ARIRANG"? Not at a horserace, nor a craft fair, nor a rock concert, but at the SHA-3 conference in Leuven, Belgium.

For several years cryptographers have agreed that the world needs a new standard for a hash function. The widely used MD5 function has serious demonstrated flaws, and its replacement, SHA-1, is not good enough. The replacement for SHA-1, named SHA-2, is unsatisfactory in its performance/security ratio. That sets the stage for yet another hash function.

The US agency responsible for cryptographic standards is NIST, and they recently launched a design competition similar to their highly successful block cipher competition of a decade ago, that resulted in the adoption of the AES cipher. The hash competition is named SHA-3, the eventual name for the standard algorithm.

At the end of February NIST held the first public meeting unveiling many of the hash function submissions. For two full days and two half days attendees heard from the organizers and the competitors, but that was barely enough time to cover the unexpectedly high number of entries.

Over 50 submissions from around the globe met the minimum criteria for acceptance into the competition, and of those, 10 are conceded as "broken". A few of the remaining entries are "seriously damaged", at least in the opinion of several cryptographers.

That still leaves dozens of viable entries, and NIST admitted that they do not have the resources to do a detailed analysis of the dozens of remaining competitors, so they hope that the cryptographic community will pitch in and publish analyses to assist them in pruning down to 15 candidates.

The NIST SHA-3 website lists all the submissions: All complete entries and the Leuven conference presentations are also online at Round 1 conference program.

Many of the candidates use functional components from the inner workings of the AES block cipher. The designers reason that the components are well-understood, supported by high-performance software, and Intel processors will soon include an new instructions that will make software even faster.

Other designers used ARX (add-rotate-xor) structures to achieve compact and/or very fast methods. There were many claims to "fastest" entry, and it was clear that the title will be tightly contested during the coming months. Some designers used novel construction methods, though perhaps not to good effect. One function (ECOH) used elliptic curve methods, resulting in what might be the slowest entry. The Spectral hash, designed by undergraduates at UC Santa Barbara, used FFTs, and was also slow.

MIT, led by Ron Rivest, submitted a design using an old idea in a new form. Non-linear feedback shift registers were used in early ciphers but have fallen by the wayside. MIT's MD6 revives them for hashing, using a large number of state bits and mixing them repeatedly with a NLFSR function.

The AURORA entry suffered a severe blow to one part of its design. The entry rules require that the hash support multiple output widths: 224, 256, 384, and 512 bits. The 512-bit version of AURORA had a weakness in its construction that was noted by Stefan Lucks and Niels Ferguson during the presentation, leading to that dread question "Could you go back to slide 13?"

NIST representatives were non-committal about how they might refine their selection criteria. However, Bill Burr of NIST did suggest an interesing way to cope with the problem of speed vs. security. He encouraged competitors to submit reduced-round versions of their algorithms that were at least as fast as SHA-2, if not as secure.

Ferguson had an "engineering considerations" presentation that seemed somewhat slanted towards the entry he contributed to: Skein. In rebuttal, several other competitors had a rump session entry that humorously detracted from all design techniques, before continuing on to counter each of Ferguson's points.

The next generation of cryptographers had a representative in 15 year old Peter Schmidt Nielson. Although his entry was not complete enough to meet criteria, NIST invited him to the conference so that he could present his work and meet the crowd.