Re: Complex Theoretical One Way Hash Question

Sebastian Gottschalk wrote:
> Ben Livengood wrote:
>> If you can get a JPEG,
>> GIF, etc. decoder to interpret each block as a pixel, you're set.
>
> Well, you know the meaning of "if"? It's a word to express "in case of"
> or "under the condition that".

More formally:

Consider a bit string S, and a new string S' that will contain S and
the MD5 digest of S' in some form. Since MD5 collisions can be
generated in the form of two blocks B and B' starting from any partial
MD5 digest it is possible to catenate a series of blocks B(0),B'(0)
through B(127),B'(127) such that for any 0<=k<128, B(k) or B'(k) is the
kth block appended or embedded in S'. The MD5 digest of S' will be a
128 value that can be encoded in S' by putting B(k) in S' if bit k of
the digest is 0, and B'(k) if the bit is 1.

Now S' is a string containing its own MD5 digest. To interpret the MD5
digest encoded in S', an array of 128 bit-positions is sufficient to
decode each of the k blocks by interpreting the bit at the given
position in the block as the kth bit of the MD5 digest. Since B and B'
are interchangable, it will always be possible to pick B(k) and B'(k)
so that a bit at a given position is 0 if the corresponding MD5 digest
bit is 0, and 1 otherwise. The array can also be embedded in S'.
Interpretation of the array in S' is up to the viewer.

If S is an image the dimensions of S could be increased to accomodate
the additional information, or the edges or other unused area of the
image could be used to store the hash. PNG might work, since LZ77
allows backreferences to previous pixel data in the window. After the
128 blocks are embedded in the image as raw pixel data, the MD5 digest
could be output in binary by picking byte differences in B and B' that
would produce high contrast pixels. Whether binary counts as human
readable is up to the original poster. If the image was large enough,
it might be possible to embed enough blocks in each scanline to produce
a hex MD5 as well. It all depends on how long someone wants to work
generating collision blocks with useful groups of pixels. It is almost
certainly less work than finding a preimage.

   Ben
Received on Mon May 1 02:02:16 2006