PKIX Working Group M. Cooper Internet Draft Orion Security Solutions Document: draft-ietf-pkix-certpathbuild-02.txt Y. Dzambasow Expires: May 2004 A&N Associates P. Hesse Gemini Security Solutions S. Joseph DigitalNet R. Nicholas DigitalNet November 2003 Internet X.509 Public Key Infrastructure: Certification Path Building Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of [RFC 2026]. This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. The draft is being discussed on the 'ietf-pkix' mailing list. To subscribe, send a message to ietf-pkix-request@imc.org with the single word subscribe in the body of the message. There is a Web site for the mailing list at http://www.imc.org/ietf-pkix/. Abstract Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 1] Certification Path Building November 2003 This document was written to provide 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 Overview of PKI Structures.................................7 1.4.1 Hierarchical Structures.............................7 1.4.2 Mesh Structures.....................................9 1.4.3 Bi-lateral Cross-Certified Structures..............10 1.4.4 Bridge Structures..................................11 1.5 Bridge Structures and Certification Path Processing.......12 2. Certification Path Building...................................13 2.1 Introduction to Certification Path Building...............13 2.2 Criteria for Path Building................................14 2.3 Path Building Algorithms..................................15 2.4 How to Build a Certification Path.........................20 2.4.1 Certificate Repetition.............................22 2.4.2 Introduction to Path Building Optimization.........23 2.5 Building Certification Paths for CRL Signers..............28 2.6 Suggested Path Building Software Components...............30 2.7 Inputs to the Path Building Module........................32 2.7.1 Required Inputs....................................33 2.7.2 Optional Inputs....................................33 3. Optimizing Path Building......................................34 3.1 Optimized Path Building...................................34 3.2 Sorting vs. Elimination...................................36 3.3 Representing The Decision Tree Programmatically...........39 3.3.1 Node Representation For CA Entities................40 3.3.2 Using Nodes to Iterate Over All Paths..............40 3.4 Implementing Path Building Optimization...................43 3.5 Selected Methods for Sorting Certificates.................44 3.5.1 basicConstraints is Present and cA Equals True.....45 3.5.2 Recognized Signature Algorithms....................46 3.5.3 keyUsage is Correct................................46 3.5.4 Time (T) Falls within the Certificate Validity.....47 3.5.5 Certificate Was Previously Validated...............47 3.5.6 Previously Verified Signatures.....................48 3.5.7 Path Length Constraints............................48 3.5.8 Name Constraints...................................48 3.5.9 Certificate is Not Revoked.........................49 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 2] Certification Path Building November 2003 3.5.10 Issuer Found in the Path Cache.....................50 3.5.11 Matching Key Identifiers (KIDs)....................50 3.5.12 Policy Processing..................................51 3.5.13 Policies Intersect The Sought Policy Set...........52 3.5.14 Endpoint Distinguished Name Matching...............52 3.5.15 Relative Distinguished Name (RDN) Matching.........53 3.5.16 Certificates are Retrieved from cACertificate......53 3.5.17 Consistent Public Key and Signature Algorithms.....54 3.5.18 Similar Issuer and Subject Names...................54 3.5.19 Certificates in the Certification Cache............55 3.5.20 Current CRL Found in Local Cache...................55 4. Forward Policy Chaining.......................................56 4.1 Simple Intersection.......................................56 4.2 Policy Mapping............................................57 4.3 Assigning Scores for Forward Policy Chaining..............58 5. Avoiding Path Building Errors.................................59 5.1 Dead-ends.................................................59 5.2 Loop Detection............................................60 5.3 Use of Key Identifiers....................................61 5.4 Distinguished Name Encoding...............................61 6. Retrieval Methods.............................................61 6.1 Directories Using LDAP....................................62 6.2 Authority Information Access..............................64 6.3 Subject Information Access................................64 6.4 CRL Distribution Points...................................64 6.5 Proprietary Mechanisms....................................65 7. Improving Retrieval Performance...............................65 7.1 Caching...................................................65 7.2 Retrieval Order...........................................66 8. Security Considerations.......................................67 Normative References.............................................68 Informative References...........................................68 Acknowledgments..................................................69 Author's Addresses...............................................69 1. Introduction [X.509] digital certificates have become an accepted method for securely binding the identity of an individual or device to a public key, for the purpose of supporting public key cryptographic operations such as digital signature verification, and public key- based encryption and decryption. However, prior to using the public key contained in a digital certificate, an application has to first determine the authenticity of that digital certificate, and specifically, the validity of all the certificates leading to a trusted root certificate. It is through validating this certification path that the assertion of the binding made between the Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 3] Certification Path Building November 2003 identity and the public key in each of the digital certificate can be traced back to a single point of trust. The process by which an application determines this authenticity of a digital certificate is called certification path processing. Certification path processing establishes a chain of trust between a trusted public key and a digital certificate. This chain of trust is composed of a series of digital certificates known as a certification path. A certification path begins with a certificate whose signature can be verified using a trusted public key and ends with the target digital certificate. Path processing entails building and validating the certification path to determine the degree of trust to place in the target digital certificate(s). See section 3.2 of [RFC 3280] for more information on certification paths and trust. 1.1 Motivation Many other documents (such as [RFC 3280]) cover certification path validation requirements and procedures in detail but do not discuss certification path building because how the path is found 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 becoming greater. Many PKIs are now using complex structures (see section 1.4) 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 information that will be helpful in 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 one particular way to best perform certification path building. This document draws upon the authors' experience with existing complex certification paths to offer insights and recommendations to developers integrating support for [X.509] digital 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 4] Certification Path Building November 2003 path building capabilities, the algorithm is no more than a suggested approach. Other approaches (e.g., building complete spanning trees of the PKI.) exist and may be shown to be more effective under certain conditions. Certification path validation is described in detail in both [X.509] and [RFC 3280] and is not repeated in this document. 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 lines between nodes. Certificate Processing System: An application or device that performs the functions of certification path building and certification path validation. Certificate Signer: A Certification Authority (represented by a certificate) that has issued another certificate. Certification Authority (CA): An entity that issues and manages digital certificates. Certification Path: An ordered list of certificates starting with a certificate signed by a trusted public key 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 5] Certification Path Building November 2003 Certification Path Validation: The process that verifies the binding between the subject and the subject-public-key defined in the target certificate, using a trusted public key and set of known constraints. CRL Signer: The specific certificate that may be used for verifying the signature on a CRL issued by, or on behalf of, a specific certificate signer. 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. 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, and whose identity is defined as the Subject of the certificate. Human end entities are often called "subscribers". 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. Public Key Infrastructure (PKI): The set of hardware, software, personnel, policy, and procedures used by a Certification Authority 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. 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.) Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 6] Certification Path Building November 2003 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 [RFC 3280]. Trust List: A list of certificates or combinations of public keys and names that are considered trustworthy. Trust Anchor: The combination of a trusted public key and the name of the entity to which the corresponding private key belongs. Trusted Root Certificate: A certificate issued to a trust anchor which 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. 1.4 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 multi-bridged mesh architectures. These structures define the types of certification paths that might be built and validated by an application. This section describes four common PKI structures. 1.4.1 Hierarchical Structures A hierarchical PKI, depicted in Figure 1, is one in which all of the end entities and relying parties trust a single "root" CA. 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. +---------+ +---| root CA |---+ | +---------+ | | | | | v v Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 7] Certification Path Building November 2003 +----+ +----+ +-----| 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 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. 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. +-------------------------------------------------------+ | Trust List | | | | +---------+ +---------+ +---------+ | | +--| Root CA | | Root CA | | Root CA | | | | +---------+ +---------+ +---------+ | | | | | | | +--|------|----------------|---------------- |----------+ | | | | | | | | Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 8] Certification Path Building November 2003 | | 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.4.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). The CAs in this environment have a peer relationship and are neither superior nor subordinate to each other. 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 unidirectional and bi-directional cross-certifications (called a partial mesh). +---------------------------------+ | | +-----------+----------------------+ | | v v | | +-------+ +------+ | | +--->| CA B |<------------->| CA C |<--+ | | | +-------+ +------+ | | | | | ^ ^ | | | | | v | | | | | | | +----+ | | | | | | | | EE | +----+ +--------+ v | | | | +----+ | | +----+ | | | | | | | EE | | | v v v v +----+ v v +------+ +------+ +------+ | CA E |<----------->| CA A |<----------->| CA D | +------+ +------+ +------+ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 9] Certification Path Building November 2003 | ^ ^ ^ ^ | | | | | | | v | +------------------------------------+ | v +----+ | | +----+ | EE | | +---------+ | | EE | +----+ +---------------| Root CA |---------------+ +----+ +---------+ 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 trusted root certificate 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 paths between the Root CA and the EE issued by D without repeating any certificates. 1.4.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, 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 | +------+ | +-----| CA |-----+ | | +------+ | | | PKI 1 Root | | v v | +------+ +------+ v PKI 2 Root +-| CA |-+ | CA | Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 10] Certification Path Building November 2003 +------+ | +------+ | +------+ +------->| 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 restrictive policies. 1.4.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 (known as a "principal" CA [PCA]) 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 11] Certification Path Building November 2003 discussed in section 2.3, non-hierarchical PKIs can be considered hierarchical, depending upon perspective.) PKI 1 cross certified with Bridge +-------------------------------+ | | v v +-----------+ +------+ | Bridge CA | +-----| CA |-----+ +-----------+ | +------+ | ^ | PKI 1 Root | PKI 2 cross|cert with Bridge v v | +------+ +------+ v PKI 2 Root +-| 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.5 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 which the Bridge may connect. (e.g., hierarchical, mesh, hybrid) 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 12] Certification Path Building November 2003 deployed in any standards compliant PKI environment and will perform the required certification path processing properly. 2. Certification Path Building Certification path building is the process by which the certificate processing system obtains the certification path between a trusted public key and the target certificate. Different implementations can build the certification path in different ways; therefore, it is not the intent of this paper 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 required 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 anchros are typically stored in self signed certificates which are frequently called trusted root 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. Figure 6 shows an example of a certification path. In this figure, the horizontal arrows represent certificates. +---------+ +-----+ +-----+ +-----+ +--------+ | Trust |----->| CA |---->| CA |---->| CA |---->| Target | | Anchor | | | A | | | B | | | C | | | EE | +---------+ | +-----+ | +-----+ | +-----+ | +--------+ | | | | | | | | v v v v 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 13] Certification Path Building November 2003 certification path is unaffected by the method in which the certification path was built. However, the ability to build a valid certification path is of paramount importance for applications that rely on a PKI. Absent valid certification paths, the certificates cannot be validated according to [RFC 3280] and therefore cannot be trusted. Thus the ability to build a path is every bit as important as the ability to properly validate them. 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, for example, need to manage a number of trusted root certificates, partially populated directory entries (e.g., missing issuedToThisCA entries in the cross certificates.), 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. For example, if the infrastructure is compliant with the Internet [X.509] Public Key Infrastructure LDAPv2 Schema [RFC 2587], a developer can always build certification paths in the forward (from target) direction. However, not all PKIs are compliant with [RFC 2587]. An infrastructure may not populate the issuedToThisCA (forward) cross-certificates and instead only populate the issuedByThisCA (reverse) entries, in which case building in reverse will be a developer's only viable option. Note that a PKI compliant with [RFC 2587] may or may not populate the optional issuedByThisCA (reverse) entry; so building in reverse may or may not work in [RFC 2587] compliant systems. 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. By this, it is meant that all possible certification paths between Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 14] Certification Path Building November 2003 the trust anchor and the target certificate which may be valid paths can be built by the algorithm. 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 [RFC 3280], 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. The algorithms and mechanisms discussed henceforth are chosen because they are considered by the authors to be good methods to meet 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. As a result, every potential valid path has a terminus, a leaf on the tree. (If certificates were allowed to repeat, paths could have infinite length and therefore no terminus.) Figure 7 below illustrates this concept from the trust anchor's perspective. +---------+ +---------+ | Trust | | Trust | | Anchor | | Anchor | +---------+ +---------+ | | | | | | | | v v v v +---+ +---+ +---+ +---+ | A |<-->| C | +--| A | | C |--+ +---+ +---+ | +---+ +---+ | | | | | | | | +---+ | v v v v +->| B |<-+ +---+ +---+ +---+ +---+ +---+ | B | | C | | A | | B | | +---+ +---+ +---+ +---+ | | | | | | | | | | v v | | v +----+ +----+ | | +----+ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 15] Certification Path Building November 2003 | EE | | EE | | | | EE | +----+ +----+ | | +----+ v v A certificate graph with +---+ +---+ bi-directional cross cert. | B | | B | Between CAs A and C. +---+ +---+ | | | | v v +----+ +----+ | 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 how complex it is - this greatly simplifies software design. In Figure 8, the same graph is depicted from the end entity (EE) (the target certificate in this example). It would appear this way if building in the forward (from EE or from target) direction. In this example, without knowing any particulars of the certificates, it appears at first that building from EE has a smaller decision tree than building from the trust anchor. While it is true that there are fewer nodes in the tree, it is not necessarily more efficient in this example. +---------+ +---------+ | Trust | | Trust | | Anchor | | Anchor | +---------+ +---------+ ^ ^ | | | | +---+ +---+ | A | | C | +---+ +---+ +---------+ ^ ^ +---------+ | Trust | | | | Trust | | Anchor | | | | Anchor | +---------+ | | +---------+ ^ | | ^ | +---+ +---+ | Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 16] Certification Path Building November 2003 +-------| 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, it is only capable of detecting that the current certificate in the tree was issued by the trust anchor, or that it issued the target certificate (EE). From the tree above, building from the target certificate will require going through two intermediate certificates before encountering a certificate issued by the trust anchor 100% of the time (e.g., EE chains to B, which then chains to C, which is issued by the Trust Anchor). The path building module would not chain C to A because it can recognize that C has a certificate issued by the Trust Anchor (TA). On the other hand, in the first tree (Figure 7: from anchor depiction), there is a 50% probability of building a path longer than needed (e.g., TA to A to C to B to EE rather than the shorter TA to A to B to EE). However, even given our simplistic example, the path building software - when at A - could be designed to recognize that B's subject distinguished name matches the issuer distinguished name of the EE. Given this one optimization, the builder could prefer B to C. (B's subject distinguished name matches that of the EE's issuer whereas C's subject distinguished name 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 distinguished name 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 17] Certification Path Building November 2003 A more complicated example involves an environment where more than one trust anchor exists. The number of trust anchors should weigh heavily upon the decision to build in the reverse direction. If, for sake of argument, it required a fixed amount of network transfer time to build all the possible paths either to or from a given CA, what should be expected if there are four trust anchors? Suppose that building paths either from the target certificate or from the trust anchor for any given trust anchor or target certificate will require N time. In the from anchor (reverse) direction, the path building software potentially needs to build paths from all 4 trusted CAs, so as much as 4*N. Assuming a path exists, if N were 10 seconds, and assuming an even probability of the path beginning with any one of the four trust anchors, an average delay of 25 [(10+20+30+40)/4] seconds is expected when building from the trust anchor. In the from target certificate (forward) direction (and using the same example), path building software would only require 10 (1*N) seconds, only 40% of the average time required when building from the trust anchor. As the number of trust anchors increases, so does the average time it takes to find a path if one does exist. Additionally, in the degenerate case where no path exists, attempting to build from the same four trust anchors would consume 40 seconds, whereas building from the end entity would consume only 10 seconds. +-----+ +-----+ +-----+ +-----+ | TR1 | | TR2 | | TR3 | | TR4 | +-----+ +-----+ +-----+ +-----+ / \ / \ / \ / \ / \ / \ / \ / \ v v v v v v v v +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | R |<->| S | | F | | G | | F |<->| G | || | C | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \ / / \ \ | / | /\ | \ / / \ \ | / | / \ | v v v v v v v v v v v +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | T | | B | | D | | E | | H |<->| I | | B | || | E | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ / \ \ \ / \ | / \ \ \ / \ | v v v v v v v +---+ +---+ +---+ +---+ +---+ +----+ | U | | V | | F | | J |<->| K | || +---+ +---+ +---+ +---+ +---+ +----+ Building from the anchor (reverse) may require traversal of multiple PKIs and unneeded paths to find the target EE. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 18] Certification Path Building November 2003 +-----+ +-----+ +-----+ +-----+ | TR1 | | TR2 | | TR3 | | TR4 | +-----+ +-----+ +-----+ +-----+ / / v +---+ || +---+ \ \ v +---+ || +---+ | | v +----+ || +----+ Building from the target certificate eliminates inapplicable PKIs (those that are not cross certified with the required one) from the path building process. Figure 9 - Reverse and Forward Path Building with Multiple Trust Anchors As Figure 9 depicts, when multiple trust anchors are present, it can be many times more efficient to build certification paths starting from the target certificate. As the number of trust anchors increases, so does the inefficiency of building paths from the trust anchors. As a result, any certificate using system supporting multiple trusted CAs is encouraged to consider developing paths in the forward (from target certificate) direction. 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 [RFC 2587] compliant (Specifically, are the issuedToThisCA [forward] cross- certificates and/or the cACertificate attributes fully Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 19] Certification Path Building November 2003 populated in the directory? If yes, you are able to build in the forward direction. b. If using a directory, does the directory contain all the issuedByThisCA (reverse) cross certificates in the crossCertificatePair attribute, or, alternately, are all certificates issued from each CA available via some other means? If yes, it is possible to build in the reverse direction. 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 trust root certificates from PKIs that do not populate reverse cross certificates for all intermediate CAs? If no, and the local PKI populates reverse cross certificates, reverse path building is an option. 2.4 How to Build a Certification Path As was discussed in the prior section, path building is essentially a tree traversal. It was easy to see how this is true in a simple example, but how about a more complicated one? Before taking a look at more a complicated scenario, it is worthwhile to address loops and what constitutes a loop in a certification path. [X.509] specifies that the same certificate may not repeat in a path. In a strict sense, this works well as it is not possible to create an endless loop without repeating one or more certificates in the path. However, this requirement fails to adequately address Bridged PKI environments. +---+ +---+ | F |--->| H | +---+ +---+ ^ ^ ^ | \ \ | \ \ | v v | +---+ +---+ | | G |--->| I | | +---+ +---+ | ^ | / Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 20] Certification Path Building November 2003 | / +------+ +-----------+ +------+ +---+ +---+ | 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 10 - Four Bridged PKIs Figure 10 depicts four root certification authorities cross-certified with a Bridge CA (BCA). By building certification paths through the BCA, trust can be extended across the four infrastructures. When looking at Figure 10, note that the boxes do not represent certificates, but rather entities (i.e. identical subject distinguished and alternate names). The certificates are represented by the arrows between the entities in the boxes. Thus, 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 21] Certification Path Building November 2003 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 be repeated when building paths. For instance, from the figure above, do not build the path E- >B->C->A->C->A->Y. Not only is the repetition unnecessary to build the path from E to Y, 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 EE to TA Z? EE->N->L->X->BCA->W->BCA->Y->BCA->Z 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 10) had double arrows between Y and C, as well as between Y and A. The following path could then be built: EE->N->L->X->BCA->W->BCA->Y->C->A->Y->BCA->Z A path such as this could become arbitrarily complex and traverse every cross certified CA in every PKI in a cross-certified environment while still remaining compliant with [X.509]. As a practical matter, the path above is not something an application would typically want or need to build for a variety of reasons: - First, certification paths like the example above are generally not intended by the PKI designers and should not be necessary in order to validate any given certificate. If a convoluted path such as the example above is required (there is no corresponding simple path) in order to validate a given certificate, this is most likely indicative of a flaw in the PKI design. - Second, the longer a path becomes, the greater the potential dilution of trust in the certification path. That is, with each successive link in the infrastructure (i.e., certification by CAs and cross-certification between CAs) some amount of Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 22] Certification Path Building November 2003 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 [RFC 3280]. 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 EE to Z in the diagram above: EE->N->L->X->BCA->Z. 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 11 depicts all the possible paths 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 EE to Z. +------+ +-----------+ +------+ +---+ | TA W |<------| Bridge CA |<-------| TA X |<--| L | +------+ +-----------+ +------+ +---+ / \ ^ / \ \ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 23] Certification Path Building November 2003 / \ \ v v \ +------+ +------+ +---+ | TA Y | | TA Z | | N | +------+ +------+ +---+ ^ \ \ +----+ | EE | +----+ Figure 11 - 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 is desirable, the graph in Figure 11 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 12 depicts all possible paths as a tree emanating from Z. +---+ +---+ | I |--->| H | +---+ +---+ ^ | +---+ +---+ | | H |--->| I | | +---+ +---+ +---+ ^ | G | / +---+ +---+ +---+ +---+ / | F |--->| H |--->| I | ^ / +---+ +---+ +---+ \ / ^ \/ / +---+ +---+ +---+ +---+ +---+ | F | | G |--->| I |--->| H | | M | +---+ +---+ +---+ +---+ +---+ ^ ^ ^ | / | +------+ +-----------+ +------+ +---+ | TA W |<------| Bridge CA |-------->| TA X |-->| L | +------+ +-----------+ +------+ +---+ / ^ \ \ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 24] Certification Path Building November 2003 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 12 - Reverse (From Anchor) Decision Tree Given the relative complexity of this decision tree, it becomes clear that making the right choices while navigating the tree can make a large difference in how quickly a valid path is returned. The path building software could potentially traverse the entire graph before choosing the shortest path: 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 not only needs to decide in which direction to traverse the tree, but it should also decide 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 stated as one of our criteria in section 2.2. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 25] Certification Path Building November 2003 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 13, with no preference given to sort order. Note: The arrows in the lower portion of the figure do not indicate the direction of certificate issuance - they indicate the direction of the tree traversal from the target certificate (EE). +----+ +----+ +----+ | TA | | TA | | TA | +----+ +----+ +----+ / \ ^ ^ / \ | | v v +---+ +---+ +---+ +---+ | A | | C | | A |<->| C | +---+ +---+ +---+ +---+ ^ ^ ^ ^ +----+ | | +----+ \ / | TA | | | | TA | v v +----+ | | +----+ +---+ ^ | | ^ | B | \ | | / +---+ \ | | / / \ +---+ +---+ / \ | C | | A | v v +---+ +---+ +---+ +---+ ^ ^ | E | | D | | / +---+ +---+ | / +---+ Infrastructure | B | +---+ ^ | +----+ | EE | +----+ The Same Infrastructure Represented as a Tree +----+ +----+ | TA | | TA | +----+ +----+ ^ ^ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 26] Certification Path Building November 2003 | | +---+ +---+ | 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 tree traversal Figure 13 - Path Building Using a Depth First Tree Traversal Figure 13 illustrates that four possible paths exist for this example. Suppose that the last path (TA->A->B->EE) is the only path that will validate. This could be for any combination of reasons such as name constraints, policy processing, validity periods, or path length constraints. The goal of an efficient path-building component is to select the fourth path first by testing properties of the certificates as the tree is traversed. For example, when the path building software is at entity B in the graph, it should examine both choices A and C to determine which certificate is the most likely best choice. An efficient module would conclude that A is the more likely correct path. Then, at A, the module compares terminating the path at TA, or moving to C. Again, an efficient module will make the better choice (TA) and thereby find the "best path first". What if the choice between CA certificates is not binary as it was in the previous example? What if the path building software encounters a branch point with some arbitrary number of CA certificates thereby Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 27] Certification Path Building November 2003 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 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 edges (certificates) have already been tried. 2.5 Building Certification Paths for CRL Signers The CRL Signer certificate may or may not be the same as the Certificate Signer certificate. For example, after a CA performs a key rollover, the new CA certificate will be the CRL Signer, whereas the old CA certificate is the Certificate Signer for previously issued certificates. In the case of indirect CRLs, the CRL Signer will have a different name and key from the Certificate Signer. In the case where the CRL Signer certificate (and certification path) is not identical to the Certificate Signer certificate (and certification path), special care should be exercised when building the CRL Signer certification path. If special consideration is not given to building CRL Signer paths, a CRL signer path could be constructed that terminates with a foreign root or through a foreign certification path to the same root. If this behavior is not prevented, the relying party may end up checking the wrong CRL, or even a maliciously substituted CRL, resulting in denial of service or security breach. For example, suppose the following certification path is built for E and is valid for the "high assurance" policy. A->B->C->E Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 28] Certification Path Building November 2003 When the building/validation routine attempts to verify that E is not revoked, C is referred to as the Certificate Signer. 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" but with a different key than the key that was used previously 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: A->X->Y->RogueCA->C2 If a path such as the one above is permitted, nothing can be concluded about the revocation status of E. The RogueCA may have revoked or "unrevoked" E and this breach would go undetected. 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 Certificate Signer certificate, the Certificate Signer path should be used to verify the CRL; no additional path building is required. If the CRL Signer certificate is not identical to the Certificate Signer certificate, a second path should be built for the CRL Signer 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 emanate from the same trust anchor (subject name and trusted public key) as the Certificate Signer's certification path. 2. CA Name Matching: The subject distinguished names of all the CA certificates in the two certification paths should match on a one-to- one basis (without regard to self-issued certificates) for the entire length of the shorter of the two paths. The CRL Signer certificate should not be included in the comparison. 3. CRL Signer Certification Path Length: The length of the CRL Signer certification path should be equal to or less than the length of the Certificate Signer certification path plus (+) one. This allows a given Certificate Signer to issue a certificate to a delegated/subordinate CRL Signer. The latter configuration represents the maximum certification path length for a CRL Signer. 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. In combination with the second guideline, the first guideline prevents a malicious individual from creating a mock Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 29] Certification Path Building November 2003 infrastructure that maps on a one-to-one subject distinguished name basis to the infrastructure they seek to compromise. The second guideline prevents roaming certification paths such as the previously described example CRL Signer path for A->B->C->E. It is especially important that the "without regard to self-issued certificates" is noted and 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 distinguished name 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 Certificate Signer 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 distinguished name 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 distinguished names, specifically, A, B, or C. 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 paper 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 30] Certification Path Building November 2003 of these are possible approaches, and each of these may offer different benefits to a particular environment or application. Regardless of semantics, a path-building module needs to contain the following components: 1) The logic for building and traversing the certificate graph. 2) Logic for retrieving the necessary certificates (and CRLs and/or other revocation status information if the path is to be validated) from the available source(s). Assuming a more efficient and agile path building module is desired, the following is a good starting point and will tie into the remainder of this document. For a path-building module to take full advantage of all the suggested optimizations listed in this document, it will need all of the components listed below. 1) A local certificate and CRL cache. a. This may be used by all certificate-using components - it does not need to be specific to the path building software. A local cache could be memory resident, stored in an operating system or application certificate store, stored in a database, or even stored in individual files on the hard disk. While the implementation of this cache is beyond the scope of this document, some design considerations are listed below. 2) The logic for building and traversing the certificate graph / tree. a. This performs sorting functionality for prioritizing certificates (and 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 31] Certification Path Building November 2003 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 and issuedByThisCA 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 in the CRL distribution point certificate extension. iii. Support LDAP referrals. This is typically only a matter of activating the appropriate flag in the LDAP API. c. HTTP support for CRL distribution points and AIA support. i. Consider HTTPS support 4) A certification path cache that stores previously validated relationships between certificates. This cache should include: a. A configurable expiration date for each entry. 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. 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 as to what could be 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 32] Certification Path Building November 2003 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 end point for the path. 2) Trust List - This is the other endpoint of the path, and can consist of either: a. Trusted CA certificates b. Trusted keys and distinguished names - a certificate is not necessarily required 2.7.2 Optional Inputs In addition to the inputs defined 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 1 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) Collection of certificates that may be useful in building the path 9) Collection of certificate revocation lists and/or other revocation data Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 33] Certification Path Building November 2003 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 in the manner 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 distinguished names. 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 which sorting provides. Consider the following diagram: +---+ | R | +---+ ^ / v +---+ +---+ +---+ +---+ +----+ | A |<----->| E |<---->| D |--->| Z |--->| EE | +---+ +---+ +---+ +---+ +----+ ^ ^ ^ ^ \ / \ / \ / \ / v v v v +---+ +---+ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 34] Certification Path Building November 2003 | B |<----->| C | +---+ +---+ Figure 14 - 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 & 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). Now the builder adds D and faces a decision between two certificates. (Choose between D(C) or D(E)) The builder now sorts the two choices in order of priority. The sorting is partially based upon what is currently in the path. Suppose the order the builder selects is [D(E), D(C)]. The current path is now D(E)->Z(D)->EE(Z). Currently the builder has three nodes in the graph (EE, Z, and D) and should maintain the state, including sort order of the certificates at D, when adding the next node, E. When E is added, the builder now has four certificates to sort: E(A), E(B), E(C), and E(D). In this case, the example builder opts for the order [E(C), E(B), E(A), E(D)]. The current path is now E(C)->D(E)- >Z(D)->EE(Z) and the path has four nodes; EE, Z, D, and E. Upon adding the fifth node, C, the builder sorts the certificates (C(B), C(D), and C(E)) at C, and selects C(E). The path is now C(E)- >E(C)->D(E)->Z(D)->EE(Z) and the path has five nodes; EE, Z, D, E, and C. Now the builder finds itself back at node E with four certificates. If the builder were to use the prior sort order from the first encounter with E, it would have [E(C), E(B), E(A), E(D)]. In the current path's context, this ordering may be inappropriate. To begin with, the certificate E(C) is already in the path so it certainly does not deserve first place. The best way to handle this situation is for the path builder to handle this instance of E as a new (sixth) node in the tree. In other words, there is no state information for this new instance of E - it is treated just as any other new node. The certificates at the new node are sorted based upon the current path content and the first certificate is then selected. For example, the builder may examine E(B) and note that it contains a name constraint prohibiting "C". At this point in the decision tree, E(B) could not be added to the path Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 35] Certification Path Building November 2003 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 make it last or eliminate it from this node since certificates can not 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 anchor keys has been found. In the event the first path fails to validate, the path builder will still have the seven nodes and associated state information to work with. On the next iteration, the path builder is able to traverse back up the tree to a working decision point, such as A, and select the next certificate in the sorted list at A. In this example, that would be A(B). (A(R) has already been tested.) This would dead end, and the builder traverse back up to the next decision point, E(2) where it would try D(E). This process repeats until the traversal backs all the way up to EE or a valid path is found. If the tree traversal returns to EE, all possible paths have been exhausted and the builder can conclude no valid path exists. This approach of sorting certificates in order to optimize path building will yield better results than not optimizing the tree traversal. However, the path building process can be further streamlined by eliminating certificates, and entire branches of the tree as a result, as paths are built. 3.2 Sorting vs. Elimination Consider a situation when building a path in which three CA certificates are found for a given target certificate and must be Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 36] Certification Path Building November 2003 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 on another point in the tree; at that point it may or may not be eliminated. The prior section details an example of this behavior. Elimination of certificates could potentially eliminate the traversal of a large, time-consuming infrastructure that will never lead to a valid path. The question of whether to sort or eliminate is one that pits the flexibility of the software interface against efficiency. To be clear, if one eliminates invalid paths as they are built, returning only likely valid paths, the end result will be an efficient path building module. The drawback to this is that unless the software makes allowances for it, the calling application will not be able to see what went wrong. The user may only see the unrevealing error message: "No certification path found." On the other hand, the path building module could opt to not rule out any certification paths. The path building software could then return any and all paths it can build from the certificate graph. It is then up to the validation engine to determine which are valid and which are invalid. The user or calling application can then have complete details on why each and every path fails to validate. The drawback is obviously one of performance, as an application or end user may wait for an extended period of time while cross-certified PKIs are navigated in order to build paths that will never validate. Neither option is a very desirable approach. One option provides good performance for users, which is beneficial. The other option though allows administrators to diagnose problems with the PKI, directory, or software. Below are some recommendations to reach a middle ground on this issue. First, developers are strongly encouraged to output detailed log information from the path building software. The log should explicitly indicate every choice the builder makes and why. It should clearly identify which certificates are found and used at each step in building the path. If care is taken to produce a useful log, Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 37] Certification Path Building November 2003 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. 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 which 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, it is up to the developer to determine how to handle the tradeoff between efficiency and provision of information. A developer could choose the middle ground by opting to implement some optimizations as elimination rules and others as not. A developer could validate certificate signatures, or even check revocation status while building the path, and then make decisions based upon the outcome of those checks as to whether to eliminate the certificate in question. This document suggests the following approach: 1) While building paths, eliminate any and all certificates that do not satisfy all path validation requirements with the following exceptions: a. Do not check revocation status if it requires a directory lookup or network access b. Do not check digital signatures c. Do not check anything that can not be checked as part of the iterative process of traversing the tree d. Keep a detailed log, if this feature is enabled Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 38] Certification Path Building November 2003 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 [RFC 3280] 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 - return this to the user in the event no valid path is found. Since the path building software was designed to return the "best path first", this is the path that should be shown to the user. As stated above, this document recommends that developers do not validate digital signatures or check revocation status as part of the path building process. This recommendation is based on two assumptions about PKI and its usage. First, signatures in a working PKI are usually good. Since signature validation is costly in terms of processor time, it is better to delay signature checking until a complete path is found. Second, it is fairly uncommon in typical application environments to encounter a revoked key; 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 Programmatically 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 39] Certification Path Building November 2003 3.3.1 Node Representation For CA Entities A "node" in the certification graph is a collection of CA certificates with identical subject distinguished names. 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 - Could be stored as an array format 2. Sorted order of the certificates - Sorting could be performed on aforementioned array 3. "Current" certificate indicator - May be an index number on the array 4. The current policy set. (May be split into authority and user constrained sets if desired.) - It is suggested that encapsulating the policy set in an object with logic for manipulating the set such as performing intersections, mappings, etc., will simplify implementation 5. Indicators (requireExplicitPolicy, inhibitPolicyMapping, anyPolicyInhibit) - skipCert values should also be stored 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. - If using the array approach, eliminated certificates could be placed at the front of the array with the current indicator set to the first certificate not eliminated 7. A "next" indicator that allows the software to locate the next node in the current path - May simply be a pointer assigned the address of the next node 8. A "previous" indicator that allows the software to locate the previous node in the current path - This is to simplify path validation. It may simply be a pointer assigned the address of the previous node 3.3.2 Using Nodes to Iterate Over All Paths In simplest form, a node is created, the certificates are sorted, the next subject distinguished name required is determined from the first certificate, and a new node is attached to the certification path via the next indicator. (Number seven above.) This process continues until the path terminates. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 40] Certification Path Building November 2003 Keeping in mind while that the following algorithm is designed to be implemented using recursion, consider the example in Figure 13 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 distinguished name (B) is read from E, and new node is created for B containing both certificates issued to B. [B(A) and B(C)]. The sorting rules are applied to these two certificates and the sorting algorithm returns B(C);B(A). This sorted order is stored and the current indicator is set to B(C). Indicators are set and the policy sets are calculated to the extent possible with respect to B(C). The following diagram illustrates the current state with the current certificate indicated with a "*". +-------------+ +---------------+ | Node 1 | | Node 2 | | Subject: E |--->| Subject: B | | Issuers: B* | | Issuers: C*,A | +-------------+ +---------------+ Next, a node is created for C and all three certificates are added to it. The sorting algorithm happens to return the certificates sorted in the following order: C(TA);C(A);C(B) +-------------+ +---------------+ +------------------+ | Node 1 | | Node 2 | | Node 3 | | Subject: E |--->| Subject: B |--->| Subject: C | | Issuers: B | | Issuers: C*,A | | Issuers: TA*,A,B | +-------------+ +---------------+ +------------------+ Recognizing that the trust anchor has been found, the path (TA->C->B- >E) is validated but fails. (Remember that the only valid path happens to be TA->A->B->E.) The path building module now moves the current certificate indicator in node 3 to C(A), and adds the node for A. +-------------+ +---------------+ +------------------+ | Node 1 | | Node 2 | | Node 3 | | Subject: E |--->| Subject: B |--->| Subject: C | | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B | +-------------+ +---------------+ +------------------+ | Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 41] Certification Path Building November 2003 v +------------------+ | Node 4 | | Subject: A | | Issuers: TA*,C,B | +------------------+ The path TA->A->C->B->E is validated and it fails. The path building module now moves the current indicator in node 4 to A(C) and adds a node for C. +-------------+ +---------------+ +------------------+ | Node 1 | | Node 2 | | Node 3 | | Subject: E |--->| Subject: B |--->| Subject: C | | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B | +-------------+ +---------------+ +------------------+ | v +------------------+ +------------------+ | Node 5 | | Node 4 | | Subject: C |<---| Subject: A | | Issuers: TA*,A,B | | Issuers: TA,C*,B | +------------------+ +------------------+ At this juncture, the decision of whether to allow repetition of name and key comes to the forefront. If the certification path building module will NOT allow repetition of name and key, there are no certificates in node 5 that can be used. (C and the corresponding public key is already in the path at node 3) At this point, node 5 is removed from the current path and the current certificate indicator on node 4 is moved to A(B). If instead, the module is only disallowing repetition of certificates, C(A) is eliminated from node 5 since it is in use in node 3, and path building continues by first validating TA->C->A->C- >B->E, and then continuing to try to build paths through C(B). After this also fails to provide a valid path, node 5 is removed from the current path and the current certificate indicator on node 4 is moved to A(B). +-------------+ +---------------+ +------------------+ | Node 1 | | Node 2 | | Node 3 | | Subject: E |--->| Subject: B |--->| Subject: C | | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B | +-------------+ +---------------+ +------------------+ | v +------------------+ Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 42] Certification Path Building November 2003 | Node 4 | | Subject: A | | Issuers: TA,C,B* | +------------------+ Now a new node 5 is created for B. Just as with the prior node 5, if not repeating name and key, B also offers no certificates that can be used (B and B's public key is in use in node 2) so the new node 5 is also removed from the path. At this point all certificates in node 4 have now been tried, so node 4 is removed from the path, and the current indicator on node 3 is moved to C(B). Also as above, if allowing repetition of name and key, B(C) is removed from the new node 5 (B(C) is already in use in node 3) and paths attempted through the remaining certificate B(A). After this fails, it will lead back to removing node 5 from the path. At this point all certificates in node 4 have now been tried, so node 4 is removed from the path, and the current indicator on node 3 is moved to C(B). This process continues until all certificates in node 1 (if there happened to be more than one) have been tried, or until a valid path has been found. Once the process ends and in the event no valid path was found, it may be concluded that no path can be found from E to TA. 3.4 Implementing Path Building Optimization The following section describes methods that may be used for optimizing the certification path building process by sorting certificates. Optimization as described earlier seeks to prioritize a list of certificates, effectively prioritizing (weighting) branches of the graph / tree. The optimization methods can be used to assign a cumulative score to each certificate. The process of scoring the certificates amounts to testing each certificate against the optimization methods a developer chooses to implement, and then adding the score for each test to a cumulative score for each certificate. After this is completed for each certificate at a given branch point in the builder's decision tree, the certificates can be sorted so that the highest scoring certificate is selected first, the second highest is selected second, etc. For example, suppose the path builder has only these two simple sorting methods: 1) If the certificate has a subject key ID, +5 to score 2) If the certificate has an authority key ID, +10 to score Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 43] Certification Path Building November 2003 And it then examined three certificates: 1) Issued by CA 1; has authority key ID; score is 10 2) Issued by CA 2; has subject key ID; score is 5 3) Issued by CA 1; has subject key ID and authority key ID; score is 15 The three certificates are sorted in descending order starting with the highest score: 3, 1, and 2. The path building software should first try building the path through certificate 3. Failing that, it should try certificate 1. Lastly, it should try building a path through certificate 2. The following optimization methods specify tests developers may choose to perform, but does not suggest scores for any of the methods. Rather, developers should evaluate each method with respect to the environment that 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, it is up to the implementer to decide 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 44] Certification Path Building November 2003 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. It is up to the implementer to decide which methods to use and what weights to assign them. As noted previously, this list is also not exhaustive. In addition, name chaining (meaning the subject name of the issuer certificate matches the issuer name of the issued certificate) is not addressed as a sorting method since adherence to this is required in order to build the decision tree to which these methods will be applied. Also unaddressed in the sorting methods is the prevention of repeating certificates. Path builders should handle name chaining and certificate repetition irrespective of the optimization approach. Each sorting method description specifies whether the method may be used to eliminate certificates, the number of possible numeric values (sorting weights) for the method, components from section 2.6 that are required for implementing the method, forward and reverse methods descriptions, and finally a justification for inclusion of the method. With regard to elimination of certificates, it is important to understand that certificates are eliminated only at a given decision point for many methods. For example, the path built up to certificate X may be invalidated due to name constraints by the addition of certificate Y. At this decision point only, Y could be eliminated from further consideration. At some future decision point, while building this same path, the addition of Y may not invalidate the path. For some other sorting methods, certificates could be eliminated from the process entirely. For example, certificates with unsupported signature algorithms could not be included in any path and validated. While the path builder may certainly be designed to operate in this fashion, it is also 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 45] Certification Path Building November 2003 Number of possible values: Binary Components required: None Forward Method: Certificates with basicConstraints present and cA=TRUE have priority. Certificates without basicConstraints, or with basicConstraints and cA=FALSE 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 [RFC 3280], basicConstraints is required to be present with cA=TRUE in all CA certificates. 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 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 can not be built through a CA certificate with inappropriate keyUsage. Note that digitalSignature is NOT required to be set in a CA certificate. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 46] Certification Path Building November 2003 3.5.4 Time (T) Falls within the Certificate Validity May be used to eliminate certificates: Yes Number of possible values: Binary Components required: None Forward Method: Certificates that contain the required time (T) within their validity period have 100% priority. Otherwise, the certificate is eliminated or has priority zero. Reverse Method: Same as forward. Justification: A valid certification path cannot be built if T falls outside of the certificate validity period. NOTE: Special care should be taken to return a meaningful error to the caller, especially in the event the target certificate does not meet this criterion, if this sorting method is used for elimination. (e.g., the certificate is expired). 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. There is some probability that the path from that certificate to a trust anchor is still 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 47] Certification Path Building November 2003 3.5.6 Previously Verified Signatures May be used to eliminate certificates: Yes Number of possible values: Binary Components required: Path Cache Forward Method: If a previously verified relationship exists in the path cache between the subject certificate and a public key present in one or more issuer certificates, all the certificates containing said public key have higher priority. Other certificates may be eliminated or set to zero priority. Reverse Method: Does not apply. (Although the path cache does contain one to one relationships in reverse, nothing can be concluded about the likelihood of finding a given target certificate down one branch versus another using this method.) 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, but the benefit is likely less than that of the forward direction. 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 48] Certification Path Building November 2003 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 lower priority (or perhaps eliminated). Reverse Method: Certificates that will allow successful processing of any name constraints present in the path to this point are given higher priority. Justification: A valid path cannot be built if name constraints are violated. 3.5.9 Certificate is Not Revoked May be used to eliminate certificates: No Number of possible values: Three Components required: CRL Cache Forward Method: If a current CRL for a certificate is present in the CRL cache, and the certificate serial number is not on the CRL, the certificate has priority. If the certificate serial number is present on the CRL, it has zero priority. Reverse Method: Same as Forward. Alternately, the certificate may be eliminated if the CRL is verified. That is, fully verify the CRL signature and relationship to the certificate in question in accordance with [RFC 3280]. While this is viable, the signature verifications required make it less attractive as an elimination method. It is suggested that this method only be used for sorting and that CRLs 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 validation is performed post path validation - CRLs 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, some status information should be preserved so that a meaningful error may be returned in the event no path is found. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 49] Certification Path Building November 2003 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 Matching Key Identifiers (KIDs) May be used to eliminate certificates: No Number of possible values: Three Components required: None Forward Method: Certificates whose subject key identifier (SKID) matches the current certificate's authority key identifier (AKID) have highest priority. Certificates without a SKID have medium priority. Certificates whose SKID does not match the current certificate's AKID (if both are present) have zero priority. If the current certificate expresses the issuer name and serial number in the AKID, certificates that match both these identifiers have highest priority. Certificates that match only the issuer name in the AKID have medium priority. Reverse Method: Certificates whose AKID matches the current certificate's SKID have highest priority. Certificates without an AKID have medium priority. Certificates whose AKID does not match the current certificate's SKID (if both are present) have zero priority. If the certificate expresses the issuer name and serial number in the AKID, certificates that match both these identifiers in the current certificate have highest priority. Certificates that match only the issuer name in the AKID have medium priority. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 50] Certification Path Building November 2003 Justification: 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 [RFC 3280], it is extremely important that KIDs be used ONLY as sorting criteria or hint 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.12 Policy Processing May be used to eliminate certificates: Yes Number of possible values: Three Components required: None Forward Method: Certificates that satisfy Forward Policy Chaining have priority. (See section 4 entitled "Forward Policy Chaining" for details.) If the caller provided an initial-policy-set and did not set the initial-require-explicit flag, the weight of this sorting method should be increased. If the initial-require-explicit-policy flag was set by the caller or by a certificate, certificates may be eliminated. Reverse Method: Certificates that contain policies/policy mappings that will allow successful policy processing of the path to this point have priority. If the caller provided an initial-policy-set and did not set the initial-require-explicit flag, the weight of this sorting method should be increased. Certificates may be eliminated only if initial-require-explicit was set by the caller or if require- explicit-policy was set by a certificate in the path to this point. Justification: In a policy-using environment, certificates that successfully propagate policies are more likely part of an intended certification path than those that do not. When building in the forward direction, it is always possible that a certificate closer to the trust anchor will set the require-explicit- policy indicator; so giving preference to certification paths that propagate policies may increase the probability of finding a valid path first. If the caller (or a certificate in the current path) has specified or set the initial-require-explicit-policy indicator as true, this sorting method can also be used to eliminate certificates when building in the forward direction. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 51] Certification Path Building November 2003 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.13 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 trusted root certificate in a cross certified environment, the policies asserted in the CA certificates will match those in the caller's domain. Since the initial acceptable policy set is specified in the caller's domain, matches may indicate that the path building is drawing nearer to a desired trust anchor. In the reverse direction, finding policies that match those of the target certificate may indicate the path is drawing near to the target's domain. 3.5.14 Endpoint Distinguished Name 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 52] Certification Path Building November 2003 Justification: In the forward direction, if a certificate's issuer DN matches a trust anchor's DN, then it may complete the path. In the reverse direction, if the certificate's subject DN matches the issuer DN of the target certificate, this may be the last certificate required to complete the path. 3.5.15 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, this sorting method appears to mirror the preceding one. However, this sorting method should be capable of producing a 100% weight even if the issuer DN has more RDNs than the trust anchor. The Issuer DN need only contain all the RDNs (in order) of the trust anchor. NOTE: In the case where all RDNs match, this sorting method mirrors the functionality of the preceding one. This allows for partial matches to be weighted differently from exact matches. Additionally, it should be noted that this method can require a lot of processing if many trust anchors are present. 3.5.16 Certificates are Retrieved from cACertificate 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 Forward Method: Certificates retrieved from the cACertificate attribute have priority over certificates retrieved from the crossCertificatePair attribute. (See [RFC 2587]) Reverse Method: Does not apply. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 53] Certification Path Building November 2003 Justification: The cACertificate attribute contains certificates issued from local sources and self issued certificates. By using the cACertificate 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. Not only do most of today's PKI applications spend most of their time processing information from the local (user's own) PKI, but the local PKI is usually very efficient to traverse due to proximity and network speed. 3.5.17 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 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 aren't consistent, the signature on the subject certificate will not 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.18 Similar Issuer and Subject Names May be used to eliminate certificates: No Number of possible values: Sliding Scale Components required: None Forward Method: Certificates that match more RDNs between the subject DN and the issuer DN 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 54] Certification Path Building November 2003 generally match fewer RDNs (if any), whereas certificates in the local domain will frequently match multiple RDNs. 3.5.19 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 repository) Forward Method: A certificate whose issuer certificate is present in the certificate cache (and populated with one or more certificates) has priority. A certificate whose issuer certificate is present in the certificate cache and fully populated with recent data (all certificate attributes have been searched within an appropriate timeout period - something shorter than cache expiry.) has higher priority. (This helps reduce LDAP lookups until necessary.) Reverse Method: If an entity named by a reverse certificate is present in the certificate cache and populated with certificates then it has higher priority. If the entry is fully populated with current data (all certificate attributes have been searched within the timeout period.) then it has higher priority. Justification: The presence of required directory values populated in the cache increases the likelihood that all the required certificates and CRLs needed to complete the path from this certificate to the trust anchor (or target if building in reverse) are present in the cache from a prior path being developed, thereby eliminating the need for directory access to complete the path. In the event no path can be found, the performance cost is low since the certificates were likely not retrieved from the network. 3.5.20 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 55] Certification Path Building November 2003 through this entity at some past point, so a path still likely exists. This also helps reduce LDAP lookups until necessary. 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 to some 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 quite 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 been long considered a weakness inherent to building in the forward (from the target certificate) direction. 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 / end entity 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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 56] Certification Path Building November 2003 When building in the forward direction, policy processing is handled in much the same fashion as 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. 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 foreign 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} Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 57] Certification Path Building November 2003 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 rest {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 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 rest {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. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 58] Certification Path Building November 2003 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. 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 15. +----+ +---+ | TA | | Z | +----+ +---+ | | | | V V +---+ +---+ | C |<-----| Y | +---+ +---+ | | V +--------+ | Target | +--------+ Figure 15 - 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, Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 59] Certification Path Building November 2003 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. 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 16 - 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 which 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 60] Certification Path Building November 2003 only need to appear once in the path (see section 2.4.1 for more information on the reasoning behind this recommendation). 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 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 which uses the authority distinguished name 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 distinguished names being encoded as PrintableString. Although frequently encoded as PrintableString, distinguished names may also appear as other types, including BMPString or UTF8String. As a result, software systems that are unable to process BMPString and UTF8String encoded distinguished names may be unable to build and validate some certification paths. Furthermore, looking forward, [RFC 3280] compliant certificates will be required to encode distinguished names as UTF8String as of January 1, 2004. Certification path building software should be prepared to handle "name rollover" certificates as described in [RFC 3280]. Note that the inclusion of a "name rollover" certificate in a certification path does NOT constitute repetition of a distinguished name and key. Implementations that include the "name rollover" certificate in the path should ensure that the distinguished names with differing encoding are regarded as dissimilar. (Implementations may instead handle matching distinguished names of different encodings and will therefore not need to include "name rollover" certificates in the path.) 6. Retrieval Methods Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 61] Certification Path Building November 2003 Building a certification path requires the availability of the certificates that make up the path. There are many different methods for performing this retrieval. 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. The LDAP v3 specification is found in [RFC 2251]. The LDAP v3 specification defines one attribute retrieval option, the "binary" option. This option, when specified in an LDAP retrieval request, was intended to force the directory to ignore any string- based representations of directory information, and send the requested attribute(s) in binary format. Since all PKI objects of concern are binary objects, the "binary" option should be used. However, not all directories support the "binary" option. (Additionally, recent developments in the LDAP working group seem to be leading toward the removal of the "binary" option.) Therefore, all attribute retrievals should specify the attribute name with and without the "binary" option. For example, if an application wishes to retrieve the userCertificate attribute, the retrieval request should contain the following list of attributes to retrieve: "userCertificate, and userCertificate;binary". 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. 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. - cACertificate: contains self-issued certificates (if any) and any certificates issued to this certification authority by Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 62] Certification Path Building November 2003 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: the crossCertificatePair is used to contain certificates issued to this certification authority by other certification authorities in other realms, as well as certificates issued by this certification authority to other certification authorities in other realms. 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 certification authorities. Both elements of the crossCertificatePair are labeled optional in the ASN.1 definition; however the LDAP v2 schema states that the issuedToThisCA (once called the 'forward' element) is mandatory and the issuedByThisCA (once called the 'reverse' element) is optional. 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. - certificateRevocationList: the certificateRevocationList attribute contains a certificate revocation list (CRL). A CRL is defined in [RFC 3280] 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 [RFC 3280]. - 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 [RFC 3280]. 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 (all with and without the ;binary option). Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 63] Certification Path Building November 2003 6.2 Authority Information Access The authority information access (AIA) extension, defined within [RFC 3280], 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 entities that issued the certificate containing the AIA extension. The AIA will provide a uniform resource identifier (URI) 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 [RFC 2560] 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, DAP, or e-mail locators. Support for AIA is optional; [RFC 3280] compliant implementations are not required to populate the AIA extension. 6.3 Subject Information Access The subject information access (SIA) extension, defined within [RFC 3280], 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) when data can be retrieved via LDAP, HTTP, or FTP. The AIA will provide a directoryName when data can be retrieved via directory access protocol (DAP). The AIA 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; [RFC 3280] compliant implementations are not required to populate the SIA extension. 6.4 CRL Distribution Points Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 64] Certification Path Building November 2003 The CRL distribution points (CRLDP) extension, defined within [RFC 3280], indicates how to access CRL information. If a CRLDP extension appears within a certificate, the CRL(s) to which the CRLDP(s) refer is the CRL 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 [RFC 3280]. 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. 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 [RFC 3280] 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.5 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. 7.1 Caching Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 65] Certification Path Building November 2003 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, or some other non-local source. Due to the delays associated with both the establishing of 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 in which retrieval efficiency can often be improved is by the use of 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. There are a number of different ways in which caching can be implemented, and 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. 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 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 66] Certification Path Building November 2003 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 wished to retrieve a certificate with a particular subject distinguished name, 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 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 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. 8. Security Considerations Although certification path building deals directly with security relevant PKI data, the PKI data itself needs no special handling as the PKI data 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 [RFC 3280] and [X.509] is required in order for certification path building, Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 67] Certification Path Building November 2003 certification path validation, and the certificate using application to be properly secured. All of the Security Considerations listed in Section 9 of [RFC 3280] 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 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 using 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. Normative References [RFC 3280] Housley, R., W. Ford, W. Polk and D. Solo, "Internet X.509 Public Key Infrastructure: Certificate and CRL Profile", RFC 2459, January 1999. [X.509] ITU-T Recommendation X.509 (1997 E): Information Technology - Open Systems Interconnection - The Directory: Authentication Framework, June 1997. Informative References [MINHPKIS] Hesse, P., Lemire, D., "Managing Interoperability in Non-Hierarchical Public Key Infrastructures", February 2002. [RFC 1738] Berners-Lee, T., L. Masinter and M. McCahill, "Uniform Resource Locators (URL)", RFC 1738, December 1994. [RFC 2026] Bradner, S., "The Internet Standards Process - Revision 3", RFC 2026, October 1996 [RFC 2247] Kille, S., M. Wahl, A. Grimstad, R. Huber and S. Sataluri, "Using Domains in LDAP/X.500 Distinguished Names", RFC 2247, January 1998. [RFC 2251] Wahl, M., T. Howes and S. Kille, "Lightweight Directory Access Protocol (v3) ", RFC 2251, December 1997. Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 68] Certification Path Building November 2003 [RFC 2252] Wahl, M., A. Coulbeck, T. Howes and S. Kille, "Lightweight Directory Access Protocol (v3): Attribute Syntax Definitions", RFC 2252, December 1997. [RFC 2396] Berners-Lee, T., Fielding, R., Irving, U.C., and L. Masinter, "Uniform Resource Identifiers (URI): Generic Syntax", RFC 2396, August 1998. [RFC 2560] Myers, M., R. Ankney, A. Malpani, S. Galperin and C. Adams, "Online Certificate Status Protocal - OCSP", June 1999. [RFC 2587] S. Boeyen, T. Howes, P. Richard, "Internet X.509 Public Key Infrastructure LDAPv2 Schema", RFC 2587, June 1999 [X.501] ITU-T Recommendation X.501: Information Technology - Open Systems Interconnection - The Directory: Models, 1993. [X.520] ITU-T Recommendation X.520: Information Technology - Open Systems Interconnection - The Directory: Selected Attribute Types, 1993. [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. Acknowledgments 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, and Alice Sturgeon. Author's Addresses Matt Cooper Orion Security Solutions, Inc. 1489 Chain Bridge Rd, Ste. 300 McLean, VA 22101, USA Phone: +1-703-917-0060 Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 69] Certification Path Building November 2003 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. 4031 University Dr. Ste. 200 Fairfax, VA 22030, USA Phone: +1-703-934-2031 Email: pmhesse@geminisecurity.com Susan Joseph DigitalNet Government Solutions, LLC. 141 National Business Parkway, Ste. 210 Annapolis Junction, MD 20701, USA Phone: +1-301-939-2705 Email: susan.joseph@digitalnet.com Richard Nicholas DigitalNet Government Solutions, LLC. 141 National Business Parkway, Ste. 210 Annapolis Junction, MD 20701, USA Phone: +1-301-939-2722 Email: richard.nicholas@digitalnet.com Cooper, Dzambasow, Hesse, Joseph, Nicholas Expires - May 2004 [Page 70]