[IP] SHA-1 cracked?
Steven M. Bellovin
smb at cs.columbia.edu
Tue Feb 22 11:37:40 EST 2005
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
More information about the cryptography
mailing list