Loops in PKI certificate hierarchies and Firefox bugs

In a previous posting, I mentioned being surprised to discover that PKI certificate hierarchies were more complicated than the strict trees that I had always assumed them to be. At the time I rather assumed that they must be directed acyclic graphs.

I've subsequently realised that there is nothing to prevent them from being cyclic graphs and have actually found a loop in an existing commercial hierarchy. Unfortunately it looks as if I wasn't the only person making false assumptions since it seems that certificate loops trigger an old-but-not-yet fixed bug in Firefox that prevents certificate chain verification.

Certificates contain within them the 'Distinguished Name' (DN) of a further certificate that contains the public half of the key used to sign the first certificate. Certificate are only identified by name, and there is nothing to stop multiple certificates sharing the same name (though all the certificates with the same name had better contain the same key or new and exciting bad things will probably happen). All this is what I worked out last time.

What I've discovered that's new is illustrated in the following diagram:

This represents part of the hierarchy under which certificates are issued to UK HE institutions by JANET (and I think by similar organisations in other countries) under a contract with Comodo. In this diagram:

1. The blocks with grey backgrounds represent key pairs. The numbers at the top of the box are the first half of the key's 'Key Identifier'.
2. The smaller blocks represent certificates containing the corresponding public keys.
3. The arrows link certificates to the keys that signed them (and so which can validate them).
4. Certificates with red backgrounds represent self-signed certificates that are trusted roots (at least on my copy of Firefox). The certificate with blue background represent an example server certificate.
5. The number in each certificate is the first half of the certificate's SHA-1 hash.
6. Certificates with a  green border represent the recommended verification chain for JANET-issued certificates.

Copies of the certificates involved (and others) can be found here.

The problem here are the two certificates "31:93:..." and "9E:99:...", since each represents a potential verification route for the other. Neither are part of the 'official' verification chain for JANET-issued certificates. "9E:99:..." is distributed by Comodo in support of other of their certificate products. I don't know where "31:93:..." comes from, but I assume it appears in someone else's 'official' certificate chain. Both these 'intermediate' certificates will presumably be included in certificate bundles by particular web servers and, once serverd, tend to be cached by web browsers.

The problem is that, once a web browser has a copy of both of these there's a danger of it going into a spin since each is an apparently acceptable
parent for the other.  It turns out that Firefox has exactly this problem, as described in bug 479508. Unfortunately this bug last saw any action in March 2008 so it's not clear when, if ever, it's going to be fixed. There are some other reports of what I suspect is the same problem here and here.

So who's problem is it? Clearly Firefox could and should be more careful in how it constructs certificate chains. It's possible that other SSL software is vulnerable to similar problems, though I've only seen this manifest in Firefox (and only then occasionally). But I also wonder what the Certification Authorities thought they were doing when they issued these certificates. As far as I can see they were both issued as 'cross-certification' certificates, intended to allow server certificates issued under one root certificate to be validated by reference to another. Issuing one of these isn't a problem. Issuing a pair clearly is.

A work around, should this problem bite you, should be to delete "31:93:..." and "9E:99:..." from Firefox's certificate store. Neither are roots, and any server that needs them to get its certificate verified should be providing them, so deleting them should be entirely safe. The work-around should last until you next pick up copies of both of these, at which point you'll need to delete them again.