[16963] in cryptography@c2.net mail archive
Re: [IP] SHA-1 cracked?
daemon@ATHENA.MIT.EDU (Steven M. Bellovin)
Thu Mar 3 14:26:51 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Steven M. Bellovin" <smb@cs.columbia.edu>
To: "J.A. Terranson" <measl@mfn.org>
Cc: Cryptography <cryptography@metzdowd.com>
In-Reply-To: Your message of "Thu, 17 Feb 2005 07:17:33 CST."
<20050217071702.R30051@ubzr.zsa.bet>
Date: Tue, 22 Feb 2005 11:37:40 -0500
In message <20050217071702.R30051@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@metzdowd.com
