Notes from the Hash Futures Panel

The Second NIST Hash Workshop was a day and a half of presentations and discussion of a wide range of topics relating to cryptographic hash functions. As you can see from the meeting's agenda, it covered topics such as designing new hash functions, attacking current hash functions, determining which hash features are important, and so on.

At the end of the first day, Arjen Lenstra from Ecole Polytechnique Fédérale de Lausanne and I co-moderated a panel called "SHA-256 Today and Maybe Something Else in a Few Years: Effects on Research and Design", and the panelists were many of the luminaries in the area of cryptographic hashes. The five panelists were Niels Ferguson from Microsoft, Antoine Joux from the Université de Versailles-Saint-Quentin-en-Yvelines (who gave the keynote for the second day of the workshop), Bart Preneel from Katholieke Universiteit Leuven, Ron Rivest from MIT, and Adi Shamir from the Weizmann Institute of Science. By all accounts afterwards, the panel was a great success, with lots of interesting viewpoints and ideas exposed in a single hour.

The slides that we used loosely for the panel are here. Lenstra did the initial introductions while I fumbled with the PowerPoint, then I covered the logistics ("hold your questions until after the hour"), and then we dove into the four topics. Note that the questions on each of the slides were to generate discussion, not actually to be answered. Some of the panelists came prepared to answer specific questions, but most just winged it; that worked out great. Some of the individual questions were ignored while others were dealt with in depth. Lenstra and I kept each of the four topics to around 15 minutes, although the panelists danced out of bounds fairly frequently.

Given that Lenstra and I were up on stage, we couldn't take notes about what was being said. At the end of the workshop, I asked people who had taken notes to send them to me and I would summarize them anonymously. The following is a mixture from the four different attendees who responded (thanks, folks!) and my own memory. In some cases, I have moved statements from the topic in which where they were made to the topic that they actually address.

Note that the following is an amalgam of the reports, not direct quotations from a transcript. Some of the statements below may be completely incorrect; if so, I apologize in advance.

What problems with SHA-1 and SHA-256 do we really face?

Shamir started by saying that it was a problem of perception: a PR disaster but not a crypto catastrophe. Uncertainty is a problem today. Still, we need a SHA-1 replacement. Preneel points out that MD5 has been known to be weak for a long time but it is still used with no catastrophic consequences.

Rivest says we need "defense in depth": carefully parameterized design (such as having the number of rounds in the compression function as a parameter) and we may need a huge margin of safety.

Preneel says that we cannot evaluate SHA-256 because we don't know what attacks it was designed to protect against, or the safety margins assumed. He also says that collisions today will eventually lead to preimage attacks tomorrow. Ferguson says that there is a shadow of doubt over the design philosophy of the MD/SHA-family.

At the end of this topic, Joux says that we do not understand what we are doing and that we do not really know what we want; there is agreement from all the panelists.

I looked out at the audience and saw that many people were a bit shaken by this conclusion. However, it became somewhat of a theme for the rest of the workshop. This conclusion was humorously recast the next day in a presentation by Kristin Lauter from Microsoft who quoted the lyrics to the Talking Heads song "Road To Nowhere":
Well we know where we're going
But we don't know where we've been
And we know what we're knowing
But we can't say what we've seen
And we're not little children
And we know what we want
And the future is certain
Give us time to work it out

What properties of hash functions do we know we need for the long term?

Ferguson pointed out that we want protection for long term, not just a function that cannot be broken now. Signatures over hashes need to be valid for more than 30 years.

Shamir says variable number of rounds is a requirement. AES with 10 rounds was cutting it close. Make the number of rounds a variable.

Preneel says collision resistance is a requirement. Ferguson says practitioners use hash functions as a random mapping, so this is a design criteria.

Rivest says focusing on the compression function important. Joux agreed, and but felt collision resistance is meaningless for a fixed hash function: we need an alternative definition.

Preneel says we should try to get rid of the use of hash functions in many places where they are not needed; this may help us better focus our requirements.

Shamir says the output should remain collision-resistant even when truncated.

Rivest proposes that maybe we should think about hash functions that work on the whole message at once instead of block-by-block. (Side-note: there was a bit of confusion about terms when people started talking about "streaming" and "non-streaming" and "in-memory". Some panelists felt that a potential new hash design could be one where the whole message being hashed is kept in memory and worked on as a whole. This was called "non-streaming" and "in-memory", to contrast with current "streaming" functions that work on a block at a time, keeping some state from previously-processed blocks.) Shamir was not convinced that multiple passes over the whole message will help.

Should we develop one all-purpose hash or several special-purpose hash functions?

There was general agreement that there is an enormous cost of adding new functions and we should aim for one function only.

Preneel wants one function + parameters + modes + number of rounds + output length; maybe we can separate the pieces. Shamir agrees, but doesn't want the mode to tinker with the parameters for the compression function. Modes that are not black boxes can cause problems.

Ferguson says that MD5 shows up about 850 times in the Windows source code. OAEP thinks it has a random oracle.

Joux wants a single new function that emulates a random oracle, but believes this can't be done with streaming, so there will have to be whole-message and streaming flavors.

Ferguson says non-streaming functions will not work with existing software architectures such as Microsoft's CAPI.

Rivest says variation in strength by having variable number of rounds is useful. Preneel points out that the low end systems such as RFID might not be able to support hashes with 512 bits of output.

How do we design the next algorithm(s)?

Lenstra asks should we tweak or start over; Shamir responds that we don't know how to start over.

Lenstra tells a story about talking to Rivest and Shamir during the break in the rump session after Wang had first announced her findings. Lenstra asked them do we need to start afresh or do we need more tweaks. Rivest's gut reaction was "more tweaks", while Shamir's was "something new". (Rivest says he didn't remember him saying that.)

Shamir believes that the current class of algorithms is flawed, but at this point we don't have better algorithms; we will have to look at tweaking SHA-2.

Ferguson says we make great strides by trying, and advocates a hash competition. Competition concentrates expertise on a particular set of process. Shamir says he thinks most of the AES entries were not revolutionary. Rivest agrees with Ferguson. Preneel says that in many of the competitions, what came out wasn't any better than what went in. Joux believes a competition will encourage novel attacks against the SHA family and help answer whether or not the Merkle-Damgård approach is dead. In general, there was a lot of enthusiasm for having NIST hold a competition, but confusion about how it would be set up.

Both Rivest and Shamir want a parameterized hash. Shamir says only parameterize number of rounds. Joux says streaming/non-streaming is a good parameter. Rivest wants parameters for input and output block size as well as number of rounds. Rivest notes that he has been burned in the past by performance goals.

Shamir says don't use AES-256 unless you are worried about quantum computers and that SHA-256 is good enough from a block size perspective. Joux thinks tweaks to SHA-256 are the easy way, because we don't know what to do.

Ferguson says that non-cryptographers do not have expertise to set the parameters. Rivest says we will need strong recommendations if we have parameters. Shamir says that we need to expand internal state to avoid collisions. Preneel says we should use what we have learned from block ciphers, and likes Shamir's tweaks, but he also wants to take risks in new modes different from Merkle-Damgård.

After the panel

We had 15 minutes for Q&A, so I encouraged the audience to actually ask questions or make short statements, not pontificate. Only one audience member pontificated, and most had good questions (that no one took notes on...). Elaine Barker from NIST said that the NSA should be making a statement in the future about the design patent on SHA-256 (US patent 6,829,355) that was mentioned in the last slide.

The following day, there was much discussion about designs for new hash functions and the proposed NIST hash competition. NIST encouraged people to join their mailing list to discuss hash functions and the competition.