Microsoft Security Advisory – MD5 collisions

I would hardly be able to call my blog “Tales from the Crypto” if I didn’t pass at least some comment on the recent Microsoft Security Advisory, and the technical pre-paper on which it is based.

To an uninformed reader, the advisory (and especially the paper) doesn’t make a whole lot of sense, as with most cryptography documents. If there’s an attack on a cryptographic technology, doesn’t that mean it’s broken and we should stop using it?

Not really, no. We should stop using, or shore up, those components that have an increased vulnerability.

First, let’s remember that cryptography is necessarily full of mathematical theory and that it is very much a developing field. If I say something along the lines of “magic happens here”, please accept that at face value. It means that there is something hugely full of mathematical complexity that I don’t understand, but which has been assessed by mathematicians who know more than I do about the subject.

How do certificates work?

So, a little background, and an explanation of the attack, before we get to the mitigations.

Every time you use HTTPS (HTTP over SSL / TLS), there’s an identifying exchange – at the very least, the server identifies itself to you, and possibly you identify yourself to the server. In SSL, this is almost always done using certificates – strictly speaking, X.509 certificates.

A certificate is a list of statements about the identity of the party it represents, followed by a mathematically-derived encrypted value called a “signature”. The signature is based on a hash function, which is chosen to be resistant to attack. Typical hash functions are MD5, SHA1, and the “SHA-2” family which are identified by the number of bits of output they produce (i.e. how well they uniquely represent the original information to be hashed). The signature is the hash of the identity statements, encrypted using the issuer’s private key. This means that anyone can decrypt the hash, but in doing so, they will recognise both that only the issuer can have created the signature, and that the identity claims made in the certificate are accepted as valid by the issuer.

This allows you to trust the owner of the certificate, on the basis that you trust the issuer. Sometimes you don’t know if you can trust the issuer, either, and so you have to find out if you can trust the issuer – by looking at their certificate, seeing what claims it made, and what other issuer signed it, and so on, up a “chain of trust”, until you either meet a certificate you do trust, or you meet a certificate that is “self-signed” – that is, that it claims to be its own issuer, and has no other signatory.

So, from this description, you should be able to envisage a chain of trust, where the “leaf certificate” of the site whose identity you want to verify, is signed by an intermediate certificate authority (CA), which may in turn be signed by an intermediate CA, and so on, until you meet a certificate that is signed by a “root CA” – a self-signed certificate whose trust you can use as a basis for trusting the leaf certificate.

Many root CAs are installed by default in operating systems, or applications that use SSL, with the intent that you should be able to trust all certificates issued by those CAs, because they take adequate steps to verify the certificates they issue, and because they use modern technology.

Where’s the attack?

There’s nothing surprising about this attack to those of us who follow cryptography news. One of the problems with hashes is that it is possible to generate two paired documents, that have different content, but whose hash is the same. It has been known since 2004 that you can generate such colliding documents using MD5 as a hash without quite as much effort as the “brute force” technique of trying to generate documents and see if they match. From that, we have (or should have) predicted that this attack was possible, though not easy.

The attack is this – the attacker requests a bona fide web-site, or email (or any other) certificate from a reputable certificate authority. The certificate request is generated along with a second ‘shadow’ certificate – the two differ in areas chosen by the attacker, and with sufficient care to make sure that the issued certificates will both match the same signature.

This gives two certificates, which each appear to have been issued by the certificate authority, but only one of which actually contains information that was seen by the certificate authority.

The method of attack beyond this point will depend on what the shadow certificate was. The simplest way to attack this would be to have both certificates be web site certificates (or both be email certificates, etc), so that you could ask the CA for a certificate for your own name, but wind up with a certificate for someone else’s name – a big company or an important individual, say. That’s useful, but it only gives you one usable certificate per request. Keep that up, and you are sure to be detected.

The method outlined in the research paper, however, goes a step further than that – the certificate request that the CA sees is, as before, a simple web site certificate request. But the shadow certificate is designed to be that of an intermediate CA itself. Once this attack is successful, you can use the intermediate CA to issue any number of web site, email, code-signing, and even other CA certificates. Because these certificates chain up through your bogus intermediate CA, and then to a trusted root, they too will be trusted.

What about defence?

There are several defences to consider, and I’ll address them from the perspective of various different parties.

1. The Certificate Authority

First of all, all certificate authorities need to move to stop using MD5 when signing other people’s certificates. They should have stopped doing this some time ago, as it was clear that the generation of colliding certificate requests was an ever-increasing possibility. Also on the way out should be SHA1 (although that does mean older systems and software may have issues, because they may not be able to support newer SHA-based hash and signature algorithms). Note that this (particularly the dropping of SHA1) is a recommendation that should be followed with glacial slowness, over years, rather than days. We’re not that broken yet.

