PKIX Working Group M. Cooper
Internet Draft Orion Security
Solutions
Document: draft-ietf-pkix-certpathbuild-00.txt Y. Dzambasow
Expires: August 2003 A&N Associates
P. Hesse
Gemini Security
Solutions
S. Joseph
DigitalNet
R. Nicholas
DigitalNet
February 2003
Internet X.509 Public Key Infrastructure:
Certification Path Building
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of [RFC2026].
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
The draft is being discussed on the ćietf-pkixĆ mailing list. To
subscribe, send a message to ietf-pkix-request@imc.org with the
single word subscribe in the body of the message. There is a Web
site for the mailing list at http://www.imc.org/ietf-pkix/.
Abstract
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 1]
Certification Path Building February 2003
This document was written to provide "best practice" guidance and
recommendations to developers building X.509 public-key certification
paths within their applications. By following the guidance and
recommendations defined in this document, an application developer is
more likely to develop a robust X.509 certificate enabled application
that can build valid certification paths across a wide range of PKI
environments.
Table of Contents
1. Introduction...................................................3
1.1 Motivation.................................................4
1.2 Terminology................................................4
1.3 Overview of PKI Structures.................................6
1.3.1 Hierarchical Structures...............................6
1.3.2 Mesh Structures.......................................8
1.3.3 Bi-lateral Cross-Certified Structures.................9
1.3.4 Bridge Structures....................................10
1.4 Bridge Structures and Certification Path Processing.......11
2. Certification Path Building...................................11
2.1 Introduction to Certification Path Building...............11
2.2 Path Building Algorithms..................................13
2.3 How to Build a Certification Path.........................18
2.4 Suggested Path Building Software Components...............26
2.5 Inputs to the Path Building Module........................28
2.5.1 Required Inputs......................................28
2.5.2 Optional Inputs......................................28
3. Optimizing Path Building Functions............................29
3.1 Optimized Path Building...................................29
3.2 Sorting vs. Elimination...................................32
3.3 Path Building Optimization................................34
3.3.1 Selected Methods for Sorting Certificates............36
3.3.1.1 basicConstraints is Present and cA Equals True...36
3.3.1.2 Recognized Signature Algorithms..................37
3.3.1.3 keyUsage is Correct..............................37
3.3.1.4 Time (T) Falls within the Certificate Validity...37
3.3.1.5 Certificate Was Previously Validated.............38
3.3.1.6 Previously Verified Signatures...................38
3.3.1.7 Path Length Constraints..........................39
3.3.1.8 Name Constraints.................................39
3.3.1.9 Certificate is Not Revoked.......................40
3.3.1.10 Issuer Found in the Path Cache..................40
3.3.1.11 Matching Key Identifiers (KIDs).................41
3.3.1.12 Policy Processing...............................42
3.3.1.13 Policies Intersect The Sought Policy Set........42
3.3.1.14 Endpoint Distinguished Name Matching............43
3.3.1.15 Relative Distinguished Name Matching............43
3.3.1.16 Certificates are Retrieved from cACertificate...44
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 2]
Certification Path Building February 2003
3.3.1.17 Consistent Public Key and Signature Algorithms..44
3.3.1.18 Similar Issuer and Subject Names................45
3.3.1.19 Certificates in the Certification Cache.........45
3.3.1.20 Current CRL Found in Local Cache................46
4. Forward Policy Chaining.......................................46
4.1 Simple Intersection.......................................47
4.2 Policy Mapping............................................48
4.3 Assigning Scores for Forward Policy Chaining..............49
5. Avoiding Common Path Building Errors..........................49
5.1 Dead-ends.................................................50
5.2 Loop Detection............................................50
5.3 Use of Key Identifiers....................................51
6. Retrieval Methods.............................................52
6.1 Retrieval From Directories Using LDAP.....................52
6.2 Retrieval Using Authority Information Access..............54
6.3 Retrieval Using CRL Distribution Points...................54
6.4 Proprietary Retrieval Mechanisms..........................54
7. Improving Retrieval Performance...............................55
7.1 Caching...................................................55
7.2 Retrieval Order...........................................56
8. Security Considerations.......................................57
9. References....................................................57
10. Acknowledgments..............................................58
11. Author's Addresses...........................................59
1. Introduction
X.509 digital certificates have become an accepted method for
securely binding the identity of an individual or device to a public
key, for the purpose of supporting public key cryptographic
operations such as digital signature verification, and public key-
based encryption and decryption. However, prior to using the public
key contained in a digital certificate, an application must first
determine the authenticity of that digital certificate, and
specifically, the validity of all the certificates leading to a
trusted root certificate. It is through validating this certificate
path that the assertion of the binding made between the identity and
the public key in each of the digital certificate can be traced back
to a single point of trust.
The process by which an application determines this authenticity of a
digital certificate, and ostensibly the trust that application will
place in the use of that digital certificate, is called certification
path processing. Certification path processing establishes a chain
of trust between a trusted public key and a digital certificate.
This chain of trust is composed of a series of digital certificates,
known as a certification path. A certification path begins with a
certificate whose signature can be verified using a trusted public
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 3]
Certification Path Building February 2003
key and ends with the target digital certificate. Path processing
entails building and validating the certification path to determine
the degree of trust to place in the target digital certificate.
1.1 Motivation
Many other documents (such as [RFC 3280]) cover certification path
validation requirements and procedures in detail but do not discuss
the intricacies of certification path building. This document
therefore is an effort to provide useful and practical guidance in
that area.
This document is an informational Internet-Draft that seeks to
provide "best-practices" for certification path building. It is
intended to provide information; there are no requirements or
specifications in this document. Furthermore, rather than suggesting
"the" way to best perform certificate path building, this document
seeks to draw upon first hand experience to offer insights and
recommendations to developers integrating support for X.509 digital
certificates into their applications.
In addition, this document suggests an effective general approach to
path building that involves a depth first tree traversal. While the
authors believe this approach offers the balance of simplicity in
design and development with very effective and infrastructure neutral
path building capabilities, the algorithm is no more than a suggested
approach. Other approaches (e.g., building complete spanning trees of
the PKI.) exist and may be shown to be more effective under certain
conditions. Certification path validation is described in detail in
both [X.509] and [RFC 3280] and is not repeated in this document.
1.2 Terminology
Terms used throughout this document will be used in the following
ways:
Certificate: A digital binding that cannot be counterfeited between
a named entity and a public key.
Certificate Graph: A graph that represents the entire PKI (or all
cross-certified PKIs) where all named entities are viewed as nodes
and all certificates are viewed as lines between nodes.
Certificate Processing System: An application or device that
performs the functions of certification path building and
certification path validation.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 4]
Certification Path Building February 2003
Certification Path: An ordered list of certificates starting with a
certificate signed by a trusted public key and ending with the target
certificate. (Sometimes referred to as a Certificate Chain.)
Certification Authority (CA): An entity that issues and manages
digital certificates.
Certification Path Building: The process used to obtain the
certification path between the trusted root and the target
certificate. (This is also sometimes referred to as Certification
Path Construction, Certification Path Development, or Certification
Path Discovery.)
Certification Path Validation: The process that verifies the binding
between the subject and the subject-public-key defined in the target
certificate, using a trusted public key and set of known constraints.
Cross-Certificate: A certificate issued by one CA to another CA for
the purpose of establishing a trust relationship between the two CAs.
Cross-Certification: The act of issuing cross-certificates.
Local PKI or Local Realm: The set of PKI components and data
(certificates, directories, CRLs, etc.) that are created and used by
the certificate using organization. In general, this concept refers
to the components that are in close proximity to the certificate
using application. The assumption is that the local data is more
easily accessible and/or inexpensive to retrieve than non-local PKI
data.
Directory: Generally used to refer an LDAP accessible repository for
certificates and PKI information. The term may also be used
generically to refer to any certificate storing repository.
Public Key Infrastructure (PKI): The set of hardware, software,
personnel, policy, and procedures used by a Certification Authority
to issue and manage certificates.
Relying Party (RP): An application or entity that processes
certificates for the purpose of 1) verifying a digital signature, 2)
authenticating another entity, or 3) establishing confidential
communications.
Subscriber: The holder of a private key and corresponding
certificate, and whose identity is defined as the Subject of the
certificate.
Target Certificate: The certificate that is to be validated by a
relying party. It is the "Certificate targeted for validation."
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 5]
Certification Path Building February 2003
Although frequently this is the End Entity or a leaf node in the PKI
structure, this could also be a CA certificate if a CA certificate is
being validated, e.g., for the purpose of building and validating
certification path for verifying signature on CRL.
Trusted Root Certificate: A certificate that contains a trusted
public key and is used in certification path processing.
1.3 Overview of PKI Structures
When verifying X.509 public key certificates, often times the
application performing the verification has no knowledge of the
underlying Public Key Infrastructure (PKI) that issued the
certificate. PKI structures can range from very simple, hierarchical
structures to complex structures such as multi-bridged, or mesh
structures. These structures define the types of certification paths
that must be constructed and validated by an application. This
section describes four well-known PKI structures.
1.3.1 Hierarchical Structures
A hierarchical PKI, depicted in Figure 1, is one in which all of the
subscribers and relying parties trust a single "root" CA. If the
hierarchy has multiple levels, the root CA certifies the public keys
of intermediate CAs (also known as subordinate CAs). These CAs then
certify end entitiesĆ (subscribersĆ) public keys or may, in a large
PKI, certify other CAs. In this architecture, certificates are
issued in only one direction, and a CA never certifies another CA
"superior" to itself. Typically, only one superior CA certifies each
CA.
+---------+
+---| root CA |---+
| +---------+ |
| |
| |
v v
+----+ +----+
+-----| CA | +-----| CA |------+
| +----+ | +----+ |
| | |
v v v
+----+ +----+ +----+
+--| CA |-----+ | CA |-+ +---| CA |---+
| +----+ | +----+ | | +----+ |
| | | | | | | |
| | | | | | | |
v v v v v v v v
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 6]
Certification Path Building February 2003
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
Figure 1 ű Sample Hierarchical PKI
Certification path building in a hierarchical PKI is a
straightforward process that simply requires the relying party to
successively retrieve issuer certificates until a certificate is
located that was issued by the trusted root.
A widely used variation on the single-rooted hierarchical PKI is the
inclusion of multiple CAs as trusted roots. [See Figure 2.] Here,
end entity certificates are validated using the same approach as with
any hierarchical PKI . The difference is that a certificate will be
accepted if it can be verified back to any of the set of trusted
roots. Popular web browsers use this approach, and are shipped with
trusted CA lists containing dozens to more than one hundred CAs.
While this approach simplifies the implementation of a limited form
of certificate verification, it also may introduce certain security
vulnerabilities. For example, the user may have little or no idea of
the policies or operating practices of the various roots, and may not
be aware of which root was used to verify a given certificate.
Conversely, if the trusted CA list is properly managed and kept to a
manageable size, it can be an efficient solution to building and
validating certification paths.
+-------------------------------------------------------+
| Trusted CA List |
| |
| +---------+ +---------+ +---------+ |
| +--| Root CA | | Root CA | | Root CA | |
| | +---------+ +---------+ +---------+ |
| | | | | |
+--|------|----------------|---------------- |----------+
| | | |
| | | |
| | | |
| | v |
| | +----+ |
| | +----| CA |---+ |
| | | +----+ | |
| | | | |
| | v v v
| | +----+ +----+ +----+
| | | CA |---+ | CA |-+ | CA |---+
| | +----+ | +----+ | +----+ |
| | | | | | | |
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 7]
Certification Path Building February 2003
| | | | | | | |
v v v v v v v v
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
Figure 2 ű Multi-Rooted Hierarchical PKI
1.3.2 Mesh Structures
In a typical mesh style PKI (depicted in Figure 3), each subscriber
trusts the CA that issued their own certificate(s). The CAs in this
environment have a peer relationship and are neither superior nor
subordinate to each other. In a mesh, CAs in the PKI cross-certify.
That is, each CA issues a certificate to, and is issued a certificate
by, peer CAs in the PKI. The figure depicts a mesh PKI that is fully
cross-certified (sometimes called a full mesh); however it is
possible to architect and deploy a mesh PKI with a mixture of
unidirectional and bi-directional cross-certifications (called a
partial mesh).
cross certified +-------+ cross certified
+---------------->| CA |<----------------+
| +-------+ |
| | | |
| | | |
| v v |
| +----+ +----+ |
| | EE | | EE | |
| +----+ +----+ |
v v
+------+ +------+
| CA |<--------------------------------->| CA |-----+
+------+ cross certified +------+ |
| | | | |
| | | | |
v v v v v
+----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+
Figure 3 - Mesh PKI
Certification path building in a mesh PKI is more complex than in a
hierarchical PKI due to the likely existence of multiple paths
between a relying partyĆs trust anchor and the certificate to be
verified. These multiple paths increase the potential for creating
"loops", "dead ends", or invalid paths while building the
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 8]
Certification Path Building February 2003
certification path between a trusted Root CA certificate and a target
certificate.
1.3.3 Bi-lateral Cross-Certified Structures
PKIs can be connected via cross-certification to enable the relying
parties of each to verify and accept certificates issued by the other
PKI. If the PKIs are hierarchical, cross-certification will
typically be accomplished by each root CA issuing a certificate for
the other PKIĆs root CA. This results in a slightly more complex,
but still essentially hierarchical environment. If the PKIs are mesh
style, then a CA within each PKI is selected, more or less
arbitrarily, to establish the cross-certification, effectively
creating a larger mesh PKI. Figure 4 depicts a hybrid situation
resulting from a hierarchical PKI cross-certifying with a mesh PKI.
PKI 1 and 2 cross certificates
+-------------------------------+
| |
| v
| +------+
| +-----| CA |-----+
| | +------+ |
| | PKI 1 Root |
| v v
| +------+ +------+
v PKI 2 Root +-| CA |-+ | CA |
+------+ | +------+ | +------+
+------->| CA |<-----+ | | | | |
| +------+ | | | | | |
| | | | v v v v v
| | | | +----+ +----+ +----+ +----+ +----+
| v v | | EE | | EE | | EE | | EE | | EE |
| +----+ +----+ | +----+ +----+ +----+ +----+ +----+
| | EE | | EE | |
| +----+ +----+ |
v v
+------+ +------+
| CA |<-------------->| CA |------+
+------+ +------+ |
| | | | |
| | | | |
v v v v v
+----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+
Figure 4 - Hybrid PKI
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 9]
Certification Path Building February 2003
In current implementations, this situation creates a concern that the
applications used under the hierarchical PKIs will not have path
building capabilities robust enough to handle this more complex
certificate graph. As the number of cross-certified PKIs grows, the
number of the relationships between them grows exponentially. Two
principal concerns about cross-certification are the creation of
unintended trust paths through transitive trust, and the dilution of
assurance when a high-assurance PKI with restrictive operating
policies is cross-certified with a PKI with less restrictive
policies.
1.3.4 Bridge Structures
Another approach to the interconnection of PKIs is the use of a
"bridge" certification authority (BCA). A BCA is a nexus to
establish trust paths among multiple PKIs. The BCA cross-certifies
with one CA (known as a "principal" CA [PCA]) in each participating
PKI. Since each PKI only cross-certifies with one other CA (i.e.,
the BCA), and the BCA cross-certifies only once with each
participating PKI, the number of cross certification relationships in
the bridged environment grows linearly with the number of PKIs,
whereas the number of cross certification relationships in mesh
architectures grows exponentially (n**2). However, when connecting
PKIs in this way, the number and variety of PKIs involved results in
a non-hierarchical environment, such as the one as depicted in Figure
5.
PKI 1 cross certified with Bridge
+-------------------------------+
| |
v v
+-----------+ +------+
| Bridge CA | +-----| CA |-----+
+-----------+ | +------+ |
^ | PKI 1 Root |
PKI 2 cross|cert with Bridge v v
| +------+ +------+
v PKI 2 Root +-| CA |-+ | CA |
+------+ | +------+ | +------+
+------->| CA |<-----+ | | | | |
| +------+ | | | | | |
| | | | v v v v v
| | | | +----+ +----+ +----+ +----+ +----+
| v v | | EE | | EE | | EE | | EE | | EE |
| +----+ +----+ | +----+ +----+ +----+ +----+ +----+
| | EE | | EE | |
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 10]
Certification Path Building February 2003
| +----+ +----+ |
v v
+------+ +------+
| CA |<-------------->| CA |------+
+------+ +------+ |
| | | | |
| | | | |
v v v v v
+----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+
Figure 5 ű Cross-Certification with a Bridge CA
1.4 Bridge Structures and Certification Path Processing
A developer building a certificate-enabled application intended for
widespread use throughout various industrial sectors should consider
supporting a Bridge PKI structure because 1) Bridge PKI structures
are becoming widely accepted as a way of interconnecting PKIs to
achieve large-scale interoperability, and 2) implementation of
certification path processing functions to support a Bridge PKI
structure will support all other PKI structures. (e.g.,
hierarchical, mesh, hybrid) This is true because a Bridge PKI
environment can potentially connect any or all of the PKI structures.
An application that can successfully construct valid certification
paths in all Bridge PKIs will have by default implemented all of the
processing logic required to support the less diverse PKI structures.
As a result, a PKI-enabled application that fully supports the Bridge
PKI structure can be deployed in any standards compliant PKI
environment and should perform the required certification path
processing properly.
2. Certification Path Building
Certification path building is the process by which the certificate
processing system obtains the certification path between a trusted
public key and the target certificate. Different implementations can
build the certification path in different ways; therefore, it is not
the intent of this paper to recommend a single "best" way to perform
this function. Rather, guidance is provided on the technical issues
that surround the path building process, and the capabilities a path
building implementation must have in order to build certification
paths successfully, irrespective of PKI structures.
2.1 Introduction to Certification Path Building
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 11]
Certification Path Building February 2003
A certification path is an ordered list of certificates starting with
a certificate that can be validated by one of the relying partyĆs
trusted public keys, and ending with the certificate to be validated.
(The certificate to be validated is referred to as the "target
certificate" throughout this document.) Though not required, as a
matter of convenience these trusted public keys are typically placed
in their own self signed certificates and are frequently called
trusted root certificates. The intermediate certificates that
comprise the certification path may be retrieved by any means
available to the validating application. These sources may include
LDAP, HTTP, SQL, a local cache or certificate store, or as part of
the security protocol itself as is common practice with signed S/MIME
messages.
Figure 6 shows an example of a certification path. In this figure,
the arrows represent certificates.
+---------+ +-----+ +-----+ +-----+ +--------+
| Trusted |----->| CA |---->| CA |---->| CA |---->| Target |
| Root | | | A | | | B | | | C | | | EE |
+---------+ | +-----+ | +-----+ | +-----+ | +--------+
| | | |
| | | |
v v v v
Cert 1 Cert 2 Cert 3 Cert 4
A(Trust Root) B(A) C(B) Target(C)
Figure 6 ű Example Certification Path
Unlike certification path validation, certification path building is
not addressed by the standards that define the semantics and
structure of a PKI. However, the ability to construct or build a
valid certification path is of paramount importance for applications
that rely on a PKI. Absent valid certification paths, the trust that
underpins the infrastructure is also absent, effectively rendering
the PKI useless. So, the ability to build a path is every bit as
important as the ability to properly validate them.
There are many issues that can complicate the path building process.
For example, building a path through a cross-certified environment
could require the path-building module to traverse multiple PKI
domains spanning multiple directories, using multiple algorithms, and
employing varying key lengths. A path-building client may also, for
example, need to manage a number of trusted root certificates,
partially populated directory entries (e.g., missing forward cross
certificates.), parsing of certain certificate extensions (e.g.,
authorityInformationAccess) and directory attributes
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 12]
Certification Path Building February 2003
(e.g.,crossCertificatePair), and error handling such as loop
detection.
In addition, a developer must also decide whether to construct paths
from a trusted root (the reverse direction) to the target certificate
or from the target certificate (the forward direction) to a trusted
root. Some implementations may decide to use both. The choice a
developer makes should be dependant on the environment and the
underlying PKI for that environment. For example, if the
infrastructure is compliant with the Internet X.509 Public Key
Infrastructure LDAPv2 Schema (RFC 2587), a developer can build
certification paths in the forward (from target) direction. However,
not all PKIs are compliant with RFC2587. An infrastructure may not
populate the forward cross-certificates and instead only populate the
reverse (fromThisCA) entries, in which case building in reverse will
be a developerĆs only viable option. Note that a PKI that does
comply with RFC2587 may or may not populate the reverse (fromThisCA)
entry; so building in reverse may or may not work in compliant
systems.
2.2 Path Building Algorithms
It is intuitive for people familiar with the Bridge CA concept or
mesh type PKIs to view path building as traversing a complex graph.
However, from the simplest viewpoint, writing a path-building module
can be nothing more than a simple tree traversal. In fact, even in a
very complex cross-certified environment, it can still be a tree
traversal. Complex environments can be traversed using spanning tree
algorithm, much like simple hierarchal PKIs, because there is little
benefit derived from revisiting a node (X.509 has a similar
requirement for not including the same certificate in a certification
path more than once). Figure 7 below illustrates this concept from
the trusted rootĆs perspective.
+---------+ +---------+
| Trusted | | Trusted |
| Root | | Root |
+---------+ +---------+
| | | |
| | | |
v v v v
+---+ +---+ +---+ +---+
| A |<-->| C | +--| A | | C |--+
+---+ +---+ | +---+ +---+ |
| | | | | |
| +---+ | v v v v
+->| B |<-+ +---+ +---+ +---+ +---+
+---+ | B | | C | | A | | B |
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 13]
Certification Path Building February 2003
| +---+ +---+ +---+ +---+
| | | | |
| | | | |
v v | | v
+----+ +----+ | | +----+
| EE | | EE | | | | EE |
+----+ +----+ | | +----+
v v
A certificate graph with +---+ +---+
bi-directional cross cert. | B | | B |
Between CAs A and C. +---+ +---+
| |
| |
v v
+----+ +----+
| EE | | EE |
+----+ +----+
The same certificate graph
rendered as a tree ű the
way path building software
could see it.
Figure 7 ű Simple Certificate Graph ű From Root Tree Depiction
When viewed from this perspective, all PKIs look like hierarchies
emanating from the trusted root at the leaves of the tree. An
infrastructure can be depicted in this way regardless of how complex
it is ű this greatly simplifies software design. In Figure 8, the
same graph is depicted from the end entity (EE) (the target
certificate in this example) perspective. It would appear this way
if building in the forward (from EE or from target) direction. In
this example, without knowing any particulars of the certificates, it
appears at first that building from EE has a smaller decision tree
than building from the trusted root. While it is true that there are
fewer nodes in the tree, it is not necessarily any more efficient.
+---------+ +---------+
| Trusted | | Trusted |
| Root | | Root |
+---------+ +---------+
^ ^
| |
| |
+---+ +---+
| A | | C |
+---+ +---+
+---------+ ^ ^ +---------+
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 14]
Certification Path Building February 2003
| Trusted | | | | Trusted |
| Root | | | | Root |
+---------+ | | +---------+
^ | | ^
| +---+ +---+ |
+-------| C | | A |---------+
+---+ +---+
^ ^
| |
| +---+ |
+---------| B |------+
+---+
^
|
|
+----+
| EE |
+----+
The same certificate graph rendered
as a tree but from the end entity
rather than the trusted root.
Figure 8 ű Certificate Graph ű From Target Certificate Depiction
Suppose a path building algorithm performed no optimizations ű that
is, it is only capable of detecting that the current node (position
in the tree) was issued by the trusted root, or that it issued the
target certifcate (EE). From the tree above, building from the
target certificate will require going through two intermediate
certificates before encountering a certificate issued by the trusted
root 100% of the time (e.g., EE chains to B, which then chains to C,
which is issued by the TR). The path building module would not chain
C to A because it can recognize that C has a certificate issued by
the TR.
On the other hand, in the first tree (Figure 7: from root depiction),
there is a 50% probability of building a path longer than needed
(e.g., TR to A to C to B to EE rather than the shorter TR to A to B
to EE). However, even given our simplistic example, the path
building software ű when at A ű could be designed to recognize that
B's subject distinguished name matches the issuer distinguished name
of the EE. Given this one optimization, the builder could use B in
preference to C. (BĆs subject distinguished name matches that of the
EEĆs issuer whereas CĆs subject distinguished name does not.) So,
for this example, assuming the reverse (fromThisCA) and forward
(toThisCA) elements were fully populated in the directory and our
path building module implemented the aforementioned distinguished
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 15]
Certification Path Building February 2003
name matching optimization method, path building from either the root
or the target certificate could be made roughly equivalent. A list
of possible optimization methods is provided later in this document.
What about more complicated examples? What about an environment
where more than one root is trusted? The number of trusted roots
should weigh heavily upon the decision to build in the reverse
direction. If, for sake of argument, it required a fixed amount of
network access to build all the possible paths either to or from a
given CA, what should be expected if there are four trusted root CAs?
Suppose that building paths either from the target certificate or
from the root for any given root or target certificate will require N
time. In the from root (reverse) direction, the path building
software potentially needs to build paths from all 4 trusted CAs, so
as much as 4*N. Assuming a path exists, and if N were 10 seconds,
one would expect an average delay of 20 (4*10 / 2) seconds when
building from the root. In the from target certificate (forward)
direction (and using the same example), path building software would
only require 10 (1*N) seconds, only 40% of the average time required
when building from the root. As the number of trusted roots
increases, so does the average time it takes to find a path if one
does exist. In the degenerate case where no path exists, attempting
to build from the same four trusted roots should consume 40 seconds,
whereas building from the end entity would consume at most 10
seconds.
+-----+ +-----+ +-----+ +-----+
| TR1 | | TR2 | | TR3 | | TR4 |
+-----+ +-----+ +-----+ +-----+
/ \ / \ / \ / \
/ \ / \ / \ / \
v v v v v v v v
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| R |<->| S | | F | | G | | F |<->| G | |<A>| | C |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
\ / / \ \ | / | /\ |
\ / / \ \ | / | / \ |
v v v v v v v v v v v
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| T | | B | | D | | E | | H |<->| I | | B | |<D>| | E |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
/ \ \ \ / \ |
/ \ \ \ / \ |
v v v v v v v
+---+ +---+ +---+ +---+ +---+ +----+
| U | | V | | F | | J |<->| K | |<EE>|
+---+ +---+ +---+ +---+ +---+ +----+
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 16]
Certification Path Building February 2003
Building from the root (reverse) may require traversal of
multiple PKIs and unneeded paths to find the target EE.
+-----+ +-----+ +-----+ +-----+
| TR1 | | TR2 | | TR3 | | TR4 |
+-----+ +-----+ +-----+ +-----+
/
/
v
+---+
|<A>|
+---+
\
\
v
+---+
|<D>|
+---+
|
|
v
+----+
|<EE>|
+----+
Building from the target certificate eliminates
inapplicable PKIs (those that are not cross certified
with the required one) from the path building process.
Figure 9 ű Reverse and Forward Path Building
with Multiple Trust Roots
As Figure 9 depicts, when multiple trusted roots are present, it can
be many times more efficient to build certification paths starting
from the target certificate. As the number of roots increases, so
does the inefficiency of building paths from the trusted roots. As a
result, any certificate using system supporting multiple trusted CAs
should consider developing paths in the forward (from target
certificate) direction.
Irrespective of the path building approach for any path-building
algorithm, cases can be constructed that make the algorithm perform
poorly. The following questions should help a developer decide from
which direction to build certification paths for a particular
environment:
1) What is required to accommodate the local PKI environment?
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 17]
Certification Path Building February 2003
A) Is the directory RFC2587 compliant (Specifically, are the
forward [IssuedtoThisCA] cross-certificates or the
cACertificate attribute populated in the directory)? If yes,
you are able to build in the forward direction.
B) Does the directory contain all the optional reverse cross
certificates (IssuedByThisCA) in the crossCertificatePair
attribute? If yes, it is possible to build in the reverse
direction.
2) What PKI environments must be interoperated with?
A) Are the other directories RFC2587 compliant? If yes, it is
possible to build in the forward direction.
B) Do the directories contain all the optional reverse cross
certificates (IssuedByThisCA) in the crossCertificatePair
attribute? If yes, it is possible to build in the reverse
direction.
3) How many root certificates (or keys) will be trusted by the path
building and validation software?
A) Are there (or will there be) multiple trusted roots in the
local PKI? If yes, forward path building may offer better
performance.
B) Will all the PKIs that the path building and validation
software needs to deal with, populate IssedByThisCA element
fully (i.e., for all CA certificates) for all CA nodes? If
yes, only then reverse path building is an option.
2.3 How to Build a Certification Path
As it was discussed in the prior section, path building is
essentially a tree traversal. It was easy to see how this is true in
a simple example, but how about a more complicated one? Before taking
a look at a complicated scenario, it is worthwhile to address loops
and what constitutes a loop in a certification path. X.509 specifies
that the same certificate may not repeat in a path. In a strict
sense, this works well as it is not possible to create an endless
loop without repeating one or more certificates in the path.
However, this requirement fails to adequately address Bridge CA
environments.
+---+ +---+
| F |--->| H |
+---+ +---+
^ ^ ^
| \ \
| \ \
| v v
| +---+ +---+
| | G |--->| I |
| +---+ +---+
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 18]
Certification Path Building February 2003
| ^
| /
| /
+------+ +-----------+ +------+ +---+ +---+
| TR W |<----->| Bridge CA |<------>| TR X |-->| L |-->| M |
+------+ +-----------+ +------+ +---+ +---+
^ ^ \ \
/ \ \ \
/ \ \ \
v v v v
+------+ +------+ +---+ +---+
| TR Y | | TR Z | | J | | N |
+------+ +------+ +---+ +---+
/ \ / \ | |
/ \ / \ | |
/ \ / \ v v
v v v v +---+ +----+
+---+ +---+ +---+ +---+ | K | | EE |
| A |<--->| C | | O | | P | +---+ +----+
+---+ +---+ +---+ +---+
\ / / \ \
\ / / \ \
\ / v v v
v v +---+ +---+ +---+
+---+ | Q | | R | | S |
| B | +---+ +---+ +---+
+---+ |
/\ |
/ \ |
v v v
+---+ +---+ +---+
| E | | D | | T |
+---+ +---+ +---+
Figure 10 ű Four Bridged PKIs
Figure 10 depicts four root certification authorities cross-certified
with a Bridge CA (BCA). By building certification paths through the
BCA, trust can be extended across the four infrastructures. When
looking at Figure 10, note that the boxes do not represent
certificates, but rather entities (i.e., Distinguished Name or DN).
The certificates are represented by the arrows between the entities
in the boxes. Thus, the BCA has four certificates issued to it; one
issued from each of the trust roots in the graph. If a directory
system is used to store certificates in the Bridge CAs directory
entry, the four certificates issued to the BCA would be stored in the
forward (or "toThisCA") entry of four different crossCertificatePair
structures. The BCA also has issued four certificates, one to each
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 19]
Certification Path Building February 2003
of the trust roots. If stored in the BCA directory system, those
certificates would be stored in the reverse or (or "fromThisCA")
entry of the same four crossCertificatePair structures. The four
CertificatePair structures would then be stored in the BCA's
directory entry in the crossCertificatePair attribute.
When building paths, a developer must make certain not to repeat
certificates in order to comply with X.509. For instance, from the
figure above, do not build the path E->B->C->A->C->A->Y. Not only is
the repetition unnecessary to build the path from E to Y, but it also
requires the reuse of a certificate (the one issued from C to A),
which is non-compliant with X.509.
What about the following path from EE to TR Z?
EE->N->L->X->BCA->W->BCA->Y->BCA->Z
Unlike the first example, this path does not require a developer to
repeat any certificates ű therefore, it is compliant with X.509.
Each of the BCA certificates is issued from a different source and is
therefore a different certificate. Suppose now that the bottom left
PKI (in Figure 10) had double arrows between Y and C, as well as
between Y and A. The following path could then be constructed:
EE->N->L->X->BCA->W->BCA->Y->C->A->Y->BCA->Z
A path such as this could become arbitrarily complex and traverse
every cross certified CA in every PKI in a cross-certified
environment while still remaining compliant with X.509. As a
practical matter, the path above is not something an application
would typically want, nor should it be necessary, to construct for a
variety of reasons:
- First, certification paths like the example above are generally
not intended by the PKI designers and should not be necessary
in order to validate any given certificate. If a convoluted
path such as the example above is required (there is no
corresponding simple path) in order to validate a given
certificate, this is most likely indicative of a flaw in the
PKI design. In other words, consumption of such paths by
relying parties could potentially yield trust in unintended
ways.
- Second, the longer a path becomes, the greater the potential
dilution of trust in the certification path. That is, with
each successive link in the infrastructure (i.e., certification
by CAs and cross-certification between CAs) some amount of
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 20]
Certification Path Building February 2003
assurance may be considered lost.
- Third, the longer and more complicated a path, the less likely
it is to validate because of policy, name constraints, CRL
availability, or even revocation.
- Lastly, and certainly not least important from a developer's or
application user's perspective, is performance. Allowing paths
like the one above dramatically increases the number of
possible paths for every certificate in a mesh or cross-
certified environment. Every path built may require one or
more of the following: validation, CPU intensive signature
validations, CRL retrievals, increased network load, and local
memory caching. Eliminating the superfluous paths can greatly
improve performance ű especially in the case where no path
exists.
How can these superfluous paths be eliminated? Rather than only
disallowing identical certificates from repeating, it is recommended
that a developer disallow the same public key and subject name pair
from being repeated. For maximum flexibility, the subject name
should collectively include any subject alternative names. Using
this rule, all of the intended and needed paths should be available,
and the excess and diluted paths should be eliminated. For example,
using this rule, only one path exists from the EE to Z in the diagram
above: EE->N->L->X->BCA->Z.
Given the simplifying rule of not repeating pairs of subject names
(including subject alternative names) and public keys, and only using
certificates found in the cACertificate and forward (IssuedtoThisCA)
element of the crossCertificatePair attributes, Figure 11 depicts all
the possible paths from the EE to all reachable nodes in the graph.
This is the ideal graph for a path builder attempting to build a path
from EE to Z.
+------+ +-----------+ +------+ +---+
| TR W |------>| Bridge CA |------->| TR X |-->| L |
+------+ +-----------+ +------+ +---+
^ ^ \
/ \ \
/ \ \
/ \ v
+------+ +------+ +---+
| TR Y | | TR Z | | N |
+------+ +------+ +---+
\
\
v
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 21]
Certification Path Building February 2003
+----+
| EE |
+----+
Figure 11 ű Forward (From Entity) Decision Tree
It is not possible to build paths into the infrastructures behind CAs
W, Y, and Z, because the other CA certificates (A, C, F, G, O, and P
shown in Figure 10) can only be found in the reverse (IssuedByThisCA)
element of the crossCertificatePair. If simplicity and speed is
desirable, the graph in Figure 11 is a very appealing way to
structure the path-building algorithm. Finding a path from the EE to
one of the four trusted roots is reasonably simple. Alternately, a
developer could choose to build in the opposite direction, using the
reverse cross-certificates from any one of the four trusted roots
around the BCA. The graph in Figure 12 depicts all possible paths as
a tree emanating from Z.
+---+ +---+
| I |--->| H |
+---+ +---+
^
| +---+ +---+
| | H |--->| I |
| +---+ +---+
+---+ ^
| G | / +---+ +---+ +---+
+---+ / | F |--->| H |--->| I |
^ / +---+ +---+ +---+
\ / ^
\/ /
+---+ +---+ +---+ +---+ +---+
| F | | G |--->| I |--->| H | | M |
+---+ +---+ +---+ +---+ +---+
^ ^ ^
| / |
+------+ +-----------+ +------+ +---+
| TR W |<------| Bridge CA |-------->| TR X |-->| L |
+------+ +-----------+ +------+ +---+
/ ^ \ \
v \ v v
+------+ +------+ +---+ +---+
| TR Y | | TR Z | | J | | N |
+------+ +------+ +---+ +---+
/ \ / \ \ \
v v v v v v
+---+ +---+ +---+ +---+ +---+ +----+
| A | | C | | O | | P | | K | | EE |
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 22]
Certification Path Building February 2003
+---+ +---+ +---+ +---+ +---+ +----+
/ \ / \ / \ \
v v v v v v v
+---+ +---+ +---+ +---+ +---+ +---+ +---+
| B | | C | | A | | B | | Q | | R | | S |
+---+ +---+ +---+ +---+ +---+ +---+ +---+
/ \ \ \ \ \ \
v v v v v v v
+---+ +---+ +---+ +---+ +---+ +---+ +---+
| E | | D | | B | | B | | E | | D | | T |
+---+ +---+ +---+ +---+ +---+ +---+ +---+
/ | | \
v v v v
+---+ +---+ +---+ +---+
| E | | D | | E | | D |
+---+ +---+ +---+ +---+
Figure 12 ű Reverse (From Root) Decision Tree
Given the relative complexity of this decision tree, it becomes clear
that making the right choices while navigating the tree can make a
large difference in how quickly a path is returned. The path
building software could potentially traverse the entire graph before
choosing the shortest path: Z->BCA->X->L->N->EE. With a decision
tree like the one above, the basic depth first traversal approach
introduces obvious inefficiencies in the path building process. To
compensate for this, a path building module not only needs to decide
in which direction to traverse the tree, but it should also decide
which branch of the tree is more likely to yield a usable path.
The path building algorithm then ideally becomes a tree traversal
algorithm with weights or priorities assigned to each branch point to
guide the decision making. If properly designed, such an approach
should effectively yield the "best path first" more often than not.
(The terminology "best path first" is quoted because the definition
of the "best" path may differ from PKI to PKI. That is ultimately to
be determined by the developer, not by this document.) Regardless of
the path building direction, a reasonable goal for every developer
should be to find the best path first, that being the one that is
most likely to validate, as often as possible, with the understanding
that there is no way to account for all possible configurations and
infrastructures.
So how should a developer go about finding the best path first?
Given the simplifying idea of addressing path building as a tree
traversal, path building can be structured as a depth first search.
A simple example of depth first tree traversal path building is
depicted in Figure 13, with no preference given to sort order.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 23]
Certification Path Building February 2003
Note: The arrows in the lower portion of the figure do not indicate
the direction of certificate issuance ű they indicate the direction
of the tree traversal from the target certificate (EE).
+----+ +----+ +----+
| TR | | TR | | TR |
+----+ +----+ +----+
/ \ ^ ^
/ \ | |
v v +---+ +---+
+---+ +---+ | A | | C |
| A |<->| C | +---+ +---+
+---+ +---+ ^ ^
^ ^ +----+ | | +----+
\ / | TR | | | | TR |
v v +----+ | | +----+
+---+ ^ | | ^
| B | \ | | /
+---+ \ | | /
/ \ +---+ +---+
/ \ | C | | A |
v v +---+ +---+
+---+ +---+ ^ ^
| E | | D | | /
+---+ +---+ | /
+---+
Infrastructure | B |
+---+
^
|
+----+
| EE |
+----+
The Same Infrastructure
Represented as a Tree
+----+ +----+
| TR | | TR |
+----+ +----+
^ ^
| |
+---+ +---+
| A | | C |
+---+ +---+
+----+ ^ ^ +----+
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 24]
Certification Path Building February 2003
| TR | | | | TR |
+----+ | | +----+
^ | | ^
\ | | /
\ | | /
+---+ +---+ +---+ +---+
| C | | C | | A | | A |
+---+ +---+ +---+ +---+
^ ^ ^ ^
| | / /
| | / /
+---+ +---+ +---+ +---+
| B | | B | | B | | B |
+---+ +---+ +---+ +---+
^ ^ ^ ^
| | | |
| | | |
+----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+
All possible paths from EE to TR
using a depth first tree traversal
Figure 13 ű Path Building Using a Depth First Tree Traversal
Figure 13 illustrates that four possible paths exist for this
example. Suppose that the last path (TR->A->B->EE) is the only path
that will validate. This could be for a number of reasons such as
name constraints, policy processing, validity periods, a path length
constraint, or a combination of reasons. The goal of an efficient
path-building component is to select the fourth path first by testing
properties of the certificates as the tree is traversed. For
example, when the path building software is at entity B in the graph,
it should examine both choices A and C to determine which certificate
is the most likely best choice. Hopefully it will conclude that A is
the more likely correct path. Then, at A, the module compares
terminating the path at TR, or moving to C. Again, hopefully the
module will make the better choice (TR) and thereby find the "best
path first".
What if the choice between CA certificates is not binary as it was in
the previous example? What if the path building software encounters
a branch point with some arbitrary number of CA certificates thereby
creating the same arbitrary number of tree branches? (This would be
typical in a mesh style PKI CA, or at a Bridge CA directory entry, as
each will have multiple certificates issued to itself from other
CAs.) This actually does not change the algorithm at all if it is
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 25]
Certification Path Building February 2003
structured properly. In our example, rather than treating each
decision as binary (i.e., choosing A or C), path building software
should sort all the available possibilities at any given branch
point, and then select the first one from the list. In the event the
path could not be built through the first choice, then the second CA
should be tried next upon traversing back to that point in the tree.
Continue following this pattern until a path is found or all CA nodes
in the tree have been traversed. Note that the certificates at any
given point in the tree should only be sorted at the time a decision
is first made. Specifically, in the example, the sorting of A and C
is done when the algorithm reached B. There is no memory resident
representation of the entire tree. Just like any other recursive
depth first search algorithm, the only information the algorithm
needs to keep track of is what nodes (entities) in the tree lie
behind it on the current path, and for each of those nodes, which
edges (certificates) have already been tried.
2.4 Suggested Path Building Software Components
There is no single way to define an interface to a path building
module; nor should there be. It is not the intent of this paper to
prescribe a particular method or semantic; rather, it is up to the
implementer to decide. There are many ways this could be done. For
example, a path-building module could construct every conceivable
path and return the entire list to the caller. Or, it could build
until it finds just one that validates and then terminate the
procedure. Or, it could build paths in an iterative fashion,
depending on validation outside of the builder and successive calls
to the builder to get more paths until one valid path is found or all
possible paths have been found. All of these are possible
approaches, and each of these may offer different benefits to a
particular environment or application.
Regardless of semantics, a path-building module needs to contain the
following components:
1) The logic for traversing the certificate graph.
2) Logic for retrieving the necessary certificates (and CRLs and/or
other revocation status information if the path is to be
validated) from the available source(s).
Assuming a more efficient and agile path building module is desired,
the following is a good starting point and will tie into the
remainder of this document. For a path-building module to take full
advantage of all the suggested optimizations listed in this document,
it will need all of the components listed below.
1) A local certificate and CRL cache.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 26]
Certification Path Building February 2003
A) This may be used by all certificate-using components - it
does not need to be specific to the path building software.
A local cache could be memory resident, stored in Microsoft
CAPI, stored in a database, or even stored in individual
files on the hard disk. While the implementation of this
cache is beyond the scope of this document, some design
considerations are describe later in Section ???.
2) The logic for traversing the certificate graph / tree.
A) This performs sorting functionality for prioritizing
certificates (and thereby optimizing path building) while
traversing the tree.
B) There is no need to build a complete graph prior to
commencing path building. Since path building can be
implemented as a depth first tree traversal, the path builder
only needs to store the current location in the tree along
with the points traversed to the current location. All
completed branches can be discarded from memory and future
branches are discovered as the tree is traversed.
3) Logic for retrieving the necessary certificates from the
available certificate source(s):
A) Local cache.
(i) Should be able retrieve all certificates for an entity by
subject name as well as individual certificates by
issuer and serial number tuple.
(ii) Tracking which directory attribute (including
IssuedtoThisCA and/or IssuedByThisCA) each certificate
was found in may be useful. This allows for
functionality such as retrieving only forward cross
certificates, etc.
(iii) A "freshness" timestamp (cache expiry time) can be used
to determine when the directory should be searched
again.
B) LDAPv3 directory for certificates and CRLs.
(i) Consider supporting multiple directories for general
queries.
(ii) Consider supporting dynamic LDAP connections for
retrieving CRLs using an LDAP URI in the CRL
distribution point certificate extension.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 27]
Certification Path Building February 2003
C) HTTP support for CRL distribution points and AIA support.
(i) Consider HTTPS support
4) A certification path cache that stores previously validated
relationships between certificates. This cache should include:
A) A configurable expiration date for each entry.
B) Support to store previously verified relationships between
two specific certificates.
2.5 Inputs to the Path Building Module
X.509 specifically addresses the list of inputs required for path
validation but makes no specific suggestions as to what could be
useful inputs to path building. However, given that the goal of path
building is to find certification paths that will validate, it
follows that the same inputs used for validation should be used to
optimize path building.
2.5.1 Required Inputs
The following are required inputs to the certification path building
process:
1) The Target Certificate - The certificate that is to be validated.
This is one end point for the path.
2) Trusted Root List ű This is the other endpoint of the path, and
can consist of either:
A) Trusted CA certificates
B) Trusted keys and distinguished names ű a certificate is not
necessarily required
2.5.2 Optional Inputs
In addition to the inputs defined in Section 2.5.1, the following
optional inputs can be useful for optimizing path building. However,
if the path building software takes advantage of all of the
optimization rules described later in this document, all of the
following optional inputs will be required.
1) Time (T) ű The time for which the certificate is to be validated
(e.g., if validating a historical signature from 1 year ago, T is
needed to construct a valid path).
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 28]
Certification Path Building February 2003
A) If not included as an input, the path building software
should always build for T equal to the current system time.
2) Initial-inhibit-policy-mapping indicator
3) Initial-require-explicit-policy indicator
4) Initial-any-policy-inhibit indicator
5) Initial user acceptable policy set
6) Error handlers (call backs or virtual classes)
7) Handlers for custom certificate extensions
8) Collection of certificates that may be useful in building the
path
9) Collection of certificate revocation lists and/or other
revocation data
The last two items are a matter of convenience. Alternately,
certificates and revocation information could be placed in a local
cache accessible to the path building module prior to attempting to
build a path.
3. Optimizing Path Building Functions
This section recommends methods for optimizing path building
processes.
3.1 Optimized Path Building
Path building can be optimized by sorting the certificates at every
decision point (at every node in the tree) and then selecting the
most promising certificate not yet selected. This process continues
until the path terminates. This is roughly equivalent to the concept
of creating a weighted edge tree, where the edges are represented by
certificates and nodes represent DNs.
The concept of statelessness with respect to nodes not in the current
path is instrumental to using the sorting optimizations listed in
this document. Initially, it may seem that sorting a given group of
certificates for a CA once and then preserving that sorted order for
later use would be an efficient way to write the path builder.
However, maintaining this state can quickly eliminate the efficiency
introduced by sorting. Consider the following diagram:
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 29]
Certification Path Building February 2003
+---+
| R |
+---+
^
/
v
+---+ +---+ +---+ +---+ +----+
| A |<----->| E |<---->| D |--->| Z |--->| EE |
+---+ +---+ +---+ +---+ +----+
^ ^ ^ ^
\ / \ /
\ / \ /
v v v v
+---+ +---+
| B |<----->| C |
+---+ +---+
In this example, the path builder is building in the forward (from
target) direction for a path between R and EE. The path builder has
also opted to allow subject name & key to repeat. (This will allow
multiple traversals through any of the cross certified CAs, creating
enough complexity in this small example to illustrate proper state
maintenance. Note that a similarly complex example could be designed
by using multiple keys for each entity and prohibiting repetition.)
The first step is simple; the builder constructs the path Z(D)-
>EE(Z). Now the builder adds D and faces a decision between two
certificates. (Choose between D(C) or D(E)) The builder should now
sort the two choices in order of priority. The sorting is partially
based upon what is currently in the path.
Suppose the order the builder selects is [D(E), D(C)]. The current
path is now D(E)->Z(D)->EE(Z). Currently the builder has three nodes
in the graph (EE, Z, and D) and should maintain the state, including
sort order of the certificates at D, when adding the next node, E.
When E is added, the builder now has four certificates to sort: E(A),
E(B), E(C), and E(D). In this case, the example builder opts for the
order [E(C), E(B), E(A), E(D)]. The current path is now E(C)->D(E)-
>Z(D)->EE(Z) and the path has four nodes; EE, Z, D, and E.
Upon adding the fifth node, C, the builder sorts the certificates
(C(B), C(D), and C(E)) at C, and selects C(E). The path is now C(E)-
>E(C)->D(E)->Z(D)->EE(Z) and the path has five nodes; EE, Z, D, E,
and C.
Now the builder finds itself back at node E with four certificates.
If the builder were to use the prior sort order from the first
encounter with E, it would have [E(C), E(B), E(A), E(D)]. In the
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 30]
Certification Path Building February 2003
current path's context, this ordering may be inappropriate. To begin
with, the certificate E(C) is already in the path so it certainly
does not deserve first place.
The best way to handle this situation is for the path builder to
handle this instance of E as a new (sixth) node in the tree. In
other words, there is no state information for this new instance of E
- it is treated just as any other new node. The certificates at the
new node are sorted based upon the current path content and the first
certificate is then selected. For example, the builder may examine
E(B) and note that it contains a name constraint prohibiting "C". At
this point in the decision tree, E(B) could not be added to the path
and produce a valid result since "C" is already in the path. As a
result, the certificate E(B) should placed at the bottom of the
prioritized list.
Alternatively, E(B) could be eliminated from this new node in the
tree. It is very important to see that this certificate is
eliminated ONLY at this node and ONLY for the current path. If path
building fails through C and traverses back up the tree to the first
instance of E, E(B) could still produce a valid path that does not
include C; specifically R->A->B->E->D->Z->EE. Thus the state at any
node should not alter the state of previous or subsequent nodes.
(Except for prioritizing certificates in the subsequent nodes.)
In this example, the builder should also note that E(C) is already in
the path and make it last or eliminate it from this node since
certificates can not be repeated in a path.
If the builder eliminates both certificates E(B) and E(C) at this
node, it is now only left to select between E(A) and E(D). Now the
path has six nodes; EE, Z, D, E(1), C, and E(2). E(1) has four
certificates, and E(2) has two, which the builder sorts to yield
[E(A), E(D)]. The current path is now E(A)->C(E)->E(C)->D(E)->Z(D)-
>EE(Z). A(R) will be discovered when the seventh node is added to
the path and the path terminated because one of the trusted root keys
has been found.
In the event the first path fails to validate, the path builder
should still have the seven nodes and associated state information to
work with. On the next iteration, the path builder is able to
traverse back up the tree to a working decision point, such as A, and
select the next certificate in the sorted list at A. In this
example, that would be A(B). (A(R) has already been tested.) This
would dead end, and the builder traverse back up to the next decision
point, E(2) where it would try D(E). This process repeats until the
traversal backs all the way up to EE or a valid path is found. If
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 31]
Certification Path Building February 2003
the tree traversal returns to EE, all possible paths have been
exhausted and the builder can conclude no valid path exists.
This approach of sorting certificates in order to optimize path
building will yield better results than not optimizing the tree
traversal. However, the path building process can be further
streamlined by eliminating certificates, and entire branches of the
tree as a result, as paths are constructed.
3.2 Sorting vs. Elimination
Consider a situation where there exists three CA certificates to
choose between at some point in building a path for a given target
certificate. When the certificates are examined, like in the
previous example, one of the three has a name constraint present that
will invalidate the path constructed thus far. When sorting the
three certificates, that one would certainly go to the back of the
line. However, the path building software could decide that this
condition should eliminate the certificate from consideration at this
point in the graph, thereby reducing the number of certificate
choices by 33% at this point.
NOTE: It is important to understand that the elimination of a
certificate only applies to a single decision point during the tree
traversal. The same certificate may appear again on another point in
the tree; at that point it may or may not be eliminated. The prior
section details an example of this behavior.
Elimination of certificates could potentially eliminate the traversal
of a large, time-consuming infrastructure that will never lead to a
valid path. The question of whether to sort or eliminate is one that
pits the flexibility of the software interface against efficiency.
To be clear, if one eliminates invalid paths as they are built,
returning only likely valid paths, the end result will be an
efficient path building module. The drawback to this is that unless
the software makes allowances for it the calling application will not
be able to see what went wrong. The user may only see the
unrevealing error message: "No certification path found."
On the other hand, the path building module could opt to not rule out
any certification paths. The path building software could then
return any and all paths it can construct from the certificate graph.
It is then up to the validation engine to determine which are valid
and which are invalid. The user or calling application can then have
complete details on why each and every path fails to validate. The
drawback is obviously one of performance, as an application or end
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 32]
Certification Path Building February 2003
user may wait for an extended period of time while cross-certified
PKIs are navigated in order to build paths that will never validate.
Neither option is a very desirable approach. One option removes a
performance burden on end users, which is always wise to do. The
other option though allows administrators to diagnose problems with
the PKI, directory, or software. Below are some recommendations to
reach a middle ground on this issue.
First, developers are strongly encouraged to output detailed log
files from the path building software. The log should explicitly
indicate every choice the builder makes and why. It should clearly
identify which certificates are found and used at each step in
building the path. If care is taken to produce a useful log file,
PKI administrators and help desk personnel should have ample
information to diagnose a problem with the PKI. Ideally, there
should be a mechanism for turning this logging on and off, so that it
is not running all the time.
Secondly, it is desirable to return something useful to the user.
The easiest approach is probably to implement a "dual mode" path
building module. In the first mode [mode 1], the software eliminates
any and all paths that will not validate, making it very efficient.
In the second mode [mode 2], all the sorting rules are still applied,
but no paths are eliminated based upon the rules. Having this dual
mode allows the module to first fail to find a valid path, but still
return one invalid path (assuming one exists) by switching over to
the second mode long enough to generate a single path. This provides
a middle ground ű the software is very fast, but still returns
something that gives the user a more specific error than "no path
found".
Ultimately, it is up to the developer to determine how to handle the
tradeoff between efficiency and provision of information. A
developer could choose the middle ground by opting to implement some
optimizations as elimination rules and others as not. A developer
could validate certificate signatures, or even check revocation
status while building the path, and then make decisions based upon
the outcome of those checks as to whether to eliminate the
certificate in question.
This document suggests the following approach:
1) While building paths, eliminate any and all certificates that do
not satisfy all path validation requirements with the following
exceptions:
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 33]
Certification Path Building February 2003
A) Do not check revocation status if it requires a directory
lookup or network access
B) Do not check signatures
C) Do not check anything that can not be checked as part of the
iterative process of traversing the tree
D) Write a detailed log file, if this feature is enabled
E) If a path cannot be found, the path builder shifts to "mode
2" and allows the building of a single bad path.
(i) Return the path with a failure indicator as well as error
information detailing why the path is bad.
2) If path building succeeds, validate the path in accordance with
[X.509] and [RFC 3280] with the following recommendations:
A) For a performance boost, do not re-check items already
checked by the path builder. (Note: if the software interface
allows validation of user supplied paths, the validation
component must perform full validation on those paths.)
B) If the path validation failed, call the path builder again to
build another path
(i) Always store the error information and path from the
first iteration ű return this to the user in the event
no valid path is found. Since the path building
software was designed to return the "best path first",
this is the path that should be shown to the user.
As stated above, this document recommends that developers do not
validate signatures or check revocation status as part of the path
building process. This recommendation is based on two assumptions
about PKI and its usage. First, signatures in a working PKI are
almost always good. Since signature validation is a costly process
from a CPU standpoint, it is better to delay signature checking until
a complete path is found. Second, it is fairly uncommon in typical
application environments to encounter a revoked key; therefore, most
certificates validated will not be revoked. As a result, it is
better to delay retrieving CRLs, or other revocation status
information, until a complete path has been found, thereby reducing
the probability of retrieving unneeded revocation status information
while building paths.
3.3 Path Building Optimization
The following sections describe methods that may be used for
optimizing the certification path building process by sorting
certificates. Optimization as described earlier seeks to prioritize
a list of certificates, effectively prioritizing (weighting) branches
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 34]
Certification Path Building February 2003
of the graph / tree, the optimization methods should be used to
assign a cumulative score to each certificate. The process of scoring
the certificates amounts to testing each certificate against the
optimization methods a developer chooses to implement, and then
adding the score for each test to a cumulative score for each
certificate. After this is completed for each certificate at a given
branch point in the builder's decision tree, the certificates can be
sorted so that the highest scoring certificate is selected first, the
second highest is selected second, etc.
For example, suppose the path builder has only these two simple
rules:
1) If the certificate has a subject key ID, +5 to score
2) If the certificate has an authority key ID, +10 to score
And it then examined three certificates:
1) Issued by CA 1; has authority key ID; score is 10
2) Issued by CA 2; has subject key ID; score is 5
3) Issued by CA 1; has subject key ID and authority key ID; score is
15
The three certificates are sorted in descending order starting with
the highest score: 3, 1, and 2. The path building software should
first try building the path through certificate 3. Failing that, it
should try certificate 1. Lastly, it should try building a path
through certificate 2.
The following optimization methods specify tests developers may
choose to perform, but does not suggest scores for any of the
methods. Rather, developers should evaluate each method with respect
to the environment that the application will operate, and assign
weights to each accordingly in the path building software.
Additionally, many of the optimization methods are not binary in
nature. Some are tri-valued, and some may be well suited to sliding
or exponential scales. Ultimately, it is up to the implementer to
decide the relative merits of each rule with respect to his or her
own software or infrastructure.
Over and above the scores for each method, many methods can be used
to eliminate branches during the tree traversal rather than simply
scoring and weighting them. All cases where certificates could be
eliminated based upon an optimization method are noted with the
method descriptions.
As a final note, many of the sorting methods described below are
based upon what has been perceived by the author as common in PKIs.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 35]
Certification Path Building February 2003
Many of the rules are aimed at making path development for common PKI
efficient, but there are cases where most any sorting rule could lead
path building astray. The assumption is that although one rule may
lead the algorithm in the wrong direction for a given situation or
configuration, the remaining rules will overcome the errant rule(s)
and send the path traversal down the correct branch of the tree more
often than not. This certainly will not be true for every
environment and configuration, and these methods may need to be
tweaked for further optimization in the applications target operating
environment. The list contained in this document is not intended to
be exhaustive. A developer may desire to define additional sorting
methods if the operating environment dictates the need.
3.3.1 Selected Methods for Sorting Certificates
Although an effort was made to order these sorting methods starting
with the stronger rules first, no specific conclusion should be drawn
as to relative merits or scores. The relative merit of any sorting
criteria is completely dependant on the specifics the operating
environment. For most any method, an example can be created to
demonstrate the method is effective. Alternately, an example could
be designed to demonstrate that it is ineffective.
Each rule is independent and may (or may not) be used to assign
additional scores to each certificate tested. It is up to the
implementer to decide which methods to use and what weights to assign
them. As noted previously, this list is also not exhaustive.
In addition, name chaining (The subject name of the issuer
certificate must match the issuer name of the issued certificate.) is
not addressed as a sorting rule since adherence to this is required
in order to build the decision tree to which these rules will be
applied. Also unaddressed in the sorting methods is the prevention
of repeating certificates. Path builders should handle these items
irrespective of optimization approach.
3.3.1.1 basicConstraints is Present and cA Equals True
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: Certificates with basicConstraints present and cA=TRUE
have priority. Certificates without basicConstraints, or with
basicConstraints and cA=FALSE may be eliminated or should have zero
priority.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 36]
Certification Path Building February 2003
Reverse Rule: Same as forward except with regard to end entity
certificates at the terminus of the path.
Justification: According to RFC 3280, basicConstraints is required
to be present with cA=TRUE in all CA certificates. A valid path can
not be constructed if this condition is not met.
3.3.1.2 Recognized Signature Algorithms
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: Certificates containing recognized signature and
public key algorithms have priority.
Reverse Rule: Same as forward.
Justification: If the path building software is not capable of
processing the signatures associated with the certificate, the
certification path cannot be validated.
3.3.1.3 keyUsage is Correct
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: If keyUsage is present, certificates with keyCertSign
set have 100% priority. If keyUsage is present and keyCertSign is
not set, the certificate may be eliminated or have zero priority. All
others have zero priority.
Reverse Rule: Same as forward.
Justification: A valid certification path can not be constructed
through a CA certificate with inappropriate keyUsage. Note that
digitalSignature is NOT required to be set in a CA certificate.
3.3.1.4 Time (T) Falls within the Certificate Validity
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: Certificates that contain the required time (T) within
their validity period have 100% priority. Otherwise, the certificate
should be eliminated or have priority zero.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 37]
Certification Path Building February 2003
Reverse Rule: Same as forward.
Justification: A valid certification path cannot be constructed if T
falls outside of the certificate validity period.
NOTE: Special care should be taken to return a meaningful error to
the caller, especially in the event the target certificate does not
meet this rule, if this rule is used for elimination. (e.g., the
certificate is expired).
3.3.1.5 Certificate Was Previously Validated
May be used to eliminate certificates: No
Number of possible values: Binary
Components required: Certificate Path Cache
Forward Rule: A certificate that is present in the certification
path cache has priority.
Reverse Rule: Does not apply. (The validity of a certificate vs.
unknown validity does not infer anything about the correct direction
in the decision tree. In other words, knowing the validity of a CA
certificate does not indicate that the target is more likely found
through that path than another.)
Justification: Certificates in the path cache have been validated
previously. There is some probability that the path from that
certificate to a trusted root is still valid.
Note: It is important that items in the path cache have appropriate
life times. For example, it could be inappropriate to cache a
relationship beyond the period the related CRL will be trusted by the
application. It is also critical to consider certificates and CRLs
farther up the path when setting cache lifetimes. For example, if the
issuer cert expires in ten days, but the issued certificate is valid
for 20 days, caching the relationship beyond 10 days would be
inappropriate.
3.3.1.6 Previously Verified Signatures
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: Path Cache
Forward Rule: If a previously verified relationship exists in the
path cache between the subject certificate and a public key present
in one or more issuer certificates, all the certificates containing
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 38]
Certification Path Building February 2003
said public key have higher priority. Other certificates may be
eliminated or set to zero priority.
Reverse Rule: Does not apply. (Although the path cache does contain
one to one relationships in reverse, nothing can be concluded about
the likelihood of finding a given target certificate down one branch
versus another using this rule.)
Justification: If the public key in a certificate (A) was previously
used to verify a signature on a second certificate (B), any and all
certificates containing the same key as (A) may be used to verify the
signature on (B). Likewise, any certificates that do not contain the
same key as (A) cannot be used to verify the signature on (B). This
forward direction rule is especially strong for multiply cross-
certified CAs after a key rollover has occurred.
3.3.1.7 Path Length Constraints
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: Certificates with basic constraints present and
containing a path length constraint that would invalidate the current
path (the current length is known since the software is building from
the target certificate) may be eliminated or set to zero priority.
Otherwise, the priority is 100%.
Reverse Rule: This rule may be applied in reverse, but the benefit
is likely less than that of the forward direction. To apply it, the
builder keeps a current path length constraint variable and then sets
zero priority for (or eliminates) certificates that would violate the
constraint.
Justification: A valid path cannot be constructed if the path length
constraint has been violated.
3.3.1.8 Name Constraints
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: Certificates that contain nameConstraints that would
be violated by certificates already in the path to this point should
have lower priority. (Or they may be eliminated.)
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 39]
Certification Path Building February 2003
Reverse Rule: Certificates that will allow successful processing of
any name constraints present in the path to this point should have
priority
Justification: A valid path cannot be constructed if name
constraints are violated.
3.3.1.9 Certificate is Not Revoked
May be used to eliminate certificates: No
Number of possible values: Three
Components required: CRL Cache
Forward Rule: If a current CRL for a certificate is present in the
CRL cache, and the certificate serial number is not on the CRL, the
certificate has priority. If the certificate serial number is
present on the CRL, it has zero priority.
Reverse Rule: Same as Forward.
Alternately, the certificate may be eliminated if the CRL is
verified. That is, fully verify the CRL signature and relationship
to the certificate in question in accordance with RFC 3280. While
this is viable, the signature verifications required make it less
attractive as an elimination rule. It is suggested that this rule
only be used for sorting and that CRLs are validated post path
building.
Justification: Certificates known to be not revoked should be, on
average, more likely to be valid than certificates for which the
revocation status is unknown. This is further justified if CRL
validation is performed post path validation ű CRLs are only
retrieved when complete paths are found.
NOTE: Special care should be taken to allow meaningful errors to
propagate to the caller, especially in cases where the target
certificate is revoked. If a path builder eliminates certificates
using CRLs, some status information should be preserved so that a
meaningful error may be returned in the event no path is found.
3.3.1.10 Issuer Found in the Path Cache
May be used to eliminate certificates: No
Number of possible values: Binary
Components required: Certificate Path Cache
Forward Rule: A certificate whose issuer has an entry (or entries)
in the path cache has priority.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 40]
Certification Path Building February 2003
Reverse Rule: Does not apply.
Justification: Since the path cache only contains entries for
certificates that were previously validated back to a trusted root,
it is more likely than not that the same or a new path may be
constructed from that point to the (or one of the) trusted root(s).
For certificates whose issuers are not found in the path cache,
nothing can be concluded.
NOTE: This rule is not the same as the preceding rule. It is
possible for this rule to evaluate to true while the preceding rule
could evaluate to zero.
3.3.1.11 Matching Key Identifiers (KIDs)
May be used to eliminate certificates: No
Number of possible values: Three
Components required: None
Forward Rule: Certificates whose subject key identifier (SKID)
matches the current certificate's authority key identifier (AKID)
have highest priority. Certificates without a SKID have medium
priority. Certificates whose SKID does not match the current
certificate's AKID (if both are present) have zero priority. If the
current certificate expresses the issuer name and serial number in
the AKID, certificates that match both these identifiers have highest
priority. Certificates that match only the issuer name in the AKID
have medium priority.
Reverse Rule: Certificates whose AKID matches the current
certificate's SKID have highest priority. Certificates without an
AKID have medium priority. Certificates whose AKID does not match
the current certificate's SKID (if both are present) have zero
priority. If the certificate expresses the issuer name and serial
number in the AKID, certificates that match both these identifiers in
the current certificate have highest priority. Certificates that
match only the issuer name in the AKID have medium priority.
Justification: KID matching is a very useful mechanism for guiding
path building (that is their purpose in the certificate) and should
therefore be assigned a heavy weight.
NOTE: It is extremely important that KIDs be used ONLY as sorting
criteria ű KIDs are not required to match by any PKI standard and
must not be used to eliminate certificates. This is of critical
importance for interoperating across domains and multi-vendor
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 41]
Certification Path Building February 2003
implementations where the KIDs may not be calculated in the same
fashion.
3.3.1.12 Policy Processing
May be used to eliminate certificates: Yes
Number of possible values: Three
Components required: None
Forward Rule: Certificates that satisfy Forward Policy Chaining have
priority. (See the section entitled "Forward Policy Chaining" for
details.) If the caller provided an initial-policy-set and did not
set the initial-require-explicit flag, the weight of this rule should
be increased. If the initial-require-explicit-policy flag was set by
the caller or by a certificate, certificates may be eliminated.
Reverse Rule: Certificates that contain policies/policy mappings
that will allow successful policy processing of the path to this
point should have priority. If the caller provided an initial-
policy-set and did not set the initial-require-explicit flag, the
weight of this rule should be increased. Certificates may be
eliminated if initial-require-explicit was set by the caller or if
require-explicit-policy was set by a certificate in the path to this
point.
Justification: In a policy-using environment, certificates that
successfully propagate policies are more likely part of an intended
certification path than those that do not.
When building in the forward direction, it is always possible that a
certificate closer to the trusted root will set the require-explicit-
policy indicator; so giving preference to certificate paths that
propagate policies may increase the probability of finding a valid
path first. If the caller (or a certificate in the current path) has
specified or set the initial-require-explicit-policy indicator as
true, this rule can also be used to eliminate certificates when
building in the forward direction.
If building in reverse, it is always possible that a certificate
farther along the path will set the require-explicit-policy
indicator; so giving preference to those certificates that propagate
policies will serve well in that case. In the case where require-
explicit-policy is set by certificates or the caller, certificates
can be eliminated with this rule.
3.3.1.13 Policies Intersect The Sought Policy Set
May be used to eliminate certificates: No
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 42]
Certification Path Building February 2003
Number of possible values: Additive
Components required: None
Forward Rule: Certificates that assert policies found in the
initial-acceptable-policy-set should have priority. Each additional
matching policy could have an additive affect on the total score.
Alternately, this could be binary; it matches 1 or more, or matches
none.
Reverse Rule: Certificates that assert policies found in the target
certificate or map policies to those found in the target certificate
should have priority. Each additional matching policy could have an
additive affect on the total score. Alternately, this could be
binary; it matches 1 or more, or matches none.
Justification: In the forward direction, as the path draws near to
the trusted root certificate in a cross certified environment, the
policies asserted in the CA certificates should match those in the
caller's domain. Since the initial acceptable policy set is
specified in the caller's domain, matches may indicate that the path
building is drawing nearer to a desired trusted root. In the reverse
direction, finding policies that match those of the target
certificate may indicate the path is drawing near to the target's
domain.
3.3.1.14 Endpoint Distinguished Name Matching
May be used to eliminate certificates: No
Number of possible values: Binary
Components required: None
Forward Rule: Certificates whose issuer exactly matches a trusted
root subject DN have priority.
Reverse Rule: Certificates whose subject exactly matches the target
entity issuer DN have priority.
Justification: In the forward direction, if a certificate's issuer
DN matches a trusted root's DN, then it may complete the path. In
the reverse direction, if the certificate's subject DN matches the
issuer DN of the target certificate, this may be the last certificate
required to complete the path.
3.3.1.15 Relative Distinguished Name Matching
May be used to eliminate certificates: No
Number of possible values: Sliding Scale
Components required: None
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 43]
Certification Path Building February 2003
Forward Rule: Certificates that match more ordered RDNs between the
issuer DN and a trust anchor DN should have priority. When all the
RDNs match, this should yield the highest priority.
Reverse Rule: Certificates with subject DNs that match more RDNs with
the target's issuer DN should have higher priority. When all the
RDNs match, this should yield the highest priority.
Justification: In PKIs the DNs are frequently constructed in a tree
like fashion. Higher numbers of matches may indicate that the trust
root is to be found in that direction within the tree. Note that in
the 100% match case, this rule appears to mirror the preceding rule.
However, this rule should be capable of producing a 100% result even
if the issuer DN has more RDNs than the trust root. The Issuer DN
need only contain all the RDNs (in order) of the trust root.
NOTE: In the 100% match case, this rule mirrors the functionality of
the preceding rule. This allows for partial matches to be weighted
differently from exact matches. Additionally, this rule can be
particularly CPU intensive if many trusted roots are present.
3.3.1.16 Certificates are Retrieved from cACertificate
May be used to eliminate certificates: No
Number of possible values: Binary
Components required: Certificate Cache with flags for the attribute
from where the certificate was retrieved
Forward Rule: Certificates retrieved from the cACertificate
attribute have priority over certificates retrieved from the
crossCertificate attribute. (See RFC 2587)
Reverse Rule: Does not apply.
Justification: The cACertificate attribute contains certificates
issued from local sources and self issued certificates. By using the
cACertificate attribute before the crossCertificate attribute, the
path building algorithm will (depending on the local PKI
configuration) tend to demonstrate a preference for the local PKI
before venturing to external cross-certified PKIs. Not only do most
of today's PKI applications spend most of their time processing
information from the local (user's own) PKI, but the local PKI is
usually very efficient to traverse due to simplicity, proximity and
network speed.
3.3.1.17 Consistent Public Key and Signature Algorithms
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 44]
Certification Path Building February 2003
May be used to eliminate certificates: Yes
Number of possible values: Binary
Components required: None
Forward Rule: If the public key in the issuer certificate matches
the algorithm used to sign the subject certificate, then it priority.
(Certificates with unmatched public key and signature algorithms may
be eliminated.)
Reverse Rule: If the public key in the current certificate matches
the algorithm used to sign the subject certificate, then it has
priority. (Certificates with unmatched public key and signature
algorithms may be eliminated.)
Justification: Since the public key and signature algorithms aren't
consistent, the signature on the subject certificate will not
successfully. For example, if the issuer certificate contains an RSA
public key, then it could not have issued a subject certificate
signed with the DSA-with-SHA-1 algorithm.
3.3.1.18 Similar Issuer and Subject Names
May be used to eliminate certificates: No
Number of possible values: Sliding Scale
Components required: None
Forward Rule: Certificates that match more RDNs between the subject
DN and the issuer DN should have priority.
Reverse Rule: Same as forward.
Justification: As it is generally more efficient to search the local
domain prior to branching to cross-certified domains, using
certificates with similar names first tends to make a more efficient
path builder. Cross certificates issued from external domains will
generally match fewer RDNs (if any), whereas certificates in the
local domain will frequently match multiple RDNs.
3.3.1.19 Certificates in the Certification Cache
May be used to eliminate certificates: No
Number of possible values: Three
Components required: Local Certificate Cache and Remote Certificate
Storage / Retrieval (E.g., LDAP repository)
Forward Rule: A certificate whose issuer certificate is present in
the certificate cache (and populated with one or more certificates)
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 45]
Certification Path Building February 2003
has priority. A certificate whose issuer certificate is present in
the certificate cache and fully populated with recent data (all
certificate attributes have been searched within an appropriate
timeout period ű something shorter than cache expiry.) has higher
priority. (This helps reduce LDAP lookups until necessary.)
Reverse Rule: If an entity named by a reverse certificate is present
in the certificate cache and populated with certificates then it has
higher priority. If the entry is fully populated with current data
(all certificate attributes have been searched within the timeout
period.) then it has higher priority.
Justification: The presence of required directory values populated
in the cache increases the likelihood that all the required
certificates and CRLs needed to complete the path from this
certificate to the root (or target if building in reverse) are
present in the cache from a prior path being developed, thereby
eliminating the need for directory access to complete the path. In
the event no path can be found, the performance cost is low since the
certificates were likely not retrieved from the network.
3.3.1.20 Current CRL Found in Local Cache
May be used to eliminate certificates: No
Number of possible values: Binary
Components Required: CRL Cache
Forward Rule: Certificates have priority if the issuer's CRL entry
exists and is populated with current data in the CRL cache.
Reverse Rule: Certificates have priority if the subject's CRL entry
exists and is populated with current data in the CRL cache.
Justification: If revocation is checked only after a complete path
has been found, this indicates that a complete path has been found
through this entity at some past point, so a path still likely
exists. This also helps reduce LDAP lookups until necessary.
4. Forward Policy Chaining
It is tempting to jump to the conclusion that certificate policies
offer little to path building when building from the target
certificate. It's easy to understand the "validate as you go"
approach from the trusted root and much less obvious to some that any
value can be derived in the other direction. However, since policy
validation consists of the intersection of the issuer policy set with
the subject policy set and the mapping of policies from the issuer
set to the subject set, policy validation can be done while
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 46]
Certification Path Building February 2003
constructing a path in the forward direction as well as the reverse.
It is simply a matter of reversing the procedure. That is not to say
this is quite as ideal as policy validation when building from the
root, but it does offer a method that can be used to mostly eliminate
what has been long touted as a weakness inherent to building in the
forward (from the end entity or target certificate) direction.
4.1 Simple Intersection
The most basic form of policy processing is the intersection of the
policy sets from the first CA certificate through the target / end
entity certificate. Fortunately, the intersection of policy sets
will always yield the same final set regardless of the order of
intersection. This allows processing of policy set intersections in
either direction. For example, if the trusted root issues a CA
certificate (A) with policies {X,Y,Z}, and that CA issues another CA
certificate (B) with policies {X,Y}, and CA B then issues a third CA
certificate (C) with policy set {Y,G}, one normally calculates the
policy set from the root as follows:
1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}
2) Intersect that result, {X,Y} with C{Y,G} to yield the final set
{Y}
Now it has been shown that certificate C is good for policy Y.
The other direction is exactly the same procedure, only in reverse:
1) Intersect C{Y,G} with B{X,Y} to yield the set {Y}
2) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
{Y}
Just like in the reverse direction, it has been shown that
certificate C is good for policy Y, but this time in the forward
direction.
When building in the forward direction, policy processing is handled
in much the same fashion as it is in reverse ű the software should
lend preference to certificates that propagate policies. Neither
approach guarantees that a path with valid policies will be found,
but rather both approaches help guide the path in the direction it
should go in order for the policies to propagate.
If the caller has supplied an initial-acceptable-policy set, there is
less value in using it when building in the forward direction unless
the caller also set inhibit-policy-mapping. In that case, the path
builder can further constrain the path building to propagating
policies that exist in the initial-acceptable-policy-set. However,
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 47]
Certification Path Building February 2003
even if the inhibit-policy-mapping is not set, the initial-policy-set
can still be used to guide the path building toward the desired trust
anchor.
4.2 Policy Mapping
When a CA issues a certificate into another domain ű an environment
with disparate policy identifiers to its own ű the CA may make use of
policy mappings to map equivalence from the local domain's policy to
the foreign domain's policy. If in the prior example, A had included
a policy mapping that mapped X to G in the certificate it issued to
B, C would be good for X and Y:
1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}
2) Process Policy Mappings in B's certificate (X maps to G) to yield
{G,Y} (same as {Y,G})
3) Intersect that result, {G,Y} with C{Y,G} to yield the final set
{G,Y}
Since policies are always expressed in the relying party's domain,
the certificate C is said to be good for {X, Y}, not {Y, G}. This is
because "G" doesn't mean anything in the context of the trusted root
that issued A without the policy mapping.
When building in the forward direction, policies can be "unmapped" by
reversing the mapping procedure. This procedure is limited by one
important aspect; if policy mapping has occurred in the forward
direction, there is no mechanism by which it can be known in advance
whether or not a future addition to the current path will invalidate
the policy chain (assuming one exists) by setting inhibit-policy-
mapping. Fortunately, it is uncommon practice to set this flag. The
following is the procedure for processing policy mapping in the
forward direction:
1) Begin with C's policy set {Y,G}
2) Apply the policy mapping in B's certificate (X maps to G) in
reverse to yield {Y,X} (same as {X,Y})
3) Intersect the rest {X,Y} with B{X,Y} to yield the set {X,Y}
4) Intersect that result, {X,Y}, with A{X,Y,Z} to yield the final
set {X,Y}
Just like in the reverse direction, it is determined in the forward
direction that certificate C is good for policies {X, Y}. If during
this procedure, an inhibit-policy-mapping flag was encountered, what
should be done? This is reasonably easy to keep track of as well.
The software simply maintains a flag on any policies that were
propagated as a result of a mapping; just a simple Boolean kept with
the policies in the set. Imagine now that the certificate issued to
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 48]
Certification Path Building February 2003
A has the inhibit-policy-mapping constraint expressed with a skip
certificates value of zero.
1) Begin with C's policy set {Y,G}
2) Apply the policy mapping in B's certificate and mark X as
resulting from a mapping. (X maps to G) in reverse to yield {Y,
Xm} (same as {Xm,Y})
3) Intersect the rest {Xm, Y} with B{X,Y} to yield the set {Xm, Y}
4) A's certificate expresses the inhibit policy mapping constraint,
so eliminate any policies in the current set that were propagated
due to mapping (which is Xm) to yield {Y}
5) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
{Y}
If in our example, the policy set had gone to empty at any point (and
require-explicit-policy was set), the path building should back up
and try to traverse another branch of the tree. This is analogous to
the path building functionality utilized in the reverse direction
when the policy set goes to empty.
4.3 Assigning Scores for Forward Policy Chaining
Assuming the path building module is maintaining the current forward
policy set; weights may be assigned using the following procedure:
1) For each CA certificate being scored;
A) Copy the current forward policy set
B) Process policy mappings in the CA certificate in order to
"un-map" policies, if any
C) Intersect the resulting set with CA certificate's policies
The larger the policy set yielded, the larger the score for that CA
certificate.
2) If an initial acceptable set was supplied, intersect this set
with the resulting set for each CA certificate from (1).
The larger the resultant set, the higher the score is for this
certificate.
Other rules and scoring schemes may work better if the operating
environment dictates.
5. Avoiding Common Path Building Errors
This section defines some common errors that may occur during the
path building process, as well as ways to avoid these errors when
developing path building functions.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 49]
Certification Path Building February 2003
5.1 Dead-ends
When building certification paths in a non-hierarchical PKI
structure, any path building algorithm may fail prematurely without
finding an existing path due to a "dead-end". Consider the example
below.
+----+ +---+
| TR | | Z |
+----+ +---+
| |
| |
V V
+---+ +---+
| C |<-----| Y |
+---+ +---+
|
|
V
+--------+
| Target |
+--------+
Note that in the example, C has two certificates: one issued by Y,
and the other issued by the Trust Root. Suppose that a simple "find
issuer" algorithm is used, and the order in which the path builder
found the certificates was Target(C), C(Y), Y(Z), Z(Z). In this
case, Z has no certificates issued by any other entities, and so the
simplistic path building process stops. Since Z is not the relying
party's trust root, the certification path is not complete, and will
not validate. This example shows that in anything but the simplest
PKI structure, additional path building logic must be included to
handle the cases in which entities are issued multiple certificates
from different issuers. The path building algorithm must have the
ability to traverse back up the decision tree and try another path in
order to be robust.
5.2 Loop Detection
In a non-hierarchical PKI structure, a path building algorithm may
become caught in a loop without finding an existing path. Consider
the example below:
+----+
| TR |
+----+
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 50]
Certification Path Building February 2003
|
|
+---+ +---+
| A | ->| Z |
+---+ / +---+
| / |
| / |
V / V
+---+ +---+
| B |<-----| Y |
+---+ +---+
|
|
V
+--------+
| Target |
+--------+
Let us suppose that in this example the simplest "find issuer"
algorithm is used, and the order in which certificates are retrieved
is Target(B), B(Y), Y(Z), Z(B), B(Y), Y(Z), Z(B), B(Y), ... A loop
has formed which will cause the correct path (Target, B, A) to never
be found. The certificate processing system must recognize loops
created by duplicate certificates (which are prohibited in a path by
X.509) before they form to allow the certification path building
process to continue and find valid paths. The authors of this
document recommend that the loop detection not only detect the
repetition of a certificate in the path, but also detect the presence
of the same subject name / subject alternative name / subject public
key combination occurring twice in the path. A name/key pair should
only need to appear once in the path.
5.3 Use of Key Identifiers
Inconsistent and/or incompatible approaches to computing the subject
key identifier and authority key identifier in public key
certificates can cause failures in certification path building
algorithms that use those fields to identify certificates, even
though otherwise valid certification paths may exist. Path building
implementations should not attempt to re-compute subject key
identifiers. Rather existing key identifiers should be used, when
present.
Path building and processing implementations should rely on the form
of authority key identifier which uses the authority distinguished
name and serial number as a restrictive matching rule, because cross-
certification can lead to this value not being matched by the cross
certificates.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 51]
Certification Path Building February 2003
6. Retrieval Methods
Building a certification path requires the availability of the
certificates and certificate revocation lists that make up the path.
There are many different methods for performing this retrieval. This
appendix lists a few of the common ways to perform this retrieval, as
well as some suggested approaches for improving performance.
6.1 Retrieval From Directories Using LDAP
Most applications utilize the lightweight directory access protocol
(LDAP) when retrieving data from directories following the X.500
model. The LDAP v3 specification is found in RFC 2251.
The LDAP v3 specification defines one attribute retrieval option, the
"binary" option. This option, when specified in an LDAP retrieval
request, was intended to force the directory to ignore any string-
based representations of directory information, and send the
requested attribute(s) in binary format. Since all PKI objects of
concern are binary objects, the "binary" option should be used.
However, not all directories support the "binary" option.
(Additionally, recent developments in the LDAP working group seem to
be leading toward the removal of the "binary" option.) Therefore,
all attribute retrievals should specify the attribute name with and
without the "binary" option. For example, if an application wishes
to retrieve the userCertificate attribute, the retrieval request
should contain the following list of attributes to retrieve:
"userCertificate, and userCertificate;binary".
The following attributes should be considered by PKI application
developers when performing retrievals:
- userCertificate: contains certificates issued by one or more
certification authorities. This is a multi-valued attribute
and all values could be received and considered during path
building. Although typically it is expected that only end
entity certificates will be stored in this attribute, (e.g.,
this is the attribute an application would request to find a
person's encryption certificate.) implementers may opt to
search this attribute when looking in CA entries to make their
path builder more robust. If it is empty, the overhead added
by including this attribute when already requesting one or both
of the two below is marginal.
- cACertificate: contains self-issued certificates (if any) and
any certificates issued to this certification authority by
other certification authorities in the same realm. (Realm is
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 52]
Certification Path Building February 2003
dependent upon local policy.) This is a multi-valued attribute
and all values should be received and considered during path
building.
- crossCertificatePair: the crossCertificatePair is used to
contain certificates issued to this certification authority by
other certification authorities in other realms, as well as
certificates issued by this certification authority to other
certification authorities in other realms. Each attribute
value is a structure containing two elements. The
issuedToThisCA element contains certificates issued to this
certification authority by other certification authorities.
The issuedByThisCA element contains certificates issued by this
certification authority to certification authorities. Both
elements of the crossCertificatePair are labeled optional in
the ASN.1 definition; however the LDAP v2 schema states that
the issuedToThisCA (once called the 'forward' element) is
mandatory and the issuedByThisCA (once called the 'reverse'
element) is optional. If both elements are present, in a
single value, the issuer name in one certificate must match the
subject name in the other and vice versa, and the subject
public key in one certificate shall be capable of verifying the
digital signature on the other certificate and vice versa.
- certificateRevocationList: the certificateRevocationList
attribute contains a certificate revocation list (CRL). A CRL
is defined in RFC 3280 as a time stamped list identifying
revoked certificates, which is signed by a CA or CRL issuer and
made freely available in a public repository. Each revoked
certificate is identified in a CRL by its certificate serial
number. There may be one or more CRLs in this attribute, and
the values should be processed in accordance with RFC 3280.
- authorityRevocationList: the authorityRevocationList attribute
also contains CRLs. These CRLs contain revocation information
regarding certificates issued to other CAs. There may be one
or more CRLs in this attribute, and the values should be
processed in accordance with RFC 3280.
Certificate Processing Systems that plan to interoperate with varying
PKI structures and directory designs should be able to retrieve and
process the userCertificate, userCertificate;binary, cACertificate,
cACertificate;binary, crossCertificatePair,
crossCertificatePair;binary, certificateRevocationList,
certificateRevocationList;binary, authorityRevocationList, and
authorityRevocationList;binary attributes from directory entries.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 53]
Certification Path Building February 2003
6.2 Retrieval Using Authority Information Access
The authority information access (AIA) extension, defined within RFC
3280, indicates how to access CA information and services for the
issuer of the certificate in which the extension appears. If a
certificate with an AIA extension contains an accessMethod defined
with the id-ad-caIssuers OID, the AIA may be used to retrieve one or
more certificates for entities that issued the certificate containing
the AIA extension. The AIA will provide a uniform resource
identifier (URI) when certificates can be retrieved via LDAP, HTTP,
or FTP. The AIA will provide a directoryName when certificates can
be retrieved via directory access protocol (DAP). The AIA will
provide an rfc822Name when certificates can be retrieved via
electronic mail.
If present, AIA can provide path-building implementations with a
direct link to a certificate for the issuer of a given certificate.
Therefore, implementations may wish to provide support for decoding
the AIA extension and following the LDAP, HTTP, FTP, DAP, or e-mail
links. Support for AIA is optional, RFC 3280 compliant
implementations need not populate the AIA extension.
6.3 Retrieval Using CRL Distribution Points
The CRL distribution points (CRLDP) extension, defined within RFC
3280, indicates how to access CRL information. If a CRLDP extension
appears within a certificate, the CRL(s) to which the CRLDP(s) refer
is the CRL that would contain revocation information for the
certificate. The CRLDP extension may point to multiple distribution
points from which the CRL information may be obtained; the
certificate processing system should process the CRLDP extension in
accordance with RFC 3280. The most common distribution points
contain URIs from which the appropriate CRL can be downloaded, and
directory names, which can be queried in a directory to retrieve the
CRL attributes from the corresponding entry.
If present, CRLDP can provide certificate processing implementations
with a link to CRL information for a given certificate. Therefore,
implementations may wish to provide support for decoding the CRLDP
extension and using the information to retrieve CRLs. Support for
CRLDP is optional and RFC3280 compliant implementations need not
populate the CRLDP extension. However, implementers of path building
and validation modules are strongly encouraged to support CRLDPs. At
a minimum, support for LDAP and HTTP should be considered; this will
provide for interoperability across a wide range of existing PKIs.
6.4 Proprietary Retrieval Mechanisms
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 54]
Certification Path Building February 2003
Some certificate issuing systems and certificate processing systems
may utilize proprietary retrieval mechanisms, such as network mapped
drives, databases, or other methods that are not directly referenced
via the IETF standards. Certificate processing systems may wish to
support other proprietary mechanisms, but unless functioning in a
closed environment should only do so in addition to supporting
standard retrieval mechanisms such as LDAP, AIA, and CRLDP.
7. Improving Retrieval Performance
Retrieval performance can be improved through a few different
mechanisms, including the use of caches and setting a specific
retrieval order. This section discusses a few methods by which the
performance of a certificate processing system may be improved during
the retrieval of PKI objects. Certificate processing systems that
are consistently very slow during processing will be disliked by
users and will be slow to be adopted into organizations. Certificate
processing systems should do whatever possible to reduce the delays
associated with requesting and retrieving data from external sources.
7.1 Caching
Certificate processing systems operating in a non-hierarchical PKI
will often need to retrieve certificates and certificate revocation
lists (CRLs) from a source outside the application protocol.
Typically, these objects are retrieved from an X.500 or LDAP
repository, an Internet URI, or some other non-local source. Due to
the delays associated with both the establishing of connections as
well as network transfers, certificate processing systems should
attempt to be as efficient as possible when retrieving data from
external sources. Perhaps the best way in which retrieval efficiency
can often be improved is by the use of a caching mechanism.
Certificate processing systems should cache data retrieved from
external sources for some period of time, but not to exceed the
useful period of the data (i.e., an expired certificate need not be
cached). Although this comes at a cost of increased memory/disk
consumption by the system, the cost and performance benefit of
reducing network transmissions is great.
There are a number of different ways in which caching can be
implemented, and the specifics of these methods can be used as
distinguishing characteristics between certificate processing
systems. However, some things that implementers may wish to consider
when developing caching systems are as follows:
- If PKI objects are cached, the certification path building
mechanism should be able to examine and retrieve from the cache
during path building. This will allow the certificate
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 55]
Certification Path Building February 2003
processing system to find or eliminate one or more paths
quickly without requiring external contact with a directory or
other mechanism.
- Sharing caches between multiple users (via a local area network
or LAN) may be useful if many users in one organization
consistently perform PKI operations with another organization.
- Caching not only PKI objects (such as certificates and CRLs)
but also relationships between PKI objects (storing a link
between a certificate and the issuer's certificate) may be
useful. This linking may not always lead to the most correct
or best relationship, but could represent a linking that worked
in another scenario.
7.2 Retrieval Order
To optimize efficiency, certificate processing systems should also
consider the order in which different PKI objects are retrieved, as
well as the mechanism from which they are retrieved. If caching is
utilized, the caches should be consulted for PKI objects before
attempting other retrieval mechanisms. If multiple caches are
present (such as local disk and network), the caches should be
consulted in the order in which they can be expected to return their
result, from fastest to slowest. For example, if a certificate
processing system wished to retrieve a certificate with a particular
subject distinguished name, the system would first consult the local
cache, then the network cache, and then attempt directory retrieval.
The specifics of the types of retrieval mechanisms and their relative
costs are left to the implementer.
In addition to ordering retrieval mechanisms, the certificate
processing system should also order the relative merits of the
different external sources from which a PKI object can be retrieved.
If the AIA is present within a certificate, with a URI for the
issuer's certificate, the certificate processing system (if able) may
wish to attempt to retrieve the certificate first from local cache,
and then using that URI because it should point directly to the
desired certificate, before attempting to retrieve the many
certificates that may exist within a directory.
If a directory is being consulted, it may be desirable to retrieve
attributes in a particular order. A highly cross-certified PKI
structure will lead to multiple possibilities for certification
paths, which may mean multiple validation attempts before a
successful path is retrieved. Therefore, cACertificate and
userCertificate (which contain certificates from within the same
'realm') should be consulted before attempting to retrieve the
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 56]
Certification Path Building February 2003
crossCertificatePair values for an entry. Ordering in this way
should ensure the certificate processing system attempts all possible
certificates within a given 'realm' before expanding the search to
include other 'realms'. Alternately, all three attributes could be
retrieved in one query, but cross certificates then tagged as such
and used only after exhausting the possibilities in the local realm.
The best approach will depend on the nature of the application and
PKI environment.
8. Security Considerations
Although certificate path development deals directly with security
relevant PKI data, the PKI data itself needs no special handling as
the PKI data integrity is secured with the digital signature applied
to it. The only exception to this is the appropriate protection of
the trusted root keys and/or trusted root certificates used for
validating paths. These must be kept safe and obtained out of band
(e.g., not from an electronic mail message or a directory.) with
respect to the path building module.
The greatest security risks associated with this document revolve
around validating while certificate paths are built. It is therefore
noted here that implementers must fully implement certificate path
validation in accordance with RFC 3280 and X.509 in order for
certificate path building, certificate path validation, and the
certificate using application to be properly secured. All of the
Security Considerations listed in Section 9 of RFC 3280 apply when
any aspect of path validation is done as part of path development.
In addition, as with any application that consumes data from
potentially untrusted network locations, path development components
should be carefully constructed so as to reduce or eliminate the
possibility of network based exploits. For example, a poorly
constructed path building module may not check the length of the
CRLDP URI before using the C language strcpy() function to place the
address in a 1024 byte buffer. A hacker could use such a flaw to
create a buffer overflow exploit by encoding his own code into the
CRLDP of a certificate and then using the certificate to attempt an
authentication. Such an attack could yield system level control to
the attacker and expose the sensitive data the PKI was meant to
protect.
9. References
[1] Hesse, P., Lemire, D., "Managing Interoperability
in Non-Hierarchical Public Key Infrastructures",
February 2002.
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 57]
Certification Path Building February 2003
[RFC 1738] Berners-Lee, T., L. Masinter and M. McCahill, "Uniform
Resource Locators (URL)", RFC 1738, December 1994.
[RFC 2026] Bradner, S., "The Internet Standards Process ű
Revision 3", RFC 2026, October 1996
[RFC 2247] Kille, S., M. Wahl, A. Grimstad, R. Huber and S.
Sataluri, "Using Domains in LDAP/X.500 Distinguished
Names", RFC 2247, January 1998.
[RFC 2252] Wahl, M., A. Coulbeck, T. Howes and S. Kille,
"Lightweight Directory Access Protocol (v3):
Attribute Syntax Definitions", RFC 2252,
December 1997.
[RFC 2560] Myers, M., R. Ankney, A. Malpani, S. Galperin and C.
Adams, "Online Certificate Status Protocal - OCSP",
June 1999.
[RFC 2587] S. Boeyen, T. Howes, P. Richard, "Internet X.509
Public Key Infrastructure LDAPv2 Schema", RFC 2587,
June 1999
[RFC 3280] Housley, R., W. Ford, W. Polk and D. Solo, "Internet
X.509 Public Key Infrastructure: Certificate and CRL
Profile", RFC 2459, January 1999.
[X.501] ITU-T Recommendation X.501: Information Technology ű
Open Systems Interconnection - The Directory: Models,
1993.
[X.509] ITU-T Recommendation X.509 (1997 E): Information
Technology - Open Systems Interconnection - The
Directory: Authentication Framework, June 1997.
[X.520] ITU-T Recommendation X.520: Information Technology ű
Open Systems Interconnection - The Directory: Selected
Attribute Types, 1993.
[PKIXALGS] Bassham, L., Polk, W. and R. Housley, "Algorithms and
Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation
Lists (CRL) Profile", RFC 3279, April 2002.
10. Acknowledgments
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 58]
Certification Path Building February 2003
The authors extend their appreciation to David Lemire for his efforts
coauthoring "Managing Interoperability in Non-Hierarchical Public Key
Infrastructures" from which material was borrowed heavily for use in
the introductory sections.
This document has also greatly benefited from the review and
additional technical insight provided by David Fillingham, Troy
Young, Dr. Santosh Chokhani, Carl Wallace, and Steve Hanna.
11. Author's Addresses
Matt Cooper
Orion Security Solutions, Inc.
1489 Chain Bridge Rd, Ste. 300
McLean, VA 22101
Phone: +1-703-917-0060
Email: mcooper@orionsec.com
Yuriy Dzambasow
A&N Associates, Inc.
999 Corporate Blvd Suite 100, Linthicum, MD 21090
Phone: +1-410-859-5449
Email: yuriy@anassoc.com
Peter Hesse
Gemini Security Solutions
4031 University Dr. Ste. 200, Fairfax, VA 22030 USA
Phone: +1-703-934-2031
Email: pmhesse@geminisecurity.com
Susan Joseph
DigitalNet
141 National Business Parkway, Ste. 210
Annapolis Junction, MD 20701
Phone: +1-301-939-2705
Email: susan.joseph@digitalnet.com
Richard Nicholas
DigitalNet
141 National Business Parkway, Ste. 210
Annapolis Junction, MD 20701
Phone: +1-301-939-2722
Email: richard.nicholas@digitalnet.com
Cooper, Dzambasow,
Hesse, Joseph,
Nicholas Expires - August 2003 [Page 59]