Re: un-hashing to reveal pass phrase [was: crypto sms]

From: Joseph Ashwood (ashwood_at_msn.com)
Date: 06/23/05 

Date: Thu, 23 Jun 2005 10:19:53 GMT

<Crypto@S.M.S> wrote in message news:11bkrbplrl0bp89@news.supernews.com...
> Thanks to all in Sci.Crypt for pointing fingers at
> this relatively new work (to me at least) on attacking
> hash functions:
>
> http://cryptography.hyperlink.cz/md5/Vlastimil_Klima_MD5_collisions.pdf
> http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf
> http://www.infosec.sdu.edu.cn/paper/md4-ripemd-attck.pdf
>
> These papers bring up more questions than they answer,
> with regard to breaking hashes to reveal pass phrases.
>
> In all of these papers, the "attack" is to compute a
> colliding hash value. That is all well and good, but
> how does being able to compute two collisions allow
> you to "back-compute" from an hash value to the
> text that produced it?

That is fairly straightforward, because the approximate length is known and
the entropic quantity is known this limits the number of possible passphrase
to just 1 in this case (unless the passphrase has > 1000-whatever it was
bits). By focusing only on the extremely limited MD5 which can hold more
entropy than is in the passphrase the entire list can be narrowed to
generally 1. This 1 collision is then the correct passphrase.

The times given in those are old, in fact I don't think the latest papers
have been officially published, but the show collisions in MD5 in 15
minutes. Because there is only one colliding value, the result is the
original passphrase.

Because of the smallness of the input there simply aren't enough collidable
values. My break didn't even actually use the MD5 attacks, instead it was
based on generating and hashing each of the 2^47 different possible values
until one collides. Considering that an up-to-the-minute laptop is clocked
just shy of 2^32 ops/sec, and that MD5 is only a few clocks to generate a
short output, the result is that in about 1 hour the collision should be
found.
                Joe

Relevant Pages

  • Re: CryptoCritic Blowhards Dumber than a Dopey Housewife ? -- un-hashing to reveal pass phrase [was
    ... > limited MD5 which can hold more entropy than is in the passphrase the ... > papers have been officially published, but the show collisions in MD5 ... Because there is only one colliding value, ...
    (sci.crypt)
  • Re: When will md5crk complete?
    ... and in that case birthday attack ... > His core message is correct however: you shouldn't be using MD5. ... Collisions DO exist for every hash algorithm... ...
    (sci.crypt)
  • Re: Re-secured Algorithm?
    ... >>MD5 collisions are actually trivial to generate. ... SHA-1 had real collisions in MD5. ... Personal attacks aside I doubt many ...
    (sci.crypt)
  • Re: MD5 status
    ... > work on collisions is that of being one-way. ... > Dobbertin as he is of course one of the biggest authorities on this. ... collisions in the MD5 compression function that you shouldn't use it. ... attack is dependent on the attack that you have against the algorithm. ...
    (SecProg)
  • Re: MD5s eulogy
    ... about anonymity, see http://mixminion.net. ... MD5 is Dead. ... slashdot article reference included below. ... >arbitrary collisions, just random collisions), it's folly to think it'll ...
    (alt.privacy)