Messaging and Directory Server software used around the world in the Government, Military, Aviation and Commercial sectors.

isode.com / whitepapers /

A Short Tutorial on Distributed PKI

Why Build Large Scale PKI?

PKI is needed to support large scale deployment of a number of security services. In particular:

• Origin authentication: Verification that a document or message was created by the person claimed. This is often referred to as “digital signature”, although digital signatures can be used to authenticate things other than origin.
• Content integrity: Securely show that a document has not been tampered with.
• Content confidentiality (encryption): This is protecting the contents of a document or message so that it can be read only by specifically identified users.
• Non-repudiation: A security service whereby creation of a document or message cannot subsequently be denied.

The requirement for large scale PKI come from situations where one or more of these services needs to be supported across multiple organizations. A common example of this is “e Government” initiatives such as the US eGov initiative supported by the Federal PKI. Another example are the security services of the Extended ATS Message Service, used to support Aviation ground to ground messaging internationally. This requires an international PKI, spanning Aviation organizations around the world.

The goal of a large scale PKI is to enable some or all of these services for users of the infrastructure. In most situations where an infrastructure is properly built, it will be used heavily. Once there is a capability to digitally sign and verify messages, it will generally make sense to use this for all transactions. Benefits:

• General improvement in security.
• Regular use of digital signatures improves security of the digital signature.
• If everything is signed, anything without signature is immediately suspicious.

This assumption has implications later, in discussions on provisioning directory.

Private and Public Keys

This is not intended to be a general tutorial on PKI. There are many detailed descriptions. This section and the next try to simply explain the essence of why a PKI is needed and how it works, so that enough information is provided to understand the directory elements of the whitepaper: Distributed Directory in support of large scale PKI.

Distributed security services using PKI are based around a technique called “asymmetric cryptography”. The central components of asymmetric cryptography are public and private keys. A simple understanding can be gained by looking at the answers to three related questions:

Q1: What is a Key Pair?

1. A Key Pair comprises a “public key” and a “private key”, which are both very large numbers.
2. The key pair is generated using special techniques from two very large randomly generated prime numbers.
3. One can be confident that every key pair is unique, in the same way that one can be confident that every finger print in the world is unique.

Q2: What is a Private Key?

1. A private key is stored securely by its owner, perhaps on a smart card or securely stored on the owner’s computer. It is held in a way that only the owner has access to it. This is the “private” element.
2. A private key can be used by the owner to create digital signatures that are unique to the owner of the private key.
3. A private key can be used (typically using a complex mechanism) to decrypt documents, and it can be guaranteed that only the holder of the private key can decrypt the document.

Q2: What is a Public Key?

1. The public key can be published and shared widely. There is no requirement to keep it secret. This is the unique and useful property of asymmetric cryptography.
2. A public key is used to verify the digital signature created by the associated private key.
3. A public key can be used by anyone to encrypt a document, such that only the holder of the private key can decrypt it.

As an example of digital signature, user Joe will create an electronic signature for a document using his private key. Anyone can very this digital signature using Joe’s public key. This approach is very flexible and powerful, simply because Joe’s public key can be published and distributed freely, so that anyone can verify Joe’s digital signature.

Why Do Public Keys need PKI?

The basic cryptography and verification provided by a public/private key mechanism does not require a PKI. To understand the need for PKI, one needs to consider the trust assumptions behind digital signature verification. Consider for example that I am given a document that is purported to be signed by Joe using Joe’s public key, along with this public key. I can use asymmetric cryptography to be certain that the public key provided was used to sign the document. The important question is: “How can I be certain that this public key belongs to Joe?”

It may be that Joe gave me a copy of his public key, or that I have other signed documents from Joe, which I have verified with the same public key (because only Joe’s public key can verify documents signed by Joe). In some small scale situations, digital signature verification with public keys can work fine on an ad hoc basis without a PKI.

In general, this trust question is a big problem. How can you establish trust that a given public key is owned by a particular person or entity? This is the problem that PKI sets out to solve, and is fundamental to using digital signatures on a large scale.

The basic building block of a PKI is a (digital) Certificate. The entity creating a certificate is called a Certification Authority (CA). The core components of a Certificate are:

