diff options
Diffstat (limited to 'doc/protocol/rfc4158.txt')
| -rw-r--r-- | doc/protocol/rfc4158.txt | 4539 |
1 files changed, 0 insertions, 4539 deletions
diff --git a/doc/protocol/rfc4158.txt b/doc/protocol/rfc4158.txt deleted file mode 100644 index 52716e1063..0000000000 --- a/doc/protocol/rfc4158.txt +++ /dev/null @@ -1,4539 +0,0 @@ - - - - - - -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] - |