MD5, clueless certificate authorities and PKI trust crisis

One of the more interesting attacks of 2008 came on the second-to-last day of  the year, when a group of researchers announced they had successfully forged a bogus CA certificate. Depending on perspective, it is either a novel demonstration or an obvious next step on MD5 collisions. Since the original announcement in 2004 of the MD5 collisions, there has been steady progress on crafting meaningful messages with identical hashes. 

  • Random collisions for messages with no structure.
  • Collisions with shared prefix, which is enough to come up with 2 different X509 certificates featuring different keys and identical hash.
  • This attack was later extended to allow chosen, different prefixes on each message, as described in a Eurocrypt paper.

These birthday collisions are dangerous to the extent that an attacker can get the target to sign a message of their choice– the hope being that while the victim thinks they are signing innocuous message #1, they are also signing message #2 with same hash but worse implications. In general few applications afford that opportunity, because acting as a signing-oracle is the cryptographic equivalent to a bureaucrat rubber-stamping everything presented on his/her desk.

That brings us to the other problem: using MD5 was not the only screw up from the handful of CAs implicated in the vulnerability. The certificate contents signed were entirely predictable or controlled by the adversary. In particular, the serial ID which could have been easily made into a unique, deterministic and completely unpredictable value (by using the encryption of an incrementing counter) was implemented as a simple counter, bumped up by one each time a new certificate was issued. Since the target CAs received particularly low-levels of customer traffic, the rate of counter increase could be estimated– although it took several attempts to get it exactly correct.

In well designed systems, it rarely takes a single failure to cause a catastrophic breakdown in security. Aside from clueless CAs using MD5 and signing whatever came their way, credit for the epic failure in PKI also goes to SSL client implementations which place equal value in all certificate authorities. A certificate is valid as long as it chains up to any trusted certificate authority– and there are about 100 of them in the Windows XP root store alone. Verisign USA, which issues the majority of SSL certificates including EV certs receives the exact same treatment as RapidSSL and FreeSSL– the latter two being examples of mismanaged CAs implicated in the attack. (Strangely enough, Verisign Japan and one CA affiliated with Thawte, another large issuer, were likewise flagged as issuing MD5 certificates.) Windows will cache previously validated certificates, to save time on future path validation efforts. But there is no logic to notice discrepancies and ask why Bank of America, which used to have a valid, unexpired GTE certificate has suddenly switched over to using an obscure CA based in Esthonia.

From a business perspective, it is not fair to blame MSFT for the proliferation of inept CAs. The company is backed into a corner: who are they to reject RapidSSL or any of the other dozens of dubious garage companies that will issue any certificate to anyone? Not when CA business model is getting paid for those certificates. If standards were raised to exclude some, the companies will cry tort interference. (Remarkably the Vista root store appears to have been cleaned up a bit.)  There are minimum standards around certificate practices, but historically the  whole concept of certifying the certifiers has been window dressing. Verisign issues 2 bogus Microsoft certificates in 2002. It was partly in recognition of this fact that “extended validation” certificates were introduced, creating a lucrative business opportunity to issue far more expensive certificates with supposedly real due diligence this time. This time, not all CAs were invited to that party.

As an aside, EV would have made no difference here contrary to the MSRC wishful thinking on mitigating factors. It is purely a visual indicator: cookies and cross-domain access are still allowed to EV-protected content from a vanilla SSL protected page in the same origin, allowing man-in-the-middle attacks to succeed. For example the attacker could allow the normal login page to be displayed to collect credentials, complete with the green address bar to inspire warm, fuzzy feelings with users. (Actually usability research says that users do not pay any attention to the EV indicator, but let’s suspend disbelief for a moment.) Only when the user enters a password and submits their credentials to the website, that connection is intercepted by the attacker who substitutes a bogus, non-EV certificate which still passes the hostname check with flying colors.


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s