Are there problems with Merkle-Damgaard and SHA-256?

From: D. J. Bernstein (djb_at_cr.yp.to)
Date: 08/28/05


Date: Sun, 28 Aug 2005 07:23:17 +0000 (UTC)

Paul Rubin wrote:
  [ regarding NIST's http://www.csrc.nist.gov/pki/HashWorkshop/index.html ]
> Maybe they will call for YA new hash function.

NIST already has a hash standard, namely SHA-256, with fairly widespread
deployment. (They also have other security projects to work on, such as
secure voting.) So why should they call for something new? What's wrong
with SHA-256?

Here are the answers I've heard so far:

   * SHA-256(m) can't be highly parallelized even if m is long.
   * SHA-256(m) takes two invocations of the compression function when m
     is short.
   * The length-extension bug: SHA-256(m,mlen,x) is easily computed from
     SHA-256(m),mlen,x.
   * The SHA-256 compression function is fairly slow, well over 1000
     cycles on typical CPUs.
   * The SHA-256 compression function doesn't have public design
     principles for us to evaluate.
   * Each node in the computation graph of the SHA-256 compression
     function has a fairly short path from the input---not nearly as
     short as in SHA-1 but much shorter than other constructions.

Most of these problems can be worked around at the application level:
consider, for example, the parallelizable tree of hashes in BitTorrent.
But these workarounds make the hashing even slower.

What else do people not like about SHA-256?

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago