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.

.

Relevant Pages

  • Re: When will md5crk complete?
    ... and in that case birthday attack ... > His core message is correct however: you shouldn't be using MD5. ... Collisions DO exist for every hash algorithm... ...
    (sci.crypt)
  • Re: MD5 Myths
    ... That's an over-broad indictment of MD5. ... ways to deliberately create collisions; ... found ways to create source strings that will hash to a ... in the MD5 digest to do more and/ or redesign ...
    (sci.crypt)
  • RE: MD5 To Be Considered Harmful Someday
    ... inputs from a given hash. ... collisions for), but that they can produce colliding inputs by some ... wrong initial values for MD5, and in the same day ...
    (Bugtraq)
  • Re: protect passwords in database
    ... All hash codes will have collisions. ... the md5 'weakness' was actually used in a defense against a traffic notice here in Australia recently. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Complex Theoretical One Way Hash Question
    ... 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, ... print quines and compute MD5s... ...
    (sci.crypt)