Are there problems with Merkle-Damgaard and SHA-256?
From: D. J. Bernstein (djb_at_cr.yp.to)
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
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
* The length-extension bug: SHA-256(m,mlen,x) is easily computed from
* 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