Splits and joins in PKI certificate hierarchies

I've always visualised PKI certificate hierarchies as strict trees. In this view, CA root certificates either directly authenticate end-user server and client certificates, or they authenticate multiple intermediate certificates, which may in their turn authenticate multiple further intermediate certificates, which eventually authenticate end-user certificates:

What hadn't occurred to me was that these hierarchies can also branch upward, with certificates being authenticated by more than one certificate above it:

But as it happens I've recently come across two real-live examples of this in commercial CA certificate hierarchies.

The first is in the one operated by Comodo implementing the JANET Certificate Service for UK HE sites. According to the documentation, the 'O=TERENA, CN=TERENA SSL CA' certificate chains to one ultimately authenticated by  'O=AddTrust AB, CN=AddTrust External CA Root'. But it can just as easily be verified by a commonly installed root 'O=The USERTRUST Network, CN=UTN-USERFirst-Hardware'. I've no idea why it's like this.

The second is in a hierarchy operated by Thawte. Here they are introducing a new 2048-bit root certificate, but as a precaution have also created an intermediate certificate that chains back to the old root:

This all has interesting implications for certificate verification since there are now multiple possible paths from an end user certificate to a potential root. From a little experimentation it appears that Firefox and Safari manage to find the shortest path to a configured root, but CryptoAPI (and so Internet Explorer and most of the rest of Windows) and OpenSSL take the certificate chain as provided by the server and then try verification from the end of that without ever trying to backtrack (but see note below).

