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

isode.com / whitepapers /

Distributed Directory in support of large scale PKI

20th July 2005

Directory is usually cited as an essential part of supporting a PKI (Public Key Infrastructure) system. A typical diagram, as given below, shows a Certification Authority (CA) accessing a directory using LDAP (Lightweight Directory Access Protocol):

This diagram is a reasonable reflection of a basic scenario. When a more complex PKI is built, this will typically comprise of many inter-related CAs; such complex PKI scenarios are widely described in the PKI literature. When the PKI increased in complexity, so do requirements on directory. As the PKI is distributed, it will generally make sense to distribute the directory that supports this complex PKI. This paper looks at the directory requirements to support a complex PKI and what is needed to provide such a directory service.

Some readers of this document will be familiar with PKI. For those who are not, an Appendix to this document gives a very simple introduction to the nature of a complex distributed PKI. This information is important to give background and context to the primary material of the paper on directory.

This paper looks at the uses of directory made by a PKI and PKI-enabled applications. It defines requirements in terms of directory and then looks at how directory can be used to meet these requirements, and implications on provision of a distributed directory.

What is Needed in the Directory

There are two types of information that are needed by a PKI to be stored in a directory. These are:

1. For each CA, to have one or more entries in the directory, holding certificates, CRLs and ARLs for the CA. Essentially, the directory is used to hold information associated with each CA that may be required by users of the PKI.
2. To have an entry for each user (typically each person or role), containing the certificates issued for that user. The CA that generates the certificate publishes it in the directory, so that users of the PKI can access it.

The following sections of this paper explain why this information is needed by the PKI.

Why Directory (1): Supporting Encryption

When encrypting a document or message, the public keys of those intended to decrypt the documents are needed. In a large system, the document or message originator is unlikely to have these public keys. The directory is the natural place to locate appropriate public keys, which will be held in a certificate belonging to the user in the user’s directory entry. Once obtained from the directory, this certificate must be verified using PKI.

Why Directory (2): Certificate Path Building

The entity verifying the certificates needs to get them from somewhere; one approach often used is to supply the necessary certificates along with the entity being signed. This can be convenient, but has a number of disadvantages:

• In many situations, the same verification is repeated, and so the verifier would have the certificates anyway. Certificates can be quite large, and for some environments this waste of bandwidth would be an issue.
• Obtaining the certificate independently removes certain types of security attack. There are more opportunities to fake things when supplying both the object to be verified and information to be used to verify the object.
• The sender has to get the certificates from somewhere, so the certificate retrieval problem is put in a different place.
• This option is not available when using PKI to support encryption.

Fortunately, the directory is a convenient place to hold certificates. The directory entry where a particular certificate is held can generally be inferred from the name of the subject, particularly where a system is built with directory retrieval as a planned approach. Because the CA trust path may be complex, the verifying entity will need to apply sensible heuristics in order to determine and retrieve all of the certificates needed.

Why Directory (3): CRLs and ARLs

The next use of the directory is for the verification process to obtain necessary CRLs and ARLs. When a certificate is issued, it may contain a CRL Distribution Point, which is the (directory) name of where the CRL relevant to that certificate is stored. It is expected that CRLs will be used widely (e.g., US Federal Government has recently mandated their use). The most recent CRL can be found by reading the CRL attribute from this entry in the directory.

When an entity is performing a verification, it will need to have up to date CRLs for all of the Certificates that are used in the process. In the example of Joe verifying Admiral Tim’s email in the Appendix, Joe will need to have up to date CRLs for each of the five certificates used in the verification. Joe may have these (typically from verifying other information). If he does not have them, the CRLs will need to be retrieved from the directory.

As CRLs generally have a quite short period of validity before they are out of date, use of directory to directly access the current CRL is very important, as caching is usually not useful.

Why Directory (4): Certificate Update

Where certificates are held by an entity, they will expire from time to time. Every entity will need to be set up with at least one manually configured certificate (an initial trust point). This initial manual installation is critical to ensure security and cannot be avoided. However, there is no need to repeat the manual step when a certificate expires. If an updated certificate (certifying the same public key) is placed in the directory, the entity can go to the directory to update its certificates.

 

An Example Supporting Directory

We now look at an example directory to support a complex PKI. We'll take the example CA structure described in the Appendix. This example is formulated in terms of a government digital signature organization for a fictitious country (C=TY).

Note the CA structure (not a true hierarchy). In comparing this to the DIT (Directory Information Tree) and DSA hierarchies shown below, it is useful to note that there is a clear relationship, but that all three are different. The DIT is shown next:

 

A number of things can be seen from this DIT.

1. It is (strictly) hierarchical, and is different to the CA hierarchy (although there are some clear relationships and similarities).
2. Every user has an entry in the directory, where the user’s certificates are stored.
3. Every CA has an entry in the directory, where (typically) the Certificates of the CA and CRLs issued by this CA are stored.
4. There is “strict naming”. All objects have full distinguished names, which are consistent across the complete service.

Requirements on Directory Distribution

The data in this directory is likely to be supported by a number of directory servers, known as DSAs (Directory System Agents). Typically each government department will run its own DSA, and use this to hold the data it manages. In general, a directory will be used for other services such as email support and white pages, and not just for PKI support. In the above example there will be DSAs for the following organizations:

This diagram shows all of the DSAs needed to support the DIT above. Note that each of these is an organizational DSA, which has a superior reference to the country DSA (first level DSA).

