Re: Is MD5 outdated ?

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 10/02/03 

Date: Thu, 02 Oct 2003 00:24:55 GMT

Mxsmanic wrote:

> Simon Johnson writes:
>
>
>>I introduce small invisible changes (easily done in formats like Adobe
>>and Word) in both documents until the birthday paradox is invoked and
>>they hash to the same value.
>
>
> But you don't know where the changes will be required, and so they won't
> necessarily be invisible (and in fact will probably be visible). You
> essentially have to make random changes to the document until you get
> the same hash, which is not computationally feasible.

That's a misunderstanding of the attack. He makes many versions
of both, and looks for any collision between a favorable and an
unfavorable document.

>>You then sign the favourable document and then i take
>>your house :)
>
> Fortunately, the decay of protons throughout the universe will have
> rendered the contract moot.

Not in this universe. On MD5, the attack is on the order of
2**64 in both time and space, though there's probably enough
overhead to make it closer to 2**80 operations. With a quick
web-search, I found the half-life of a proton exceeds 10**33
years. 

-- 
--Bryan
firstname dot lastname at domain of the Association for Computing Machinery

Relevant Pages

  • Re: Salt
    ... using a salted hash instead of a simple hash has ... But you are not the only one in the universe who has a credit card. ... tables built to attack other people's credit cards to attack yours. ...
    (sci.crypt)
  • Re: Hashing of short fixed length messages
    ... You actually have 55 bytes of useful payload before MD5 requires a 2nd ... to present a traditional hash interface since the ... The input itself is a hash too, so I can ignore related key attack, ... to a speed-up factor of two, but I don't think it's secure. ...
    (sci.crypt)
  • Re: How good an encryption algorithm is this?
    ... Actually it's vitally important that the salt is different every time. ... but a one-way hash of the password). ... >>> attack (using my dictionary of plaintext trial passwords and the ... you need to perform this iteration only once. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: How good an encryption algorithm is this?
    ... Actually it's vitally important that the salt is different every time. ... but a one-way hash of the password). ... >>> attack (using my dictionary of plaintext trial passwords and the ... you need to perform this iteration only once. ...
    (microsoft.public.vc.language)
  • Re: Public key encryption
    ... >>messages as to break the hash algorithm. ... > it amounts to equivalence to the RSA problem. ... > anything that can forge PSS signatures can do arbitrary RSA ... > attack on weak padding is Bleichenbacher's "Million Message Attack", ...
    (sci.crypt)