Yesterday, I posted a long entry on the recent news about how some researchers obtained a “rogue” certificate from one of the Internet Certificate Authorities. There are some points I missed in the original post that should be noted.

 
• The authors of the exploit have a very readable, interesting description of what they did and why it worked. I should have included a link to it in the original posting, but forgot to edit it in. The interested reader should definitely see that article online, include the animations.
 
• There are other ways this attack can be defeated, certainly, but they are stop-gap measures. I didn’t explain them because I don’t view them as other than quick patches. However, if you are forced to continue to use MD5 and you issue certificates, then it is important to randomize the certificate serial number that is issued, and to insert a random delay interval in the validity time field. Both will introduce enough random bits so as to make this particular attack against the CA infeasible given current technology.
 
• I suggested that vendors use another hash algorithm, and have SHA-1 as an example. SHA-2 would be better, as SHA-1 has been shown to have a theoretical weakness similar to MD5, although it has proven more resistant to attack to date. Use of SHA-1 could possible result in a similar problem within a few years (or, as suggested in the final part of my post, within a few weeks if a breakthrough occurs). However, use of SHA-1 would be preferable to MD5!
 
• MD5 is not “broken” in a complete way. There are several properties of a message digest that are valuable, including collision resistance: that it is infeasible to end up with two inputs giving the same hash value. To the best of my knowledge, MD5 has only been shown to be susceptible to “weak collisions”—instances where the attacker can pick one or both inputs so as to produce identical hash values. The stronger form of preimage resistance, where there is an arbitrary hash output H and an attacker cannot form an input that also produces H, still holds for MD5. Thus, applications that depend on this property (including many signing applications and integrity tools) are apparently still okay.
 
• One of our recent PhD grads, William Speirs, worked on defining hash functions for his PhD dissertation. His dissertation, Dynamic Cryptographic Hash Functions, is available online for those interested in seeing it.

I want to reiterate that there are more fundamental issues of trust involved than what hash function is used. The whole nature of certificates is based around how much we trust the certificate authorities that issue the certificates, and the correctness of the software that verifies those certificates then shows us the results. If an authority is careless or rogue, then the certificates may be technically valid but not match our expectations for validity. If our local software (such as a WWW browser) incorrectly validates a certificate, or presents the results incorrectly, we may trust a certificate we shouldn’t. Even such mundane issues as having one’s system at the correct time/date can be important: the authors of this particular hack demonstrated that by backdating their rogue certificate.

My continuing message to the community is to not lose sight of those things we assume. Sometimes, changes in the world around us render those assumptions invalid, and everything built on them becomes open to question. If we forget those assumptions—and our chains of trust built on them—we will continue to be surprised by the outcomes.

That is perhaps fitting to state (again) on the last day of the year. Let me observe that as human beings we sometimes take things for granted in our lives. Spend a few moments today (and frequently, thereafter) to pause and think about the things in your life that you may be taking for granted: family, friends, love, health, and the wonder of the world around you. Then as is your wont, celebrate what you have.

Best wishes for a happy, prosperous, safe—and secure—2009.

[12/31/08 Addition]: Steve Bellovin has noted that transition to the SHA-2 hash algorithm in certificates (and other uses) would not be simple or quick. He has written a paper describing the difficulties and that paper is online.