Peter Selinger, a mathematician at Dalhousie University, hosts papers on category theory and the Quipper language, plus an MD5 collision demo.
Commenters cite his MD5 collision examples as proof the hash is broken, and recommend his graphical category theory paper as an introduction.
Hi moxie, might I ask if you've considered SHA-384 instead?
If I understand correctly, SHA-256 is part of the SHA-2 family of hash algorithms, and like SHA-1, when used alone it is subject to length extension attacks.
SHA-384 is also a member of the SHA-2 algorithm family, but is immune to length extension attacks because it runs with an internal state size of 512 bits -- by emitting fewer bits than its total internal state, length extensions are ruled out. (Wikipedia has a great table for clarifying all these confusing names and families of hashes: [5].) Other hashes like BLAKE-2 [1], though young, also promise built-in immunity to length-extension attacks. mdm [2] is immune to this because the relevant git datastructures all include either explicit field lengths as a prefix, or are sorted lists will null terminators, both of which diffuse length extension attacks by virtue of breaking their data format if extended.
Not that it's by any means easy to find a SHA-256 collision at present; but should collisions be found in the future, a length extension attack will increase the leverage for using those collisions to produce binaries that slip past this verification. An md5 Collision Demo[3] by Peter Selinger is my favourite site for concretely demonstrating what this looks like (though I think this[4] publication by CITS mentions the relationship to length extension more explicitly).
(I probably don't need to lecture to you of all people about length extensions :) but…
Birthday attacks can work against content-based addressing schemes too. Sure, they may be a little bit harder (you need to convince someone to merge something that is able to carry a large random payload), but given that, say, the Linux kernel has a bunch of binary blob firmwares, it wouldn't be too hard for a hardware manufacturer to submit a driver for new hardware with one firmware, and then replace it with another later on.
For a similar example, you may think that generating a CA signing certificate would involve a second preimage attack, as you would need to generate a certificate that had a hash that matched one of an existing CA. But it turns out that you only need a birthday attack, because you just need to submit a certificate for signing that is one of two that collide, where the second one is marked as being a CA cert. This has actually been done a with certificate authority that used MD5 for signing certificates.[1]
There are lots of file formats that allow you to fairly easily create MD5 collisions, by virtue of being able to stick a random string that won't be interpreted somewhere in them.[2] If it were feasible to produce such a collision using SHA-1, anyone who got such a file merged in Git could then substitute it for an evil file and no one would be the wiser.
That said, this attack does require the ability to generate a collision on SHA-1 (which has not yet been done), the ability to convince Linus (or a subsystem maintainer) to pull your tree…
Absolutely false. Some MD5 collision-generators specifically find pairs of equally-lengthed inputs with the same hash. See for example hit #2 for [MD5 collisions]:
http://www.mscs.dal.ca/~selinger/md5collision/
'Extension attacks' are something else, which let you turn one collision into more, or create valid hashes for combinations of unknown text plus a chosen extension – not find an initial collision. See:
http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction#Security_characteristics
The 'length extension' property can be helpful, once you find a collision based on 'random' nonsense, in extending that into two documents that are each meaningful-but-different and still colliding, as was done in this 2005 MD5 collision demonstration:
http://replay.waybackmachine.org/20050612011328/http://www.cits.rub.de/MD5Collisions/
Oh goodness no, there are lots of practical attacks that would work if people still trusted MD5.
For example, two self-extracting archives with the same MD5 that unpack to completely different contents: http://eprint.iacr.org/2004/356.pdf
Two postscript files with the same MD5 that print different letters: http://web.archive.org/web/20071226014140/http://www.cits.rub.de/MD5Collisions/
And plenty more as listed here by Peter Selinger: http://www.mscs.dal.ca/~selinger/md5collision/
That doesn't appear to be true. From http://www.mscs.dal.ca/~selinger/md5collision/:
It is now well-known that the crytographic hash function MD5 has been broken. [...] The following is an improvement of Diaz's example, which does not need a special extractor. Here are two pairs of executable programs (one pair runs on Windows, one pair on Linux) [...] Here, you can download the software that I used to create MD5-colliding executable files.
Technically yes, but don't use md5 for anything security-related ever. It's broken. http://www.mscs.dal.ca/~selinger/md5collision/ is just one example. (I also remember reading some years ago that md5s within md5s can make the resulting hash more vulnerable to certain attacks but I don't have any formal knowledge in cryptology to say for sure.) Use bcrypt/scrypt and you're automatically protected from both rainbow tables and brute force.