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

Relevant Pages

  • Re: making SHA-512 as fast as MD5
    ... function with different diagonal constants. ... Bernstein estimates that a Rumba20-based hash function runs at half the speed of the Salsa20 stream cipher, and based on my own implementation of Salsa20, I think that such a hash function will run at 10 bytes per cycle on the Intel Core 2, which compares favorably with 12 bytes per cycle for SHA-512 on the same CPU. ... However, it occured to me that we can apply the same principle behind Rumba20's design to the SHA-512 compression function, and derive a faster variant of SHA-512. ... This variant is probably faster than any currently unbroken hash function design, and nearly as fast as MD5. ...
    (sci.crypt)
  • Re: Reversible hash function
    ... > block cipher that is similar to DES, ... > could you use a hash function to replace the F function in DES? ... Luby and Rackoff proved this construction ... iterated `compression function' which looks like a block cipher sideways ...
    (sci.crypt)
  • making SHA-512 as fast as MD5
    ... J. Bernstein recently proposed a 1536-bit-to-512-bit compression function called Rumba20 to be used in a future hash function design. ... Bernstein estimates that a Rumba20-based hash function runs at half the speed of the Salsa20 stream cipher, and based on my own implementation of Salsa20, I think that such a hash function will run at 10 bytes per cycle on ... However, it occured to me that we can apply the same principle behind Rumba20's design to the SHA-512 compression function, and derive a faster ... This variant is probably faster than any currently unbroken hash function design, and nearly as fast as MD5. ...
    (sci.crypt)
  • Re: Properties of MD5
    ... MD5 has some very bad known weaknesses. ... Truncation is fine with ... any cryptographic one-way hash function. ... output of the previous round of the compression function. ...
    (sci.crypt)