RFC 4158
Internet X.509 Public Key Infrastructure: Certification Path Building
Pages: 81
Informational
Informational
Part 2 of 4 – Pages 15 to 35
2. Certification Path Building
Certification path building is the process by which the certificate processing system obtains the certification path between a trust anchor and the target certificate. Different implementations can build the certification path in different ways; therefore, it is not the intent of this document 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 on the capabilities path-building implementations need in order to build certification paths successfully, irrespective of PKI structures.2.1. Introduction to Certification Path Building
A certification path is an ordered list of certificates starting with a certificate that can be validated by one of the relying party's trust anchors, 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 trust anchors are typically stored in trust anchor 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 and SSL/TLS sessions. Figure 6 shows an example of a certification path. In this figure, the horizontal arrows represent certificates, and the notation B(A) signifies a certificate issued to B, signed by A. +---------+ +-----+ +-----+ +-----+ +--------+ | Trust |----->| CA |---->| CA |---->| CA |---->| Target | | Anchor | : | A | : | B | : | C | : | EE | +---------+ : +-----+ : +-----+ : +-----+ : +--------+ : : : : : : : : Cert 1 Cert 2 Cert 3 Cert 4 A(Trust Anchor) 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. This is because the validation of a certification path is unaffected by the method in which the certification path was built. However, the ability to build a valid certification path is of paramount importance for applications that
rely on a PKI. Without valid certification paths, certificates cannot be validated according to [RFC3280] and therefore cannot be trusted. Thus, the ability to build a path is every bit as important as the ability to validate it properly. 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 need to manage a number of trust anchors, partially populated directory entries (e.g., missing issuedToThisCA entries in the crossCertificatePair attribute), parsing of certain certificate extensions (e.g., authorityInformationAccess) and directory attributes (e.g., crossCertificatePair), and error handling such as loop detection. In addition, a developer has to decide whether to build paths from a trust anchor (the reverse direction) to the target certificate or from the target certificate (the forward direction) to a trust anchor. Some implementations may even decide to use both. The choice a developer makes should be dependent on the environment and the underlying PKI for that environment. More information on making this choice can be found in Section 2.3.2.2. Criteria for Path Building
From this point forward, this document will be discussing specific algorithms and mechanisms to assist developers of certification path-building implementations. To provide justification for these mechanisms, it is important to denote what the authors considered the criteria for a path-building implementation. Criterion 1: The implementation is able to find all possible paths, excepting paths containing repeated subject name/public key pairs. This means that all potentially valid certification paths between the trust anchor and the target certificate which may be valid paths can be built by the algorithm. As discussed in Section 2.4.2, we recommend that subject names and public key pairs are not repeated in paths. Criterion 2: The implementation is as efficient as possible. An efficient certification path-building implementation is defined to be one that builds paths that are more likely to validate following [RFC3280], before building paths that are not likely to validate, with the understanding that there is no way to account for all possible configurations and infrastructures. This criterion is intended to ensure implementations that can produce useful error
information. If a particular path is entirely valid except for a single expired certificate, this is most likely the 'right' path. If other paths are developed that are invalid for multiple obscure reasons, this provides little useful information. The algorithms and mechanisms discussed henceforth are chosen because the authors consider them to be good methods for meeting the above criteria.2.3. 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 traversal of a spanning tree, even in a very complex cross-certified environment. Complex environments as well as hierarchical PKIs can be represented as trees because certificates are not permitted to repeat in a path. If certificates could be repeated, loops can be formed such that the number of paths and number of certificates in a path both increase without bound (e.g., A issues to B, B issues to C, and C issues to A). Figure 7 below illustrates this concept from the trust anchor's perspective.
+---------+ +---------+ | Trust | | Trust | | Anchor | | Anchor | +---------+ +---------+ | | | | v v v v +---+ +---+ +---+ +---+ | A |<-->| C | +--| A | | C |--+ +---+ +---+ | +---+ +---+ | | | | | | | | +---+ | v v v v +->| B |<-+ +---+ +---+ +---+ +---+ +---+ | B | | C | | A | | B | | +---+ +---+ +---+ +---+ v | | | | +----+ v v v v | EE | +----+ +---+ +---+ +----+ +----+ | EE | | B | | B | | EE | +----+ +---+ +---+ +----+ A certificate graph with | | bi-directional cross-cert. v v between CAs A and C. +----+ +----+ | EE | | EE | +----+ +----+ The same certificate graph rendered as a tree - the way path-building software could see it. Figure 7 - Simple Certificate Graph - From Anchor Tree Depiction When viewed from this perspective, all PKIs look like hierarchies emanating from the trust anchor. An infrastructure can be depicted in this way regardless of its complexity. In Figure 8, the same graph is depicted from the end entity (EE) (the target certificate in this example). 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 trust anchor. While it is true that there are fewer nodes in the tree, it is not necessarily more efficient in this example.
+---------+ +---------+ | Trust | | Trust | | Anchor | | Anchor | +---------+ +---------+ ^ ^ | | | | +---+ +---+ | A | | C | +---+ +---+ +---------+ ^ ^ +---------+ | Trust | | | | Trust | | Anchor | | | | Anchor | +---------+ | | +---------+ ^ | | ^ | +---+ +---+ | +-------| C | | A |---------+ +---+ +---+ ^ ^ | | | +---+ | +---------| B |------+ +---+ ^ | | +----+ | EE | +----+ The same certificate graph rendered as a tree but from the end entity rather than the trust anchor. Figure 8 - Certificate Graph - From Target Certificate Depiction Suppose a path-building algorithm performed no optimizations. That is, the algorithm is only capable of detecting that the current certificate in the tree was issued by the trust anchor, or that it issued the target certificate (EE). From the tree above, building from the target certificate will require going through two intermediate certificates before encountering a certificate issued by the trust anchor 100% of the time (e.g., EE chains to B, which then chains to C, which is issued by the Trust Anchor). The path-building module would not chain C to A because it can recognize that C has a certificate issued by the Trust Anchor (TA).
On the other hand, in the first tree (Figure 7: from anchor depiction), there is a 50% probability of building a path longer than needed (e.g., TA to A to C to B to EE rather than the shorter TA 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 (DN) matches the issuer DN of the EE. Given this one optimization, the builder could prefer B to C. (B's subject DN matches that of the EE's issuer whereas C's subject DN does not.) So, for this example, assuming the issuedByThisCA (reverse) and issuedToThisCA (forward) elements were fully populated in the directory and our path-building module implemented the aforementioned DN matching optimization method, path building from either the trust anchor or the target certificate could be made roughly equivalent. A list of possible optimization methods is provided later in this document. A more complicated example is created when the path-building software encounters a situation when there are multiple certificates from which to choose while building a path. We refer to this as a large decision tree, or a situation with high fan-out. This might occur if an implementation has multiple trust anchors to choose from, and is building in the reverse (from trust anchor) direction. Or, it may occur in either direction if a Bridge CA is encountered. Large decision trees are the enemy of efficient path-building software. To combat this problem, implementations should make careful decisions about the path-building direction, and should utilize optimizations such as those discussed in Section 3.1 when confronted with a large decision tree. 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 their application: 1) What is required to accommodate the local PKI environment and the PKI environments with which interoperability will be required? a. If using a directory, is the directory [RFC2587] compliant (specifically, are the issuedToThisCA [forward] cross- certificates and/or the cACertificate attributes fully populated in the directory)? If yes, you are able to build in the forward direction. b. If using a directory, does the directory contain all the issuedByThisCA (reverse) cross-certificates in the crossCertificatePair attribute, or, alternately, are all certificates issued from each CA available via some other means? If yes, it is possible to build in the reverse
direction. Note: [RFC2587] does not require the issuedByThisCA
(reverse) cross-certificates to be populated; if they are
absent it will not be possible to build solely in the reverse
direction.
c. Are all issuer certificates available via some means other than
a directory (e.g., the authorityInformationAccess extension is
present and populated in all certificates)? If yes, you are
able to build in the forward direction.
2) How many trust anchors will the path-building and validation
software be using?
a. Are there (or will there be) multiple trust anchors in the
local PKI? If yes, forward path building may offer better
performance.
b. Will the path-building and validation software need to place
trust in trust anchors from PKIs that do not populate reverse
cross-certificates for all intermediate CAs? If no, and the
local PKI populates reverse cross-certificates, reverse path
building is an option.
2.4. How to Build a Certification Path
As 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 more 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 Bridged PKI
environments.
+---+ +---+ | F |--->| H | +---+ +---+ ^ ^ ^ | \ \ | \ \ | v v | +---+ +---+ | | G |--->| I | | +---+ +---+ | ^ | / | / +------+ +-----------+ +------+ +---+ +---+ | TA W |<----->| Bridge CA |<------>| TA X |-->| L |-->| M | +------+ +-----------+ +------+ +---+ +---+ ^ ^ \ \ / \ \ \ / \ \ \ v v v v +------+ +------+ +---+ +---+ | TA Y | | TA 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 9 - Four Bridged PKIs
Figure 9 depicts four root certification authorities cross-certified with a Bridge CA (BCA). While multiple trust anchors are shown in the Figure, our examples all consider TA Z as the trust anchor. The other trust anchors serve different relying parties. By building certification paths through the BCA, trust can be extended across the four infrastructures. In Figure 9, the BCA has four certificates issued to it; one issued from each of the trust anchors in the graph. If stored in the BCA directory system, the four certificates issued to the BCA would be stored in the issuedToThisCA (forward) entry of four different crossCertificatePair structures. The BCA also has issued four certificates, one to each of the trust anchors. If stored in the BCA directory system, those certificates would be stored in the issuedByThisCA (reverse) entry of the same four crossCertificatePair structures. (Note that the cross-certificates are stored as matched pairs in the crossCertificatePair attribute. For example, a crossCertificatePair structure might contain both A(B) and B(A), but not contain A(C) and B(A).) The four crossCertificatePair structures would then be stored in the BCA's directory entry in the crossCertificatePair attribute.2.4.1. Certificate Repetition
[X.509] requires that certificates are not repeated when building paths. For instance, from the figure above, do not build the path TA Z->BCA->Y->A->C->A->C->B->D. Not only is the repetition unnecessary to build the path from Z to D, but it also requires the reuse of a certificate (the one issued from C to A), which makes the path non- compliant with [X.509]. What about the following path from TA Z to EE? TA Z->BCA->Y->BCA->W->BCA->X->L->N->EE 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 9) had double arrows between Y and C, as well as between Y and A. The following path could then be built: TA Z->BCA->Y->A->C->Y->BCA->W->BCA->X->L->N->EE 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 or need to build 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.
- 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
assurance may be considered lost.
- Third, the longer and more complicated a path, the less likely
it is to validate because of basic constraints, policies or
policy constraints, name constraints, CRL availability, or even
revocation.
- Lastly, and certainly not least important from a developer's or
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 of certificate properties, 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.
There is a special case involving certificates with the same
distinguished names but differing encodings required by [RFC3280].
This case should not be considered a repeated certificate. See
Section 5.4 for more information.
2.4.2. Introduction to Path-Building Optimization
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 approach, all of the intended and needed paths should be
available, and the excess and diluted paths should be eliminated.
For example, using this approach, only one path exists from the TA Z
to EE in the diagram above: TA Z->BCA->X->L->N->EE.
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 10 depicts the forward path-building decision tree 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 TA Z to EE. +------+ +-----------+ +------+ +---+ | TA W |<------| Bridge CA |<-------| TA X |<--| L | +------+ +-----------+ +------+ +---+ / \ ^ / \ \ / \ \ v v \ +------+ +------+ +---+ | TA Y | | TA Z | | N | +------+ +------+ +---+ ^ \ \ +----+ | EE | +----+ Figure 10 - Forward (From Entity) Decision Tree It is not possible to build forward direction paths into the infrastructures behind CAs W, Y, and Z, because W, Y, and Z have not been issued certificates by their subordinate CAs. (The subordinate CAs are F and G, A and C, and O and P, respectively.) If simplicity and speed are desirable, the graph in Figure 10 is a very appealing way to structure the path-building algorithm. Finding a path from the EE to one of the four trust anchors 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 trust anchors around the BCA. The graph in Figure 11 depicts all possible paths as a tree emanating from TA Z. (Note: it is not recommended that implementations attempt to determine all possible paths, this would require retrieval and storage of all PKI data including certificates and CRLs! This example is provided to demonstrate the complexity which might be encountered.)
+---+ +---+ | I |--->| H | +---+ +---+ ^ | +---+ +---+ | | H |--->| I | | +---+ +---+ +---+ ^ | G | / +---+ +---+ +---+ +---+ / | F |--->| H |--->| I | ^ / +---+ +---+ +---+ \ / ^ \/ / +---+ +---+ +---+ +---+ +---+ | F | | G |--->| I |--->| H | | M | +---+ +---+ +---+ +---+ +---+ ^ ^ ^ | / | +------+ +-----------+ +------+ +---+ | TA W |<------| Bridge CA |-------->| TA X |-->| L | +------+ +-----------+ +------+ +---+ / ^ \ \ v \ v v +------+ +------+ +---+ +---+ | TA Y | | TA Z | | J | | N | +------+ +------+ +---+ +---+ / \ / \ \ \ v v v v v v +---+ +---+ +---+ +---+ +---+ +----+ | A | | C | | O | | P | | K | | EE | +---+ +---+ +---+ +---+ +---+ +----+ / \ / \ / \ \ 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 11 - Reverse (From Anchor) 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 valid path is returned. The path- building software could potentially traverse the entire graph before choosing the shortest path: TA 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 needs to decide not only in which direction to traverse the tree, but also which branches of the tree are more likely to yield a valid 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 would 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.) Finding the "best path first" is an effort to make the implementation efficient, which is one of our criteria as stated in Section 2.2. So how would a developer go about finding the best path first? Given the simplifying idea of addressing path building as a tree traversal, path building could be structured as a depth first search. A simple example of depth first tree traversal path building is depicted in Figure 12, with no preference given to sort order. 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).
+----+ +----+ +----+
| TA | | TA | | TA |
+----+ +----+ +----+
/ \ ^ ^
/ \ | |
v v +---+ +---+
+---+ +---+ | A | | C |
| A |<->| C | +---+ +---+
+---+ +---+ ^ ^
^ ^ +----+ | | +----+
\ / | TA | | | | TA |
v v +----+ | | +----+
+---+ ^ | | ^
| B | \ | | /
+---+ \ | | /
/ \ +---+ +---+
/ \ | C | | A |
v v +---+ +---+
+---+ +---+ ^ ^
| E | | D | | /
+---+ +---+ | /
+---+
Infrastructure | B |
+---+
^
|
+----+
| EE |
+----+
The Same Infrastructure
Represented as a Tree
+----+ +----+ | TA | | TA | +----+ +----+ ^ ^ | | +---+ +---+ | A | | C | +---+ +---+ +----+ ^ ^ +----+ | TA | | | | TA | +----+ | | +----+ ^ | | ^ \ | | / +---+ +---+ +---+ +---+ | C | | C | | A | | A | +---+ +---+ +---+ +---+ ^ ^ ^ ^ | | / / | | / / +---+ +---+ +---+ +---+ | B | | B | | B | | B | +---+ +---+ +---+ +---+ ^ ^ ^ ^ | | | | | | | | +----+ +----+ +----+ +----+ | EE | | EE | | EE | | EE | +----+ +----+ +----+ +----+ All possible paths from EE to TA using a depth first decision tree traversal Figure 12 - Path Building Using a Depth First Tree Traversal Figure 12 illustrates that four possible paths exist for this example. Suppose that the last path (TA->A->B->EE) is the only path that will validate. This could be for any combination of reasons such as name constraints, policy processing, validity periods, or path length constraints. 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. An efficient module would conclude that A is the more likely correct path. Then, at A, the module compares terminating the path at TA, or moving to C. Again, an efficient module will make the better choice (TA) 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 situation actually does not change the algorithm at all, if it is structured properly. In our example, rather than treating each decision as binary (i.e., choosing A or C), the path-building software should sort all the available possibilities at any given branch point, and then select the best choice from the list. In the event the path could not be built through the first choice, then the second choice 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 arcs (certificates) have already been tried.2.5. Building Certification Paths for Revocation Signer Certificates
Special consideration is given to building a certification path for the Revocation Signer certificate because it may or may not be the same as the Certification Authority certificate. For example, after a CA performs a key rollover, the new CA certificate will be the CRL Signer certificate, whereas the old CA certificate is the Certification Authority certificate for previously issued certificates. In the case of indirect CRLs, the CRL Signer certificate will contain a different name and key than the Certification Authority certificate. In the case of OCSP, the Revocation Signer certificate may represent an OCSP Responder that is not the same entity as the Certification Authority. When the Revocation Signer certificate and the Certification Authority certificate are identical, no additional consideration is required from a certification path-building standpoint. That is, the certification path built (and validated) for the Certification Authority certificate can also be used as the certification path for the Revocation Signer certificate. In this case, the signature on the revocation data (e.g., CRL or OCSP response) is verified using the same certificate, and no other certification path building is required. An efficient certification path validation algorithm should first try all possible CRLs issued by the Certification
Authority to determine if any of the CRLs (a) cover the certificate in question, (b) are current, and (c) are signed using the same key used to sign the certificate. When the Revocation Signer certificate is not identical to the Certification Authority certificate, a certification path must be built (and validated) for the Revocation Signer certificate. In general, the certification path-building software may build the path as it would for any other certificate. However, this document also outlines methods in later sections for greatly improving path building efficiency for Revocation Signer certificate case.2.6. Suggested Path-Building Software Components
There is no single way to define an interface to a path-building module. It is not the intent of this document 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 build every conceivable path and return the entire list to the caller. Or, the module 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 building and 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. 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 an operating system
or application certificate store, 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 listed below.
2) The logic for building and traversing the certificate graph/tree.
a. This performs sorting functionality for prioritizing
certificates (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. Be able to 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 <forward> and issuedByThisCA <reverse>
for split crossCertificatePair attributes) 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 [RFC3986] in the CRL
distribution point certificate extension.
iii. Support LDAP referrals. This is typically only a matter
of activating the appropriate flag in the LDAP API.
c. HTTP support for CRL distribution points and authority
information access (AIA) support.
i. Consider HTTPS support, but be aware that this may create
an unbounded recursion when the implementation tries to
build a certification path for the server's certificate if
this in turn requires an additional HTTPS lookup.
4) A certification path cache that stores previously validated
relationships between certificates. This cache should include:
a. A configurable expiration date for each entry. This date can
be configured based upon factors such as the expiry of the
information used to determine the validity of an entry,
bandwidth, assurance level, storage space, etc.
b. Support to store previously verified issuer certificate to
subject certificate relationships.
i. Since the issuer DN and serial number tuple uniquely
identifies a certificate, a pair of these tuples (one for
both the issuer and subject) is an effective method of
storing this relationship.
c. Support for storing "known bad" paths and certificates. Once a
certificate is determined to be invalid, implementations can
decide not to retry path development and validation.
2.7. Inputs to the Path-Building Module
[X.509] specifically addresses the list of inputs required for path
validation but makes no specific suggestions concerning 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 could be used to optimize path
building.
2.7.1. Required Inputs
Setting aside configuration information such as repository or cache
locations, 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 endpoint for the path. (It is also possible to
provide information used to retrieve a certificate for a target,
rather than the certificate itself.)
2) Trust List: This is the other endpoint of the path, and can
consist of either:
a. Trusted CA certificates
b. Trusted keys and DNs; a certificate is not necessarily required
2.7.2. Optional Inputs
In addition to the inputs listed in Section 2.7.1, the following
optional inputs can also be useful for optimizing path building.
However, if the path-building software takes advantage of all of the
optimization methods 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 one year ago, T
is needed to build a valid path)
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) Is-revocation-provider indicator
a. IMPORTANT: When building a certification path for an OCSP
Responder certificate specified as part of the local
configuration, this flag should not be set. It is set when
building a certification path for a CRL Signer certificate or
for an OCSP Responder Signer certificate discovered using the
information asserted in an authorityInformationAccess
certificate extension.
9) The complete certification path for the Certification Authority
(if Is-revocation-provider is set)
10) Collection of certificates that may be useful in building the
path
11) 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.
(page 35 continued on part 3)