3.6. Certificates

One problem with using public key cryptography that we've ignored so far is how to distribute the public keys. When Alice wants to send a message to Bob, she must first find Bob's public key. Likewise, if Alice signs the message and Bob wants to verify it, he must find Alice's public key. This problem was recognized from the beginning of public key cryptography and was usually glossed over by saying that Alice and Bob would put their public keys, along with their names and perhaps some other identifying information, in a "public database" available to anyone who needed to locate another person's public key [Diffie and Hellman 1976, Rivest, Shamir, and Adleman 1978].

Certificates are often used as a solution to the problem. Most of us are familiar with certificates from their use in secure Web browsing (we discuss this in detail in Chapter 6). The basic idea is that the certificate binds an identitya person's name, sayto their public key. The certificate is signed, as described in the previous section, by a trusted organization called a certificate authority (CA). This still leaves open the method of distributing the certificates, but notice that we have gained something: If Bob sends Alice his certificate so that she can communicate with him, Alice is better off than if Bob had merely sent his public key, because the certificate is signed and Alice can be sure, to the extent that she trusts the CA, that it is, in fact, Bob's certificate and not that of someone who is impersonating Bob.

A system such as this, where a CA signs certificates that bind users' identities to public keys, is called a public key infrastructure (PKI). The ideal PKI is a universal one in which a central authoritythe government or even a worldwide organization, such as the UN, sayissues a certificate for anyone who needs one. The problem with this, aside from the obvious administrative problems, which are probably intractable on their own, is trust. We noted above that when Bob sends Alice his certificate, Alice can be sure of Bob's identity only to the extent that she trusts the CA. As noted in [Ferguson and Schneier 2003], no organization is trusted by most people, let alone everyone, so the ideal of the universal PKI is doomed from the start.

There are other problems with the PKI notion as well, especially those PKIs that attempt to provide a general solution rather than focus on a particular small problem. Fortunately, our interest in certificates is restricted to their use in VPNs, and that is a small enough problem that solutions are possible. Chapters 19 and 20 of [Ferguson and Schneier 2003] provide an excellent discussion of PKIs, the problems they must overcome, and examples of their use in solving smaller specific key-distribution problems. See [Wilson 2003] for more thoughts on using PKI for small, focused applications.

Like cryptography itself, the subjects of PKI and certificates embody far too much for us to cover in detail. Indeed, whole books have been written about PKI. We look briefly at the most common type of certificate in the next subsection.

X.509 Certificates

The most common type of certificate is the X.509 certificate, so called for the International Telecommunication Union (ITU) standard that defines it [International Telecommunication Union 2000]. Most observers consider the X.509 specification a poster child for all that can go wrong with standards committees. The standard is at once bloated and incomplete. As Peter Gutmann [Gutmann 2000] says, "Since the original X.509 spec is somewhat vague and open-ended, every non-trivial group which has any reason to work with certificates has to produce an X.509 profile which nails down many features which are left undefined in X.509." These profiles are largely incompatible, so we end up with many different types of certificates that can't interoperate.

The Internet PKI profile is the responsibility of the IETF PKIX working group <http://www.ietf.org/html.charters/pkix-charter.html>. The profile itself is published as RFC 3280 [Housley, Polk et al. 2002], but there are several supporting documents. As of this writing, the PKIX home page lists several Internet Drafts as well as 17 RFCs in addition to RFC 3280more than 2,000 pages.

Figure 3.10 shows the structure of an X.509 certificate. The Version section specifies which of the three versions of the X.509 specification applies to this certificate. Each certificate that a CA issues has a unique serial number that appears in the Serial Number section. The Signature Algorithm specifies which digital signature algorithm the CA (the Issuer) used to sign the certificate. For security reasons, certificates are valid for a limited time. The Validity section lists the start and end dates of the certificate's validity. The Subject and Subject Public Key Information sections contain the name of the holder of the certificate and the associated public key. The Extensions section contains additional information required by individual profiles. Finally, the Signature section contains the CA's digital signature.

Figure 3.10. X.509 Certificate Structure

[View full size image]

