Posted by Erwin Moller on 09/05/05 17:43

Jerry Stuckle wrote:

<snip>

Hi Jerry,

For clarity's sake: I do not claim to be an encryption-expert. You might
very well know a lot more than me.
I am just restating what Schneier and Slashdot wrote because I think it is
important to all people using the SHA-0/SHA-1/MD5 algoritms.
(The math behind it all is way over my head.)

>
> One thing you're all forgetting.

Tell me. :-)

>
> Obviously different strings can create the same MD5 hash. After all, it
> is a one-way hash. If the hash were unique, it could be bi-directional.

I knew that.
That would be a great zip-algoritm. ;-)

>
> Additionally, the results of a unique encryption must be at least as
> long as the data being encrypted (before any compression algorithms).
> This obviously isn't true here.

Agree.

>
> Yes, the hash value may be duplicated by changing only a few bits of a
> 1024 bit input. That's possible - an MD5 hash is not 128 bytes long.
> So there is a 100% chance that there will be at least 2 128 byte strings
> with the same hash. In fact, there is probably almost a 100% chance
> that EVERY 128 bit string has another 128 bit string producing the same
> hash.

Indeed.

>
> That this can be accomplished by "changing a few bits" doesn't surprise
> me, either. But finding the right bits to change would be very
> difficult. There would be 1024! (1024 factorial - 1024 x 1023 x 1022 x
> ...) possible combinations. And yes, there would probably be more than
> one which gave that same hash value.

And here you missed the important point (I think):
You do NOT need to try brute-force all possible combinations.
The new MD5-cracking algoritm can do that smarter/quicker/better-guessing.
(I am not sure since they didn't publish their results yet AFAIK)

>
> Now - you might be able to analyze the algorithm to limit the
> possibilities - I haven't tried, so I don't know.

And that is excactly what happened.

> But that might help
> in certain circumstances.

It did for Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu: the Chineese
researchers. :-)

>
> Virtually any hash or encryption method can be broken for specific
> examples.
> That doesn't mean it isn't secure for general use. Only in
> those specific examples.

True.
But we just do not know how many SHA-1 hashes are prone to collions-finding
algoritms.
A good algoritm will let the Bad Guys only break it brute force, hence
forcing them to try random inputstrings for a zillion years.

From Schneier's weblog:

<quote>
Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the
fire exits. You don't see smoke, but the fire alarms have gone off." That's
basically what I said last August.

It's time for us all to migrate away from SHA-1.

Luckily, there are alternatives. The National Institute of Standards and
Technology already has standards for longer -- and harder to break -- hash
functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already
government standards, and can already be used. This is a good stopgap, but
I'd like to see more.
</quote>



For clarity's sake: I do not claim to be an encryption-expert. You might
very well know a lot more than me.
I am just restating what Schneier and Slashdot wrote.
The math behind it all is way over my head.

Some links:
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

or this newer and much more informative article:

http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

Regards,
Erwin Moller

[Back to original message]