3.  Optimizing Path Building

   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 as described in Section
   2.4.2.  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
   subject DNs.  However, unlike the weighted edge graph concept, a
   certification path builder need not have the entire graph available
   in order to function efficiently.  In addition, the path builder can
   be stateless with respect to nodes of the graph not present in the
   current path, so the working data set can be relatively small.

   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
   that sorting provides.  Consider the following diagram:

            +---+
            | R |
            +---+
             ^
            /
           v
         +---+       +---+      +---+    +---+    +----+
         | A |<----->| E |<---->| D |--->| Z |--->| EE |
         +---+       +---+      +---+    +---+    +----+
            ^         ^ ^        ^
             \       /   \      /
              \     /     \    /
               v   v       v  v
               +---+       +---+
               | B |<----->| C |
               +---+       +---+

            Figure 13 - Example of Path-Building Optimization

   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 and 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 builds the path Z(D)->EE(Z).
   Next the builder adds D and faces a decision between two
   certificates. (Choose between D(C) or D(E)).  The builder now sorts
   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
   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 should make it last or eliminate it from this node since
   certificates cannot 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 found when the seventh node is added to
   the path and the path terminated because one of the trust anchors has
   been found.

   In the event the first path fails to validate, the path builder will
   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 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 built.

3.2.  Sorting vs. Elimination

   Consider a situation when building a path in which three CA
   certificates are found for a given target certificate and must be
   prioritized.  When the certificates are examined, as in the previous
   example, one of the three has a name constraint present that will
   invalidate the path built 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
   eliminates 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 at another point in
   the tree; at that point it may or may not be eliminated.  The
   previous 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 build 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
   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 provides
   good performance for users, which is beneficial.  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
   information 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,
   PKI administrators and help desk personnel will have ample
   information to diagnose a problem with the PKI.  Ideally, there would
   be a mechanism for turning this logging on and off, so that it is not
   running all the time.  Additionally, it is recommended that the log
   contain information so that a developer or tester can recreate the
   paths tried by the path-building software, to assist with diagnostics
   and testing.

   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 methods are still
   applied, but no paths are eliminated based upon the sorting methods.
   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".

   Third, it may be useful to not rule out any paths, but instead limit
   the number of paths that may be built given a particular input.
   Assuming the path-building module is designed to return the "best
   path first", the paths most likely to validate would be returned
   before this limit is reached.  Once the limit is reached the module
   can stop building paths, providing a more rapid response to the
   caller than one which builds all possible paths.

   Ultimately, the developer determines how to handle the trade-off
   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:

      a. Do not check revocation status if it requires a directory
         lookup or network access

      b. Do not check digital signatures (see Section 8.1, General
         Considerations for Building A Certification Path, for
         additional considerations).

      c. Do not check anything that cannot be checked as part of the
         iterative process of traversing the tree.

      d. Create a detailed log, 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 [RFC3280] with the following recommendations:

      a. For a performance boost, do not re-check items already checked
         by the path builder. (Note: if pre-populated paths are supplied
         to the path-building system, the entire path has to be fully
         re-validated.)

      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 and return this to the user in the event
               that no valid path is found.  Since the path-building
               software was designed to return the "best path first",
               this path should be shown to the user.

   As stated above, this document recommends that developers do not
   validate digital 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 usually good.  Since signature validation is costly in terms
   of processor time, it is better to delay signature checking until a
   complete path is found and then check the signatures on each
   certificate in the certification path starting with the trust anchor
   (see Section 8.1).  Second, it is fairly uncommon in typical
   application environments to encounter a revoked certificate;
   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.  This
   reduces the probability of retrieving unneeded revocation status
   information while building paths.

3.3.  Representing the Decision Tree

   There are a multitude of ways to implement certification path
   building and as many ways to represent the decision tree in memory.

   The method described below is an approach that will work well with
   the optimization methods listed later in this document.  Although
   this approach is the best the authors of this document have
   implemented, it is by no means the only way to implement it.
   Developers should tailor this approach to their own requirements or
   may find that another approach suits their environment, programming
   language, or programming style.

