[NBLUG/talk] The (maybe) SHA1 hash crack

[Mitch Patenaude]

On Thu, 17 Feb 2005 13:53:25 -0800, Mark Janes <mkjanes at sonic.net> 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?

I haven't been able to read the paper, so this is mostly speculation,
gleaned from what I've read in the popular press.  I believe what the
team in China has managed to do is create a collision.  That is, two
plaintext messages which produce the same 160-bit message digest
(hash).

The simplest brute force methodology for producing collisions is
called a birthday attack[*].  This basically means generating random
messages, computing their hashes and checking them against all
previously generated hashes until you get a duplication.  For a
"perfect" 160 bit hashing function, this should take about 2^80 hash
computations (computationally infeasible.. one hopes).   This attack
reportedly allowed them to generate a collision in only 2^69 hash
computations (which puts it in the realm of people or organizations
who can dedicate 1000's or 10000's of cpus for a few months or
years... so governments, large corporate entities.)

It's still too early to panic.  I doubt this will quickly transform
into a practical attack against GPG/PGP/S-MIME, etc.  The only attack
I can think of right now is:  If they have 2 plaintexts (say chunk A
and chunk B), and they can fool you into putting chunk A into your
message/key/document, then they can substitute chunk B without
changing the overall hash value (assuming that the chunks fall neatly
on block boundries.)  There *might* be some packet injection attacks
against WPA or 802.11i, I haven't thought it through yet, but of
limited usefulness.

It would be much more serious if they've been able to generate a
random plaintext with a specific hash value... which should be
considerably more difficult. A brute force attack is O(2^160). 
Generating a plaintext with a predetermined hash value that also
conforms to some other constraint (looks like english text, is a valid
JPG image, etc.) will be more difficult still.

  -- Mitch

[*] Say you're having a big party, and you want to see if any two
people have the same birthday.  The average number of people you need
to check before two people have the same birthday is only about 20
(Maybe 30? It's been a while since I've done the calculation).  Look
it up in a statistics book if you want the whole explanation.  But the
gist is... There's a 1 in 365 chance that the first two have the same
birthday,  But it they don't, then there's a 2 in 365 chance for the
third person, a 3 in 365 chance for the fourth, etc.