At work I recently gave a presentation about the practical aspects of public key cryptography with the OpenSSL toolkit. This is an expanded transcript of the presentation, published here on my blog in the hope that it’s useful for a broader audience.

There are four parts covering these major topics:

• Part 1: Public Key Cryptography
• Part 2: Public Key Infrastructure (PKI)
• Part 3: Inspecting and Creating X.509 Certificates
• Part 4: OpenSSL Bag of Tricks

You are reading part 2, about Public Key Infrastructure (PKI). This part shows the practical problems with simple public key cryptography, and how a public key infrastructure attempts to solve them. While part 1 was fairly technical, this part is about real-world organizational structures and trust relationships. Part 3 will again be more technical, showing how these real-world concepts are mapped to systems and software.

Some things in this part are based on the German book “Kryptografie und Public-Key Infrastrukturen im Internet”. A revised English edition is available as “Cryptography and Public Key Infrastructure on the Internet”. Both are probably a bit dated by now, so you should look for newer books.

Practical Problems With Plain Public Key Cryptography

There are a few practical issues with the basic operations provided to us by plain public key crypto. The next few sections highlight some of them:

• Key authenticity
• Key revocation
• Key validity periods

There are other issues not discussed here, such as non-repudiation and policy enforcement.

For public cryptography to be useful in real-world use on a large scale, these issues need to be addressed, and that is what a Public Key Infrastructure, or PKI, is about.

Key authenticity

Part 1 didn’t go into the details of how two parties who want to exchange encrypted or signed messages exchange their public keys, but these details are critical.

One possibility is to exchange the keys at a face-to-face meeting. This approach is not feasible on a large scale, and public key cryptography with its asymmetric nature is interesting exactly in a large scale scenario.

In the absence of a secure communications channel for key exchange between the two parties, another possibility is to exchange the keys over an open, untrusted network like the Internet. The problem with this is that the recipient of the key can never be sure if the key is authentic.

A third party C, with the ability to intercept messages on the untrusted network, could intercept the public key in transit from the sender A to the recipient B and note it. C could generate a new key pair and send the public key to B, pretending to be A. If B then uses this public key to send an encrypted message to A, the third party could again intercept the message, decrypt it with the private key it generated to read the message, and then re-encrypt the message using A’s real public key and send it to A, pretending to be the legitimate sender B. It would work the same in the other direction and it’s called the man-in-the-middle attack (MITM).

A public key infrastructure should make it possible to verify a public key’s authenticity.

Key revocation

If a private key is compromised, we want our communication partners to stop using the related public key, otherwise confidential information is sent around and people other than the intended recipient are able to decrypt it.

A public key infrastructure should make it possible to revoke previously distributed public keys.

Key validity periods

Encryption keys should be replaced in regular intervals. One reason is that the longer a key is in use, the more material is available for cryptanalysis. Another reason is to limit the damage caused by a private key being compromised without detection.

A public key infrastructure should provide means to specify a validity period for a public key.

Trust Relationships

Ultimately, these issues are about trust and trust relationships between the involved parties. There are different types of trust relationships, and this section shows how well each one addresses the problems.

Direct Trust

This model could also be called “no infrastructure”. It’s the basic face-to-face meeting case from above, where the parties exchange their public keys directly.

It’s difficult to do with parties who are total strangers, and between difficult and impossible to do with lots of communication partners.

Key revocation means directly contacting the other party and telling them to stop using the old key.

There is no support for formal validity periods.

Web of Trust

This model is an extension of direct trust. If participants A and B have previously exchanged their keys, both can now act as introducers and sign (and forward to the other party) the public keys of all other partners they know directly. Each can add the public keys obtained this way to its list of known, trusted keys.

So if A knows B, and B knows C, B is the introducer and can:

• sign C’s public key and send it to A
• sign A’s public key and send it to C

This enables A and C each to verify the new public keys using B’s public key, which they already know and trust, and begin exchanging secure messages directly, knowing that their public keys for each other are authentic.

Now that A and C trust each other, they can again sign keys of partners they know directly, and so on, thus creating and extending the web of trust.

