Schneier on Security

James Landis • June 10, 2005 4:29 PM

I’m not particularly impressed with this attack. To those that are saying that hash algorithms are killed by finding collisions (yes, this includes SHA-1), you have to put this finding into the correct context. All that the researchers are demonstrating here is that it is possible to create two functionally different yet valid files with the same signature in a very short amount of time.

This and the other referenced attacks all take advantage of the length extension property of hash functions after finding two pieces of data with colliding hash values. Effectively, all they demonstrate is the possibility of wrapping identical content around these two separate sets of colliding bits.

While this is important, this is not nearly the same thing as demonstrating that it is possible to create two ARBITRARY documents with the same hash value or that it is possible to generate a NEW document with the same hash value as an EXISTING document.

In plain English, this is what the finding means: if we have control over both the original and the forgery AND the documents can appear or function quite differently with very minor changes, then MD5 (or any algorithm that has computable collisions) is broken. This means that we must be careful about what we sign ourselves and how we trust the signatures of others. However, if someone we trust has signed something and we know that they did not sign anything that has this sort of “dual functionality”, then we can still trust that someone else has not created something malicious with the same signature and tried to pawn it off on us. Matthew Dempsky sums it up nicely: MD5 is still fine for its use as an authenticator in most scenarios.

Otto, your comment is incorrect. The original AC was correct. The two documents DO have to contain the exact same data except for the precomputed bits that have colliding MD5 sums, and those bits must both be inserted in the exact same place in the two documents.

Many have asked why we don’t simply combine two different hash functions. This attack still works if we can find colliding values that collide in both functions. You could essentially think of the two combined algorithms as one algorithm with different collision properties.

James Landis • June 11, 2005 9:25 AM

@Benny

This attack demonstrated that two arbitrary STRINGS with the same hash can be generated, but not two arbitrary DOCUMENTS. If you look at the actual strings that they created to have the same hash, it should be clear that they are not particularly useful on their own as documents in any standard format.

Have a closer look at slide 5. The authors concatenated the random strings R1 and R2 to the SAME preamble, not different strings A and B as you suggest. Again, this works because of the length extension property.

MD5 is not the same thing as a signature. This is an important distinction. MD5 is used in digital signature algorithms because it is much faster to compute the signature based on an MD5 hash than on the entire contents of a document.

I don’t understand your assertions about how “we” use digital certs in “most situations.” You said “we use a signing algorithm precisely because we don’t fully trust the document author’s good intentions or the signer’s ability to avoid evil documents.” How does a signature protect us from an author’s evil intentions? If the author can’t avoid evil documents, how does it help us if he signs them anyway? My assertion is that MD5 hashes are still useful in signature algorithms when we trust the original signatory and are verifying OTHER documents agains the signed hash of the original, or we are signing something we have vetted ourselves in order to authenticate the document.

Any technology can fail if it is used incorrectly. This is in fact the only point that the authors of the PostScript example are trying to make. It has already been shown that it is trivial to find hash collisions in MD5 by other researchers – they are simply trying to drive the point home that we have to be careful about the hashes that we sign ourselves and how we choose to trust the hashes signed by others.

James Landis • June 14, 2005 1:39 PM

@Roger

To address your point a), the knowledge about the expected form of attack helps us resist the attack because once we know what to look for it becomes vastly more difficult to construct a pair of documents that hold up to even casual inspection. It seems that you undermine your own point by agreeing that once we’re at the point of obfuscating PostScript or hand-coding in assembly “the signature has become worthless.” In what scenario would we ever agree to sign the hash of a file to authenticate it if the contents are not transparent?

As for b), the only gain I could see from concatenating multiple collisions is to have more ‘switches’ that can trigger additional behavior. For the layman, where the attack described in the article was “Preamble + (R1 or R2) + Content”, Roger’s proposed attack resembles “Preamble + (R1 or R2) + Content + (R3 or R4) + .. + Content”, where MD5(R3) = MD5(R4). More simply put, it is a series of identical strings concatenated with multiple sets of bits with known hash collisions. Again, this hardly approaches the same category of vulnerability as a method for taking two distinct documents and tweaking them until the hashes match.

Your arguments center on the premise that it is possible to make arbitrarily complex documents with the same hash using this technique. For MD5 to be seriously broken it must be demonstrated that it is possible to create extremely SIMPLE documents with the same hash, simple enough to pass as ordinary and innocuous.