Re: md5 collisions and speeding tickets

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 08/20/05


Date: 19 Aug 2005 23:19:05 GMT

Mxsmanic <mxsmanic@gmail.com> writes:

>Crypto@S.M.S writes:

>> Yes, by "reversing" the hash, I mean a "preimage" attack; that is,
>> given an MD5 value, "uncompute" it to reveal the underlying input
>> string.

>This is generally impossible. You might be able to find _an_ input
>message that produces a given digest, working backward from the
>digest, but you won't be able to find _the_ message, if the message is
>longer than the hash and the hash is truly a random function of the
>input message. A hugely defective algorithm might allow _some_
>messages to be identified from the hash (if, for example, only one
>message actually hashed to that value), but MD5 isn't that defective;
>if it were, people would have noticed by now.

>> It has been quoted time & again. He claims to be able to determine
>> the pass phrase used as input to an MD5, where the hash will be used
>> as an encryption key.

>He can't do that, if the pass phrase is significantly longer than the
>hash.

False, if the long passphrase is constrained. Let us say that you have a 20
character passphrase, and each character is only the number either 0 or 1.
Then the colliding preimages will almost certainly NOT have the property.
Ie, althought the phrase is significantly longer than the hash ( 10
characters, instead of 16 characters) there will almost certainly be a
unique preimage for each passphrase obeying those rules.

His consideration was that the passphrase was an english phrase, which
restricts the field significantly.

>--
>Transpose mxsmanic and gmail to reach me by e-mail.



Relevant Pages