1
$\begingroup$

I know that collisions in md5 and sha1 have been demonstrated in particular pairs of files (by incrementing some none viewable portion of a PDF, etc).

Would generating the above string be meaningfully more computationally difficult than generating such a collision?

| improve this question | | | | |
$\endgroup$
2
$\begingroup$

Yes, it would be much more difficult to generate a string of the form The (MD5|SHA-1) hash of this string is (x) where x is (in hexadecimal or binary) the hash of that string, than it is to find collisions for MD5 or SHA-1. In fact, even though we can generate collisions for MD5 at low cost including for short messages (64-octet), I don't think that we could plug this one. Main issue is that the string x that we can change is much too small, and the rest too constrained.

However, we can easily construct a family of $2^{128}$ octet strings all with the same MD5 hash that are valid PDF documents and display any desired 128-bit value in hexadecimal, including one such document (that we can exhibit) displaying its own hash. That also works for Postscript, non-signed executables.. It would be feasible to do this for SHA-1, but that would cost about 128 times more work than what was used for one collision.

The trick is to start from a PDF document that displays a value depending on its content at 128 bits changing in 128 different local changes that each leave the hash invariant; each change involving altering 2 message blocks for SHA-1, or just 1 for MD5.

Update: That trick was pulled for a GIF image!

| improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.