Posted by Jerry Stuckle on 09/05/05 17:39

Erwin Moller 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.
>
>
> No,
>
> The MD5-attack is based on having ONLY the md5-hash.
> If you had StringA already, you were ready already with the 'cracking',
> since StingA contains the original password. :-)
>
> 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
>
> Regards,
> Erwin Moller

One thing you're all forgetting.

Obviously different strings can create the same MD5 hash. After all, it
is a one-way hash. If the hash were unique, it could be bi-directional.

Additionally, the results of a unique encryption must be at least as
long as the data being encrypted (before any compression algorithms).
This obviously isn't true here.

Yes, the hash value may be duplicated by changing only a few bits of a
1024 bit input. That's possible - an MD5 hash is not 128 bytes long.
So there is a 100% chance that there will be at least 2 128 byte strings
with the same hash. In fact, there is probably almost a 100% chance
that EVERY 128 bit string has another 128 bit string producing the same
hash.

That this can be accomplished by "changing a few bits" doesn't surprise
me, either. But finding the right bits to change would be very
difficult. There would be 1024! (1024 factorial - 1024 x 1023 x 1022 x
....) possible combinations. And yes, there would probably be more than
one which gave that same hash value.

Now - you might be able to analyze the algorithm to limit the
possibilities - I haven't tried, so I don't know. But that might help
in certain circumstances.

Virtually any hash or encryption method can be broken for specific
examples. That doesn't mean it isn't secure for general use. Only in
those specific examples.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

[Back to original message]