Today’s news concerning web security made me think about a 1964 school desegregation decision from the Supreme Court of the United States; the title of this blog post is taken from Justice Black’s opinion. But before I can explain the connection, I need to provide some security background.
When you visit a “secure” web site and see the reassuring padlock icon, a lot of math is going on behind the scenes to confirm that you’ve got the real site and not an impostor. One important ingredient is a particular kind of function: a “message digest” or “cryptographic hash” function. Although these functions are many-to-one, they are designed to require a lot of effort to find two elements of the domain that map to the same element of the range. (The elements of the range are called “hash codes”; when two elements of the domain share a hash code, they constitute a “collision.”)
The practical significance of this property is that it is very difficult to get away with copying a digital signature from one document and pasting it onto another. The cryptographic hash is used to tie the signature to the specific document that was signed; only another document with the same hash code could legitimately cary the same signature. One reason this matters is because digitally signed documents, known as certificates, persuade your web browser of the authenticity of the sites you visit.
Unfortunately, a string of mathematical papers starting in 2004 showed some clever techniques that make finding collisions much easier for the oldest message digest function in general use, MD5. Although this was still fundamental mathematical research, and had not yet ripened into practical attack techniques, security experts immediately began recommending a move away from MD5. I played a very small role in disseminating those experts’ warnings; in January of 2006, I published a textbook in which I wrote that new systems should not use MD5 and “existing systems using MD5 … should be converted to … successor functions with deliberate speed.”
Not everyone took these warnings seriously; in particular, there are companies who continued to use MD5 to sign the certificates for web sites. Apparently these companies needed a stronger wake-up call. So today, a group of security researchers announced that they had demonstrated a practical method of using MD5 collisions to allow them to forge certificates that any of the standard web browsers would accept. Moreover, these forged certificates could be used for any web site at all, even one whose real certificate was not signed using MD5.
The Washinton Post reports that Verisign’s VP of Marketing, Tim Callan, “said Verisign has been phasing out MD5 in favor of more secure signing algorithms amongst its CA properties for the past couple of years, and expects to finish the process in January 2009.”
Which brings me at last to Justice Hugo Black. Writing in 1964, he noted that in 1955, the Court had ordered the desegregation of schools to take place “with all deliberate speed,” but that “there has been entirely too much deliberation and not enough speed.” His bottom-line message to state and local governments was that “the time for mere ‘deliberate speed’ has run out.” I can’t help but think that is the same message Tim Callan should have heard loudly and clearly today.
[Update the next day (2008-12-31): Verisign did hear loudly and reasonably clearly. Their press release today says
VeriSign has been phasing out the MD5 hashing algorithm for years. Until the MD5 exploit was made public, VeriSign had planned to discontinue the use of MD5 in customers’ certificates by the end of January, 2009. VeriSign has since discontinued using MD5 when issuing RapidSSL Certificates and has confirmed that all other SSL Certificates that VeriSign issues are not vulnerable to this MD5 attack. VeriSign will continue on its path to discontinue MD5 in all end entity certificates by the end of January, 2009.
This needs to be parsed carefully. They immediately eliminated the use of MD5 by the one brand that was specifically shown to be vulnerable. But, they still plan to continue using MD5 in some of their other brands for up to another month because they “are not vulnerable to this MD5 attack” (emphasis mine). Presumably this is because they have less easily predictable serial numbers. I wouldn’t take that as comfort enough to delay long, but a few weeks is probably reasonable.]