RFC 4158
Internet X.509 Public Key Infrastructure: Certification Path Building
Pages: 81
Informational
Informational
Part 1 of 4 – Pages 1 to 14
Network Working Group M. Cooper Request for Comments: 4158 Orion Security Solutions Category: Informational Y. Dzambasow A&N Associates P. Hesse Gemini Security Solutions S. Joseph Van Dyke Technologies R. Nicholas BAE Systems September 2005 Internet X.509 Public Key Infrastructure: Certification Path Building Status of This Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2005).Abstract
This document provides guidance and recommendations to developers building X.509 public-key certification paths within their applications. By following the guidance and recommendations defined in this document, an application developer is more likely to develop a robust X.509 certificate-enabled application that can build valid certification paths across a wide range of PKI environments.Table of Contents
1. Introduction ....................................................3 1.1. Motivation .................................................4 1.2. Purpose ....................................................4 1.3. Terminology ................................................5 1.4. Notation ...................................................8 1.5. Overview of PKI Structures .................................8 1.5.1. Hierarchical Structures .............................8 1.5.2. Mesh Structures ....................................10 1.5.3. Bi-Lateral Cross-Certified Structures ..............11 1.5.4. Bridge Structures ..................................13 1.6. Bridge Structures and Certification Path Processing .......14
2. Certification Path Building ....................................15 2.1. Introduction to Certification Path Building ...............15 2.2. Criteria for Path Building ................................16 2.3. Path-Building Algorithms ..................................17 2.4. How to Build a Certification Path .........................21 2.4.1. Certificate Repetition .............................23 2.4.2. Introduction to Path-Building Optimization .........24 2.5. Building Certification Paths for Revocation Signer Certificates ..............................................30 2.6. Suggested Path-Building Software Components ...............31 2.7. Inputs to the Path-Building Module ........................33 2.7.1. Required Inputs ....................................33 2.7.2. Optional Inputs ....................................34 3. Optimizing Path Building .......................................35 3.1. Optimized Path Building ...................................35 3.2. Sorting vs. Elimination ...................................38 3.3. Representing the Decision Tree ............................41 3.3.1. Node Representation for CA Entities ................41 3.3.2. Using Nodes to Iterate Over All Paths ..............42 3.4. Implementing Path-Building Optimization ...................45 3.5. Selected Methods for Sorting Certificates .................46 3.5.1. basicConstraints Is Present and cA Equals True .....47 3.5.2. Recognized Signature Algorithms ....................48 3.5.3. keyUsage Is Correct ................................48 3.5.4. Time (T) Falls within the Certificate Validity .....48 3.5.5. Certificate Was Previously Validated ...............49 3.5.6. Previously Verified Signatures .....................49 3.5.7. Path Length Constraints ............................50 3.5.8. Name Constraints ...................................50 3.5.9. Certificate Is Not Revoked .........................51 3.5.10. Issuer Found in the Path Cache ....................52 3.5.11. Issuer Found in the Application Protocol ..........52 3.5.12. Matching Key Identifiers (KIDs) ...................52 3.5.13. Policy Processing .................................53 3.5.14. Policies Intersect the Sought Policy Set ..........54 3.5.15. Endpoint Distinguished Name (DN) Matching .........55 3.5.16. Relative Distinguished Name (RDN) Matching ........55 3.5.17. Certificates are Retrieved from cACertificate Directory Attribute .................56 3.5.18. Consistent Public Key and Signature Algorithms ....56 3.5.19. Similar Issuer and Subject Names ..................57 3.5.20. Certificates in the Certification Cache ...........57 3.5.21. Current CRL Found in Local Cache ..................58 3.6. Certificate Sorting Methods for Revocation Signer Certification Paths .......................................58 3.6.1. Identical Trust Anchors ............................58 3.6.2. Endpoint Distinguished Name (DN) Matching ..........59 3.6.3. Relative Distinguished Name (RDN) Matching .........59
3.6.4. Identical Intermediate Names .......................60
4. Forward Policy Chaining ........................................60
4.1. Simple Intersection .......................................61
4.2. Policy Mapping ............................................62
4.3. Assigning Scores for Forward Policy Chaining ..............63
5. Avoiding Path-Building Errors ..................................64
5.1. Dead Ends .................................................64
5.2. Loop Detection ............................................65
5.3. Use of Key Identifiers ....................................66
5.4. Distinguished Name Encoding ...............................66
6. Retrieval Methods ..............................................67
6.1. Directories Using LDAP ....................................67
6.2. Certificate Store Access via HTTP .........................69
6.3. Authority Information Access ..............................69
6.4. Subject Information Access ................................70
6.5. CRL Distribution Points ...................................70
6.6. Data Obtained via Application Protocol ....................71
6.7. Proprietary Mechanisms ....................................71
7. Improving Retrieval Performance ................................71
7.1. Caching ...................................................72
7.2. Retrieval Order ...........................................73
7.3. Parallel Fetching and Prefetching .........................73
8. Security Considerations ........................................74
8.1. General Considerations for Building a Certification Path ..74
8.2. Specific Considerations for Building Revocation
Signer Paths ..............................................75
9. Acknowledgements ...............................................78
10. Normative References ..........................................78
11. Informative References ........................................78
1. Introduction
[X.509] public key certificates have become an accepted method for
securely binding the identity of an individual or device to a public
key, in order to support public key cryptographic operations such as
digital signature verification and public key-based encryption.
However, prior to using the public key contained in a certificate, an
application first has to determine the authenticity of that
certificate, and specifically, the validity of all the certificates
leading to a trusted public key, called a trust anchor. Through
validating this certification path, the assertion of the binding made
between the identity and the public key in each of the certificates
can be traced back to a single trust anchor.
The process by which an application determines this authenticity of a
certificate is called certification path processing. Certification
path processing establishes a chain of trust between a trust anchor
and a certificate. This chain of trust is composed of a series of
certificates known as a certification path. A certification path begins with a certificate whose signature can be verified using a trust anchor and ends with the target certificate. Path processing entails building and validating the certification path to determine whether a target certificate is appropriate for use in a particular application context. See Section 3.2 of [RFC3280] for more information on certification paths and trust.1.1. Motivation
Many other documents (such as [RFC3280]) cover certification path validation requirements and procedures in detail but do not discuss certification path building because the means used to find the path does not affect its validation. This document therefore is an effort to provide useful guidance for developers of certification path- building implementations. Additionally, the need to develop complex certification paths is increasing. Many PKIs are now using complex structures (see Section 1.5) rather than simple hierarchies. Additionally, some enterprises are gradually moving away from trust lists filled with many trust anchors, and toward an infrastructure with one trust anchor and many cross-certified relationships. This document provides helpful information for developing certification paths in these more complicated situations.1.2. Purpose
This document provides information and guidance for certification path building. There are no requirements or protocol specifications in this document. This document provides many options for performing certification path building, as opposed to just one particular way. This document draws upon the authors' experiences with existing complex certification paths to offer insights and recommendations to developers who are integrating support for [X.509] certificates into their applications. In addition, this document suggests using an effective general approach to path building that involves a depth first tree traversal. While the authors believe this approach offers the balance of simplicity in design with very effective and infrastructure-neutral path-building capabilities, the algorithm is no more than a suggested approach. Other approaches (e.g., breadth first tree traversals) exist and may be shown to be more effective under certain conditions. Certification path validation is described in detail in both [X.509] and [RFC3280] and is not repeated in this document.
This document does not provide guidance for building the certification path from an end entity certificate to a proxy certificate as described in [RFC3820].1.3. Terminology
Terms used throughout this document will be used in the following ways: Building in the Forward direction: The process of building a certification path from the target certificate to a trust anchor. 'Forward' is the former name of the crossCertificatePair element 'issuedToThisCA'. Building in the Reverse direction: The process of building a certification path from a trust anchor to the target certificate. 'Reverse' is the former name of the crossCertificatePair element 'issuedByThisCA'. Certificate: A digital binding that cannot be counterfeited between a named entity and a public key. Certificate Graph: A graph that represents the entire PKI (or all cross-certified PKIs) in which all named entities are viewed as nodes and all certificates are viewed as arcs between nodes. Certificate Processing System: An application or device that performs the functions of certification path building and certification path validation. Certification Authority (CA): An entity that issues and manages certificates. Certification Path: An ordered list of certificates starting with a certificate signed by a trust anchor and ending with the target certificate. Certification Path Building: The process used to assemble the certification path between the trust anchor and the target certificate. Certification Path Validation: The process that verifies the binding between the subject and the subject-public-key defined in the target certificate, using a trust anchor and set of known constraints.
Certificate Revocation List (CRL): A signed, time stamped list
identifying a set of certificates that are no longer considered
valid by the certificate issuer.
CRL Signer Certificate: The specific certificate that may be used for
verifying the signature on a CRL issued by, or on behalf of, a
specific CA.
Cross-Certificate: A certificate issued by one CA to another CA for
the purpose of establishing a trust relationship between the two
CAs.
Cross-Certification: The act of issuing cross-certificates.
Decision Tree: When the path-building software has multiple
certificates to choose from, and must make a decision, the
collection of possible choices is called a decision tree.
Directory: Generally used to refer an LDAP accessible repository for
certificates and PKI information. The term may also be used
generically to refer to any certificate storing repository.
End Entity: The holder of a private key and corresponding
certificate, whose identity is defined as the Subject of the
certificate. Human end entities are often called "subscribers".
Is-revocation-signer indicator: A boolean flag furnished to the
path-building software. If set, this indicates that the target
certificate is a Revocation Signer certificate for a specific CA.
For example, if building a certification path for an indirect CRL
Signer certificate, this flag would be set.
Local PKI: The set of PKI components and data (certificates,
directories, CRLs, etc.) that are created and used by the
certificate using organization. In general, this concept refers
to the components that are in close proximity to the certificate
using application. The assumption is that the local data is more
easily accessible and/or inexpensive to retrieve than non-local
PKI data.
Local Realm: See Local PKI.
Node (in a certificate graph): The collection of certificates having
identical subject distinguished names.
Online Certificate Status Protocol (OCSP): An Internet protocol used
by a client to obtain the revocation status of a certificate from
a server.
OCSP Response Signer Certificate: The specific certificate that may
be used for verifying the signature on an OCSP response. This
response may be provided by the CA, on behalf of the CA, or by a
different signer as determined by the Relying Party's local
policy.
Public Key Infrastructure (PKI): The set of hardware, software,
personnel, policy, and procedures used by a CA to issue and manage
certificates.
Relying Party (RP): An application or entity that processes
certificates for the purpose of 1) verifying a digital signature,
2) authenticating another entity, or 3) establishing confidential
communications.
Revocation Signer Certificate: Refers collectively to either a CRL
Signer Certificate or OCSP Response Signer Certificate.
Target Certificate: The certificate that is to be validated by a
Relying Party. It is the "Certificate targeted for validation".
Although frequently this is the End Entity or a leaf node in the
PKI structure, this could also be a CA certificate if a CA
certificate is being validated. (e.g., This could be for the
purpose of building and validating a certification path for the
signer of a CRL.)
Trust (of public keys): In the scope of this document, a public key
is considered trustworthy if the certificate containing the public
key can be validated according to the procedures in [RFC3280].
Trust List: A list of trust anchors.
Trust Anchor: The combination of a trusted public key and the name of
the entity to which the corresponding private key belongs.
Trust Anchor Certificate: A self-signed certificate for a trust
anchor that is used in certification path processing.
User: An individual that is using a certificate processing system.
This document refers to some cases in which users may or may not
be prompted with information or requests, depending upon the
implementation of the certificate processing system.
1.4. Notation
This document makes use of a few common notations that are used in the diagrams and examples. The first is the arrow symbol (->) which represents the issuance of a certificate from one entity to another. For example, if entity H were to issue a certificate to entity K, this is denoted as H->K. Sometimes it is necessary to specify the subject and issuer of a given certificate. If entity H were to issue a certificate to entity K this can be denoted as K(H). These notations can be combined to denote complicated certification paths such as C(D)->B(C)->A(B).1.5. Overview of PKI Structures
When verifying [X.509] public key certificates, often the application performing the verification has no knowledge of the underlying Public Key Infrastructure (PKI) that issued the certificate. PKI structures can range from very simple, hierarchical structures to complex structures such as mesh architectures involving multiple bridges (see Section 1.5.4). These structures define the types of certification paths that might be built and validated by an application [MINHPKIS]. This section describes four common PKI structures.1.5.1. Hierarchical Structures
A hierarchical PKI, depicted in Figure 1, is one in which all of the end entities and relying parties use a single "Root CA" as their trust anchor. If the hierarchy has multiple levels, the Root CA certifies the public keys of intermediate CAs (also known as subordinate CAs). These CAs then certify end entities' (subscribers') public keys or may, in a large PKI, certify other CAs. In this architecture, certificates are issued in only one direction, and a CA never certifies another CA "superior" to itself. Typically, only one superior CA certifies each CA.
+---------+ +---| Root CA |---+ | +---------+ | | | | | v v +----+ +----+ +-----| CA | +-----| CA |------+ | +----+ | +----+ | | | | v v v +----+ +----+ +----+ +--| CA |-----+ | CA |-+ +---| CA |---+ | +----+ | +----+ | | +----+ | | | | | | | | | | | | | | | | | v v v v v v v v +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ Figure 1 - Sample Hierarchical PKI Certification path building in a hierarchical PKI is a straightforward process that simply requires the relying party to successively retrieve issuer certificates until a certificate that was issued by the trust anchor (the "Root CA" in Figure 1) is located. A widely used variation on the single-rooted hierarchical PKI is the inclusion of multiple CAs as trust anchors. (See Figure 2.) Here, end entity certificates are validated using the same approach as with any hierarchical PKI. The difference is that a certificate will be accepted if it can be verified back to any of the set of trust anchors. Popular web browsers use this approach, and are shipped with trust lists containing dozens to more than one hundred CAs. While this approach simplifies the implementation of a limited form of certificate verification, it also may introduce certain security vulnerabilities. For example, the user may have little or no idea of the policies or operating practices of the various trust anchors, and may not be aware of which root was used to verify a given certificate. Additionally, the compromise of any trusted CA private key or the insertion of a rogue CA certificate to the trust list may compromise the entire system. Conversely, if the trust list is properly managed and kept to a reasonable size, it can be an efficient solution to building and validating certification paths.
+-------------------------------------------------------+ | Trust List | | | | +---------+ +---------+ +---------+ | | +--| Root CA | | Root CA | | Root CA | | | | +---------+ +---------+ +---------+ | | | | | | | +--|------|----------------|---------------- |----------+ | | | | | | | | | | v | | | +----+ | | | +----| CA |---+ | | | | +----+ | | | | | | | | | v v v | | +----+ +----+ +----+ | | | CA |---+ | CA |-+ | CA |---+ | | +----+ | +----+ | +----+ | | | | | | | | | | | | | | | | | v v v v v v v v +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ Figure 2 - Multi-Rooted Hierarchical PKI1.5.2. Mesh Structures
In a typical mesh style PKI (depicted in Figure 3), each end entity trusts the CA that issued their own certificate(s). Thus, there is no 'Root CA' for the entire PKI. The CAs in this environment have peer relationships; they are neither superior nor subordinate to one another. In a mesh, CAs in the PKI cross-certify. That is, each CA issues a certificate to, and is issued a certificate by, peer CAs in the PKI. The figure depicts a mesh PKI that is fully cross-certified (sometimes called a full mesh). However, it is possible to architect and deploy a mesh PKI with a mixture of uni-directional and bi- directional cross-certifications (called a partial mesh). Partial meshes may also include CAs that are not cross-certified with other CAs in the mesh.
+---------------------------------+ | | +-----------+----------------------+ | | v v | | +-------+ +------+ | | +--->| CA B |<------------->| CA C |<--+ | | | +-------+ +------+ | | | | | ^ ^ | | | | | v | | | | | | | +----+ | | | | | | | | EE | +----+ +--------+ v | | | | +----+ | | +----+ | | | | | | | EE | | | v v v v +----+ v v +------+ +------+ +------+ | CA E |<----------->| CA A |<----------->| CA D | +------+ +------+ +------+ | ^ ^ ^ ^ | | | | | | | v | +------------------------------------+ | v +----+ | | +----+ | EE | | +------+ | | EE | +----+ +----------------| CA F |-----------------+ +----+ +------+ Figure 3 - Mesh PKI Certification path building in a mesh PKI is more complex than in a hierarchical PKI due to the likely existence of multiple paths between a relying party's trust anchor and the certificate to be verified. These multiple paths increase the potential for creating "loops", "dead ends", or invalid paths while building the certification path between a trust anchor and a target certificate. In addition, in cases where no valid path exists, the total number of paths traversed by the path-building software in order to conclude "no path exists" can grow exceedingly large. For example, if ignoring everything except the structure of the graph, the Mesh PKI figure above has 22 non-self issued CA certificates and a total of 5,092,429 certification paths between CA F and the EE issued by CA D without repeating any certificates.1.5.3. Bi-Lateral Cross-Certified Structures
PKIs can be connected via cross-certification to enable the relying parties of each to verify and accept certificates issued by the other PKI. If the PKIs are hierarchical, cross-certification will typically be accomplished by each Root CA issuing a certificate for the other PKI's Root CA. This results in a slightly more complex,
but still essentially hierarchical environment. If the PKIs are mesh style, then a CA within each PKI is selected, more or less arbitrarily, to establish the cross-certification, effectively creating a larger mesh PKI. Figure 4 depicts a hybrid situation resulting from a hierarchical PKI cross-certifying with a mesh PKI. PKI 1 and 2 cross-certificates +-------------------------------+ | | | v | +---------+ | +----| Root CA |---+ | | +---------+ | | | PKI 1 | | v v | +------+ +------+ v PKI 2 +-| CA |-+ | CA | +------+ | +------+ | +------+ +------->| CA |<-----+ | | | | | | +------+ | | | | | | | | | | v v v v v | | | | +----+ +----+ +----+ +----+ +----+ | v v | | EE | | EE | | EE | | EE | | EE | | +----+ +----+ | +----+ +----+ +----+ +----+ +----+ | | EE | | EE | | | +----+ +----+ | v v +------+ +------+ | CA |<-------------->| CA |------+ +------+ +------+ | | | | | | | | | | | v v v v v +----+ +----+ +----+ +----+ +----+ | EE | | EE | | EE | | EE | | EE | +----+ +----+ +----+ +----+ +----+ Figure 4 - Hybrid PKI In current implementations, this situation creates a concern that the applications used under the hierarchical PKIs will not have path building capabilities robust enough to handle this more complex certificate graph. As the number of cross-certified PKIs grows, the number of the relationships between them grows exponentially. Two principal concerns about cross-certification are the creation of unintended certification paths through transitive trust, and the dilution of assurance when a high-assurance PKI with restrictive operating policies is cross-certified with a PKI with less
restrictive policies. (Proper name constraints and certificate policies processing can help mitigate the problem of assurance dilution.)1.5.4. Bridge Structures
Another approach to the interconnection of PKIs is the use of a "bridge" certification authority (BCA). A BCA is a nexus to establish trust paths among multiple PKIs. The BCA cross-certifies with one CA in each participating PKI. Each PKI only cross-certifies with one other CA (i.e., the BCA), and the BCA cross-certifies only once with each participating PKI. As a result, the number of cross certified relationships in the bridged environment grows linearly with the number of PKIs whereas the number of cross-certified relationships in mesh architectures grows exponentially. However, when connecting PKIs in this way, the number and variety of PKIs involved results in a non-hierarchical environment, such as the one as depicted in Figure 5. (Note: as discussed in Section 2.3, non- hierarchical PKIs can be considered hierarchical, depending upon perspective.)
PKI 1 cross-certified with Bridge +-------------------------------+ | | v v +-----------+ +---------+ | Bridge CA | +---| Root CA |-----+ +-----------+ | +---------+ | ^ | PKI 1 | PKI 2 cross|cert with Bridge v v | +------+ +------+ v PKI 2 +-| CA |-+ | CA | +------+ | +------+ | +------+ +------->| CA |<-----+ | | | | | | +------+ | | | | | | | | | | v v v v v | | | | +----+ +----+ +----+ +----+ +----+ | v v | | EE | | EE | | EE | | EE | | EE | | +----+ +----+ | +----+ +----+ +----+ +----+ +----+ | | EE | | EE | | | +----+ +----+ | v v +------+ +------+ | CA |<-------------->| CA |------+ +------+ +------+ | | | | | | | | | | | v v v v v +----+ +----+ +----+ +----+ +----+ | EE | | EE | | EE | | EE | | EE | +----+ +----+ +----+ +----+ +----+ Figure 5 - Cross-Certification with a Bridge CA1.6. Bridge Structures and Certification Path Processing
Developers building certificate-enabled applications intended for widespread use throughout various sectors are encouraged to consider supporting a Bridge PKI structure because implementation of certification path processing functions to support a Bridge PKI structure requires support of all the PKI structures (e.g., hierarchical, mesh, hybrid) which the Bridge may connect. An application that can successfully build valid certification paths in all Bridge PKIs will therefore have implemented all of the processing logic required to support the less complicated PKI structures. Thus, if an application fully supports the Bridge PKI structure, it can be deployed in any standards-compliant PKI environment and will perform the required certification path processing properly.