Re: When will md5crk complete?

From: WinTerMiNator (me_at_privacy.net)
Date: 05/25/04 

Date: Tue, 25 May 2004 21:53:27 +0200

Hello,

Simon Johnson wrote:
>> Hello,
>>
>> This is the scheme of "birthday attack"; this is not what JLC claims
>> to fight against: in his site the examples he gives are attacks
>> against existing certificates, and in that case birthday attack
>> doesn't apply (it is
>> not the same probability to find two documents having same hash than
>> to find
>> a certificate having *the* same hash as a given one).
>
> Unfortunately, I have to conceed that JLC's attack is of little
> consequence to breaking certificates.
> His core message is correct however: you shouldn't be using MD5.

Why? have some weaknesses found in the algorithm?

> Once collisions are known to exist you're on tricky ground.

Collisions DO exist for every hash algorithm...

> There
> might be a trick that you can use
> against the SSL certificate if you have a hash function for which a
> fair number of known collisions.

For every hash algorithm there exist an infinity of collisions... MD5 sees
all potential files as 2^128 classes. SHA512 sees them as 2^512. There are
an infinite number of potential files, which, divided by 2^128 or 2^512 give
an infinite amount of collisions for each value of hash.

> Athough, I think that's unlikely.
> I'd go after somewhere in a system where the interaction with the
> hash is more complicated and more open to abuse.
> It's my opinion that with a fair bunch of collisions in MD5

Where do you find this fair bunch of collisions? The fact that they do exist
doesn't imply there are easy to find... Except some weaknesses in algorithm.
Do you have any reference to quote?

> you could
> tear down the security at least one protocol in the field with a bit
> of thought.
>
> It's not about absolutes. It's about managing the risk of a break
> occuring. Once MD5 has known collisions

I am French, and I have learnt that English uses conditional: If MD5 had
known collisions...

> the risk becomes much greater

the risk would become much greater

> of various protocols collasping and that risk can be inexpensively

Yes, I agree with the "can"! My opinion is: why not to use the biggest gun
(SHA512) since it doesn't cost any more than the smaller one (MD5). And I
don't see the necessity to waste time in a pseudo demonstration of MD5
supposed weakness, as JLC does. And maybe I'm not alone, and that could be
why not so much volunteers have enrolled in this useless adventure.

> avoided by using a longer hash length. You're not thinking about the
> cryptography properly if you choose to use MD5.
>
>> Note that, even in birthday attack, you are requested to generate a
>> bit more
>> documents:
>> - you have a probability ~ 0.5 to find a collision between two
>> documents among 1.17742*SQRT(N);
>
> 17% more work is a significant work increase but requires only a small
> additional cost to meet it.

Yeah, but with a 0.5 probability. What would be the cost with a resonable
probability? (0.9, or 0.95, the kind of probability you trust...). And don't
forget that to reach a probability of 1 is impossible in a finite number of
trials.

>> - but, the collisions in a same subset (nasty or nice) don't
>> interest you: you need a collision between a document from nasty
>> subset and nice one. This increases the number of documents to
>> generate in each subset (I let you
>> calculate it...).
>
> There is no practical difference between nasty and nice subsets.. The
> fact that both the nice
> and bad sets are far bigger than the set of hash outputs means that I
> can treat them as selections from the same
> set without skewing the birthday attack.

No, if you get a collision between two "good" variants of the contract (or
two nasty ones), it is useless for you: you won't have available a good
contract to have it signed by your co-contractor and its nasty counterpart
with same hash. Come back to the attack sheme that you have defined...

>> And, second, let's consider the contact has "only" a size of 5 kBytes
>> (~one
>> page of text).
>>
>> With your figure, underestimated, you have to store 5*2^64 kBytes of
>> files,
>> that means 461168602 hard disks of 200 GBytes each... Good luck,
>> rich man!
>>
>
> Not true.. I'm pretty sure you can adapt the Pollard Rho algorithm to
> work with hashes. That's how JLC is hoping to find a collision
> without a metric buttload of storage.

We will see it. Going back to the case of a "real" birthday attack, you
still have to keep a copy of each contract you have generated, to have the
"good" and the "nasty" signed. And, in that case you will need 549505004805
hard disks (549 billions, I had made a small error...), unless you have a
way to be able to rebuild the contract from its hash.

Note that:
- MD5 is not known invertible,
- and it is proven not bijective...

Regards, 

-- 
Michel Nallino aka WinTerMiNator
http://www.chez.com/winterminator
(Internet et sécurité: comment surfer en paix)
http://www.gnupgwin.fr.st
(GnuPG pour Windows)
Adresse e-mail: http://www.cerbermail.com/?vdU5HHs5WG