This makes it impossible to take advantage of having both roots available since, taking the Thawte case, if you include the 'O=thawte, Inc., CN=thawte Primary Root CA' intermediate in the chain then your Windows/OpenSSL clients are bound to end up attempting verification against 'O=Thawte Consulting cc, CN=Thawte Premium Server CA' (and failing if they don't have it), and if you don't they will verify against the 'O=thawte, Inc., CN=thawte Primary Root CA' root (and failing if the don't have that).

The situation isn't helped by the fact that (if I'm reading it right) the relavent RFC describes verification from root to leaf even though in practice you'll always be doing it from leaf to root.

Note: subsequent further experimentation suggests that it's more complicated. Firefox does seem to be finding the shorter path in the Thawte case,  but finds the longer path in the Comodo case and fails validation if the 'O=AddTrust AB, CN=AddTrust External CA Root' is disabled. It's possible that the behaviour is influenced by other data in the various certificates.

Doing certificate verification in OpenSSL clients (properly)

Many SSL-capable applications, particularly those that started life on a Unix/Linux platform, use OpenSSL to implement the SSL protocol. Amongst other checks, SSL clients are expected to verify that certificates that they receive from servers have been correctly signed by a Certification Authority (CA) that the client has been configured to trust, but doing this correctly (or at all) with OpenSSL turns out to be harder than you might think.

For a start, OpenSSL can be instructed not to bother with verification. This can seem like an easy way to get rid of annoying error messages and to make  things work, but doing so makes clients vulnerable to server impersonation and man-in-the-middle attacks. Most clients do verification by default, but things like curl's  -k and --insecure command line options,  and Pine's /novalidate-cert option in mailbox and SMTP server definitions will suppress this. The first step towards doing certificate verification properly is to make sure you have verification turned on.

The next problem is that to verify a server certificate a client must have access to the root certificates of the CAs it chooses to trust. OpenSSL can access these in two ways: either from a single file containing a concatenation of root certificates, or from a directory containing the certificates in separate files. In the latter case, the directory must also contain a set of symlinks pointing to the certificate files, each named using a hash of the corresponding certificate's subject's Distinguished Name. OpenSSL comes with a program, c_rehash, that generates or regenerates these symlinks and it should be run whenever the set of certificates in a directory changes. All the certificates should be in PEM format (base64 encoded certificate data,   enclosed between "-----BEGIN CERTIFICATE-----" and "-----END CERTIFICATE-----" lines).

[Actually it's worse than this, because the client also needs access to any intermediate certificates that are needed to construct a chain linking the servers certificate to the corresponding root. It's the server's responsibility to provide these in intermediates along with its own certificate but sometimes they don't, making verification difficult or impossible. See below for how to detect this problem]

The OpenSSL library has compiled-in default locations for root certificates. You can find out what it is by first running the OpenSSL version utility:

openssl version -d

to find OpenSSL's configuration directory. The default certificate file is called certs.pem, and the default certificate directory is called certs, both within this configuration directory. However be careful: it's not unusual to have multiple copies of the OpenSSL library installed on a single system and different versions of the library may have different ideas of where the configuration directory is. You need to be running a copy of 'version' that's linked against the same copy of the OpenSSL library as the client you are trying to configure.

The base OpenSSL distribution no longer puts anything in these locations. Debian (and so Ubuntu), and OpenSUSE/SLES 11 have a seperate package that install an extensive collection of roots. SLES10's OpenSSL package installs a small and idiosyncratic set, and OpenSSL under Mac OSX installs none at all. Worse, while the library knows about these default locations, applications have to make a concious decision to use them, and some don't -  for example, wget seem to do so but ldapsearch doesn't.

OpenSSL applications generally have configuration options for selecting a certificate file and/or directory. Sometimes these are command line options (the OpenSSL utilities use -CAfile and -CApath; curl uses --cacert and --capath), sometimes they appear in configuration files (the OpenLDAP utilities look for TLS_CACERT and TLS_CACERTDIR in ldap.conf or ~/.ldaprc), and client libraries will have their own syntax (the Perl Net::LDAP module supports 'cafile' and 'capath' options in calls to both the Net::LDAPS->new() and $ldap->start_tls() methods).

However the locations are established, you'll need an appropriate collection of root certificates - at least containing one for each CA that issued the certificates on the the servers you want to talk to. It's often easiest if these are in the default locations, but you can put them anywhere as long as you tell you clients where to find them. You should of course be a little careful about this - by installing root certificates you are choosing to trust the corresponding CAs with at least part of your system's security. One approach is only to install roots as and when you need them to contact particular servers, but beware that this may lead to unexpected problems in the future if a server gets a new certificate from a new CA that you don't yet trust. In practice the easiest and probably best approach may be to use either a distribution-supplied collection of roots or to extract the root certificates from something like the Mozilla certificate bundle (see for example the make-ca-bundle utility distributed with curl). [Update 2011-02-01: see this new post for a better solution under MacOS]

So, putting this together, you need to do the following to use OpenSSL properly:

1. Make sure you have enabled, or at least haven't suppressed, certificate verification.
2. Get yourself an appropriate set of root certificates. If you add these to a certificate directory, remember to run c_rehash afterwards to recreate the hash symlinks.
3. If you install these certificates in one of OpenSSL's default locations and you application uses those locations then everything should work immediatly. Otherwise, add appropriate configuration to tell the application where to look.

You can test that OpenSSL itself is getting things right using the s_client utility. Run something like

openssl s_client -connect <host name>:<port> -CApath <certificate directory> 

Replacing <host name>, <port>, and <certificate directory> appropriately (<port> needs to be 443 for a HTTPS server, 636 for LDAPS, etc.). Or replace -CApath with -CAfile to select a file containing root certificates. This actually establishes a connection to the server - you can terminate it by typing ctrl-c or similar.

If you see "Verify return code: 0 (ok)" then everything worked and the server's certificate was successfully validated. If you see "Verify return code: 20 (unable to get local issuer certificate)" then OpenSSL was unable to verify the certificate, either because it doesn't have access to the necessary root certificate or because the server failed to include a necessary intermediate certificate. Yiou can check for the latter by adding the -showcerts option to the command line - this will display all the certificates provided by the server and you should expect to see everything necessary to link the server certificate up to but not including one of the roots you've installed. If you see "Verify return code: 19 (self signed certificate in certificate chain)" then either the servers is really trying to use a self-signed certificate (which a client is never going to be able to verify), or OpenSSL hasn't got access to the necessary root but the server is trying to provide it itself (which it shouldn't do becasue it's pointless - a client can never trust a server to supply the root coresponding to the server's own certificate). Again, adding -showcerts will help you diagnose which. Once you've got OpenSSL itself to work, move on to your actual client and hopefully it will work too.

Um, and that's about all, though there is one more wrinkle. Several applications that can use OpenSSL can also use GnuTLS and/or NSS instead. This can change many of the details above. In particular, GnuTLS only supports certificate files, not certificate directories but clients using it don't always report this. As a result you can waste (i.e. I have wasted) lots of time trying to work out why something like ldapsearch is continuing to reject server certificates despite being passed an entirely legitimate  directory of CA root certificates...