Re: Complex Theoretical One Way Hash Question

> I wish to know if it is possible to embed an MD5 of an image (e.g. a
> JPEG) in the image such that the MD5 is human readable in the image AND
> is an MD5 of the modified image including the readable MD5.

> That is - if I execute an MD5 hash sum off the entire image, that MD5
> has will be the same as the MD5 shown in human readable format in the
> image (I don't mean a JPEG tag, I mean literally on the image canvas
> itself).

> The questions:
> 1. Is it theoretically possible ?
> 2. Is it feasible ?
> 3. Has it already been done ?
> 4. Would other one way hash algorithms be more suited ?

> E-Mail me on sci(dot)crypt(@)craznar(dot)com if you have any specific
> questions, or reply here.

> Thanks.

You can't do this without breaking the hash. But what if *you* can
break the hash but nobody else can? Is this sufficient for your
purpose?

It should be possible to construct such a hash using x^2 mod n, where
only you know the factorisation of n. x^2 mod n has exactly four
solutions. It has been proven that the computing the square root is
equal to the difficulty of factoring. Everyone thinks that factoring a
large n is a difficult problem (except James Harris :) ). Finding
collisions in this hash would easy since you can compute x^2 mod n =
y^2 mod n easily.

A hash using x^2 mod n would chain a series of these operations
together so it doesn't take many iterations to get rather alot of
possible collisions. Even after just 20 interations of the hash there
are 4^20 = 109,9511,627,776 trivial collisions. It may be possible to
use the mathematical structure of x^2 mod n to get even more
collisions.

Whether any of these collisions would be useable in a JPEG is an open
question. The algorithm would also take a long time to run but it's
certainly not ruled out in principle.

I'd say a definte maybe if you're willing to drop MD5 as the hash
function.

Simon.
Received on Mon May 1 02:03:34 2006