1. The name of the entity that the Certificate refers to. For convenience the certificate might contain several names for the entity, such as the email address and LDAP directory name.
2. The public key of the entity (e.g., Joe's public key).
3. A digital signature created by the CA (using the CA’s private key). This signature binds together the components of the Certificate.

By creating a Certificate containing Joe’s name and public key, the CA is stating that it has verified that the public key in the certificate does in fact belong to Joe. This can be verified using the CA’s public key.

Certificates and CAs enable a trust chain to be built. This is shown in the diagram below:

The starting point of the trust chain is that the CA is trusted. Technically, this means that the identity of the CA’s public key is trusted. This trust leads to trust of Certificates issued by the CA, because the digital signature on the certificate can be verified using the CA’s public key. Because Joe’s name and Joe’s public key are contained in the certificate, trust is gained that Joe’s public key really does belong to Joe. Now, a document signed by Joe’s private key is linked back by cryptographic trust to Joe’s public key (in which trust was established in the previous step). It can be seen that starting with the point of only trusting the CA, that a trust chain can be established to build trust that a document was signed by Joe.

An important extension is that a CA can also issue certificates for other CAs. This means that a trust chain can be established through multiple CAs, going CA -> CA -> CA -> User’s Public Key. This enables a mesh of CAs with trust links to be used. The importance of this will be seen in the example later.

There is a lot of PKI complexity not covered here, which does not need to be understood for the purpose of this paper. One concept that is important for the following examples is CA policy. A CA is participating in a trust chain. When a CA creates a Certificate, it will follow certain process with more or less care to be certain that the information being certified is correct. These processes are published as a CA policy. When a CA has certain policies that are expected by those that trust it, this also needs to be reflected into other CAs that it certifies. Higher trust and care has higher cost, and so different CAs will have different policies. High trust CAs will not generally certify lower trust CAs, in order to provide consistent trust quality. This leads to partially interlinked meshes of CAs with different policies.

An Example PKI

This section shows how this structure might come together in a non-trivial example that we also look at in terms of directory support. This is formulated in terms of a government digital signature organization for a fictitious country (C=TY).

The overall structure is a somewhat complex mesh, which is somewhat hierarchical. Arrows show trust, which is reflected by issue of a certificate. The core of this government structure is CAs associated with departments. These CAs are in a position to certify users within the department.

CAs will generally (but not always) have mutual trust reflecting aligned policies. Mutual trust will be represented by certificates being issued in both directions between CAs. Because there are many government departments, it would be overly complex to have every department certify each other department, Therefore, the government has established a number of central CAs which are used to provide a trust path between all government departments.

This example structure does not (and should not) contain well known or generally trusted CAs, such as the visible public CAs for which trust is often installed by default on many computers. A typical user will establish trust with a local CA. For example Joe Farmer will establish trust with the Agriculture CA. This will typically be done by providing Joe Farmer with a certificate that includes the Agriculture CA’s public key that will be installed on Joe Farmer’s computer. This is his initial trust point, and means that he will trust certificates signed by the Agriculture CA.

Consider an example where Joe wants to verify a document signed by Fred Train Driver. The trust chain requires two certificates:

1. A Railways CA Certificate, signed by the Agriculture CA.
• Certificates are referred to by their “subject” (in this case the Railways CA) and will always contain the name and public key of the subject, Joe can verify this certificate using the public key of the Agriculture CA (which he trusts), and thus gain trust in the Railways CA (and its public key).
2. Fred Train Driver’s Certificate, signed by the Railway CA.
   • Joe can verify this using the public key of the Railways CA. Joe has now gained trust of the Fred’s public key, from this certificate.

Joe can now use Fred’s public key to verify the document, and this example verification is complete.

A longer trust chain is listed below, to show how Joe could verify a digitally signed email from Admiral Tim.

1. Low Assurance CA Certificate (signed by Agriculture CA).
2. High Assurance CA Certificate (signed by Low Assurance CA).
3. Military CA Certificate (signed by High Assurance CA).
4. Navy CA Certificate (signed by Military CA).
5. Admiral Tim’s Certificate (signed by Navy CA).

Certificate Life Cycle

Certificates do not last forever. If a user ceases to be trusted, perhaps because of ceasing to be an employee, the certificate must be deactivated. If a user’s private key is stolen or otherwise compromised, signatures made by the user’s private key can no longer be trusted and so the certificate must be deactivated (just like handling a lost credit card). There are two primary mechanisms to achieve this:

1. At regular intervals each CA issues a Certificate Revocation List (CRL), and sometimes an associated Authority Revocation List (ARL), which has a similar function. The CRL contains a list of revoked certificates, and the issue date of the CRL. A recent CRL for each CA must be checked as part of the verification process. A CRL indicates when the next update will be issued, so that it is clear when a CRL is out of date.
2. Certificates have an expiry date. This is important, as it enables old certificates to be removed from the CRL, and thus prevent the CRL from getting too large. The certificates used for verification must be up to date. Note that when a certificate is renewed, the public key will not generally change. Essentially the same certificate is re-issued with a new expiry date.