question regarding relative security of md5 vs sha1

[David Shaw]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wed, Sep 10, 2003 at 11:58:52PM -0400, John J. Courie II wrote:

> so let me get this straight, if moore's law is 'true' than a
> mathmetical analysis of hash sizes will result in it being ~30 years
> before md5 will be susceptible to bf/dict/b-day attacks, but it will
> be about about 80 before sha1 will be susceptible to cracks of that
> level.  I know this is sort of OT but I couldn't think of anyone
> more qualified than the experts of the crypto software I am using.

It's not an easy question - susceptible to attacks by *whom*?  Attacks
become feasible for different groups at different times (people who
have lots of fast computers and/or lots of money to spend on fast
computers are going to be able to attack sooner).  Also the difficulty
of different attacks varies widely (a birthday attack is massively
easier).

Because of this, and other reasons, the years you'll hear from
different people are likely to vary.

For what it's worth, the year I've seen cited for the ability to do a
birthday attack against MD5 is 1992 (yes, it passed already), and 2013
for SHA1.[1] It shouldn't be inferred that SHA1 suddenly becomes
broken in 2013 - just that somewhat around that time, the difficulty
of the attack goes from "practically impossible" to merely "absurdly
difficult" (think distributed.net).  Or someone could break it
tomorrow with a brand new attack that doesn't involve brute forcing.

Not everyone agrees with those dates, of course, but in any event MD5
has also had some successful analysis attacks against it.[2] It was
never "broken", but regardless of whether the hash is short enough to
be birthday attacked, it still would not be prudent to use it.

David

[1] http://secinf.net/uplarticle/4/cryptosizes.pdf

[2] http://samsimpson.com/cryptography/pgp/pgpfaqnew.html#SubMD5Broke
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.3.3-cvs (GNU/Linux)
Comment: Key available at http://www.jabberwocky.com/david/keys.asc

iHEEARECADEFAj9gY/EqGGh0dHA6Ly93d3cuamFiYmVyd29ja3kuY29tL2Rhdmlk
L2tleXMuYXNjAAoJEOJmXIdJ4cvJCAkAniE4YoSrPipeZyFDlJn6QkpJJv2iAKCW
bJ7/lyN4xvJahZ3p/cAZHeUZUQ==
=lZWY
-----END PGP SIGNATURE-----