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

On Sun, 12 Jun 2005, Petr Baudis wrote:

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