Here is a printout of the information from one of the certificates that we will use in Chapter 6:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 9 (0x9)
        Signature Algorithm: sha1WithRSAEncryption
        Issuer: C=US, ST=Florida, L=Tampa, O=Text CA,
            CN=bsd.jcs.local
        Validity
            Not Before: Mar 31 20:02:42 2003 GMT
            Not After : Mar 30 20:02:42 2004 GMT
        Subject: C=US, ST=Florida, L=Tampa, O=sslecho,
            CN=linux.jcs.local
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (1024 bit)
                Modulus (1024 bit):
                    00:d6:6f:d6:40:00:8a:c6:86:00:b8:31:62:f3:a6:
                    bd:c1:f0:10:b5:69:34:8c:f7:d6:09:98:66:9d:dd:
                    a5:90:5e:58:fb:06:9d:59:21:75:fb:ac:ab:86:56:
                    83:57:af:85:1e:53:90:45:f7:e9:3f:66:b1:f3:e7:
                    fd:59:c1:88:ee:86:13:3c:79:55:c9:50:58:ae:5a:
                    32:d5:6e:aa:a7:f0:fd:2c:88:b9:89:1c:9d:3e:95:
                    27:6b:cc:a9:1f:5e:c0:99:d5:65:79:1e:2d:64:d3:
                    63:dd:99:8f:1f:22:1d:2f:2e:1b:f9:39:6c:c5:1e:
                    b3:01:a0:1a:07:56:21:5b:c3
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            Netscape Cert Type:
                SSL Server
     Signature Algorithm: sha1WithRSAEncryption
         4b:e7:22:94:f9:a9:c3:db:6b:a5:c3:ea:39:b7:9a:04:36:c9:
         de:d7:c2:ed:59:d7:bb:b9:4c:ec:35:a4:15:e9:32:d6:b0:ea:
         d8:64:5d:5c:41:3f:bb:c9:41:c7:32:fd:ad:47:52:20:c4:d5:
         04:3a:92:a8:59:f8:34:3c:57:bd:cc:15:ac:f4:3e:59:11:3f:
         c4:3f:2f:a5:7f:ef:89:8f:13:51:e6:9c:a7:94:20:71:ed:5a:
         1d:57:65:bb:38:34:2f:0a:86:73:e2:18:e0:8f:23:4d:d0:a3:
         37:b6:ee:0f:44:07:1d:94:66:70:78:ef:31:d1:97:50:11:ec:
         25:c3

We use several certificates such as this in Chapter 6, where we examine SSL. As is typical for a private organization, we have set up our own CA (Text CA) to sign these certificates. We see this in the Issuer section of the printout.

Certificate Chains

If we imagine a large international corporation that wants to issue certificates to its employees for email or remote access, say, we see that the corporation is faced with an administrative problem. How are all the business units and branch offices going to get their certificates signed? They could send them to the home office, where they would be signed by the company's CA, but this would take time and introduce verification problems because the home office won't know the employees personally. It would be much better to have the local offices sign the certificates for the employees who work there, but that would require giving each branch a copy of the CA's private key, a significant security risk.

To solve this problem, it is possible for the CA, now called the root CA, to create sub-CAs that are authorized to sign user certificates. To do this, the root CA issues special certificates to the sub-CAs and signs them. The sub-CAs, in turn, use these certificates to sign user certificates. This hierarchy can be extended to several levels. For example, the root CA might sign certificates for each business unit's CA, which might, in turn, sign certificates for each branch's CA, and so on. Note that a user who wants to verify another user's certificate doesn't need to know and trust each sub-CA, because the sub-CA has been vouched for by its immediate parent and ultimately by the root CA via the signing of the sub-CAs' certificates.

Revocation

By far the most difficult problem to solve in setting up a PKI is providing some means of revoking certificates. Revocation is necessary because employees leave a company, private keys are compromised, or some other event renders the certificate invalid.

As is the case of the certificates themselves, the revocation problem is much easier if we restrict our attention to a small, specific PKI implementation rather than try to create a general solution. A common example is a secure Web server's SSL certificate. If the certificate becomes invalid for some reason, the system administrator need merely replace it, because, as we'll see in Chapter 6, the SSL server sends the client a copy of the certificate when the SSL session is established [Gutmann 2003a]. Similarly, certificates used to allow remote logins are effectively revoked by merely closing the account to which they are tied. As we noted earlier, [Ferguson and Schneier 2003] has an excellent summary of the various revocation schemes. See [Zheng 2003] for a detailed analysis of several revocation schemes and some of the engineering tradeoffs involved in choosing one.