It is usually not just the public key that is signed, but a whole package of information that includes the public key, the subject’s name, e-mail address etc. This whole information package, when signed, is also called a certificate. Make a mental note of this, because it’s important: A certificate contains a public key and additional information, and somebody signed the whole package with a private key that’s unrelated to the public key in the package.

The party who signs the bunch of data, and therefore issues the certificate, vouches for the entire information, and not just for the public key. This means that the signing party needs to verify all information that it signs. For things like e-mail addresses, that can be through an automated process, but for things like a company or personal name, it usually requires checking official records such as commercial registry papers, passports, ID cards etc.

Handling revocation, expiration and scaling to large users bases can be difficult, as can be getting introduced into a web of trust. Wikipedia’s article on web of trust has more information.

Web of trust is the trust model used by PGP.

Hierarchical Trust

In this model, all parties agree on one or more trusted, independent authorities to issue certificates. These authorities are called certificate authorities (CAs) or trust centers.

A CA’s own certificate, which the parties need in order to verify the certificates issued by that particular CA, is called a root certificate and it is distributed widely, e.g. as part of client programs such as e-mail clients or web browsers or directly in operating systems.

Here are parts of the root certificate lists of Mac OS X and Windows XP:

Because literally millions of users trust these CA certificates, the non-disclosure of the associated private keys is absolutely critical. The CA’s organizational structures and operational processes are designed to prevent a compromise of these very important private keys. A CA has to document the quality of these structures and processes by passing an audit before its root certificate is accepted by operating system and other client software vendors. One requirement is the use of Hardware Security Modules conforming to the FIPS 140-2 standard for the generation, storage and use of the CA’s sensitive key material.

Once a party trusts a CA (by having its certificate with its public key in the list of trusted root certificates), it can immediately validate the probably very large number of certificates issued by that CA now and in the future. A CA can also sign intermediate signing keys of other CAs, and they can in turn do the same, which creates the hierarchical trust structure that gives this model its name.

With a CA in place, if two parties both trust that CA and want to communicate securely with each other using public keys certified by that CA, they both have to get a certificate. They generate a key pair and prepare a certificate request. The request is the “bunch of data” mentioned above and it consists of the public key along with all other information required by the CA, according to the CA’s policies.

These policies can vary according to the level of certification, and the price of the certificate usually depends on that level. It could be that only an e-mail address is certified and the certification is free. In other cases, commercial banking-grade certificates are issued that certify not only the name of a web site but also the organization name, after extensive review of legal proof of incorporation and domain name ownership.

After following its procedures to verify that all information presented in the certificate request is valid, the CA signs the public key and other information in the request with its private key. The result is the certificate, which is sent back to the party that requested it.

Once both parties have their certificates, they can exchange them, and they can do this even over insecure public networks because both will be able to verify the certificate’s authenticity using the CA’s root certificate, which they both already know and trust.

So how well does this trust model deal with our practical issues?

Regarding key revocation: With the centralization resulting from a limited number of trusted certificate issuers (my Mac OS X system keychain lists about 150 trusted root CAs), certificate revocation in the form of certificate revocation lists (CRLs) becomes feasible. A CRL is a list of serial numbers of certificates that the CA has revoked. When a CA issues a certificate, it includes the location of this CRL. When a client needs to verify a certificate, it can check if it is on the list of revoked certificates.

For this setup to be useful, the list needs to be updated frequently. On Mac OS X, there’s a daemon called ocspd that does just that. Its name already suggests that it also provides support for an alternative to CRLs, the Online Certificate Status Protocol (OCSP). With OCSP, the client doesn’t download a potentially large list from the CA’s servers from time to time. Instead, it asks specifically about the validity of one particular certificate that it needs to check in real-time. This results in up-to-date validity information and reduces network and storage requirements, a benefit especially on mobile devices.

Other things like validity periods, mandatory attributes etc. are not only possible but actively enforced by the issuing CA according to its policies.

Conclusion

Of these models, only the hierarchical trust model is considered a Public Key Infrastructure (PKI), so that’s what people refer to when they talk about PKI.

The technical standard in use for this model on the Internet today is X.509, and more specifically the IETF’s variant PKIX.

The next part in this series, part 3, gets back to the practical technical level and shows you how you can inspect and create X.509 certificates with the OpenSSL toolkit.