Re: Instances of deliberate, full MD5 collision?

From: Walter Roberson (roberson@ibd.nrc.ca)
Date: 11/17/02


From: roberson@ibd.nrc.ca (Walter Roberson)
Date: 17 Nov 2002 05:13:36 GMT

In article <87n0o95s4e.fsf@Astalo.y2000.kon.iki.fi>,
Kalle Olavi Niemitalo <kon@iki.fi> wrote:
:unruh@string.physics.ubc.ca (Bill Unruh) writes:

:> The hash is not a one to one function. There are provably an infinite
:> number of clear texts which hash to the same value.

:Yes, for at least one value. But can you prove that there are an
:infinite number of clear texts for _every_ hash value?

If one makes the assumption that every possible 128 bit result
is generated by *some* 512 bit imput, then Yes, it's not hard to
prove that there are an infinite number of clear texts for every
hash value. (Unless you mean 'clear texts' in the sense of
"a bytestream that would make sense as ASCII/ISO9660- encoded
prose in some existing human language such as English.)

The key to showing infinite clear texts is to find a 512-bit clear text
that MD5-hashes to the set of constants that are the initial values
given to the registers (A, B, C, D). Once you have that cleartext, then
indefinite numbers of 2^54 copies of the padded version of it can
prepended to the input stream without affecting the output in any way.

To phrase this another way, if you can find even one 512 bit clear text
that hashes to those particular constants, then you can construct 2^64
bit chunks that are fixed-points in the MD5 algorithm, leaving the
state registers and padding values in exactly the same form as if the
chunks had not been present at all.

--
   Oh, to be a Blobel!