3.3.1.  Node Representation for CA Entities

   A "node" in the certification graph is a collection of CA
   certificates with identical subject DNs.  Minimally, for each node,
   in order to fully implement the optimizations to follow, the path-
   building module will need to be able to keep track of the following
   information:

   1. Certificates contained in the node

   2. Sorted order of the certificates

   3. "Current" certificate indicator

   4. The current policy set (It may be split into authority and user
      constrained sets, if desired.)

      - It is suggested that encapsulating the policy set in an object
        with logic for manipulating the set such as performing
        intersections, mappings, etc., will simplify implementation.

   5. Indicators (requireExplicitPolicy, inhibitPolicyMapping,
      anyPolicyInhibit) and corresponding skipCert values

   6. A method for indicating which certificates are eliminated or
      removing them from the node.

      - If nodes are recreated from the cache on demand, it may be
        simpler to remove eliminated certificates from the node.

   7. A "next" indicator that points to the next node in the current
      path

   8. A "previous" indicator that points to the previous node in the
      current path

3.3.2.  Using Nodes to Iterate Over All Paths

   In simplest form, a node is created, the certificates are sorted, the
   next subject DN required is determined from the first certificate,
   and a new node is attached to the certification path via the next
   indicator (Number 7 above).  This process continues until the path
   terminates.  (Note: end entity certificates may not contain subject
   DNs as allowed by [RFC3280].  Since end entity certificates by
   definition do not issue certificates, this has no impact on the
   process.)

   Keeping in mind that the following algorithm is designed to be
   implemented using recursion, consider the example in Figure 12 and
   assume that the only path in the diagram is valid for E is TA->A->
   B->E:

   If our path-building module is building a path in the forward
   direction for E, a node is first created for E.  There are no
   certificates to sort because only one certificate exists, so all
   initial values are loaded into the node from E.  For example, the
   policy set is extracted from the certificate and stored in the node.

   Next, the issuer DN (B) is read from E, and new node is created for B
   containing both certificates issued to B -- B(A) and B(C).  The
   sorting rules are applied to these two certificates and the sorting
   algorithm returns B(C);B(A).  This sorted order is stored and the
   current indicator is set to B(C).  Indicators are set and the policy
   sets are calculated to the extent possible with respect to B(C).  The
   following diagram illustrates the current state with the current
   certificate indicated with a "*".

   +-------------+    +---------------+
   | Node 1      |    | Node 2        |
   | Subject: E  |--->| Subject: B    |
   | Issuers: B* |    | Issuers: C*,A |
   +-------------+    +---------------+

   Next, a node is created for C and all three certificates are added to
   it.  The sorting algorithm happens to return the certificates sorted
   in the following order: C(TA);C(A);C(B)

   +-------------+    +---------------+    +------------------+
   | Node 1      |    | Node 2        |    | Node 3           |
   | Subject: E  |--->| Subject: B    |--->| Subject: C       |
   | Issuers: B  |    | Issuers: C*,A |    | Issuers: TA*,A,B |
   +-------------+    +---------------+    +------------------+

   Recognizing that the trust anchor has been found, the path
   (TA->C->B->E) is validated but fails. (Remember that the only valid
   path happens to be TA->A->B->E.)  The path-building module now moves
   the current certificate indicator in node 3 to C(A), and adds the
   node for A.

      +-------------+    +---------------+    +------------------+
      | Node 1      |    | Node 2        |    | Node 3           |
      | Subject: E  |--->| Subject: B    |--->| Subject: C       |
      | Issuers: B  |    | Issuers: C*,A |    | Issuers: TA,A*,B |
      +-------------+    +---------------+    +------------------+
                                                        |
                                                        v
                                              +------------------+
                                              | Node 4           |
                                              | Subject: A       |
                                              | Issuers: TA*,C,B |
                                              +------------------+

   The path TA->A->C->B->E is validated and it fails.  The path-building
   module now moves the current indicator in node 4 to A(C) and adds a
   node for C.

   +-------------+    +---------------+    +------------------+
   | Node 1      |    | Node 2        |    | Node 3           |
   | Subject: E  |--->| Subject: B    |--->| Subject: C       |
   | Issuers: B  |    | Issuers: C*,A |    | Issuers: TA,A*,B |
   +-------------+    +---------------+    +------------------+
                                                     |
                                                     v
                   +------------------+    +------------------+
                   | Node 5           |    | Node 4           |
                   | Subject: C       |<---| Subject: A       |
                   | Issuers: TA*,A,B |    | Issuers: TA,C*,B |
                   +------------------+    +------------------+

   At this juncture, the decision of whether to allow repetition of name
   and key comes to the forefront.  If the certification path-building
   module will NOT allow repetition of name and key, there are no
   certificates in node 5 that can be used. (C and the corresponding
   public key is already in the path at node 3.)  At this point, node 5
   is removed from the current path and the current certificate
   indicator on node 4 is moved to A(B).

   If instead, the module is only disallowing repetition of
   certificates, C(A) is eliminated from node 5 since it is in use in
   node 3, and path building continues by first validating TA->C->A->
   C->B->E, and then continuing to try to build paths through C(B).
   After this also fails to provide a valid path, node 5 is removed from
   the current path and the current certificate indicator on node 4 is
   moved to A(B).

      +-------------+    +---------------+    +------------------+
      | Node 1      |    | Node 2        |    | Node 3           |
      | Subject: E  |--->| Subject: B    |--->| Subject: C       |
      | Issuers: B  |    | Issuers: C*,A |    | Issuers: TA,A*,B |
      +-------------+    +---------------+    +------------------+
                                                        |
                                                        v
                                              +------------------+
                                              | Node 4           |
                                              | Subject: A       |
                                              | Issuers: TA,C,B* |
                                              +------------------+

   Now a new node 5 is created for B.  Just as with the prior node 5, if
   not repeating name and key, B also offers no certificates that can be
   used (B and B's public key is in use in node 2) so the new node 5 is
   also removed from the path.  At this point all certificates in node 4
   have now been tried, so node 4 is removed from the path, and the
   current indicator on node 3 is moved to C(B).

   Also as above, if allowing repetition of name and key, B(C) is
   removed from the new node 5 (B(C) is already in use in node 3) and
   paths attempted through the remaining certificate B(A).  After this
   fails, it will lead back to removing node 5 from the path.  At this
   point all certificates in node 4 have now been tried, so node 4 is
   removed from the path, and the current indicator on node 3 is moved
   to C(B).

   This process continues until all certificates in node 1 (if there
   happened to be more than one) have been tried, or until a valid path
   has been found.  Once the process ends and in the event no valid path
   was found, it may be concluded that no path can be found from E to
   TA.

3.4.  Implementing Path-Building Optimization

   The following section describes 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
   of the graph/tree.  The optimization methods can 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
   sorting methods:

   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 in which 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, the implementer decides the
   relative merits of each optimization 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.

   Many of the sorting methods described below are based upon what has
   been perceived by the authors as common in PKIs.  Many of the methods
   are aimed at making path building for the common PKI fast, but there
   are cases where most any sorting method could lead to inefficient
   path building.  The desired behavior is that although one method may
   lead the algorithm in the wrong direction for a given situation or
   configuration, the remaining methods will overcome the errant
   method(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 application's target
   operating environment.

   As a final note, 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.5.  Selected Methods for Sorting Certificates

   The reader should draw no specific conclusions as to the relative
   merits or scores for each of the following methods based upon the
   order in which they appear.  The relative merit of any sorting
   criteria is completely dependent on the specifics of the operating
   environment.  For most any method, an example can be created to
   demonstrate the method is effective and a counter-example could be
   designed to demonstrate that it is ineffective.

   Each sorting method is independent and may (or may not) be used to
   assign additional scores to each certificate tested.  The implementer
   decides which methods to use and what weights to assign them.  As
   noted previously, this list is also not exhaustive.

   In addition, name chaining (meaning the subject name of the issuer
   certificate matches the issuer name of the issued certificate) is not
   addressed as a sorting method since adherence to this is required in
   order to build the decision tree to which these methods will be
   applied.  Also, unaddressed in the sorting methods is the prevention
   of repeating certificates.  Path builders should handle name chaining
   and certificate repetition irrespective of the optimization approach.

   Each sorting method description specifies whether the method may be
   used to eliminate certificates, the number of possible numeric values
   (sorting weights) for the method, components from Section 2.6 that
   are required for implementing the method, forward and reverse methods
   descriptions, and finally a justification for inclusion of the
   method.

   With regard to elimination of certificates, it is important to
   understand that certificates are eliminated only at a given decision
   point for many methods.  For example, the path built up to
   certificate X may be invalidated due to name constraints by the
   addition of certificate Y.  At this decision point only, Y could be
   eliminated from further consideration.  At some future decision
   point, while building this same path, the addition of Y may not
   invalidate the path.

   For some other sorting methods, certificates could be eliminated from
   the process entirely.  For example, certificates with unsupported
   signature algorithms could not be included in any path and validated.
   Although the path builder may certainly be designed to operate in
   this fashion, it is sufficient to always discard certificates only
   for a given decision point regardless of cause.

3.5.1.  basicConstraints Is Present and cA Equals True

   May be used to eliminate certificates: Yes
   Number of possible values: Binary
   Components required: None

   Forward Method:  Certificates with basicConstraints present and
   cA=TRUE, or those designated as CA certificates out-of-band have
   priority.  Certificates without basicConstraints, with
   basicConstraints and cA=FALSE, or those that are not designated as CA
   certificates out-of-band may be eliminated or have zero priority.

   Reverse Method:  Same as forward except with regard to end entity
   certificates at the terminus of the path.

   Justification:  According to [RFC3280], basicConstraints is required
   to be present with cA=TRUE in all CA certificates, or must be

   verified via an out-of-band mechanism.  A valid path cannot be built
   if this condition is not met.

3.5.2.  Recognized Signature Algorithms

   May be used to eliminate certificates: Yes
   Number of possible values: Binary
   Components required: None

   Forward Method:  Certificates containing recognized signature and
   public key algorithms [PKIXALGS] have priority.

   Reverse Method:  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.5.3.  keyUsage Is Correct

   May be used to eliminate certificates:  Yes
   Number of possible values:  Binary
   Components required:  None

   Forward Method:  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 Method:  Same as forward except with regard to end entity
   certificates at the terminus of the path.

   Justification:  A valid certification path cannot be built through a
   CA certificate with inappropriate keyUsage.  Note that
   digitalSignature is not required to be set in a CA certificate.

3.5.4.  Time (T) Falls within the Certificate Validity

   May be used to eliminate certificates:  Yes
   Number of possible values:  Binary
   Components required:  None

   Forward Method:  Certificates that contain the required time (T)
   within their validity period have 100% priority.  Otherwise, the
   certificate is eliminated or has priority zero.

   Reverse Method:  Same as forward.

   Justification:  A valid certification path cannot be built 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 criterion, if this sorting method is used for elimination.
   (e.g., the certificate is expired or is not yet valid).

3.5.5.  Certificate Was Previously Validated

   May be used to eliminate certificates:  No
   Number of possible values:  Binary
   Components required:  Certification Path Cache

   Forward Method:  A certificate that is present in the certification
   path cache has priority.

   Reverse Method:  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.  Assuming the initial constraints have not changed, it is
   highly likely that the path from that certificate to a trust anchor
   is still valid.  (Changes to the initial constraints may cause a
   certificate previously considered valid to no longer be considered
   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 certificate expires in ten days, but the issued
   certificate is valid for 20 days, caching the relationship beyond 10
   days would be inappropriate.

3.5.6.  Previously Verified Signatures

   May be used to eliminate certificates:  Yes
   Number of possible values:  Binary
   Components required:  Path Cache

   Forward Method:   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

   said public key have higher priority.  Other certificates may be
   eliminated or set to zero priority.

   Reverse Method:  If known bad signature relationships exist between
   certificates, these relationships can be used to eliminate potential
   certificates from the decision tree.  Nothing can be concluded about
   the likelihood of finding a given target certificate down one branch
   versus another using known good signature relationships.

   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 method is especially strong for multiply cross-
   certified CAs after a key rollover has occurred.

3.5.7.  Path Length Constraints

   May be used to eliminate certificates: Yes
   Number of possible values: Binary
   Components required: None

   Forward Method:  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 Method:  This method may be applied in reverse.  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 built if the path length
   constraint has been violated.

3.5.8.  Name Constraints

   May be used to eliminate certificates:  Yes
   Number of possible values:  Binary
   Components required:  None

   Forward Method:  Certificates that contain nameConstraints that would
   be violated by certificates already in the path to this point are
   given zero priority or eliminated.

   Reverse Method:  Certificates that will allow successful processing
   of any name constraints present in the path to this point are given
   higher priority.

   Justification:  A valid path cannot be built if name constraints are
   violated.

3.5.9.  Certificate Is Not Revoked

   May be used to eliminate certificates: No
   Number of possible values:  Three
   Components required:  CRL Cache

   Forward Method:  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.  If an (acceptably fresh)
   OCSP response is available for a certificate, and identifies the
   certificate as valid, the certificate has priority.  If an OCSP
   response is available for a certificate, and identifies the
   certificate as invalid, the certificate has zero priority.

   Reverse Method:  Same as Forward.

   Alternately, the certificate may be eliminated if the CRL or OCSP
   response is verified.  That is, fully verify the CRL or OCSP response
   signature and relationship to the certificate in question in
   accordance with [RFC3280].  While this is viable, the signature
   verification required makes it less attractive as an elimination
   method.  It is suggested that this method only be used for sorting
   and that CRLs and OCSP responses are validated post path building.

   Justification:  Certificates known to be not revoked can be
   considered more likely to be valid than certificates for which the
   revocation status is unknown.  This is further justified if CRL or
   OCSP response validation is performed post path validation - CRLs or
   OCSP responses 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 or OCSP responses, some status information should be
   preserved so that a meaningful error may be returned in the event no
   path is found.

3.5.10.  Issuer Found in the Path Cache

   May be used to eliminate certificates: No
   Number of possible values: Binary
   Components required:  Certification Path Cache

   Forward Method:  A certificate whose issuer has an entry (or entries)
   in the path cache has priority.

   Reverse Method:  Does not apply.

   Justification:  Since the path cache only contains entries for
   certificates that were previously validated back to a trust anchor,
   it is more likely than not that the same or a new path may be built
   from that point to the (or one of the) trust anchor(s).  For
   certificates whose issuers are not found in the path cache, nothing
   can be concluded.

   NOTE: This method is not the same as the method named "Certificate
   Was Previously Validated".  It is possible for this sorting method to
   evaluate to true while the other method could evaluate to zero.

3.5.11.  Issuer Found in the Application Protocol

   May be used to eliminate certificates: No
   Number of possible values: Binary
   Components required:  Certification Path Cache

   Forward Method:  If the issuer of a certificate sent by the target
   through the application protocol (SSL/TLS, S/MIME, etc.), matches the
   signer of the certificate you are looking at, then that certificate
   has priority.

   Reverse Method:  If the subject of a certificate matches the issuer
   of a certificate sent by the target through the application protocol
   (SSL/TLS, S/MIME, etc.), then that certificate has priority.

   Justification:  The application protocol may contain certificates
   that the sender considers valuable to certification path building,
   and are more likely to lead to a path to the target certificate.

3.5.12.  Matching Key Identifiers (KIDs)

   May be used to eliminate certificates:  No
   Number of possible values:  Three
   Components required:  None

   Forward Method:  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 Method:  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:  Key Identifier (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:  Although required to be present by [RFC3280], it is extremely
   important that KIDs be used only as sorting criteria or as hints
   during certification path building.  KIDs are not required to match
   during certification path validation and cannot be used to eliminate
   certificates.  This is of critical importance for interoperating
   across domains and multi-vendor implementations where the KIDs may
   not be calculated in the same fashion.

3.5.13.  Policy Processing

   May be used to eliminate certificates: Yes
   Number of possible values: Three
   Components required: None

   Forward Method:  Certificates that satisfy Forward Policy Chaining
   have priority.  (See Section 4 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 sorting
   method should be increased.  If the initial-require-explicit-policy
   flag was set by the caller or by a certificate, certificates may be
   eliminated.

   Reverse Method:  Certificates that contain policies/policy mappings
   that will allow successful policy processing of the path to this
   point have priority.  If the caller provided an initial-policy-set
   and did not set the initial-require-explicit flag, the weight of this

   sorting method should be increased.  Certificates may be eliminated
   only 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 trust anchor will set the require-
   explicit-policy indicator; so giving preference to certification
   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 sorting method 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 method.

3.5.14.  Policies Intersect the Sought Policy Set

   May be used to eliminate certificates: No
   Number of possible values: Additive
   Components required: None

   Forward Method:  Certificates that assert policies found in the
   initial-acceptable-policy-set 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 Method:  Certificates that assert policies found in the
   target certificate or map policies to those found in the target
   certificate 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 trust anchor in a cross-certified environment, the policies
   asserted in the CA certificates will 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 trust anchor.  In the reverse direction,
   finding policies that match those of the target certificate may
   indicate that the path is drawing near to the target's domain.

3.5.15.  Endpoint Distinguished Name (DN) Matching

   May be used to eliminate certificates: No
   Number of possible values: Binary
   Components required: None

   Forward Method:  Certificates whose issuer exactly matches a trust
   anchor subject DN have priority.

   Reverse Method:  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 trust anchor's DN [X.501], then it may complete the
   path.  In the reverse direction, if the certificate's subject DN
   matches the issuer DN of the target certificate, it may be the last
   certificate required to complete the path.

3.5.16.  Relative Distinguished Name (RDN) Matching

   May be used to eliminate certificates: No
   Number of possible values: Sliding Scale
   Components required: None

   Forward Method:  Certificates that match more ordered RDNs between
   the issuer DN and a trust anchor DN have priority.  When all the RDNs
   match, this yields the highest priority.

   Reverse Method: Certificates with subject DNs that match more RDNs
   with the target's issuer DN have higher priority.  When all the RDNs
   match, this yields 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
   anchor is to be found in that direction within the tree.  Note that
   in the case where all the RDNs match [X.501], this sorting method
   appears to mirror the preceding one.  However, this sorting method
   should be capable of producing a 100% weight even if the issuer DN
   has more RDNs than the trust anchor.  The Issuer DN need only contain
   all the RDNs (in order) of the trust anchor.

   NOTE: In the case where all RDNs match, this sorting method mirrors
   the functionality of the preceding one.  This allows for partial

   matches to be weighted differently from exact matches.  Additionally,
   this method can require a lot of processing if many trust anchors are
   present.

3.5.17.  Certificates are Retrieved from cACertificate Directory
         Attribute

   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 and Remote Certificate
   Storage/Retrieval using a directory

   Forward Method:   Certificates retrieved from the cACertificate
   directory attribute have priority over certificates retrieved from
   the crossCertificatePair attribute. (See [RFC2587].)

   Reverse Method:  Does not apply.

   Justification:  The cACertificate directory attribute contains
   certificates issued from local sources and self issued certificates.
   By using the cACertificate directory attribute before the
   crossCertificatePair 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.  Most of today's PKI applications spend most of their
   time processing information from the local (user's own) PKI, and the
   local PKI is usually very efficient to traverse due to proximity and
   network speed.

3.5.18.  Consistent Public Key and Signature Algorithms

   May be used to eliminate certificates: Yes
   Number of possible values: Binary
   Components required: None

   Forward Method:  If the public key in the issuer 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.)

   Reverse Method:  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 are not
   consistent, the signature on the subject certificate will not verify

   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.5.19.  Similar Issuer and Subject Names

   May be used to eliminate certificates:  No
   Number of possible values:  Sliding Scale
   Components required:  None

   Forward Method:  Certificates encountered with a subject DN that
   matches more RDNs with the issuer DN of the target certificate have
   priority.

   Reverse Method:  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.5.20.  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 directory as the repository)

   Forward Method:  A certificate whose issuer certificate is present in
   the certificate cache and populated with certificates has higher
   priority.  A certificate whose issuer's entry is fully populated with
   current data (all certificate attributes have been searched within
   the timeout period) has higher priority.

   Reverse Method:  If the subject of a 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 trust anchor (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.5.21.  Current CRL Found in Local Cache

   May be used to eliminate certificates: No
   Number of possible values:  Binary
   Components Required:  CRL Cache

   Forward Method:  Certificates have priority if the issuer's CRL entry
   exists and is populated with current data in the CRL cache.

   Reverse Method:  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 remote retrievals until necessary.

3.6.  Certificate Sorting Methods for Revocation Signer Certification
      Paths

   Unless using a locally-configured OCSP responder or some other
   locally-configured trusted revocation status service, certificate
   revocation information is expected to be provided by the PKI that
   issued the certificate.  It follows that when building a
   certification path for a Revocation Signer certificate, it is
   desirable to confine the building algorithm to the PKI that issued
   the certificate.  The following sorting methods seek to order
   possible paths so that the intended Revocation Signer certification
   path is found first.

   These sorting methods are not intended to be used in lieu of the ones
   described in the previous section; they are most effective when used
   in conjunction with those in Section 3.5. Some sorting criteria below
   have identical names as those in the preceding section.  This
   indicates that the sorting criteria described in the preceding
   section are modified slightly when building the Revocation Signer
   certification path.

3.6.1.  Identical Trust Anchors

   May be used to eliminate certificates: No
   Number of possible values: Binary
   Components required: Is-revocation-signer indicator and the
   Certification Authority's trust anchor

   Forward Method:  Not applicable.

   Reverse Method:  Path building should begin from the same trust
   anchor used to validate the Certification Authority before trying any
   other trust anchors.  If any trust anchors exist with a different
   public key but an identical subject DN to that of the Certification
   Authority's trust anchor, they should be tried prior to those with
   mismatched names.

   Justification:  The revocation information for a given certificate
   should be produced by the PKI that issues the certificate.
   Therefore, building a path from a different trust anchor than the
   Certification Authority's is not desirable.

3.6.2.  Endpoint Distinguished Name (DN) Matching

   May be used to eliminate certificates: No
   Number of possible values: Binary
   Components required: Is-revocation-signer indicator and the
   Certification Authority's trust anchor

   Forward Method:  Operates identically to the sorting method described
   in 3.5.15, except that instead of performing the matching against all
   trust anchors, the DN matching is performed only against the trust
   anchor DN used to validate the CA certificate.

   Reverse Method:  No change for Revocation Signer's certification
   path.

   Justification:  The revocation information for a given certificate
   should be produced by the PKI that issues the certificate.
   Therefore, building a path to a different trust anchor than the CA's
   is not desirable.  This sorting method helps to guide forward
   direction path building toward the trust anchor used to validate the
   CA certificate.

3.6.3.  Relative Distinguished Name (RDN) Matching

   May be used to eliminate certificates: No
   Number of possible values: Sliding Scale
   Components required: Is-revocation-signer indicator and the
   Certification Authority's trust anchor

   Forward Method:  Operates identically to the sorting method described
   in 3.5.16 except that instead of performing the RDN matching against
   all trust anchors, the matching is performed only against the trust
   anchor DN used to validate the CA certificate.

   Reverse Method:  No change for Revocation Signer's certification
   path.

   Justification:  The revocation information for a given certificate
   should be produced by the PKI that issues the certificate.
   Therefore, building a path to a different trust anchor than the CA's
   is not desirable.  This sorting method helps to guide forward
   direction path building toward the trust anchor used to validate the
   CA certificate.

3.6.4.  Identical Intermediate Names

   May be used to eliminate certificates: No
   Number of possible values: Binary
   Components required: Is-revocation-signer indicator and the
   Certification Authority's complete certification path

   Forward Method:  If the issuer DN in the certificate matches the
   issuer DN of a certificate in the Certification Authority's path, it
   has higher priority.

   Reverse Method:  If the subject DN in the certificate matches the
   subject DN of a certificate in the Certification Authority's path, it
   has higher priority.

   Justification:  Following the same path as the Certificate should
   deter the path-building algorithm from wandering in an inappropriate
   direction.  Note that this sorting method is indifferent to whether
   the certificate is self-issued.  This is beneficial in this situation
   because it would be undesirable to lower the priority of a re-key
   certificate.