The distributed PKI has led to a situation where PKI supporting data is held in a number of DSAs, which need to act as a distributed directory. The reason for this is that an entity performing verification needs to access information which may be in any DSA. The verifying entity will make LDAP queries to locate information. This query will need to be sent to the “right” DSA. There are three ways to achieve this.

1. Referrals. The DSA can return an LDAP referral to the client (that points to the right DSA), and the client will then connect to the other DSA. Most LDAP servers and many clients support this process.
2. Chaining. The first server connects to the other DSA and to make the query, and then returns the result to the client. This makes the distributed operation transparent to the client. Chaining is a standard part of X.500 (discussed later). Some DSAs, including Isode’s M-Vault support LDAP Chaining, so that queries can be chained to DSAs that do not support X.500.
3. Replication. Rather than sending the query to a remote DSA, an alternate strategy is to replicate data to the local DSA. This is discussed later.

The important point about the distributed directory is that the necessary service cannot be provided by a single LDAP server. Rather, a collection of DSAs need to act in a distributed manner to provide the information needed by the PKI.

Patterns of Directory Use

In planning a distributed directory, it is important to understand the load that will be applied. The details of this can only be done for a specific deployment. It will depend significantly on the number of entities and the number of verifications being done. As discussed at the start of this paper, it is likely that once this type of infrastructure is built, that it will be used for most supportable transactions and so many verifications will be performed.

Necessary CRLs will typically get cached when they are retrieved. In a high volume system, when a CRL is out of date, every verifying entity will need to get the latest version of the CRL. This will typically mean that there is a spike of requests for CRLs just after they expire. The same is true for certificates, although in general certificates will have a much longer expiry than the CRL refresh time.

Verifying entities are likely to quite quickly cache most necessary CA certificates. Path building will need more occasional access to certificates from all over the DIT.

Referral versus Chaining

Referral and chaining are the basic choices for a distributed directory. Referral is the simplest (and most widely supported by directory servers). Although simple, there are three basic problems with use of LDAP referrals:

1. LDAP client support of referrals is often not good. Many LDAP clients assume that results come back from the server queried.
2. Building a distributed directory with referrals assumes that every client can talk to every server. In a distributed environment, with multiple levels of firewall, this is often not possible.
3. LDAP referrals requires that every client can authenticate to every server. This is often not possible.

In practice, this means that chaining is the best approach to build a distributed directory. Configuration can be set up and tested to verify that directories can correctly talk to each other, and pass back results to the requesting LDAP client.

Requirements on Directory Replication

An important characteristic of directory servers is that data can be replicated. Data is replicated for a number of reasons:

• Robustness. Data is placed in more that one location, so that it can be accessed in the event of a server failing or being unavailable.
• Performance. Where one server can be a potential bottleneck, data may be replicated to improve performance.
• Locality of access. In order to get high read and search performance, it is often desirable to replicate data so that it can be access on a local DSA.

We can now consider these principles in light of patterns of expected use. Some specific notes can be made:

1. Verification of digital signature is almost certainly going to be a highly critical process. For this reason, it will generally be a sound approach to replicate every directory server, so that access to information in the directory is not dependent on a single server. Ideally these servers should be independent, with no single common point of failure.
2. While there are relatively few CA directory entries, they will be widely scattered over the DIT, with only one or two in each DSA. These will be the entries that are accessed most frequently. There is likely to be spikes of access after CRLs are updated. This pattern of access to critical data suggests that it is highly desirable to replicate this information very widely, so that it will be available in local DSAs.
3. Other entries will have lower access rates. While it will not be necessary to replicate for performance reasons, it may be desirable to replicate data for robustness and locality of access. Military directories usually take an extreme approach here, and replicate all data, so that operations are not dependent on availability of remote servers.

These principles will need to be applied to the specific requirements of a deployment. It is likely that replication will be important for most distributed directories supporting PKI.

Meta Directories

Meta Directories (Directory Synchronization) are useful when the primary goal is information integration. Because of the requirements on strict naming to be able to consistently retrieve information based on directory name that is held in the certificate, this needs to be consistent across the entire system described here. In general, a Meta directory will perform data transformation. While this may be convenient for synchronizing and sharing human data, it will generally be problematic for PKI support. True directory replication will generally be the best approach.

When X.500 Matters

X.500 is the ITU standard for directories, and defines a complete system for provision of a directory service. LDAP defines a standard for access to a directory, which works well with X.500 but is not restricted to X.500. Most X.500 directory products support LDAP, but many LDAP servers do not support X.500. X.500 defines many important functions that are not present in LDAP. These include:

• A protocol to do chaining and handle queries between servers (DSP – Directory System Protocol).
• Replication using DISP (Directory Information Shadowing Protocol).
• Administrative framework.
• Access Control.

In LDAP directory servers that do not support X.500, some or all of these capabilities may be provided using proprietary mechanisms, . Replication and chaining are likely to be key components of a distributed directory supporting PKI. When such a distributed directory is specified, there are essentially two options:

1. Specify use of X.500.
2. Specify use of directory servers from a single vendor, and ensure that these products meet the necessary requirements.

In many deployments, this means that use of X.500 will be essential.

Conclusions

This paper has given a brief illustration of how distributed directory is used to support PKI, and the requirements that PKI places onto such a service. In general, use of directory servers that support both LDAP and X.500, such as Isode’s M-Vault are the best way to build such a service.

Next Steps

If you have not already done so you should consider reading the Appendix to this paper, A Short Tutorial on distributed PKI, which contains background material helpful in setting into context the material in this white paper.