Re: Complex Theoretical One Way Hash Question

"Ben Livengood" <ben.livengood@gmail.com> writes:

>Francois Grieu wrote:
>> In article <e27gr8$1a2n$2@agate.berkeley.edu>,
>> daw@taverner.cs.berkeley.edu (David Wagner) wrote:
>>
>> > The more complicated the image format, the more plausible it
>> > is that there is some existing corner case functionality that
>> > can be used in a strange way.
>>
>> It comes to me that, juste like it is feasible to make two
>> different postscript files with the same MD5 and showing
>> different meaningfull things
>> http://www.cits.rub.de/MD5Collisions
>> it is possible to make a postscript file that displays
>> its own MD5: we make it contain 128 blocks that each
>> can be changed to two states without changing the MD5,
>> and display the 128 bits coded herein as 32 hex chars,
>> on top of an image also in the (end of) of the file;
>> then set the 128 blocks as approriate to display the
>> MD5 of the file.
>>

IF you use an insecure hash Which is what MD5 is as far as collision
resistance is concerned then what was asked is possible. But then why not
just use a CRC hash which would make the problem trivial.

If you want to use a cryptographically secure hash, then I do not believe
that the process ispossible. Ie, if it were the hash would be useless
cryptographically.

Now, I do not thing that the collision weakness of MD5 could be used for
the original purpose. Ie, you can find two files with the same hash, but
not a file with a given hash. Once you have enbedded the number in the
image, then you must find a file, the file in question, with bit twiddling
of unimportant bits, with exactly that hash.

>Since postscript is a turing complete language, couldn't you just make
>it calculate the MD5 digest of itself and then print it? It would
>essentially be a quine that instead of printing itself printed the MD5
>digest of itself. It should be possible in any language that allows
>both printing quines and calculating MD5.

That would of course be useless in verifying the photo, since anyone could
change the code in the postscript file to print out whatever they wanted,
including any purported hash.

The OP never did say what he really wanted this for so it is entirely
unclear if any of these ideas would meet his needs. When pressed he refuses
to say what he wants.

> Ben
Received on Mon May 1 02:03:23 2006