Hashing algorithms—mathematical functions that produce a short "fingerprint" from pieces of data—are one of the cornerstones of computer security. These fingerprints, named hashes, are used in password systems, in the public key infrastructure (PKI) that makes online shopping relatively safe, and in many file distribution systems. In each case, the hash is used because of an important property that hash algorithms all have: they are one-way functions.
Given a hash, there's no practical way of determining what the input was or of generating an input that hashes to the same value. For example, a system's password database will usually contain only hashes of users' passwords. Even if hackers manage to read the password database, they cannot log on to the system because there is no way to determine the password from the hashes in the database.
MD5
One widespread hash algorithm is Message-Digest algorithm 5, or MD5. MD5 was developed in the early 1990s and, due to its use in a variety of Internet specifications, is commonly used whenever a hash function is needed. As with any other algorithm with security implications, MD5 has been studied by security researchers ever since its release.
What the researchers are looking for is a way to generate collisions, that is, different files that have the same hash value. The best attack on a hash algorithm would allow an attacker to generate a file with a specific hash without any constraints on the content of the generated file.
Such an attack has not been found for MD5; however, this is not the only kind of attack that exists. In 2004, an attack was discovered/devised that allowed someone to create two files with the same MD5 hash. These files would have to be identical, except for one portion of 128 contiguous bytes. These bytes would be allowed to differ.
Although cryptography experts were troubled by this result, it did not lead to the wholesale abandonment of MD5. Many felt that the practical applications of such an attack would be so limited as to render the findings relatively unimportant; in other words, it was a theoretical curiosity but not a practical flaw of the algorithm.
This attack was then extended in 2007 to allow collisions to be generated with much greater freedom, in an attack called the "chosen prefix attack." The 2007 attack allows attackers to take two arbitrary files (the "chosen prefixes") and then generate suffixes for those files that will cause the total (each file with its respective suffix) to have the same MD5 hash.
If the original 128 byte attack did not cause wholesale rejection of MD5 then perhaps this one should have. However, its reception was similar to that of the 2004 work: interesting theory, but not a practical vulnerability. It allowed some neat tricks—such as fake predictions of the winner of the 2008 US Presidential Election—but didn't jeopardize any of the systems that depended on MD5 for their security.
Now, a paper presented at the 25th Chaos Communication Congress security conference in Berlin this week should finally put paid to the dismissal of the flaws as "theoretical."
PKI
One of the systems that can use use MD5 is PKI. PKI is the system that allows computers and people to prove their identity to computer systems. The most visible use of PKI is the certificates used by secure websites to prove that a secure connection to https://amazon.com/ is indeed connecting to Amazon's computers, and not those of some ne'er-do-well hacker. It does this by establishing a hierarchy of trust.
At the root, the most trusted level, are the Certificate Authorities (CAs), companies like Verisign and Thawte. The CAs are supposed to then issue certificates only to people and organizations that have proven their identities. When this has been done to the CA's satisfaction, the CA issues a certificate, a small file that says, for example, "this server is operated by Amazon, according to Verisign."
Each certificate references the certificate of the group that issued it, and some certificates ("Intermediate CA" certificates) can be used to create new certificates, allowing a multi-level hierarchy of trust to be established. The CA's certificates are issued by the CAs themselves, and these certificates are typically pre-loaded into web browsers and operating systems so that any certificates issued by them are automatically trusted.
The importance of these certificates to online commerce is immense. Without them, although securing connections against passive eavesdroppers is easy (just use encryption), there would be no way of ensuring that one was in fact communicating with the site one thought one was communicating with.
Encryption alone cannot prevent "man-in-the-middle" attacks; these are attacks where the malicious party actively intercepts and decrypts the traffic between client and server. The client believes it is creating a secure connection to the remote server, but in fact is making a connection only to the man in the middle, who in turn makes a secure connection to the server. The man in the middle can then eavesdrop at his leisure, passing traffic between client and server as he sees fit.
PKI prevents this attack. Although the man in the middle can intercept the traffic, he cannot recreate the proof of identity that the legitimate server has; this means that the client computer can reject the connection, safeguarding credit card details and passwords.
The certificates themselves are typically requested online. The person wanting a certificate creates a Certificate Signing Request, which contains information about their identity, the kind of certificate they would like, the domain name they are requesting a certificate for, and some cryptographic data, then sends this to the CA. The CA validates the identity information and then cryptographically signs the CSR, producing a certificate.
It's here that MD5 comes into play; cryptographic signing of an object is performed by first hashing that object, and then encrypting the hash. One of the hashing algorithms that can be used for the hashing step is MD5. It is this feature that was exploited by the security researchers.
From theory into practice
Essentially, the researchers required two chosen prefixes. The first prefix was that of a legitimate CSR for a domain that the researchers genuinely owned. The second prefix was a CSR for an Intermediate CA. This kind of CSR should not normally be signed by the root CA, because Intermediate CAs can be used to issue certificates to anyone, and those certificates would be trusted because they could be referenced back to a trusted root.
To each of these CSRs was appended a computed suffix ensuring that the MD5 hashes were identical. The legitimate CSR was then sent to the CA, which duly signed it and issued the certificate. The legitimate CSR in the issued certificate was then replaced with the Intermediate CA CSR.
This didn't violate the integrity of the certificate (because the CSRs hashed to the same value), which meant that the researchers had created a fully functional, trusted Intermediate CA certificate, capable of creating whatever certificates the researchers wanted. In so doing they showed once and for all that the theoretical attack had practical value; chosen prefixes are enough to undermine systems built using MD5.
They could take that Intermediate CA certificate and issue certificates for (say) amazon.com and use them to sit as a man in the middle. The traditional problem with being a man in the middle—that you cannot provide the proof of identity that the legitimate server can provide—disappears. The amazon.com certificate will be trusted by the client browser and hence will not raise any alarm bells.
The actual process of creating the bogus Intermediate CA certificate was a little more complex, as the root CA adds a small amount of extra information to the CSR before signing it. However, the researchers found a root CA that added highly predictable information to the CSR; this meant they had to generate a few hundred suffixes (to accommodate the few hundred possible pieces of information that the CA could add, and hence the few hundred chosen plaintexts), but this was not a significant difficulty; they used custom software running on a cluster of 200 PS3s in a day or two.
So, using MD5 in certificates is well and truly broken, and theoretical flaws can have practical repercussions. Although most CAs no longer use MD5 in their certificates (preferring stronger hash algorithms such as SHA-1), the researchers found that many certificates in-use do use MD5; just under a third of the certificates they looked at used MD5 signatures. The vast majority of these were created by one CA, RapidSSL, which happens to be the same CA that the researchers used to generate their bogus certificate.
The CAs that the researchers spoke to indicated that they would soon cease using MD5 for their certificates, thereby closing this particular vulnerability. CAs should also ensure that the extra information they add to the CSR is not readily predictable, which would both provide some protection against this attack and might also prevent future, as-yet-unknown attacks.
For their part, the researchers are not detailing certain improvements they made to the suffix generation process until they believe it will be safe to do.
While recommendations for the CAs are clear, what this means for the general public is harder to say. The major browser vendors have been informed of the issue; thus far none has committed to any particular course of action. The most heavy-handed route would be to remove the root CA for the vendors that have been issuing MD5 certificates. This would neuter any bogus certificates from these CAs, but would also break any legitimate certificates.
It's impossible to know if such an attack has been perpetrated for real, and if it hasn't, this would be a hugely disruptive change for no real gain. Even if browser vendors do not remove the CA certificates in question, end-users can stop trusting the root CA certificates if they choose and if they are willing to tolerate the inconvenience this will cause.
The Extended Validation certificates that cause green or gold address bars in many browsers are also immune to this problem, as EV certificates prohibit the use of MD5. Simply looking for a padlock icon is no longer enough to be sure that communication with the remote server is truly secure.
Looking to the future, one lesson that will hopefully be learned is that the security industry should not be so cavalier with "theoretical" attacks. More traditional computer security flaws such as buffer overflows are already generally treated as exploitable unless proven otherwise, and patched accordingly; in light of this pessimistic viewpoint, the dismissal of cryptography findings as merely theoretical is perhaps a little surprising.
That is not to say that there are not such findings; many cryptographic attacks serve only to reduce the time taken to break encryption from trillions to hundreds of billions of years and so are not especially significant, but out-of-hand dismissal without proper evaluation is clearly a dangerous course of action.
.jpg)
