tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 4158


Internet X.509 Public Key Infrastructure: Certification Path Building

Part 2 of 4, p. 15 to 35
Prev RFC Part       Next RFC Part


prevText      Top      Up      ToC       Page 15 
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

Top      Up      ToC       Page 16 
   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

   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

Top      Up      ToC       Page 17 
   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

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.

Top      Up      ToC       Page 18 
            +---------+                        +---------+
            |  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.

Top      Up      ToC       Page 19 
                      +---------+         +---------+
                      |  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).

Top      Up      ToC       Page 20 
   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

Top      Up      ToC       Page 21 
         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

      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

      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

Top      Up      ToC       Page 22 
            +---+    +---+
            | 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

Top      Up      ToC       Page 23 
   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:

Top      Up      ToC       Page 24 
      - 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

      - 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

   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.

Top      Up      ToC       Page 25 
   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.)

Top      Up      ToC       Page 26 
     +---+    +---+
     | 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

Top      Up      ToC       Page 27 
   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).

Top      Up      ToC       Page 28 
               +----+                        +----+  +----+
               | 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

Top      Up      ToC       Page 29 
                    +----+               +----+
                    | 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".

Top      Up      ToC       Page 30 
   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

Top      Up      ToC       Page 31 
   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

   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

Top      Up      ToC       Page 32 
         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

      b. LDAPv3 directory for certificates and CRLs.

            i. Consider supporting multiple directories for general

           ii. Consider supporting dynamic LDAP connections for
               retrieving CRLs using an LDAP URI [RFC3986] in the CRL
               distribution point certificate extension.

Top      Up      ToC       Page 33 
          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

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

Top      Up      ToC       Page 34 
      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.

Top      Up      ToC       Page 35 
   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

   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)

Next RFC Part