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!


Relevant Pages

  • Re: compare-by-hash (was Re: sharing /etc/passwd)
    ... Hash: SHA1 ... infinite number of inputs, you are guaranteed an infinite number of ... > blocks comparing as equal exists, ... hashes to generate a collision. ...
    (FreeBSD-Security)
  • Re: [Full-disclosure] Month of Random Hashes: DAY THREE
    ... On Fri, 15 Jun 2007, Brian Dessent wrote: ... inputs and a finite number of outputs, just like any other hash ... an infinite number of corresponding inputs. ... Hosted and sponsored by Secunia - http://secunia.com/ ...
    (Full-Disclosure)
  • Re: Programming Open-Ended Plots In Games
    ... is randomly generated in the main plot. ... There are well known structures that can generate an infinite set from ... quality hash of the current gamestate and/or ... The Art of Computer Programming: ...
    (comp.programming)
  • Re: Revert MD4
    ... possibles COLLISIONS that means that a file has the ... same hash value as the original but with a infinite ... the cryptographic attacks on md4 are different ...
    (sci.math)
  • Re: Fancyhdr and scaling text
    ... Hash: SHA1 ... with fancyhdr borders' texts is another problem, ...
    (comp.text.tex)