[vox] [fwd] The (maybe) SHA1 hash crack

[Bill Kendrick]

Interesting read seen on NBLUG...

----- Forwarded message from Eric Eisenhart -----

Date: Sun, 20 Feb 2005 13:41:24 -0800
From: Eric Eisenhart
Subject: Re: [NBLUG/talk] The (maybe) SHA1 hash crack

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

On Thu, Feb 17, 2005 at 01:55:18PM -0800, Mark Janes wrote:
>   As I sent off the last message, I noted that my current version of
> gpg uses SHA1 by default. I decided, just to be sure, to generate new
> keys using another hashing algorithm. In any event just how serious is
> this, really?

At this point in time, not very serious.

Basically, they found a mathematical trick that allows for more easily
generating two messages with the same hash; made it so that it can be done,
now, as fast as it *should* have taken in about 2020...

SHA1 is a 160-bit hash.  It *should* take 2^80 attempts to generate two
"plaintexts" that have the same SHA-1 hash value.  According to their
results, it's now down to 2^69 attempts.  That's 1/2048th as long. 
Generating a plaintext that hashes to the same value as a given plaintext
"should" take 2^160 attempts, and so far that's how long it does take,
AFAIK.

But being able to generate two plaintexts that hash to the same value isn't
actually all that interesting by itself.  It means you could sign a
random-looking bit of stuff and then later sign a different random-looking
bit of stuff and have it be the same signature....

It would be much more interesting (critical) if their results allowed for
replacing *part* of a message (or otherwise partial control over the
plaintext) to get the same hash or if they'd been able to generate a
matching hash for an arbitrary message, there'd be more to worry about.

The reason everybody's all excited about it is that what they've discovered
will probably eventually *lead* to making those other things more efficient. 
With the current level of knowledge and technology, it'll still remain
cheaper to invade your home, copy your hard drive and install a hardware
keylogger than to break SHA-1.

I'm leaving my GPG keys alone for now.  Why?  Because with a DSA key, the
"OpenPGP" standard (aka RFC2440) only allows for a 160-bit hashing algorithm
with a DSA signature, meaning either SHA-1 or RIPEMD-160.  SHA-256 or
SHA-512 aren't allowed by the standard (for now) and forcing gpg to use one
of them will make you incompatible with, well, almost everything.

I'll wait for the standards to catch up with the SHA-1 weakness.  The group
responsible for the standard *is* talking about the issue:
http://www.imc.org/ietf-openpgp/mail-archive/threads.html -- I'm sure
they'll come up with a standardized approach while SHA-1 is still "good".

Also, there's no reason to believe that SHA-256 (or SHA-512) is any stronger
than SHA-1. AFAIK, nobody has done that kind of analysis work on it. 
Remember, SHA-256 and SHA-512 are based on SHA-1, which are based on SHA-0,
which are based on, I think, MD4 (and MD5 is based on MD4... and I think MD4
is based on MD2...)...  Several points in that little tree have now been
shown to be weaker than they should be; I'm not convinced that switching to
a hashing algorithm that's barely been scrutinized by anybody is the right
way to go; they may be only exactly as secure as regular SHA-1 or even
weaker than SHA-1.  You can't just throw bits at that kind of problem and
guarantee higher security; the problem needs to be understood thoroughly.  I
think the larger number of bits versions of SHA-1 were intended to reduce
the likelyhood of accidental collisions and to fit in better with some other
algorithms, not to be inherently more secure.
- -- 
Eric Eisenhart
NBLUG Co-Founder, Scribe and InstallFest Coordinator
The North Bay Linux Users Group -- http://nblug.org/
eric at nblug.org, IRC: Freiheit at fn AIM: falschfreiheit
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)

iD8DBQFCGQQEE6qEmrbN7dcRAuwaAJ0Y7TqhBYmTXVN5qyW2y9VzHK+YXACeO2S7
LeuToT+eCRVyz6FSYdyde5o=
=qQMn
-----END PGP SIGNATURE-----

_______________________________________________
talk mailing list
talk at nblug.org
http://nblug.org/cgi-bin/mailman/listinfo/talk

----- End forwarded message -----

-- 
-bill!
bill at newbreedsoftware.com         "I'm anticipating an all-out tactical
http://newbreedsoftware.com/      dog-fight, followed by a light dinner."