Re: When will md5crk complete?

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 05/25/04 

Date: Tue, 25 May 2004 12:38:10 GMT

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.
>
> Once collisions are known to exist you're on tricky ground. 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. Athough, I think that's unlikely.

By this logic though you could argue the differential attacks on MD4 are
not "real". I mean [afaik] you can't produce arbitrary collisions with
MD4 [efficiently]. So let's all use MD4 it's much faster!

The point of md5crk is to show that *any* 128-bit hash is too small.
After random collisions can be efficiently produced the hash can't be
used to hash unstructured data. While I think JL [btw: call him Jean
Luc or JL but not JLC.] may have over-estimated the impact of this
program nobody else has shown collisions in MD5 and it will be certainly
interesting to see.

I mean Dobbertin got some press for showing *pseudo* collisions of MD5
so let's cut JL some slack here ;-)

That and I'm getting good rates on md5crk .... !!!

Tom

Relevant Pages

  • Re: Re-secured Algorithm?
    ... i remember a time when the ability to find collisions with less ... >>work than a brute force search meant that the hash algorithm was broken... ... 6,000 machines would take 3 weeks to attack md5 with a complexity just ... > To get the desired results for just ONE SINGLE successful attack, ...
    (sci.crypt)
  • Re: Generate unique ID for URL
    ... depending on the needs. ... and there is always the possibility of collisions. ... A hash is the wrong answer to the issue as a hash is open to all sorts ... of attack vectors like length extension attack. ...
    (comp.lang.python)
  • Re: When will md5crk complete?
    ... > existing certificates, and in that case birthday attack doesn't apply (it ... > not the same probability to find two documents having same hash than to ... Once collisions are known to exist you're on tricky ground. ...
    (sci.crypt)
  • Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)
    ... > The problem with a hashed state table is that hash tables are very ... > an attack totally blow out the D$ and TLB. ... an attacker could manufacture enough collisions to push the hash table ... Couldn't that attack be frustrated by a more sophisticated hash function ...
    (Firewall-Wizards)
  • Re: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)
    ... >> The problem with a hashed state table is that hash tables are very ... >> an attack totally blow out the D$ and TLB. ... > an attacker could manufacture enough collisions to push the hash table ... > Couldn't that attack be frustrated by a more sophisticated hash function ...
    (Firewall-Wizards)