Even if the CA continues to use MD5 and SHA1, they can adequately protect against this attack by using non-predictable serial numbers when generating the certificate signatures. This is essentially the area where the CA can most easily and most effectively prevent this attack from succeeding, relying as it does on being able to predict precisely the contents of the returned certificate. This will continue to work so long as the attackers can only generate two colliding paired documents – if there is ever a sustainable attack that allows creating a document that matches the hash of another document without generating them together, this too will be a cause to doubt those certificates.

Another defence against this (but not the simpler form of the attack) is to ensure that you use different CAs to issue leaf certificates than you use to issue intermediate CA certificates, and that you set limits on how long the chain may be as signed by your CAs. That way, a leaf certificate request cannot be used to create a shadow intermediate CA certificate, because verification of the chain will fail because of length constraints.

Check your certificate requests, and make sure that you have not seen a large number of certificate requests from substantially the same source, in an attempt to generate a desired serial number. Offer your existing customers, if they are worried about MD5-signed certificates, the option to replace their certificates with certificates signed by other hash schemes.

2. The Web-Site Owner

There’s really not anything the web-site owner can do, beyond checking any reports of hijacked sessions, or web sites not appearing to be correctly identified, and then taking legal action to remove such pretender sites when they are found.

One thing that can be done is to champion the use of Enhanced Validation (EV) SSL Certificates, as specified by the Browser Forum. These certificates are required to use a chain that has no MD5 signatures in anything other than the root CA. Push the message to your customers and users that the green bar indicates a higher level of trustworthiness. You’ve not only identified yourself to the CA’s satisfaction, but your CA and you are committed to a more up-to-date technical configuration.

Ask your CA if you need to take action with your existing certificates – if they are signed by using MD5 hashes, it may be that some customers will refuse to accept your certificates. Your CA may have a reasonable offer on replacing your certificates with ones signed by SHA1 or other hashes.

3. The Web-Site Visitor

These are the guys that really matter – because if they can be fooled, then the attack has succeeded.

The first thing that has to be drummed into web-site users’ heads is that a certificate error message should be reason for you to stop your visit to the web site with the error, and to not place any orders with them, or supply it with your private information (password, personal details, etc) until you have resolved with their technical support what the issue is. This step alone is something that I have emphasised before, and I emphasise it again now, not because it is the best fix for this issue (because a clever attacker will try to produce a certificate that doesn’t error), but because it’s something that protects against the far easier attacks, and it is still not a habit that users have gotten into.

Next, keep up-to-date with patches. If there are interesting ways to block this at the browser, those will be distributed through security patches to your browser or other applications. If you use a lot of OpenSSL-based applications, keep looking for updates to those; if you use a lot of CryptoAPI-based apps, updates should come to you automatically through Windows Update.

Read Microsoft’s Security Advisory, as well as entries on the Microsoft Security Response Center Blog and the Microsoft Security Vulnerability Research & Defense Blog.

4. The software developer

Consider, if you already verify certificate chains yourself, adding or documenting features to refuse chains that flow through CA certificates signed with MD5; also to refuse chains that flow through CA certificates with too much ‘cruft’ (this attack uses the “Netscape Comment” field and fills it with binary that doesn’t look very comment-like).

Make sure that your verification routines check for chain length constraints, as well as corrupt or absent revocation list locations. Again, this attack had no space to put a valid CRL location in place.

If you develop IDS solutions, you may want to try and check for an SSL negotiation that includes certificates signed by intermediate CAs that are themselves signed by using the MD5 hash algorithm – although this is a little complex to track, it shouldn’t be completely impossible.

And, in summary (phew – at last!)

This is a proof of concept of a theoretical attack, and has generated some interest because it’s a shoe we’ve been waiting to see drop. Repeating the work with the information supplied by Sotirov et al would require a lot of significant and serious mathematics. I know that’s not something to make it impossible, but I think it’s enough to suggest that the sort of people with enough resources to hire advanced mathematicians would find it cheaper and easier to just use something more like social engineering to achieve the effect of having visitors trust your web site.

In several months, the tools will become more widely available, but by then, CAs should be smart enough to stop using MD5, and be considering a move to SHA256 and above. And if they aren’t, I’m sure there will be further advisories with instructions on which root CAs to remove from your trusts.

This is a thoroughly interesting attack, and exciting to people like me. That shouldn’t be taken as an indication that the world is about to collapse, or that you can’t go on trusting HTTPS the way you currently do. Even though we now have the ‘perfect storm’ of a serious DNS flaw backed with a way to subvert SSL, it doesn’t appear to be in use at the present, and with the information on how this attack was achieved, it’s possible for a root CA to comb back through their records and find suspicious behaviours that match this attack.

Link: Verisign’s statement (they own RapidSSL, the CA that was the subject of this attack).