Network Computingwww.networkcomputing.com

Other Articles by Robert Moskowitz

EDI to E-commerce: Two Generations of Spending, Columnists, December 15, 1998 Are Biometrics Too Good?, Columnists, January 25, 1999 The Need for Host Authentication, Columnists, February 22, 1999 DES Is Dead. Long Live...Well, Um, What?, Columnists, March 22, 1999 Building Trust in Digital Certificates, Columnists, April 19, 1999

Other Columnists this issue

Net Results By Dave Molta On the Edge By Art Wittmann

Company Directory

Browse our directory to get data, starting with a particular company.

Reader Service

Allows you to request additional product information from our advertisers.

Print The Full Article

ClickHere

E-mail this URL

ClickHere

Buy the Book

		our customizable newsletter, sends you security alerts, product updates and software patches on the products you use. Sign up now at www.networkcomputing.com /express/

Obviously, due to its importance, this concept warrants some aids. Certificate path construction is the process of building the chain of trust from your certificate to the certificate for the person (or system) on the other side of the communication link. Without path construction, we will never witness our certificate environments grow from the difficult-to-maintain Trusted List of the Web browsers to functional PKIs. When some of the original developers of digital certificates were asked for documentation on path construction, their response was either "It is simple graph theory--why do they need documentation?" or "Our tool kit does it for them." Simple graph theory? When was the last time I worked with that? And being told the documentation is in two tool kits out of a dozen may help some vendors implement it, but does not clarify the process for anyone.

What Is a Certificate Path and Why Do We Need It? Your (and your business partner's) digital certificate is signed by the private key of someone you and others trust. The matching public key's certificate is called either a signing or a root certificate. More important, it is called your Trust Anchor. If both parties' Trust Anchors are the same, mutual certificate validation is trivial. But if the Trust Anchors differ, both parties must construct a trusted chain from their Trust Anchor to the other's Trust Anchor in order to validate each other.

The builders of a PKI can choose from two methods to lay the groundwork for path construction, both of which are based on the relationship of the individual Trust Anchors. One approach is to use a hierarchy: one ultimate Trust Anchor and lots of dependent Trust Anchors. The other method involves a mesh of Trust Anchors that cross-certify one another. Multiple Trust Anchors reduce security risks (and liability), provide for provisioning competition (which reduces costs) and can better address corporate policies. Although the administration, security risks and policies differ for a hierarchy as opposed to a cross-certified mesh, both need graph theory to construct the path.

Alternatives to Path Construction Because path construction is complex, it can lead to many interesting problems in complex PKIs--so you may want to consider alternatives. Your two primary options are the Trusted List model found in the browsers, and online certificate-validation services. The former relies on distribution to all systems--all Trust Anchors. Unfortunately, this model entails a long-term maintenance issue, which the browsers generally address by introducing new software every six months with new Trusted Lists. Understandably, the practicality of this solution is questionable for many users. Your other primary alternative, the online certificate-validation services, turns the path construction problem around by having the CAs (Certificate Authorities) register with the service and thus eliminates the need to field Trust Anchors at all. However, offline users and real-time systems cannot effectively use these services. In the case of either alternative, the solution does not suit everyone, so understanding and implementing path construction is wise.

Getting Around Connecting dots is a familiar child's, and road engineer's, game. As a child connects dots to produce an image, a road engineer connects dots, representing cities, to manage traffic. Like a road engineer, a PKI administrator uses one-way hierarchical links and two-way cross-certificate links to build an efficient route for trust that is represented in the PKI map.

Where a person can "read" a map to find the desired route, a program must construct all paths from a starting point until the desired route is constructed. Starting with the Trust Anchor, the certificate-enabled application needs to discover all adjacent Trust Anchors, then those adjacent to the expanded list until the partner's Trust Anchor is found.

In a hierarchy, path construction involves going up a one-way street to a more authoritative Trust Anchor, then finding all one-way streets descending from it. This discovery process works by retrieving caCertificate objects from the Certificate Repository (Internet Draft draft-ietf-pkix-LDAPv2-schema-02.txt).

An application ascends the hierarchy by retrieving objects with the Subject field matching the Issuer field of Trust Anchors. To descend the hierarchy, the application retrieves objects with the Issuer field matching the Subject field. In the end, the hierarchy is turned inside out with the Trust Anchor now the head of the hierarchy and the partner's Trust Anchor at the bottom.

Path construction in a cross-certification mesh resembles the hierarchy process. Here the object retrieved is crossCertificatePair. Where caCertificate contains a single root or signing certificate, crossCertificatePair contains both of the certificates that define the cross-certification. A crossCertificatePair object has "forward" and "backward" certificate elements. For a given CA, the forward element is the pointer to CAs with which it has cross-certified; the backward element is a pointer from that cross-certified CA to the originating CA. In a Certificate Repository, there likely will be two crossCertificatePairs, each mirroring the other. Building the path here entails retrieving crossCertificatePair objects where the Issuer field in the forward element matches the Subject field in the Trust Anchor. The path is built when the Subject in the Forward element matches the Issuer in the partner's certificate.

In these examples, path-building processes are the same, but the objects retrieved are different. Also, in a hierarchy the path is complete when the end point's Trust Anchor is retrieved, while in a cross-certified mesh, Trust Anchors are never retrieved and never need to be placed in the repository. The final forward element contains the same public key as the corresponding Trust Anchor.

Optimizing Path Construction Of the two most important optimizations for path construction--both affecting hierarchical PKIs--the more well-known one is appointing the root certificate at the top of the hierarchy as the Trust Anchor for all end points. Although this entails a one-time operational cost (which comes into play when a user sets up a certificate), it simplifies every certificate path construction. Because the system does not have the direct Trust Anchor, the user must construct the path from the Trust Anchor that he or she has, at the top of the hierarchy, to the certificate. Once this is done, building a path is simply a downward retrieval process.

Proponents of this optimization note the advantages for deployment. Every device can be initialized with the same Trust Anchor. Because Intermediate Certificate Authorities are created as additional Trust Anchors, they never need to be distributed, which is a big attraction for corporations wishing to standardize system loads. The downside is that a compromise of the single Trust Anchor would affect every user of the PKI, not just the immediate subservient CAs.

The second, more important optimization is described in the Internet Draft, draft-ietf-pkix-LDAPv2-schema-02.txt. CA signing certificates can be stored in the forward element of the crossCertificatePair instead of in cACertificate. If the PKI's repository is populated this way, the LDAP queries for walking down a hierarchy are identical to those for traversing a cross-certificate mesh. If this approach is implemented by the CA vendors, the application vendor's development and testing would be simplified and less likely to have errors.

The Role of the PKI Administrators Many PKI advocates disagree as to whether hierarchies or cross-certificate meshes are better models for building a PKI. Interestingly, we have seen that with proper setup they are operationally equivalent in the critical area of path construction. As current and budding PKI administrators come to realize this, they can start demanding that certificate enabling and certificate-enabled products adhere to path construction methodologies that let users choose a model that fits, and even mix them in complex PKI models.

Back in my carefree college days when I actually understood the math underlying graph theory, we learned that you can start anywhere in a graph, move out from there and in the end turn the graph inside out. This was an interesting academic discussion back then. Now we are drawing graphs and turning them inside out as a course of business, forgetting that there is graph theory to help standardize and optimize the process. There is a certain gratification in the realization that those college lessons were not for naught.

Robert Moskowitz is a senior technical director at ICSA. Send your comments on this column to him at rgm@htt-consult.com.