[zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful documents]

----- Forwarded message from zooko@zooko.com -----

There is nothing theoretically surprising about this, but hopefully its concreteness and the accompanying scenario will make an impression on people on people. The same technique should work to generate two documents with identical SHA1 hashes.

http://www.cits.rub.de/MD5Collisions/

----- End forwarded message -----

I expected the two postscript files differing in some huge binary blob, but it turns out the binary part is very small (about 256 bytes) and only few (about nine) bytes are different, contrary to how people have predicted the collisions. This is much more close to finding a collision between similar pure C files, I think. Rather unsettling.

I looked at this.

If you can find just *one* colliding pair that does not contain a few select bytes like 0x22 (quote), 0x5c (backslash) and perhaps 0x0a then it is trivial to make a colliding pair of C programs.

Call the initial pair (A,B) and make the programs

/* Common prefix that happens to have integer block size
   ending just before the A below. */
const char junk[] = "AB";
/* "AA" in program 1, "AB" in program 2.  */
...
int
main ()
{
  int hsize = sizeof (junk) / 2;
  if (memcmp (junk, junk + hsize, hsize))
    return do_program_2 ();
  else
    return do_program_1 ();
}

On Sun, Jun 12, 2005 at 10:25:55AM +0200, Petr Baudis wrote:

This attack scenario doesn't demonstrate the danger of hash collisions but the danger of signing documents you do not understand. The same technique works exactly in the same way with postscript files which are actually identical but produce different output under different conditions (time, fonts installed on the printer whatever).

Never sign anything but plain text or documents which are created in a controlled way and avoid signing documents you did not create yourself.

Martin

On Sun, 12 Jun 2005, Petr Baudis wrote:

This is not close at all. The "small" binary blob (256 bytes) only encodes one single bit of information.

In other words, they've really changed _one_ bit of information by doing a 256-byte random binary blob. Anybody who calls that "small" didn't really look closely.

Is it clever? Yes. But it isn't about making one C file look like another, it's using the property of controlling _both_ of the files, and making them contain all the information, and then making the the single-bit change collapse the output into two different modes by using a postscript interpreter to make it print out the same.

Is it a real problem? Yes, because a _lot_ of document formats are structured and are amenable to things like this. But the problem here is the fact that you can fool somebody into signing something without realizing that it has a lot of hidden information thanks to having formats that can hide the blobs.

So the problem is totally different from the way git uses a hash. In the git model, an attacker by definition cannot control both versions of a file, since if he controls just _one_ version, he doesn't need to do the attack in the first place!

Put another way: you could use this exact example for a version of git that uses md5-sums instead of sha1's, but it wouldn't show anything at all about a git vulnerability even so.

The one thing it does show is that you should probably never sign anything but a nice human-readable ASCII file that you actually opened in your own editor.

		Linus

On Sun, 12 Jun 2005, Linus Torvalds wrote:

You couldn't use this exact example for an md5 git; git compresses the files before hashing, which means that you don't have an md5 block of arbitrary data you can replace with a different arbitrary block because it wouldn't decompress.

Of course, if zlib has a way of saying, "if bytes 256-511 match 512-767, decompress the first of the two records starting at 768, otherwise decompress the second" then the attack would work, and we should all by worried (and disturbed by zlib in general). Chances are that it would be impractical to find a pair of blocks such that they are both valid in the same part of a zlib record and both leave the compression context such that the same remaining content decompresses successfully and both have the same md5 hash, let alone getting the results in both cases to be valid C that depends on the difference between the blocks. It's possible that you could get it to work with only a moderately large number of weak collisions between very similar blocks, but it's not nearly so easy a task.

	-Daniel
*This .sig left intentionally blank*