[IP] SHA-1 cracked?

[Steven M. Bellovin]

In message <20050217071702.R30051 at ubzr.zsa.bet>, "J.A. Terranson" writes:
>
>On Wed, 16 Feb 2005, Ben Laurie wrote:
>
>> A work factor of 2^69 is still a serious amount of work.
>
>Yep.
>
>Does anyone recall DeepCrack's specs?

See http://www.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/
which includes links to scanned copies of the book.

Note that finding a hash function collision  by brute force is
inherently harder, because it requires some communication:  two
widely-separated machines may have produced matching outputs, but
they need to know about the other one.

That said, van Oorschot and Wiener published a paper in 1994 on
how to do it.  They estimated then that an MD5-cracker could be
built for $10,000,000 with an expected runtime of 24 days.  The
SHA1 attack is a 2^69 problem; MD5 collisions are 2^64; the difference
is pretty close to the Moore's Law gain since 1994.  I haven't
followed the literature on that subject; I don't know if there are
better designs or, for that matter, if they got it wrong.

I should note, though, that this is a meaningless discussion -- no
technical details have been released about the new attack, so we
don't know how easily it parallelizes.

As for gates -- from a naive level, SHA1 has 80 rounds; DES has
16.  If you want high throughput (again, for a brute force style
of attack), you need a pipeline and replication of the core logic;
that alone would imply a 5-fold increase in the gate count.  Beyond
that, SHA1 has a 160-bit data path; DES uses a 32-bit path.  I
won't try to estimate the relative complexities of the mixing
functions at each round.


		--Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com