Posted by Andy Hassall on 09/05/05 21:33

On Mon, 05 Sep 2005 10:25:52 +0200, Erwin Moller
<since_humans_read_this_I_am_spammed_too_much@spamyourself.com> wrote:

>Andy Hassall wrote:
>
><snip>
>
>>>So: effectively MD5 is broken. Do not use it.
>>
>> OK, so the MD5 collision attack is based on already having plaintext A
>> and
>> hash M, and being able to produce a different plaintext B that has the
>> same hash M.
>
>The MD5-attack is based on having ONLY the md5-hash.

Sorry, which MD5 attack are you referring to? The MD5 attack required to break
MD5-based password systems is indeed based on having only the MD5 hash, but I
wasn't aware of any such attacks that exist, beyond brute force.

>If you had StringA already, you were ready already with the 'cracking',
>since StingA contains the original password. :-)

Exactly the point - which is why the published weakness does not appear to be
particularly relevant to this usage, since it requires this approach. It finds
collisions such that one plaintext can be transformed in a specific way into a
second plaintext, yet have the same MD5 - it does not produce any of the
infinite plaintexts from a single MD5.

e.g.
http://www.cits.rub.de/MD5Collisions/
http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf

Given both message M and hash H(M) this attack provides a method of modifying
M to produce M' such that H(M) = H(M').

It doesn't, given only H(M) and _not_ M, find any M' (which may or may not
equal M) such that H(M) = H(M').

(Unless I've drastically missed the point somewhere).

>The point is that giving a certain MD5-Hash, you can come up with some
>String as input that produces the same MD5-hash.
>
>An example:
>You password is 'verySecret'
>md5('verySecret') -> asgfjhasgfjhgsadfj
>
>Some Bad Guy ONLY gets hold of the md5-hash (asgfjhasgfjhgsadfj).
>Based on this String (s)he can produce another string that also produces
>asgfjhasgfjhgsadfj.
>for example:
>md5Cracker('asgfjhasgfjhgsadfj ') -> 'hhgttg'
>
>md5('hhgttg') -> asgfjhasgfjhgsadfj

But do you have a link to such an attack? That's not what the attacks being
referred to do, is it?

There is still only brute force enumeration as far as I'm aware, made easier
to look up through Rainbow Tables and the search space being reduced by users
having weak passwords, but then salted MD5 password hashes make it harder again
(you have to find the salt and then regenerate your tables all over again).

--
Andy Hassall :: andy@andyh.co.uk :: http://www.andyh.co.uk
http://www.andyhsoftware.co.uk/space :: disk and FTP usage analysis tool

[Back to original message]