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

From: Linus Torvalds <torvalds@osdl.org>
Date: Jun 12, 2005, 17:03 UTC
Message-ID: <Pine.LNX.4.58.0506120949150.2286@ppc970.osdl.org>
In-Reply-To: <20050612082555.GB6620@pasky.ji.cz>

On Sun, 12 Jun 2005, Petr Baudis wrote:

Show 6 quoted lines

>
> 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.

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