Re: When will md5crk complete?

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

Date: Sun, 23 May 2004 21:03:10 +0200

Tom St Denis wrote:
> Gregory G Rose wrote:
>> I was just looking at the md5crk web site, stats
>> page, http://www.md5crk.com/stats/ , and realized
>> that the rate of total MD5s per second isn't
>> climbing very much, and therefore the probability
>> of completion in a given time isn't getting much
>> better. So then I asked myself, "When do we expect
>> it to complete?", and I didn't like the answer (or
>> the punctuation :-) ); I get about 222 years.
>>
>> This surprised me. Were there really that many
>> more machines on the RC5/64 project? Or is MD5
>> really that much slower? Or what?
>
> IIRC on my Athlon XP box I got around 6M/sec with dnet and on my P4 I
> get around 11.3M/sec with md5crk.
>
> I don't think that md5crk is any slower I just think there are far
> fewer active members. Just recently I've gone up from mid 500 to
> ~290 in the ranking in the span of a week.
>
> The best advice is to just keep plugging, hope that Jean-Luc got his
> coding right [hehehe just kidin JL] and try to recruit new volunteers.
>
> Tom

I have read md5crck FAQ carefully, and I have found strong contradictions:

- JL wants to show that the use of MD5 hash in digital signatures is
unsecure; he gives as examples the use of certificates by Paypal, merchants
sites... In that case, the signature is existing, and, using brute force,
there is a 0.5 probability to find a collision against a given signature
(that means, a forged certificate having same MD5 hash) after 2^127 trials,
provided MD5 is really a randomly distributed function.

- However, his attack follows the "birthday paradox" scheme: he just wants
to find, in a large set, two documents colliding. In that case, the order of
magnitude of trials will be proportional to the root of the number of
possible hashes, ~2^64 (and the birthday attack in signing a contract is
very easy to counter: just make a very slight change - adding a space
character - to any contract proposed to signature that you have not written
yourself!).

This is all the problem of md5crck: the attack is not against the threat
model! And an eventual success in finding a collision in a set will prove
nothing about forging a given signature: let's suppose as, like JL expects,
~2 years will be necessary, with thousands computers, to find a collision
like he intends. This will just prove that, with the same computer power,
one will need 2^63 more time, that is 2^64 years, or 18446744073709551616
years to forge a certificate...

Very counterproductive! This is not the way to convince certificate builders
to stop to use MD5... 

-- 
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

Relevant Pages

  • Re: [PHP] need insights on encrypting and uploading ASCII file using PHP
    ... John A DAVIS wrote: ... As a sample of how this would work you read the file into memory, add a long string, the signature, that is never transmitted but that both ends know, and pass it all through an algorithm like MD5 or such. ... Or you could burn a CD and sent it through the mail, publish keys in the newspaper under personal ads, flash Morse code on clouds, or try smoke signals -- all work in one fashion or another to transmit data. ...
    (php.general)
  • Re: RSA signing security
    ... and these are used to sign a hash (MD5) of the data. ... came from a particular logger, and has not been tampered with since. ... No matter how clumsy the RSA signature padding/protocol is, ... that no publicly known technique allows attacking a particular system). ...
    (sci.crypt)
  • Re: HMAC-MD5 shown not compromized by MD5 collisions
    ... If the signature scheme first enters ... other one with neither signature changed, as in practice MD5 and SHA1 ... PGP seems to hash the public key as submitted. ... If the attacker is to inject meaningful data where the messages ...
    (sci.crypt)
  • Re: MD5
    ... > In PHP there is MD5 function it converts strings to MD5 encription, ... MD5 is not ment as an encryption to be decrypted, but only as a signature. ... Message digest algorithms have much in common with techniques ...
    (comp.lang.php)
  • signature of X509 certificates
    ... I'm trying to understand the signature value of X509-Certificates. ... certificate hencrypted with the private key of the corresponding ... If this value is the same as the hash value of the certificate the ... As the algorithm ID for MD5 is ...
    (sci.crypt)
Quantcast