summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc4158.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc4158.txt')
-rw-r--r--doc/rfc/rfc4158.txt4539
1 files changed, 4539 insertions, 0 deletions
diff --git a/doc/rfc/rfc4158.txt b/doc/rfc/rfc4158.txt
new file mode 100644
index 0000000..52716e1
--- /dev/null
+++ b/doc/rfc/rfc4158.txt
@@ -0,0 +1,4539 @@
+
+
+
+
+
+
+Network Working Group M. Cooper
+Request for Comments: 4158 Orion Security Solutions
+Category: Informational Y. Dzambasow
+ A&N Associates
+ P. Hesse
+ Gemini Security Solutions
+ S. Joseph
+ Van Dyke Technologies
+ R. Nicholas
+ BAE Systems
+ September 2005
+
+
+ Internet X.509 Public Key Infrastructure:
+ Certification Path Building
+
+Status of This Memo
+
+ This memo provides information for the Internet community. It does
+ not specify an Internet standard of any kind. Distribution of this
+ memo is unlimited.
+
+Copyright Notice
+
+ Copyright (C) The Internet Society (2005).
+
+Abstract
+
+ This document provides guidance and recommendations to developers
+ building X.509 public-key certification paths within their
+ applications. By following the guidance and recommendations defined
+ in this document, an application developer is more likely to develop
+ a robust X.509 certificate-enabled application that can build valid
+ certification paths across a wide range of PKI environments.
+
+Table of Contents
+
+ 1. Introduction ....................................................3
+ 1.1. Motivation .................................................4
+ 1.2. Purpose ....................................................4
+ 1.3. Terminology ................................................5
+ 1.4. Notation ...................................................8
+ 1.5. Overview of PKI Structures .................................8
+ 1.5.1. Hierarchical Structures .............................8
+ 1.5.2. Mesh Structures ....................................10
+ 1.5.3. Bi-Lateral Cross-Certified Structures ..............11
+ 1.5.4. Bridge Structures ..................................13
+ 1.6. Bridge Structures and Certification Path Processing .......14
+
+
+
+Cooper, et al. Informational [Page 1]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 2. Certification Path Building ....................................15
+ 2.1. Introduction to Certification Path Building ...............15
+ 2.2. Criteria for Path Building ................................16
+ 2.3. Path-Building Algorithms ..................................17
+ 2.4. How to Build a Certification Path .........................21
+ 2.4.1. Certificate Repetition .............................23
+ 2.4.2. Introduction to Path-Building Optimization .........24
+ 2.5. Building Certification Paths for Revocation Signer
+ Certificates ..............................................30
+ 2.6. Suggested Path-Building Software Components ...............31
+ 2.7. Inputs to the Path-Building Module ........................33
+ 2.7.1. Required Inputs ....................................33
+ 2.7.2. Optional Inputs ....................................34
+ 3. Optimizing Path Building .......................................35
+ 3.1. Optimized Path Building ...................................35
+ 3.2. Sorting vs. Elimination ...................................38
+ 3.3. Representing the Decision Tree ............................41
+ 3.3.1. Node Representation for CA Entities ................41
+ 3.3.2. Using Nodes to Iterate Over All Paths ..............42
+ 3.4. Implementing Path-Building Optimization ...................45
+ 3.5. Selected Methods for Sorting Certificates .................46
+ 3.5.1. basicConstraints Is Present and cA Equals True .....47
+ 3.5.2. Recognized Signature Algorithms ....................48
+ 3.5.3. keyUsage Is Correct ................................48
+ 3.5.4. Time (T) Falls within the Certificate Validity .....48
+ 3.5.5. Certificate Was Previously Validated ...............49
+ 3.5.6. Previously Verified Signatures .....................49
+ 3.5.7. Path Length Constraints ............................50
+ 3.5.8. Name Constraints ...................................50
+ 3.5.9. Certificate Is Not Revoked .........................51
+ 3.5.10. Issuer Found in the Path Cache ....................52
+ 3.5.11. Issuer Found in the Application Protocol ..........52
+ 3.5.12. Matching Key Identifiers (KIDs) ...................52
+ 3.5.13. Policy Processing .................................53
+ 3.5.14. Policies Intersect the Sought Policy Set ..........54
+ 3.5.15. Endpoint Distinguished Name (DN) Matching .........55
+ 3.5.16. Relative Distinguished Name (RDN) Matching ........55
+ 3.5.17. Certificates are Retrieved from
+ cACertificate Directory Attribute .................56
+ 3.5.18. Consistent Public Key and Signature Algorithms ....56
+ 3.5.19. Similar Issuer and Subject Names ..................57
+ 3.5.20. Certificates in the Certification Cache ...........57
+ 3.5.21. Current CRL Found in Local Cache ..................58
+ 3.6. Certificate Sorting Methods for Revocation Signer
+ Certification Paths .......................................58
+ 3.6.1. Identical Trust Anchors ............................58
+ 3.6.2. Endpoint Distinguished Name (DN) Matching ..........59
+ 3.6.3. Relative Distinguished Name (RDN) Matching .........59
+
+
+
+Cooper, et al. Informational [Page 2]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 3.6.4. Identical Intermediate Names .......................60
+ 4. Forward Policy Chaining ........................................60
+ 4.1. Simple Intersection .......................................61
+ 4.2. Policy Mapping ............................................62
+ 4.3. Assigning Scores for Forward Policy Chaining ..............63
+ 5. Avoiding Path-Building Errors ..................................64
+ 5.1. Dead Ends .................................................64
+ 5.2. Loop Detection ............................................65
+ 5.3. Use of Key Identifiers ....................................66
+ 5.4. Distinguished Name Encoding ...............................66
+ 6. Retrieval Methods ..............................................67
+ 6.1. Directories Using LDAP ....................................67
+ 6.2. Certificate Store Access via HTTP .........................69
+ 6.3. Authority Information Access ..............................69
+ 6.4. Subject Information Access ................................70
+ 6.5. CRL Distribution Points ...................................70
+ 6.6. Data Obtained via Application Protocol ....................71
+ 6.7. Proprietary Mechanisms ....................................71
+ 7. Improving Retrieval Performance ................................71
+ 7.1. Caching ...................................................72
+ 7.2. Retrieval Order ...........................................73
+ 7.3. Parallel Fetching and Prefetching .........................73
+ 8. Security Considerations ........................................74
+ 8.1. General Considerations for Building a Certification Path ..74
+ 8.2. Specific Considerations for Building Revocation
+ Signer Paths ..............................................75
+ 9. Acknowledgements ...............................................78
+ 10. Normative References ..........................................78
+ 11. Informative References ........................................78
+
+1. Introduction
+
+ [X.509] public key certificates have become an accepted method for
+ securely binding the identity of an individual or device to a public
+ key, in order to support public key cryptographic operations such as
+ digital signature verification and public key-based encryption.
+ However, prior to using the public key contained in a certificate, an
+ application first has to determine the authenticity of that
+ certificate, and specifically, the validity of all the certificates
+ leading to a trusted public key, called a trust anchor. Through
+ validating this certification path, the assertion of the binding made
+ between the identity and the public key in each of the certificates
+ can be traced back to a single trust anchor.
+
+ The process by which an application determines this authenticity of a
+ certificate is called certification path processing. Certification
+ path processing establishes a chain of trust between a trust anchor
+ and a certificate. This chain of trust is composed of a series of
+
+
+
+Cooper, et al. Informational [Page 3]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ certificates known as a certification path. A certification path
+ begins with a certificate whose signature can be verified using a
+ trust anchor and ends with the target certificate. Path processing
+ entails building and validating the certification path to determine
+ whether a target certificate is appropriate for use in a particular
+ application context. See Section 3.2 of [RFC3280] for more
+ information on certification paths and trust.
+
+1.1. Motivation
+
+ Many other documents (such as [RFC3280]) cover certification path
+ validation requirements and procedures in detail but do not discuss
+ certification path building because the means used to find the path
+ does not affect its validation. This document therefore is an effort
+ to provide useful guidance for developers of certification path-
+ building implementations.
+
+ Additionally, the need to develop complex certification paths is
+ increasing. Many PKIs are now using complex structures (see Section
+ 1.5) rather than simple hierarchies. Additionally, some enterprises
+ are gradually moving away from trust lists filled with many trust
+ anchors, and toward an infrastructure with one trust anchor and many
+ cross-certified relationships. This document provides helpful
+ information for developing certification paths in these more
+ complicated situations.
+
+1.2. Purpose
+
+ This document provides information and guidance for certification
+ path building. There are no requirements or protocol specifications
+ in this document. This document provides many options for performing
+ certification path building, as opposed to just one particular way.
+ This document draws upon the authors' experiences with existing
+ complex certification paths to offer insights and recommendations to
+ developers who are integrating support for [X.509] certificates into
+ their applications.
+
+ In addition, this document suggests using an effective general
+ approach to path building that involves a depth first tree traversal.
+ While the authors believe this approach offers the balance of
+ simplicity in design with very effective and infrastructure-neutral
+ path-building capabilities, the algorithm is no more than a suggested
+ approach. Other approaches (e.g., breadth first tree traversals)
+ exist and may be shown to be more effective under certain conditions.
+ Certification path validation is described in detail in both [X.509]
+ and [RFC3280] and is not repeated in this document.
+
+
+
+
+
+Cooper, et al. Informational [Page 4]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ This document does not provide guidance for building the
+ certification path from an end entity certificate to a proxy
+ certificate as described in [RFC3820].
+
+1.3. Terminology
+
+ Terms used throughout this document will be used in the following
+ ways:
+
+ Building in the Forward direction: The process of building a
+ certification path from the target certificate to a trust anchor.
+ 'Forward' is the former name of the crossCertificatePair element
+ 'issuedToThisCA'.
+
+ Building in the Reverse direction: The process of building a
+ certification path from a trust anchor to the target certificate.
+ 'Reverse' is the former name of the crossCertificatePair element
+ 'issuedByThisCA'.
+
+ Certificate: A digital binding that cannot be counterfeited between
+ a named entity and a public key.
+
+ Certificate Graph: A graph that represents the entire PKI (or all
+ cross-certified PKIs) in which all named entities are viewed as
+ nodes and all certificates are viewed as arcs between nodes.
+
+ Certificate Processing System: An application or device that
+ performs the functions of certification path building and
+ certification path validation.
+
+ Certification Authority (CA): An entity that issues and manages
+ certificates.
+
+ Certification Path: An ordered list of certificates starting with a
+ certificate signed by a trust anchor and ending with the target
+ certificate.
+
+ Certification Path Building: The process used to assemble the
+ certification path between the trust anchor and the target
+ certificate.
+
+ Certification Path Validation: The process that verifies the binding
+ between the subject and the subject-public-key defined in the
+ target certificate, using a trust anchor and set of known
+ constraints.
+
+
+
+
+
+
+Cooper, et al. Informational [Page 5]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ Certificate Revocation List (CRL): A signed, time stamped list
+ identifying a set of certificates that are no longer considered
+ valid by the certificate issuer.
+
+ CRL Signer Certificate: The specific certificate that may be used for
+ verifying the signature on a CRL issued by, or on behalf of, a
+ specific CA.
+
+ Cross-Certificate: A certificate issued by one CA to another CA for
+ the purpose of establishing a trust relationship between the two
+ CAs.
+
+ Cross-Certification: The act of issuing cross-certificates.
+
+ Decision Tree: When the path-building software has multiple
+ certificates to choose from, and must make a decision, the
+ collection of possible choices is called a decision tree.
+
+ Directory: Generally used to refer an LDAP accessible repository for
+ certificates and PKI information. The term may also be used
+ generically to refer to any certificate storing repository.
+
+ End Entity: The holder of a private key and corresponding
+ certificate, whose identity is defined as the Subject of the
+ certificate. Human end entities are often called "subscribers".
+
+ Is-revocation-signer indicator: A boolean flag furnished to the
+ path-building software. If set, this indicates that the target
+ certificate is a Revocation Signer certificate for a specific CA.
+ For example, if building a certification path for an indirect CRL
+ Signer certificate, this flag would be set.
+
+ Local PKI: The set of PKI components and data (certificates,
+ directories, CRLs, etc.) that are created and used by the
+ certificate using organization. In general, this concept refers
+ to the components that are in close proximity to the certificate
+ using application. The assumption is that the local data is more
+ easily accessible and/or inexpensive to retrieve than non-local
+ PKI data.
+
+ Local Realm: See Local PKI.
+
+ Node (in a certificate graph): The collection of certificates having
+ identical subject distinguished names.
+
+ Online Certificate Status Protocol (OCSP): An Internet protocol used
+ by a client to obtain the revocation status of a certificate from
+ a server.
+
+
+
+Cooper, et al. Informational [Page 6]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ OCSP Response Signer Certificate: The specific certificate that may
+ be used for verifying the signature on an OCSP response. This
+ response may be provided by the CA, on behalf of the CA, or by a
+ different signer as determined by the Relying Party's local
+ policy.
+
+ Public Key Infrastructure (PKI): The set of hardware, software,
+ personnel, policy, and procedures used by a CA to issue and manage
+ certificates.
+
+ Relying Party (RP): An application or entity that processes
+ certificates for the purpose of 1) verifying a digital signature,
+ 2) authenticating another entity, or 3) establishing confidential
+ communications.
+
+ Revocation Signer Certificate: Refers collectively to either a CRL
+ Signer Certificate or OCSP Response Signer Certificate.
+
+ Target Certificate: The certificate that is to be validated by a
+ Relying Party. It is the "Certificate targeted for validation".
+ Although frequently this is the End Entity or a leaf node in the
+ PKI structure, this could also be a CA certificate if a CA
+ certificate is being validated. (e.g., This could be for the
+ purpose of building and validating a certification path for the
+ signer of a CRL.)
+
+ Trust (of public keys): In the scope of this document, a public key
+ is considered trustworthy if the certificate containing the public
+ key can be validated according to the procedures in [RFC3280].
+
+ Trust List: A list of trust anchors.
+
+ Trust Anchor: The combination of a trusted public key and the name of
+ the entity to which the corresponding private key belongs.
+
+ Trust Anchor Certificate: A self-signed certificate for a trust
+ anchor that is used in certification path processing.
+
+ User: An individual that is using a certificate processing system.
+ This document refers to some cases in which users may or may not
+ be prompted with information or requests, depending upon the
+ implementation of the certificate processing system.
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 7]
+
+RFC 4158 Certification Path Building September 2005
+
+
+1.4. Notation
+
+ This document makes use of a few common notations that are used in
+ the diagrams and examples.
+
+ The first is the arrow symbol (->) which represents the issuance of a
+ certificate from one entity to another. For example, if entity H
+ were to issue a certificate to entity K, this is denoted as H->K.
+
+ Sometimes it is necessary to specify the subject and issuer of a
+ given certificate. If entity H were to issue a certificate to entity
+ K this can be denoted as K(H).
+
+ These notations can be combined to denote complicated certification
+ paths such as C(D)->B(C)->A(B).
+
+1.5. Overview of PKI Structures
+
+ When verifying [X.509] public key certificates, often the application
+ performing the verification has no knowledge of the underlying Public
+ Key Infrastructure (PKI) that issued the certificate. PKI structures
+ can range from very simple, hierarchical structures to complex
+ structures such as mesh architectures involving multiple bridges (see
+ Section 1.5.4). These structures define the types of certification
+ paths that might be built and validated by an application [MINHPKIS].
+ This section describes four common PKI structures.
+
+1.5.1. Hierarchical Structures
+
+ A hierarchical PKI, depicted in Figure 1, is one in which all of the
+ end entities and relying parties use a single "Root CA" as their
+ trust anchor. If the hierarchy has multiple levels, the Root CA
+ certifies the public keys of intermediate CAs (also known as
+ subordinate CAs). These CAs then certify end entities'
+ (subscribers') public keys or may, in a large PKI, certify other CAs.
+ In this architecture, certificates are issued in only one direction,
+ and a CA never certifies another CA "superior" to itself. Typically,
+ only one superior CA certifies each CA.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 8]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---------+
+ +---| Root CA |---+
+ | +---------+ |
+ | |
+ | |
+ v v
+ +----+ +----+
+ +-----| CA | +-----| CA |------+
+ | +----+ | +----+ |
+ | | |
+ v v v
+ +----+ +----+ +----+
+ +--| CA |-----+ | CA |-+ +---| CA |---+
+ | +----+ | +----+ | | +----+ |
+ | | | | | | | |
+ | | | | | | | |
+ v v v v v v v v
+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
+ | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
+
+ Figure 1 - Sample Hierarchical PKI
+
+ Certification path building in a hierarchical PKI is a
+ straightforward process that simply requires the relying party to
+ successively retrieve issuer certificates until a certificate that
+ was issued by the trust anchor (the "Root CA" in Figure 1) is
+ located.
+
+ A widely used variation on the single-rooted hierarchical PKI is the
+ inclusion of multiple CAs as trust anchors. (See Figure 2.) Here,
+ end entity certificates are validated using the same approach as with
+ any hierarchical PKI. The difference is that a certificate will be
+ accepted if it can be verified back to any of the set of trust
+ anchors. Popular web browsers use this approach, and are shipped
+ with trust lists containing dozens to more than one hundred CAs.
+ While this approach simplifies the implementation of a limited form
+ of certificate verification, it also may introduce certain security
+ vulnerabilities. For example, the user may have little or no idea of
+ the policies or operating practices of the various trust anchors, and
+ may not be aware of which root was used to verify a given
+ certificate. Additionally, the compromise of any trusted CA private
+ key or the insertion of a rogue CA certificate to the trust list may
+ compromise the entire system. Conversely, if the trust list is
+ properly managed and kept to a reasonable size, it can be an
+ efficient solution to building and validating certification paths.
+
+
+
+
+
+Cooper, et al. Informational [Page 9]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +-------------------------------------------------------+
+ | Trust List |
+ | |
+ | +---------+ +---------+ +---------+ |
+ | +--| Root CA | | Root CA | | Root CA | |
+ | | +---------+ +---------+ +---------+ |
+ | | | | | |
+ +--|------|----------------|---------------- |----------+
+ | | | |
+ | | | |
+ | | v |
+ | | +----+ |
+ | | +----| CA |---+ |
+ | | | +----+ | |
+ | | | | |
+ | | v v v
+ | | +----+ +----+ +----+
+ | | | CA |---+ | CA |-+ | CA |---+
+ | | +----+ | +----+ | +----+ |
+ | | | | | | | |
+ | | | | | | | |
+ v v v v v v v v
+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
+ | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
+
+ Figure 2 - Multi-Rooted Hierarchical PKI
+
+1.5.2. Mesh Structures
+
+ In a typical mesh style PKI (depicted in Figure 3), each end entity
+ trusts the CA that issued their own certificate(s). Thus, there is
+ no 'Root CA' for the entire PKI. The CAs in this environment have
+ peer relationships; they are neither superior nor subordinate to one
+ another. In a mesh, CAs in the PKI cross-certify. That is, each CA
+ issues a certificate to, and is issued a certificate by, peer CAs in
+ the PKI. The figure depicts a mesh PKI that is fully cross-certified
+ (sometimes called a full mesh). However, it is possible to architect
+ and deploy a mesh PKI with a mixture of uni-directional and bi-
+ directional cross-certifications (called a partial mesh). Partial
+ meshes may also include CAs that are not cross-certified with other
+ CAs in the mesh.
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 10]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---------------------------------+
+ | |
+ +-----------+----------------------+ |
+ | v v |
+ | +-------+ +------+ |
+ | +--->| CA B |<------------->| CA C |<--+ |
+ | | +-------+ +------+ | |
+ | | | ^ ^ | | |
+ | | v | | | | |
+ | | +----+ | | | | |
+ | | | EE | +----+ +--------+ v | |
+ | | +----+ | | +----+ | |
+ | | | | | EE | | |
+ v v v v +----+ v v
+ +------+ +------+ +------+
+ | CA E |<----------->| CA A |<----------->| CA D |
+ +------+ +------+ +------+
+ | ^ ^ ^ ^ |
+ | | | | | |
+ v | +------------------------------------+ | v
+ +----+ | | +----+
+ | EE | | +------+ | | EE |
+ +----+ +----------------| CA F |-----------------+ +----+
+ +------+
+
+ Figure 3 - Mesh PKI
+
+ Certification path building in a mesh PKI is more complex than in a
+ hierarchical PKI due to the likely existence of multiple paths
+ between a relying party's trust anchor and the certificate to be
+ verified. These multiple paths increase the potential for creating
+ "loops", "dead ends", or invalid paths while building the
+ certification path between a trust anchor and a target certificate.
+ In addition, in cases where no valid path exists, the total number of
+ paths traversed by the path-building software in order to conclude
+ "no path exists" can grow exceedingly large. For example, if
+ ignoring everything except the structure of the graph, the Mesh PKI
+ figure above has 22 non-self issued CA certificates and a total of
+ 5,092,429 certification paths between CA F and the EE issued by CA D
+ without repeating any certificates.
+
+1.5.3. Bi-Lateral Cross-Certified Structures
+
+ PKIs can be connected via cross-certification to enable the relying
+ parties of each to verify and accept certificates issued by the other
+ PKI. If the PKIs are hierarchical, cross-certification will
+ typically be accomplished by each Root CA issuing a certificate for
+ the other PKI's Root CA. This results in a slightly more complex,
+
+
+
+Cooper, et al. Informational [Page 11]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ but still essentially hierarchical environment. If the PKIs are mesh
+ style, then a CA within each PKI is selected, more or less
+ arbitrarily, to establish the cross-certification, effectively
+ creating a larger mesh PKI. Figure 4 depicts a hybrid situation
+ resulting from a hierarchical PKI cross-certifying with a mesh PKI.
+
+ PKI 1 and 2 cross-certificates
+ +-------------------------------+
+ | |
+ | v
+ | +---------+
+ | +----| Root CA |---+
+ | | +---------+ |
+ | | PKI 1 |
+ | v v
+ | +------+ +------+
+ v PKI 2 +-| CA |-+ | CA |
+ +------+ | +------+ | +------+
+ +------->| CA |<-----+ | | | | |
+ | +------+ | | | | | |
+ | | | | v v v v v
+ | | | | +----+ +----+ +----+ +----+ +----+
+ | v v | | EE | | EE | | EE | | EE | | EE |
+ | +----+ +----+ | +----+ +----+ +----+ +----+ +----+
+ | | EE | | EE | |
+ | +----+ +----+ |
+ v v
+ +------+ +------+
+ | CA |<-------------->| CA |------+
+ +------+ +------+ |
+ | | | | |
+ | | | | |
+ v v v v v
+ +----+ +----+ +----+ +----+ +----+
+ | EE | | EE | | EE | | EE | | EE |
+ +----+ +----+ +----+ +----+ +----+
+
+ Figure 4 - Hybrid PKI
+
+ In current implementations, this situation creates a concern that the
+ applications used under the hierarchical PKIs will not have path
+ building capabilities robust enough to handle this more complex
+ certificate graph. As the number of cross-certified PKIs grows, the
+ number of the relationships between them grows exponentially. Two
+ principal concerns about cross-certification are the creation of
+ unintended certification paths through transitive trust, and the
+ dilution of assurance when a high-assurance PKI with restrictive
+ operating policies is cross-certified with a PKI with less
+
+
+
+Cooper, et al. Informational [Page 12]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ restrictive policies. (Proper name constraints and certificate
+ policies processing can help mitigate the problem of assurance
+ dilution.)
+
+1.5.4. Bridge Structures
+
+ Another approach to the interconnection of PKIs is the use of a
+ "bridge" certification authority (BCA). A BCA is a nexus to
+ establish trust paths among multiple PKIs. The BCA cross-certifies
+ with one CA in each participating PKI. Each PKI only cross-certifies
+ with one other CA (i.e., the BCA), and the BCA cross-certifies only
+ once with each participating PKI. As a result, the number of cross
+ certified relationships in the bridged environment grows linearly
+ with the number of PKIs whereas the number of cross-certified
+ relationships in mesh architectures grows exponentially. However,
+ when connecting PKIs in this way, the number and variety of PKIs
+ involved results in a non-hierarchical environment, such as the one
+ as depicted in Figure 5. (Note: as discussed in Section 2.3, non-
+ hierarchical PKIs can be considered hierarchical, depending upon
+ perspective.)
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 13]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ PKI 1 cross-certified with Bridge
+ +-------------------------------+
+ | |
+ v v
+ +-----------+ +---------+
+ | Bridge CA | +---| Root CA |-----+
+ +-----------+ | +---------+ |
+ ^ | PKI 1 |
+ PKI 2 cross|cert with Bridge v v
+ | +------+ +------+
+ v PKI 2 +-| CA |-+ | CA |
+ +------+ | +------+ | +------+
+ +------->| CA |<-----+ | | | | |
+ | +------+ | | | | | |
+ | | | | v v v v v
+ | | | | +----+ +----+ +----+ +----+ +----+
+ | v v | | EE | | EE | | EE | | EE | | EE |
+ | +----+ +----+ | +----+ +----+ +----+ +----+ +----+
+ | | EE | | EE | |
+ | +----+ +----+ |
+ v v
+ +------+ +------+
+ | CA |<-------------->| CA |------+
+ +------+ +------+ |
+ | | | | |
+ | | | | |
+ v v v v v
+ +----+ +----+ +----+ +----+ +----+
+ | EE | | EE | | EE | | EE | | EE |
+ +----+ +----+ +----+ +----+ +----+
+
+ Figure 5 - Cross-Certification with a Bridge CA
+
+1.6. Bridge Structures and Certification Path Processing
+
+ Developers building certificate-enabled applications intended for
+ widespread use throughout various sectors are encouraged to consider
+ supporting a Bridge PKI structure because implementation of
+ certification path processing functions to support a Bridge PKI
+ structure requires support of all the PKI structures (e.g.,
+ hierarchical, mesh, hybrid) which the Bridge may connect. An
+ application that can successfully build valid certification paths in
+ all Bridge PKIs will therefore have implemented all of the processing
+ logic required to support the less complicated PKI structures. Thus,
+ if an application fully supports the Bridge PKI structure, it can be
+ deployed in any standards-compliant PKI environment and will perform
+ the required certification path processing properly.
+
+
+
+
+Cooper, et al. Informational [Page 14]
+
+RFC 4158 Certification Path Building September 2005
+
+
+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
+
+
+
+Cooper, et al. Informational [Page 15]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ rely on a PKI. Without valid certification paths, certificates
+ cannot be validated according to [RFC3280] and therefore cannot be
+ trusted. Thus, the ability to build a path is every bit as important
+ as the ability to validate it properly.
+
+ There are many issues that can complicate the path-building process.
+ For example, building a path through a cross-certified environment
+ could require the path-building module to traverse multiple PKI
+ domains spanning multiple directories, using multiple algorithms, and
+ employing varying key lengths. A path-building client may also need
+ to manage a number of trust anchors, partially populated directory
+ entries (e.g., missing issuedToThisCA entries in the
+ crossCertificatePair attribute), parsing of certain certificate
+ extensions (e.g., authorityInformationAccess) and directory
+ attributes (e.g., crossCertificatePair), and error handling such as
+ loop detection.
+
+ In addition, a developer has to decide whether to build paths from a
+ trust anchor (the reverse direction) to the target certificate or
+ from the target certificate (the forward direction) to a trust
+ anchor. Some implementations may even decide to use both. The
+ choice a developer makes should be dependent on the environment and
+ the underlying PKI for that environment. More information on making
+ this choice can be found in Section 2.3.
+
+2.2. Criteria for Path Building
+
+ From this point forward, this document will be discussing specific
+ algorithms and mechanisms to assist developers of certification
+ path-building implementations. To provide justification for these
+ mechanisms, it is important to denote what the authors considered the
+ criteria for a path-building implementation.
+
+ Criterion 1: The implementation is able to find all possible paths,
+ excepting paths containing repeated subject name/public key pairs.
+ This means that all potentially valid certification paths between the
+ trust anchor and the target certificate which may be valid paths can
+ be built by the algorithm. As discussed in Section 2.4.2, we
+ recommend that subject names and public key pairs are not repeated in
+ paths.
+
+ Criterion 2: The implementation is as efficient as possible. An
+ efficient certification path-building implementation is defined to be
+ one that builds paths that are more likely to validate following
+ [RFC3280], before building paths that are not likely to validate,
+ with the understanding that there is no way to account for all
+ possible configurations and infrastructures. This criterion is
+ intended to ensure implementations that can produce useful error
+
+
+
+Cooper, et al. Informational [Page 16]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ information. If a particular path is entirely valid except for a
+ single expired certificate, this is most likely the 'right' path. If
+ other paths are developed that are invalid for multiple obscure
+ reasons, this provides little useful information.
+
+ The algorithms and mechanisms discussed henceforth are chosen because
+ the authors consider them to be good methods for meeting the above
+ criteria.
+
+2.3. Path-Building Algorithms
+
+ It is intuitive for people familiar with the Bridge CA concept or
+ mesh type PKIs to view path building as traversing a complex graph.
+ However, from the simplest viewpoint, writing a path-building module
+ can be nothing more than traversal of a spanning tree, even in a very
+ complex cross-certified environment. Complex environments as well as
+ hierarchical PKIs can be represented as trees because certificates
+ are not permitted to repeat in a path. If certificates could be
+ repeated, loops can be formed such that the number of paths and
+ number of certificates in a path both increase without bound (e.g., A
+ issues to B, B issues to C, and C issues to A). Figure 7 below
+ illustrates this concept from the trust anchor's perspective.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 17]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---------+ +---------+
+ | 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.
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 18]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---------+ +---------+
+ | 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).
+
+
+
+
+
+Cooper, et al. Informational [Page 19]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 20]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ direction. Note: [RFC2587] does not require the issuedByThisCA
+ (reverse) cross-certificates to be populated; if they are
+ absent it will not be possible to build solely in the reverse
+ direction.
+
+ c. Are all issuer certificates available via some means other than
+ a directory (e.g., the authorityInformationAccess extension is
+ present and populated in all certificates)? If yes, you are
+ able to build in the forward direction.
+
+ 2) How many trust anchors will the path-building and validation
+ software be using?
+
+ a. Are there (or will there be) multiple trust anchors in the
+ local PKI? If yes, forward path building may offer better
+ performance.
+
+ b. Will the path-building and validation software need to place
+ trust in trust anchors from PKIs that do not populate reverse
+ cross-certificates for all intermediate CAs? If no, and the
+ local PKI populates reverse cross-certificates, reverse path
+ building is an option.
+
+2.4. How to Build a Certification Path
+
+ As was discussed in the prior section, path building is essentially a
+ tree traversal. It was easy to see how this is true in a simple
+ example, but how about a more complicated one? Before taking a look
+ at more a complicated scenario, it is worthwhile to address loops and
+ what constitutes a loop in a certification path. [X.509] specifies
+ that the same certificate may not repeat in a path. In a strict
+ sense, this works well as it is not possible to create an endless
+ loop without repeating one or more certificates in the path.
+ However, this requirement fails to adequately address Bridged PKI
+ environments.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 21]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---+ +---+
+ | 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
+
+
+
+
+
+
+Cooper, et al. Informational [Page 22]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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:
+
+
+
+
+Cooper, et al. Informational [Page 23]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ - First, certification paths like the example above are generally
+ not intended by the PKI designers and should not be necessary in
+ order to validate any given certificate. If a convoluted path
+ such as the example above is required (there is no corresponding
+ simple path) in order to validate a given certificate, this is
+ most likely indicative of a flaw in the PKI design.
+
+ - Second, the longer a path becomes, the greater the potential
+ dilution of trust in the certification path. That is, with each
+ successive link in the infrastructure (i.e., certification by
+ CAs and cross-certification between CAs) some amount of
+ assurance may be considered lost.
+
+ - Third, the longer and more complicated a path, the less likely
+ it is to validate because of basic constraints, policies or
+ policy constraints, name constraints, CRL availability, or even
+ revocation.
+
+ - Lastly, and certainly not least important from a developer's or
+ user's perspective, is performance. Allowing paths like the one
+ above dramatically increases the number of possible paths for
+ every certificate in a mesh or cross-certified environment.
+ Every path built may require one or more of the following:
+ validation of certificate properties, CPU intensive signature
+ validations, CRL retrievals, increased network load, and local
+ memory caching. Eliminating the superfluous paths can greatly
+ improve performance, especially in the case where no path
+ exists.
+
+ There is a special case involving certificates with the same
+ distinguished names but differing encodings required by [RFC3280].
+ This case should not be considered a repeated certificate. See
+ Section 5.4 for more information.
+
+2.4.2. Introduction to Path-Building Optimization
+
+ How can these superfluous paths be eliminated? Rather than only
+ disallowing identical certificates from repeating, it is recommended
+ that a developer disallow the same public key and subject name pair
+ from being repeated. For maximum flexibility, the subject name
+ should collectively include any subject alternative names. Using
+ this approach, all of the intended and needed paths should be
+ available, and the excess and diluted paths should be eliminated.
+ For example, using this approach, only one path exists from the TA Z
+ to EE in the diagram above: TA Z->BCA->X->L->N->EE.
+
+
+
+
+
+
+Cooper, et al. Informational [Page 24]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.)
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 25]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---+ +---+
+ | 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
+
+
+
+Cooper, et al. Informational [Page 26]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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).
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 27]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +----+ +----+ +----+
+ | 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
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 28]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +----+ +----+
+ | 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".
+
+
+
+Cooper, et al. Informational [Page 29]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 30]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ Authority to determine if any of the CRLs (a) cover the certificate
+ in question, (b) are current, and (c) are signed using the same key
+ used to sign the certificate.
+
+ When the Revocation Signer certificate is not identical to the
+ Certification Authority certificate, a certification path must be
+ built (and validated) for the Revocation Signer certificate. In
+ general, the certification path-building software may build the path
+ as it would for any other certificate. However, this document also
+ outlines methods in later sections for greatly improving path
+ building efficiency for Revocation Signer certificate case.
+
+2.6. Suggested Path-Building Software Components
+
+ There is no single way to define an interface to a path-building
+ module. It is not the intent of this document to prescribe a
+ particular method or semantic; rather, it is up to the implementer to
+ decide. There are many ways this could be done. For example, a
+ path-building module could build every conceivable path and return
+ the entire list to the caller. Or, the module could build until it
+ finds just one that validates and then terminate the procedure. Or,
+ it could build paths in an iterative fashion, depending on validation
+ outside of the builder and successive calls to the builder to get
+ more paths until one valid path is found or all possible paths have
+ been found. All of these are possible approaches, and each of these
+ may offer different benefits to a particular environment or
+ application.
+
+ Regardless of semantics, a path-building module needs to contain the
+ following components:
+
+ 1) The logic for building and traversing the certificate graph.
+
+ 2) Logic for retrieving the necessary certificates (and CRLs and/or
+ other revocation status information if the path is to be
+ validated) from the available source(s).
+
+ Assuming a more efficient and agile path-building module is desired,
+ the following is a good starting point and will tie into the
+ remainder of this document. For a path-building module to take full
+ advantage of all the suggested optimizations listed in this document,
+ it will need all of the components listed below.
+
+ 1) A local certificate and CRL cache.
+
+ a. This may be used by all certificate-using components; it does
+ not need to be specific to the path-building software. A local
+ cache could be memory resident, stored in an operating system
+
+
+
+Cooper, et al. Informational [Page 31]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ or application certificate store, stored in a database, or even
+ stored in individual files on the hard disk. While the
+ implementation of this cache is beyond the scope of this
+ document, some design considerations are listed below.
+
+ 2) The logic for building and traversing the certificate graph/tree.
+
+ a. This performs sorting functionality for prioritizing
+ certificates (thereby optimizing path building) while
+ traversing the tree.
+
+ b. There is no need to build a complete graph prior to commencing
+ path building. Since path building can be implemented as a
+ depth first tree traversal, the path builder only needs to
+ store the current location in the tree along with the points
+ traversed to the current location. All completed branches can
+ be discarded from memory and future branches are discovered as
+ the tree is traversed.
+
+ 3) Logic for retrieving the necessary certificates from the available
+ certificate source(s):
+
+ a. Local cache.
+
+ i. Be able to retrieve all certificates for an entity by
+ subject name, as well as individual certificates by
+ issuer and serial number tuple.
+
+ ii. Tracking which directory attribute (including
+ issuedToThisCA <forward> and issuedByThisCA <reverse>
+ for split crossCertificatePair attributes) each
+ certificate was found in may be useful. This allows for
+ functionality such as retrieving only forward cross-
+ certificates, etc.
+
+ iii. A "freshness" timestamp (cache expiry time) can be used
+ to determine when the directory should be searched
+ again.
+
+ b. LDAPv3 directory for certificates and CRLs.
+
+ i. Consider supporting multiple directories for general
+ queries.
+
+ ii. Consider supporting dynamic LDAP connections for
+ retrieving CRLs using an LDAP URI [RFC3986] in the CRL
+ distribution point certificate extension.
+
+
+
+
+Cooper, et al. Informational [Page 32]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ iii. Support LDAP referrals. This is typically only a matter
+ of activating the appropriate flag in the LDAP API.
+
+ c. HTTP support for CRL distribution points and authority
+ information access (AIA) support.
+
+ i. Consider HTTPS support, but be aware that this may create
+ an unbounded recursion when the implementation tries to
+ build a certification path for the server's certificate if
+ this in turn requires an additional HTTPS lookup.
+
+ 4) A certification path cache that stores previously validated
+ relationships between certificates. This cache should include:
+
+ a. A configurable expiration date for each entry. This date can
+ be configured based upon factors such as the expiry of the
+ information used to determine the validity of an entry,
+ bandwidth, assurance level, storage space, etc.
+
+ b. Support to store previously verified issuer certificate to
+ subject certificate relationships.
+
+ i. Since the issuer DN and serial number tuple uniquely
+ identifies a certificate, a pair of these tuples (one for
+ both the issuer and subject) is an effective method of
+ storing this relationship.
+
+ c. Support for storing "known bad" paths and certificates. Once a
+ certificate is determined to be invalid, implementations can
+ decide not to retry path development and validation.
+
+2.7. Inputs to the Path-Building Module
+
+ [X.509] specifically addresses the list of inputs required for path
+ validation but makes no specific suggestions concerning useful inputs
+ to path building. However, given that the goal of path building is
+ to find certification paths that will validate, it follows that the
+ same inputs used for validation could be used to optimize path
+ building.
+
+2.7.1. Required Inputs
+
+ Setting aside configuration information such as repository or cache
+ locations, the following are required inputs to the certification
+ path-building process:
+
+ 1) The Target Certificate: The certificate that is to be validated.
+ This is one endpoint for the path. (It is also possible to
+
+
+
+Cooper, et al. Informational [Page 33]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+
+
+Cooper, et al. Informational [Page 34]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 9) The complete certification path for the Certification Authority
+ (if Is-revocation-provider is set)
+
+ 10) Collection of certificates that may be useful in building the
+ path
+
+ 11) Collection of certificate revocation lists and/or other
+ revocation data
+
+ The last two items are a matter of convenience. Alternately,
+ certificates and revocation information could be placed in a local
+ cache accessible to the path-building module prior to attempting to
+ build a path.
+
+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:
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 35]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +---+
+ | 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.
+
+
+
+
+
+Cooper, et al. Informational [Page 36]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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)
+
+
+
+Cooper, et al. Informational [Page 37]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 38]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 39]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 40]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+
+
+Cooper, et al. Informational [Page 41]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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 "*".
+
+
+
+
+
+
+Cooper, et al. Informational [Page 42]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +-------------+ +---------------+
+ | 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 43]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ +-------------+ +---------------+ +------------------+
+ | 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).
+
+
+
+Cooper, et al. Informational [Page 44]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+Cooper, et al. Informational [Page 45]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+Cooper, et al. Informational [Page 46]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 47]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+
+Cooper, et al. Informational [Page 48]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 49]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+
+
+Cooper, et al. Informational [Page 50]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 51]
+
+RFC 4158 Certification Path Building September 2005
+
+
+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)
+
+
+
+Cooper, et al. Informational [Page 52]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 53]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 54]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 55]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 56]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+
+Cooper, et al. Informational [Page 57]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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
+
+
+
+Cooper, et al. Informational [Page 58]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+
+
+
+Cooper, et al. Informational [Page 59]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ 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.
+
+4. Forward Policy Chaining
+
+ It is tempting to jump to the conclusion that certificate policies
+ offer little assistance to path building when building from the
+ target certificate. It's easy to understand the "validate as you go"
+ approach from the trust anchor, and much less obvious that any value
+ can be derived in the other direction. However, since policy
+ validation consists of the intersection of the issuer policy set with
+ the subject policy set and the mapping of policies from the issuer
+ set to the subject set, policy validation can be done while building
+ a path in the forward direction as well as the reverse. It is simply
+ a matter of reversing the procedure. That is not to say this is as
+ ideal as policy validation when building from the trust anchor, but
+ it does offer a method that can be used to mostly eliminate what has
+ long been considered a weakness inherent to building in the forward
+ (from the target certificate) direction.
+
+
+
+Cooper, et al. Informational [Page 60]
+
+RFC 4158 Certification Path Building September 2005
+
+
+4.1. Simple Intersection
+
+ The most basic form of policy processing is the intersection of the
+ policy sets from the first CA certificate through the target
+ certificate. Fortunately, the intersection of policy sets will
+ always yield the same final set regardless of the order of
+ intersection. This allows processing of policy set intersections in
+ either direction. For example, if the trust anchor issues a CA
+ certificate (A) with policies {X,Y,Z}, and that CA issues another CA
+ certificate (B) with policies {X,Y}, and CA B then issues a third CA
+ certificate (C) with policy set {Y,G}, one normally calculates the
+ policy set from the trust anchor as follows:
+
+ 1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}
+
+ 2) Intersect that result, {X,Y} with C{Y,G} to yield the final set
+ {Y}
+
+ Now it has been shown that certificate C is good for policy Y.
+
+ The other direction is exactly the same procedure, only in reverse:
+
+ 1) Intersect C{Y,G} with B{X,Y} to yield the set {Y}
+
+ 2) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
+ {Y}
+
+ Just like in the reverse direction, it has been shown that
+ certificate C is good for policy Y, but this time in the forward
+ direction.
+
+ When building in the forward direction, policy processing is handled
+ much like it is in reverse -- the software lends preference to
+ certificates that propagate policies. Neither approach guarantees
+ that a path with valid policies will be found, but rather both
+ approaches help guide the path in the direction it should go in order
+ for the policies to propagate.
+
+ If the caller has supplied an initial-acceptable-policy set, there is
+ less value in using it when building in the forward direction unless
+ the caller also set inhibit-policy-mapping. In that case, the path
+ builder can further constrain the path building to propagating
+ policies that exist in the initial-acceptable-policy-set. However,
+ even if the inhibit-policy-mapping is not set, the initial-policy-set
+ can still be used to guide the path building toward the desired trust
+ anchor.
+
+
+
+
+
+Cooper, et al. Informational [Page 61]
+
+RFC 4158 Certification Path Building September 2005
+
+
+4.2. Policy Mapping
+
+ When a CA issues a certificate into another domain, an environment
+ with disparate policy identifiers to its own, the CA may make use of
+ policy mappings to map equivalence from the local domain's policy to
+ the non-local domain's policy. If in the prior example, A had
+ included a policy mapping that mapped X to G in the certificate it
+ issued to B, C would be good for X and Y:
+
+ 1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}
+
+ 2) Process Policy Mappings in B's certificate (X maps to G) to yield
+ {G,Y} (same as {Y,G})
+
+ 3) Intersect that result, {G,Y} with C{Y,G} to yield the final set
+ {G,Y}
+
+ Since policies are always expressed in the relying party's domain,
+ the certificate C is said to be good for {X, Y}, not {Y, G}. This is
+ because "G" doesn't mean anything in the context of the trust anchor
+ that issued A without the policy mapping.
+
+ When building in the forward direction, policies can be "unmapped" by
+ reversing the mapping procedure. This procedure is limited by one
+ important aspect: if policy mapping has occurred in the forward
+ direction, there is no mechanism by which it can be known in advance
+ whether or not a future addition to the current path will invalidate
+ the policy chain (assuming one exists) by setting inhibit-policy-
+ mapping. Fortunately, it is uncommon practice to set this flag. The
+ following is the procedure for processing policy mapping in the
+ forward direction:
+
+ 1) Begin with C's policy set {Y,G}
+
+ 2) Apply the policy mapping in B's certificate (X maps to G) in
+ reverse to yield {Y,X} (same as {X,Y})
+
+ 3) Intersect the result {X,Y} with B{X,Y} to yield the set {X,Y}
+
+ 4) Intersect that result, {X,Y}, with A{X,Y,Z} to yield the final set
+ {X,Y}
+
+ Just like in the reverse direction, it is determined in the forward
+ direction that certificate C is good for policies {X,Y}. If during
+ this procedure, an inhibit-policy-mapping flag was encountered, what
+ should be done? This is reasonably easy to keep track of as well.
+ The software simply maintains a flag on any policies that were
+ propagated as a result of a mapping; just a simple Boolean kept with
+
+
+
+Cooper, et al. Informational [Page 62]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ the policies in the set. Imagine now that the certificate issued to
+ A has the inhibit-policy-mapping constraint expressed with a skip
+ certificates value of zero.
+
+ 1) Begin with C's policy set {Y,G}
+
+ 2) Apply the policy mapping in B's certificate and mark X as
+ resulting from a mapping. (X maps to G) in reverse to yield {Y,Xm}
+ (same as {Xm,Y})
+
+ 3) Intersect the result {Xm,Y} with B{X,Y} to yield the set {Xm,Y}
+
+ 4) A's certificate expresses the inhibit policy mapping constraint,
+ so eliminate any policies in the current set that were propagated
+ due to mapping (which is Xm) to yield {Y}
+
+ 5) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
+ {Y}
+
+ If in our example, the policy set had gone to empty at any point (and
+ require-explicit-policy was set), the path building would back up and
+ try to traverse another branch of the tree. This is analogous to the
+ path-building functionality utilized in the reverse direction when
+ the policy set goes to empty.
+
+4.3. Assigning Scores for Forward Policy Chaining
+
+ Assuming the path-building module is maintaining the current forward
+ policy set, weights may be assigned using the following procedure:
+
+ 1) For each CA certificate being scored:
+
+ a. Copy the current forward policy set.
+
+ b. Process policy mappings in the CA certificate in order to
+ "un-map" policies, if any.
+
+ c. Intersect the resulting set with CA certificate's policies.
+
+ The larger the policy set yielded, the larger the score for that CA
+ certificate.
+
+ 2) If an initial acceptable set was supplied, intersect this set with
+ the resulting set for each CA certificate from (1).
+
+ The larger the resultant set, the higher the score is for this
+ certificate.
+
+
+
+
+Cooper, et al. Informational [Page 63]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ Other scoring schemes may work better if the operating environment
+ dictates.
+
+5. Avoiding Path-Building Errors
+
+ This section defines some errors that may occur during the path-
+ building process, as well as ways to avoid these errors when
+ developing path-building functions.
+
+5.1. Dead Ends
+
+ When building certification paths in a non-hierarchical PKI
+ structure, a simple path-building algorithm could fail prematurely
+ without finding an existing path due to a "dead end". Consider the
+ example in Figure 14.
+
+ +----+ +---+
+ | TA | | Z |
+ +----+ +---+
+ | |
+ | |
+ V V
+ +---+ +---+
+ | C |<-----| Y |
+ +---+ +---+
+ |
+ |
+ V
+ +--------+
+ | Target |
+ +--------+
+
+ Figure 14 - Dead End Example
+
+ Note that in the example, C has two certificates: one issued by Y,
+ and the other issued by the Trust Anchor. Suppose that a simple
+ "find issuer" algorithm is used, and the order in which the path
+ builder found the certificates was Target(C), C(Y), Y(Z), Z(Z). In
+ this case, Z has no certificates issued by any other entities, and so
+ the simplistic path-building process stops. Since Z is not the
+ relying party's trust anchor, the certification path is not complete,
+ and will not validate. This example shows that in anything but the
+ simplest PKI structure, additional path-building logic will need to
+ handle the cases in which entities are issued multiple certificates
+ from different issuers. The path-building algorithm will also need
+ to have the ability to traverse back up the decision tree and try
+ another path in order to be robust.
+
+
+
+
+Cooper, et al. Informational [Page 64]
+
+RFC 4158 Certification Path Building September 2005
+
+
+5.2. Loop Detection
+
+ In a non-hierarchical PKI structure, a path-building algorithm may
+ become caught in a loop without finding an existing path. Consider
+ the example below:
+
+ +----+
+ | TA |
+ +----+
+ |
+ |
+ +---+ +---+
+ | A | ->| Z |
+ +---+ / +---+
+ | / |
+ | / |
+ V / V
+ +---+ +---+
+ | B |<-----| Y |
+ +---+ +---+
+ |
+ |
+ V
+ +--------+
+ | Target |
+ +--------+
+
+ Figure 15 - Loop Example
+
+ Let us suppose that in this example the simplest "find issuer"
+ algorithm is used, and the order in which certificates are retrieved
+ is Target(B), B(Y), Y(Z), Z(B), B(Y), Y(Z), Z(B), B(Y), ... A loop
+ has formed that will cause the correct path (Target, B, A) to never
+ be found. The certificate processing system will need to recognize
+ loops created by duplicate certificates (which are prohibited in a
+ path by [X.509]) before they form to allow the certification path-
+ building process to continue and find valid paths. The authors of
+ this document recommend that the loop detection not only detect the
+ repetition of a certificate in the path, but also detect the presence
+ of the same subject name / subject alternative name/ subject public
+ key combination occurring twice in the path. A name/key pair should
+ only need to appear once in the path. (See Section 2.4.2 for more
+ information on the reasoning behind this recommendation.)
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 65]
+
+RFC 4158 Certification Path Building September 2005
+
+
+5.3. Use of Key Identifiers
+
+ Inconsistent and/or incompatible approaches to computing the subject
+ key identifier and authority key identifier in public key
+ certificates can cause failures in certification path-building
+ algorithms that use those fields to identify certificates, even
+ though otherwise valid certification paths may exist. Path-building
+ implementations should use existing key identifiers and not attempt
+ to re-compute subject key identifiers. It is extremely important
+ that Key Identifiers be used only as sorting criteria or hints. 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.
+
+ Path-building and processing implementations should not rely on the
+ form of authority key identifier that uses the authority DN and
+ serial number as a restrictive matching rule, because cross-
+ certification can lead to this value not being matched by the cross-
+ certificates.
+
+5.4. Distinguished Name Encoding
+
+ Certification path-building software should not rely on DNs being
+ encoded as PrintableString. Although frequently encoded as
+ PrintableString, DNs may also appear as other types, including
+ BMPString or UTF8String. As a result, software systems that are
+ unable to process BMPString and UTF8String encoded DNs may be unable
+ to build and validate some certification paths.
+
+ Furthermore, [RFC3280] compliant certificates are required to encode
+ DNs as UTF8String as of January 1, 2004. Certification path-building
+ software should be prepared to handle "name rollover" certificates as
+ described in [RFC3280]. Note that the inclusion of a "name rollover"
+ certificate in a certification path does not constitute repetition of
+ a DN and key. Implementations that include the "name rollover"
+ certificate in the path should ensure that the DNs with differing
+ encoding are regarded as dissimilar. (Implementations may instead
+ handle matching DNs of different encodings and will therefore not
+ need to include "name rollover" certificates in the path.)
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 66]
+
+RFC 4158 Certification Path Building September 2005
+
+
+6. Retrieval Methods
+
+ Building a certification path requires the availability of the
+ certificates and CRLs that make up the path. There are many
+ different methods for obtaining these certificates and CRLs. This
+ section lists a few of the common ways to perform this retrieval, as
+ well as some suggested approaches for improving performance. This
+ section is not intended to provide a complete reference for
+ certificate and CRL retrieval methods or optimizations that would be
+ useful in certification path building.
+
+6.1. Directories Using LDAP
+
+ Most applications utilize the Lightweight Directory Access Protocol
+ (LDAP) when retrieving data from directories following the X.500
+ model. Applications may encounter directories which support either
+ LDAP v2 [RFC1777] or LDAP v3 [RFC3377].
+
+ The LDAP v3 specification defines one attribute retrieval option, the
+ "binary" option. When specified in an LDAP retrieval request, this
+ option was intended to force the directory to ignore any string-based
+ representations of BER-encoded directory information, and send the
+ requested attribute(s) in BER format. Since all PKI objects of
+ concern are BER-encoded objects, the "binary" option should be used.
+ However, not all directories support the "binary" option. Therefore,
+ applications should be capable of requesting attributes with and
+ without the "binary" option. For example, if an application wishes
+ to retrieve the userCertificate attribute, the application should
+ request "userCertificate;binary". If the desired information is not
+ returned, robust implementations may opt to request "userCertificate"
+ as well.
+
+ The following attributes should be considered by PKI application
+ developers when performing certificate retrieval from LDAP sources:
+
+ userCertificate: contains certificates issued by one or more
+ certification authorities with a subject DN that matches that of
+ the directory entry. This is a multi-valued attribute and all
+ values should be received and considered during path building.
+ Although typically it is expected that only end entity
+ certificates will be stored in this attribute, (e.g., this is the
+ attribute an application would request to find a person's
+ encryption certificate) implementers may opt to search this
+ attribute when looking in CA entries to make their path builder
+ more robust. If it is empty, the overhead added by including this
+ attribute when already requesting one or both of the two below is
+ marginal.
+
+
+
+
+Cooper, et al. Informational [Page 67]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ cACertificate: contains self-issued certificates (if any) and any
+ certificates issued to this certification authority by other
+ certification authorities in the same realm. (Realm is dependent
+ upon local policy.) This is a multi-valued attribute and all
+ values should be received and considered during path building.
+
+ crossCertificatePair: in conformant implementations, the
+ crossCertificatePair is used to contain all, except self-issued
+ certificates issued to this certification authority, as well as
+ certificates issued by this certification authority to other
+ certification authorities. Each attribute value is a structure
+ containing two elements. The issuedToThisCA element contains
+ certificates issued to this certification authority by other
+ certification authorities. The issuedByThisCA element contains
+ certificates issued by this certification authority to other
+ certification authorities. Both elements of the
+ crossCertificatePair are labeled optional in the ASN.1 definition.
+ If both elements are present in a single value, the issuer name in
+ one certificate is required to match the subject name in the other
+ and vice versa, and the subject public key in one certificate
+ shall be capable of verifying the digital signature on the other
+ certificate and vice versa. As this technology has evolved,
+ different standards have had differing requirements on where
+ information could be found. For example, the LDAP v2 schema
+ [RFC2587] states that the issuedToThisCA (once called 'forward')
+ element of the crossCertificatePair attribute is mandatory and the
+ issuedByThisCA (once called 'reverse') element is optional. In
+ contrast, Section 11.2.3 of [X.509] requires the issuedByThisCA
+ element to be present if the CA issues a certificate to another CA
+ if the subject is not a subordinate CA in a hierarchy. Conformant
+ directories behave as required by [X.509], but robust path-
+ building implementations may want to retrieve all certificates
+ from the cACertificate and crossCertificatePair attributes to
+ ensure all possible certification authority certificates are
+ obtained.
+
+ certificateRevocationList: the certificateRevocationList attribute
+ contains a certificate revocation list (CRL). A CRL is defined in
+ [RFC3280] as a time stamped list identifying revoked certificates,
+ which is signed by a CA or CRL issuer and made freely available in
+ a public repository. Each revoked certificate is identified in a
+ CRL by its certificate serial number. There may be one or more
+ CRLs in this attribute, and the values should be processed in
+ accordance with [RFC3280].
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 68]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ authorityRevocationList: the authorityRevocationList attribute also
+ contains CRLs. These CRLs contain revocation information
+ regarding certificates issued to other CAs. There may be one or
+ more CRLs in this attribute, and the values should be processed in
+ accordance with [RFC3280].
+
+ Certification path processing systems that plan to interoperate with
+ varying PKI structures and directory designs should at a minimum be
+ able to retrieve and process the userCertificate, cACertificate,
+ crossCertificatePair, certificateRevocationList, and
+ authorityRevocationList attributes from directory entries.
+
+6.2. Certificate Store Access via HTTP
+
+ Another possible method of certificate retrieval is using HTTP as an
+ interface mechanism for retrieving certificates and CRLs from PKI
+ repositories. A current PKIX document [CERTSTORE] provides a
+ protocol for a general-purpose interface capability for retrieving
+ certificates and CRLs from PKI repositories. Since the [CERTSTORE]
+ document is a work in progress as of the writing of this document, no
+ details are given here on how to utilize this mechanism for
+ certificate and CRL retrieval. Instead, refer to the [CERTSTORE]
+ document or its current version. Certification path processing
+ systems may wish to implement support for this interface capability,
+ especially if they will be used in environments that will provide
+ HTTP-based access to certificates and CRLs.
+
+6.3. Authority Information Access
+
+ The authority information access (AIA) extension, defined within
+ [RFC3280], indicates how to access CA information and services for
+ the issuer of the certificate in which the extension appears. If a
+ certificate with an AIA extension contains an accessMethod defined
+ with the id-ad-caIssuers OID, the AIA may be used to retrieve one or
+ more certificates for the CA that issued the certificate containing
+ the AIA extension. The AIA will provide a uniform resource
+ identifier (URI) [RFC3986] when certificates can be retrieved via
+ LDAP, HTTP, or FTP. The AIA will provide a directoryName when
+ certificates can be retrieved via directory access protocol (DAP).
+ The AIA will provide an rfc822Name when certificates can be retrieved
+ via electronic mail. Additionally, the AIA may specify the location
+ of an OCSP [RFC2560] responder that is able to provide revocation
+ information for the certificate.
+
+ If present, AIA may provide forward path-building implementations
+ with a direct link to a certificate for the issuer of a given
+ certificate. Therefore, implementations may wish to provide support
+ for decoding the AIA extension and processing the LDAP, HTTP, FTP,
+
+
+
+Cooper, et al. Informational [Page 69]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ DAP, or e-mail locators. Support for AIA is optional; [RFC3280]
+ compliant implementations are not required to populate the AIA
+ extension. However, implementers of path-building and validation
+ modules are strongly encouraged to support AIA, especially the HTTP
+ transport; this will provide for usability and interoperability with
+ many existing PKIs.
+
+6.4. Subject Information Access
+
+ The subject information access (SIA) extension, defined within
+ [RFC3280], indicates how to access information and services for the
+ subject of the certificate in which the extension appears. If a
+ certificate with an SIA extension contains an accessMethod defined
+ with the id-ad-caRepository OID, the SIA may be used to locate one or
+ more certificates (and possibly CRLs) for entities issued
+ certificates by the subject. The SIA will provide a uniform resource
+ identifier (URI) [RFC3986] when data can be retrieved via LDAP, HTTP,
+ or FTP. The SIA will provide a directoryName when data can be
+ retrieved via directory access protocol (DAP). The SIA will provide
+ an rfc822Name when data can be retrieved via electronic mail.
+
+ If present, the SIA extension may provide reverse path-building
+ implementations with the certificates required to continue building
+ the path. Therefore, implementations may wish to provide support for
+ decoding the SIA extension and processing the LDAP, HTTP, FTP, DAP,
+ or e-mail locators. Support for SIA is optional; [RFC3280] compliant
+ implementations are not required to populate the SIA extension.
+ However, implementers of path-building and validation modules are
+ strongly encouraged to support SIA, especially the HTTP transport;
+ this will provide for usability and interoperability with many
+ existing PKIs.
+
+6.5. CRL Distribution Points
+
+ The CRL distribution points (CRLDP) extension, defined within
+ [RFC3280], indicates how to access CRL information. If a CRLDP
+ extension appears within a certificate, the CRL(s) to which the CRLDP
+ refer are generally the CRLs that would contain revocation
+ information for the certificate. The CRLDP extension may point to
+ multiple distribution points from which the CRL information may be
+ obtained; the certificate processing system should process the CRLDP
+ extension in accordance with [RFC3280]. The most common distribution
+ points contain URIs from which the appropriate CRL may be downloaded,
+ and directory names, which can be queried in a directory to retrieve
+ the CRL attributes from the corresponding entry.
+
+
+
+
+
+
+Cooper, et al. Informational [Page 70]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ If present, CRLDP can provide certificate processing implementations
+ with a link to CRL information for a given certificate. Therefore,
+ implementations may wish to provide support for decoding the CRLDP
+ extension and using the information to retrieve CRLs. Support for
+ CRLDP is optional and [RFC3280] compliant implementations need not
+ populate the CRLDP extension. However, implementers of path-building
+ and validation modules are strongly encouraged to support CRLDPs. At
+ a minimum, developers are encouraged to consider supporting the LDAP
+ and HTTP transports; this will provide for interoperability across a
+ wide range of existing PKIs.
+
+6.6. Data Obtained via Application Protocol
+
+ Many application protocols, such as SSL/TLS and S/MIME, allow one
+ party to provide certificates and CRLs to another. Data provided in
+ this method is generally very valuable to path-building software
+ (will provide direction toward valid paths), and should be stored and
+ used accordingly. Note: self-signed certificates obtained via
+ application protocol are not trustworthy; implementations should only
+ consider the relying party's trust anchors when building paths.
+
+6.7. Proprietary Mechanisms
+
+ Some certificate issuing systems and certificate processing systems
+ may utilize proprietary retrieval mechanisms, such as network mapped
+ drives, databases, or other methods that are not directly referenced
+ via the IETF standards. Certificate processing systems may wish to
+ support other proprietary mechanisms, but should only do so in
+ addition to supporting standard retrieval mechanisms such as LDAP,
+ AIA, and CRLDP (unless functioning in a closed environment).
+
+7. Improving Retrieval Performance
+
+ Retrieval performance can be improved through a few different
+ mechanisms, including the use of caches and setting a specific
+ retrieval order. This section discusses a few methods by which the
+ performance of a certificate processing system may be improved during
+ the retrieval of PKI objects. Certificate processing systems that
+ are consistently very slow during processing will be disliked by
+ users and will be slow to be adopted into organizations. Certificate
+ processing systems are encouraged to do whatever possible to reduce
+ the delays associated with requesting and retrieving data from
+ external sources.
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 71]
+
+RFC 4158 Certification Path Building September 2005
+
+
+7.1. Caching
+
+ Certificate processing systems operating in a non-hierarchical PKI
+ will often need to retrieve certificates and certificate revocation
+ lists (CRLs) from a source outside the application protocol.
+ Typically, these objects are retrieved from an X.500 or LDAP
+ repository, an Internet URI [RFC3986], or some other non-local
+ source. Due to the delays associated with establishing connections
+ as well as network transfers, certificate processing systems ought to
+ be as efficient as possible when retrieving data from external
+ sources. Perhaps the best way to improve retrieval efficiency is by
+ using a caching mechanism. Certificate processing systems can cache
+ data retrieved from external sources for some period of time, but not
+ to exceed the useful period of the data (i.e., an expired certificate
+ need not be cached). Although this comes at a cost of increased
+ memory/disk consumption by the system, the cost and performance
+ benefit of reducing network transmissions is great. Also, CRLs are
+ often issued and available in advance of the nextUpdate date in the
+ CRL. Implementations may wish to obtain these "fresher" CRLs before
+ the nextUpdate date has passed.
+
+ There are a number of different ways in which caching can be
+ implemented; the specifics of these methods can be used as
+ distinguishing characteristics between certificate processing
+ systems. However, some things that implementers may wish to consider
+ when developing caching systems are as follows:
+
+ - If PKI objects are cached, the certification path-building
+ mechanism should be able to examine and retrieve from the cache
+ during path building. This will allow the certificate
+ processing system to find or eliminate one or more paths quickly
+ without requiring external contact with a directory or other
+ retrieval mechanism.
+
+ - Sharing caches between multiple users (via a local area network
+ or LAN) may be useful if many users in one organization
+ consistently perform PKI operations with another organization.
+
+ - Caching not only PKI objects (such as certificates and CRLs) but
+ also relationships between PKI objects (storing a link between a
+ certificate and the issuer's certificate) may be useful. This
+ linking may not always lead to the most correct or best
+ relationship, but could represent a linking that worked in
+ another scenario.
+
+ - Previously built paths and partial paths are quite useful to
+ cache, because they will provide information on previous
+ successes or failures. Additionally, if the cache is safe from
+
+
+
+Cooper, et al. Informational [Page 72]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ unauthorized modifications, caching validation and signature
+ checking status for certificates, CRLs, and paths can also be
+ stored.
+
+7.2. Retrieval Order
+
+ To optimize efficiency, certificate processing systems are encouraged
+ to also consider the order in which different PKI objects are
+ retrieved, as well as the mechanism from which they are retrieved.
+ If caching is utilized, the caches can be consulted for PKI objects
+ before attempting other retrieval mechanisms. If multiple caches are
+ present (such as local disk and network), the caches can be consulted
+ in the order in which they can be expected to return their result
+ from fastest to slowest. For example, if a certificate processing
+ system wishes to retrieve a certificate with a particular subject DN,
+ the system might first consult the local cache, then the network
+ cache, and then attempt directory retrieval. The specifics of the
+ types of retrieval mechanisms and their relative costs are left to
+ the implementer.
+
+ In addition to ordering retrieval mechanisms, the certificate
+ processing system ought to order the relative merits of the different
+ external sources from which a PKI object can be retrieved. If the
+ AIA is present within a certificate, with a URI [RFC3986] for the
+ issuer's certificate, the certificate processing system (if able) may
+ wish to attempt to retrieve the certificate first from local cache
+ and then by using that URI (because it is expected to point directly
+ to the desired certificate) before attempting to retrieve the
+ certificates that may exist within a directory.
+
+ If a directory is being consulted, it may be desirable to retrieve
+ attributes in a particular order. A highly cross-certified PKI
+ structure will lead to multiple possibilities for certification
+ paths, which may mean multiple validation attempts before a
+ successful path is retrieved. Therefore, cACertificate and
+ userCertificate (which typically contain certificates from within the
+ same 'realm') could be consulted before attempting to retrieve the
+ crossCertificatePair values for an entry. Alternately, all three
+ attributes could be retrieved in one query, but cross-certificates
+ then tagged as such and used only after exhausting the possibilities
+ from the cACertificate attribute. The best approach will depend on
+ the nature of the application and PKI environment.
+
+7.3. Parallel Fetching and Prefetching
+
+ Much of this document has focused on a path-building algorithm that
+ minimizes the performance impact of network retrievals, by preventing
+ those retrievals and utilization of caches. Another way to improve
+
+
+
+Cooper, et al. Informational [Page 73]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ performance would be to allow network retrievals to be performed in
+ advance (prefetching) or at the same time that other operations are
+ performed (parallel fetching). For example, if an email application
+ receives a signed email message, it could download the required
+ certificates and CRLs prior to the recipient viewing (or attempting
+ to verify) the message. Implementations that provide the capability
+ of parallel fetching and/or prefetching, along with a robust cache,
+ can lead to greatly improved performance or user experience.
+
+8. Security Considerations
+
+8.1. General Considerations for Building a Certification Path
+
+ Although certification path building deals directly with security
+ relevant PKI data, the PKI data itself needs no special handling
+ because its integrity is secured with the digital signature applied
+ to it. The only exception to this is the appropriate protection of
+ the trust anchor public keys. These are to be kept safe and obtained
+ out of band (e.g., not from an electronic mail message or a
+ directory) with respect to the path-building module.
+
+ The greatest security risks associated with this document revolve
+ around performing certification path validation while certification
+ paths are built. It is therefore noted here that fully implemented
+ certification path validation in accordance with [RFC3280] and
+ [X.509] is required in order for certification path building,
+ certification path validation, and the certificate using application
+ to be properly secured. All of the Security Considerations listed in
+ Section 9 of [RFC3280] apply equally here.
+
+ In addition, as with any application that consumes data from
+ potentially untrusted network locations, certification path-building
+ components should be carefully implemented so as to reduce or
+ eliminate the possibility of network based exploits. For example, a
+ poorly implemented path-building module may not check the length of
+ the CRLDP URI [RFC3986] before using the C language strcpy() function
+ to place the address in a 1024 byte buffer. A hacker could use such
+ a flaw to create a buffer overflow exploit by encoding malicious
+ assembly code into the CRLDP of a certificate and then use the
+ certificate to attempt an authentication. Such an attack could yield
+ system level control to the attacker and expose the sensitive data
+ the PKI was meant to protect.
+
+ Path building may be used to mount a denial of service (DOS) attack.
+ This might occur if multiple simple requests could be performed that
+ cause a server to perform a number of path developments, each taking
+ time and resources from the server. Servers can help avoid this by
+ limiting the resources they are willing to devote to path building,
+
+
+
+Cooper, et al. Informational [Page 74]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ and being able to further limit those resources when the load is
+ heavy. Standard DOS protections such as systems that identify and
+ block attackers can also be useful.
+
+ A DOS attack can be also created by presenting spurious CA
+ certificates containing very large public keys. When the system
+ attempts to use the large public key to verify the digital signature
+ on additional certificates, a long processing delay may occur. This
+ can be mitigated by either of two strategies. The first strategy is
+ to perform signature verifications only after a complete path is
+ built, starting from the trust anchor. This will eliminate the
+ spurious CA certificate from consideration before the large public
+ key is used. The second strategy is to recognize and simply reject
+ keys longer than a certain size.
+
+ A similar DOS attack can occur with very large public keys in end
+ entity certificates. If a system uses the public key in a
+ certificate before building and validating that certificate's
+ certification path, long processing delays may occur. To mitigate
+ this threat, the public key in an end entity certificate should not
+ be used for any purpose until a complete certification path for that
+ certificate is built and validated.
+
+8.2. Specific Considerations for Building Revocation Signer
+ Certification Paths
+
+ If the CRL Signer certificate (and certification path) is not
+ identical to the Certification Authority certificate (and
+ certification path), special care should be exercised when building
+ the CRL Signer certification path.
+
+ If special consideration is not given to building a CRL Signer
+ certification path, that path could be constructed such that it
+ terminates with a different root or through a different certification
+ path to the same root. If this behavior is not prevented, the
+ relying party may end up checking the wrong revocation data, or even
+ maliciously substituted data, resulting in denial of service or
+ security breach.
+
+ For example, suppose the following certification path is built for E
+ and is valid for an example "high assurance" policy.
+
+ A->B->C->E
+
+ When the building/validation routine attempts to verify that E is not
+ revoked, C is referred to as the Certification Authority certificate.
+ The path builder finds that the CRL for checking the revocation
+ status of E is issued by C2; a certificate with the subject name "C",
+
+
+
+Cooper, et al. Informational [Page 75]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ but with a different key than the key that was used to sign E. C2 is
+ referred to as the CRL Signer. An unrestrictive certification path
+ builder might then build a path such as the following for the CRL
+ Signer C2 certificate:
+
+ X->Y->Z->C2
+
+ If a path such as the one above is permitted, nothing can be
+ concluded about the revocation status of E since C2 is a different CA
+ from C.
+
+ Fortunately, preventing this security problem is not difficult and
+ the solution also makes building CRL Signer certification paths very
+ efficient. In the event the CRL Signer certificate is identical to
+ the Certification Authority certificate, the Certification Authority
+ certification path should be used to verify the CRL; no additional
+ path building is required. If the CRL Signer certificate is not
+ identical to the Certification Authority certificate, a second path
+ should be built for the CRL Signer certificate in exactly the same
+ fashion as for any certificate, but with the following additional
+ guidelines:
+
+ 1. Trust Anchor: The CRL Signer's certification path should start
+ with the same trust anchor as the Certification Authority's
+ certification path. Any trust anchor certificate with a subject
+ DN matching that of the Certification Authority's trust anchor
+ should be considered acceptable though lower in priority than the
+ one with a matching public key and subject DN. While different
+ trust anchor public keys are acceptable at the beginning of the
+ CRL signer's certification path and the Certification Authority's
+ certification path, both keys must be trusted by the relying
+ party per the recommendations in Section 8.1.
+
+ 2. CA Name Matching: The subject DNs for all CA certificates in the
+ two certification paths should match on a one-to-one basis
+ (ignoring self-issued certificates) for the entire length of the
+ shorter of the two paths.
+
+ 3. CRL Signer Certification Path Length: The length of the CRL
+ Signer certification path (ignoring self-issued certificates)
+ should be equal to or less than the length of the Certification
+ Authority certification path plus (+) one. This allows a given
+ Certification Authority to issue a certificate to a
+ delegated/subordinate CRL Signer. The latter configuration
+ represents the maximum certification path length for a CRL Signer
+ certificate.
+
+
+
+
+
+Cooper, et al. Informational [Page 76]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ The reasoning behind the first guideline is readily apparent.
+ Lacking this and the second guideline, any trusted CA could issue
+ CRLs for any other CA, even if the PKIs are not related in any
+ fashion. For example, one company could revoke certificates issued
+ by another company if the relying party trusted the trust anchors
+ from both companies. The two guidelines also prevent erroneous CRL
+ checks since Global uniqueness of names is not guaranteed.
+
+ The second guideline prevents roaming certification paths such as the
+ previously described example CRL Signer certification path for
+ A->B->C->E. It is especially important that the "ignoring self-
+ issued certificates" is implemented properly. Self-issued
+ certificates are cast out of the one-to-one name comparison in order
+ to allow for key rollover. The path-building algorithm may be
+ optimized to only consider certificates with the acceptable subject
+ DN for the given point in the CRL Signer certification path while
+ building the path.
+
+ The third and final guideline ensures that the CRL used is the
+ intended one. Without a restriction on the length of the CRL Signer
+ certification path, the path could roam uncontrolled into another
+ domain and still meet the first two guidelines. For example, again
+ using the path A->B->C->E, the Certification Authority C, and a CRL
+ Signer C2, a CRL Signer certification path such as the following
+ could pass the first two guidelines:
+
+ A->B->C->D->X->Y->RogueCA->C2
+
+ In the preceding example, the trust anchor is identical for both
+ paths and the one-to-one name matching test passes for A->B->C.
+ However, accepting such a path has obvious security consequences, so
+ the third guideline is used to prevent this situation. Applying the
+ second and third guideline to the certification path above, the path
+ builder could have immediately detected this path was not acceptable
+ (prior to building it) by examining the issuer DN in C2. Given the
+ length and name guidelines, the path builder could detect that
+ "RogueCA" is not in the set of possible names by comparing it to the
+ set of possible CRL Signer issuer DNs, specifically, A, B, or C.
+
+ Similar consideration should be given when building the path for the
+ OCSP Responder certificate when the CA is the OCSP Response Signer or
+ the CA has delegated the OCSP Response signing to another entity.
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 77]
+
+RFC 4158 Certification Path Building September 2005
+
+
+9. Acknowledgements
+
+ The authors extend their appreciation to David Lemire for his efforts
+ coauthoring "Managing Interoperability in Non-Hierarchical Public Key
+ Infrastructures" from which material was borrowed heavily for use in
+ the introductory sections.
+
+ This document has also greatly benefited from the review and
+ additional technical insight provided by Dr. Santosh Chokhani, Carl
+ Wallace, Denis Pinkas, Steve Hanna, Alice Sturgeon, Russ Housley, and
+ Tim Polk.
+
+10. Normative References
+
+ [RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet
+ X.509 Public Key Infrastructure Certificate and
+ Certificate Revocation List (CRL) Profile", RFC 3280,
+ April 2002.
+
+11. Informative References
+
+ [MINHPKIS] Hesse, P., and D. Lemire, "Managing Interoperability in
+ Non-Hierarchical Public Key Infrastructures", 2002
+ Conference Proceedings of the Internet Society Network
+ and Distributed System Security Symposium, February 2002.
+
+ [RFC1777] Yeong, W., Howes, T., and S. Kille, "Lightweight
+ Directory Access Protocol", RFC 1777, March 1995.
+
+ [RFC2560] Myers, M., Ankney, R., Malpani, A., Galperin, S., and C.
+ Adams, "X.509 Internet Public Key Infrastructure Online
+ Certificate Status Protocol - OCSP", RFC 2560, June 1999.
+
+ [RFC2587] Boeyen, S., Howes, T., and P. Richard, "Internet X.509
+ Public Key Infrastructure LDAPv2 Schema", RFC 2587, June
+ 1999.
+
+ [RFC3377] Hodges, J. and R. Morgan, "Lightweight Directory Access
+ Protocol (v3): Technical Specification", RFC 3377,
+ September 2002.
+
+ [RFC3820] Tuecke, S., Welch, V., Engert, D., Pearlman, L., and M.
+ Thompson, "Internet X.509 Public Key Infrastructure (PKI)
+ Proxy Certificate Profile", RFC 3820, June 2004.
+
+ [RFC3986] Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform
+ Resource Identifier (URI): Generic Syntax", STD 66, RFC
+ 3986, January 2005.
+
+
+
+Cooper, et al. Informational [Page 78]
+
+RFC 4158 Certification Path Building September 2005
+
+
+ [X.501] ITU-T Recommendation X.501: Information Technology - Open
+ Systems Interconnection - The Directory: Models, 1993.
+
+ [X.509] ITU-T Recommendation X.509 (2000 E): Information
+ Technology - Open Systems Interconnection - The
+ Directory: Authentication Framework, March 2000.
+
+ [PKIXALGS] Bassham, L., Polk, W. and R. Housley, "Algorithms and
+ Identifiers for the Internet X.509 Public Key
+ Infrastructure Certificate and Certificate Revocation
+ Lists (CRL) Profile", RFC 3279, April 2002.
+
+ [CERTSTORE] P. Gutmann, "Internet X.509 Public Key Infrastructure
+ Operational Protocols: Certificate Store Access via
+ HTTP", Work in Progress, August 2004.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 79]
+
+RFC 4158 Certification Path Building September 2005
+
+
+Authors' Addresses
+
+ Matt Cooper
+ Orion Security Solutions, Inc.
+ 1489 Chain Bridge Rd, Ste. 300
+ McLean, VA 22101, USA
+
+ Phone: +1-703-917-0060
+ EMail: mcooper@orionsec.com
+
+
+ Yuriy Dzambasow
+ A&N Associates, Inc.
+ 999 Corporate Blvd Ste. 100
+ Linthicum, MD 21090, USA
+
+ Phone: +1-410-859-5449 x107
+ EMail: yuriy@anassoc.com
+
+
+ Peter Hesse
+ Gemini Security Solutions, Inc.
+ 4451 Brookfield Corporate Dr. Ste. 200
+ Chantilly, VA 20151, USA
+
+ Phone: +1-703-378-5808 x105
+ EMail: pmhesse@geminisecurity.com
+
+
+ Susan Joseph
+ Van Dyke Technologies
+ 6716 Alexander Bell Drive
+ Columbia, MD 21046
+
+ EMail: susan.joseph@vdtg.com
+
+
+ Richard Nicholas
+ BAE Systems Information Technology
+ 141 National Business Parkway, Ste. 210
+ Annapolis Junction, MD 20701, USA
+
+ Phone: +1-301-939-2722
+ EMail: richard.nicholas@it.baesystems.com
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 80]
+
+RFC 4158 Certification Path Building September 2005
+
+
+Full Copyright Statement
+
+ Copyright (C) The Internet Society (2005).
+
+ This document is subject to the rights, licenses and restrictions
+ contained in BCP 78, and except as set forth therein, the authors
+ retain all their rights.
+
+ This document and the information contained herein are provided on an
+ "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
+ OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
+ ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
+ INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
+ INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
+ WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+
+Intellectual Property
+
+ The IETF takes no position regarding the validity or scope of any
+ Intellectual Property Rights or other rights that might be claimed to
+ pertain to the implementation or use of the technology described in
+ this document or the extent to which any license under such rights
+ might or might not be available; nor does it represent that it has
+ made any independent effort to identify any such rights. Information
+ on the procedures with respect to rights in RFC documents can be
+ found in BCP 78 and BCP 79.
+
+ Copies of IPR disclosures made to the IETF Secretariat and any
+ assurances of licenses to be made available, or the result of an
+ attempt made to obtain a general license or permission for the use of
+ such proprietary rights by implementers or users of this
+ specification can be obtained from the IETF on-line IPR repository at
+ http://www.ietf.org/ipr.
+
+ The IETF invites any interested party to bring to its attention any
+ copyrights, patents or patent applications, or other proprietary
+ rights that may cover technology that may be required to implement
+ this standard. Please address the information to the IETF at ietf-
+ ipr@ietf.org.
+
+Acknowledgement
+
+ Funding for the RFC Editor function is currently provided by the
+ Internet Society.
+
+
+
+
+
+
+
+Cooper, et al. Informational [Page 81]
+