< draft-ietf-pkix-certpathbuild-04.txt   draft-ietf-pkix-certpathbuild-05.txt >
PKIX Working Group M. Cooper PKIX Working Group M. Cooper
Internet Draft Orion Security Internet Draft Orion Security
Solutions Solutions
Document: draft-ietf-pkix-certpathbuild-04.txt Y. Dzambasow Document: draft-ietf-pkix-certpathbuild-05.txt Y. Dzambasow
Expires: December 2004 A&N Associates Expires: July 2005 A&N Associates
P. Hesse P. Hesse
Gemini Security Gemini Security
Solutions Solutions
S. Joseph S. Joseph
DigitalNet BAE Systems
R. Nicholas R. Nicholas
DigitalNet BAE Systems
June 2004 January 2005
Internet X.509 Public Key Infrastructure: Internet X.509 Public Key Infrastructure:
Certification Path Building Certification Path Building
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of [RFC 2026]. all provisions of Section 10 of [RFC 2026].
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
skipping to change at page 1, line 46 skipping to change at page 1, line 46
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
The draft is being discussed on the 'ietf-pkix' mailing list. To The draft is being discussed on the 'ietf-pkix' mailing list. To
subscribe, send a message to ietf-pkix-request@imc.org with the 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 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/. site for the mailing list at http://www.imc.org/ietf-pkix/.
Abstract IPR Statement
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
This document was written to provide guidance and recommendations to . Certification Path Building January 2005
developers building X.509 public-key certification paths within their
By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668.
Copyright Notice
Copyright (C) The Internet Society (2005). All Rights Reserved.
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 applications. By following the guidance and recommendations defined
in this document, an application developer is more likely to develop in this document, an application developer is more likely to develop
a robust X.509 certificate enabled application that can build valid a robust X.509 certificate enabled application that can build valid
certification paths across a wide range of PKI environments. certification paths across a wide range of PKI environments.
Table of Contents Table of Contents
1. Introduction...................................................4 1. Introduction...................................................4
1.1 Motivation.................................................4 1.1 Motivation.................................................4
1.2 Purpose....................................................4 1.2 Purpose....................................................5
1.3 Terminology................................................5 1.3 Terminology................................................5
1.4 Overview of PKI Structures.................................7 1.4 Notation...................................................8
1.4.1 Hierarchical Structures.............................8 1.5 Overview of PKI Structures.................................8
1.4.2 Mesh Structures.....................................9 1.5.1 Hierarchical Structures.............................9
1.4.3 Bi-lateral Cross-Certified Structures..............11 1.5.2 Mesh Structures....................................10
1.4.4 Bridge Structures..................................12 1.5.3 Bi-lateral Cross-Certified Structures..............12
1.5 Bridge Structures and Certification Path Processing.......13 1.5.4 Bridge Structures..................................13
2. Certification Path Building...................................13 1.6 Bridge Structures and Certification Path Processing.......14
2.1 Introduction to Certification Path Building...............13 2. Certification Path Building...................................14
2.2 Criteria for Path Building................................15 2.1 Introduction to Certification Path Building...............14
2.3 Path Building Algorithms..................................15 2.2 Criteria for Path Building................................16
2.4 How to Build a Certification Path.........................19 2.3 Path Building Algorithms..................................16
2.4.1 Certificate Repetition.............................21 2.4 How to Build a Certification Path.........................20
2.4.2 Introduction to Path Building Optimization.........22 2.4.1 Certificate Repetition.............................22
2.4.2 Introduction to Path Building Optimization.........23
2.5 Building Certification Paths for Revocation Signer 2.5 Building Certification Paths for Revocation Signer
Certificates..................................................27 Certificates..................................................28
2.6 Suggested Path Building Software Components...............28 2.6 Suggested Path Building Software Components...............29
2.7 Inputs to the Path Building Module........................30 2.7 Inputs to the Path Building Module........................31
2.7.1 Required Inputs....................................30 2.7.1 Required Inputs....................................31
2.7.2 Optional Inputs....................................31 2.7.2 Optional Inputs....................................32
3. Optimizing Path Building......................................32 3. Optimizing Path Building......................................33
3.1 Optimized Path Building...................................32 3.1 Optimized Path Building...................................33
3.2 Sorting vs. Elimination...................................35 3.2 Sorting vs. Elimination...................................35
3.3 Representing The Decision Tree Programmatically...........38 3.3 Representing The Decision Tree............................38
3.3.1 Node Representation For CA Entities................38
3.3.2 Using Nodes to Iterate Over All Paths..............38
3.4 Implementing Path Building Optimization...................41
3.5 Selected Methods for Sorting Certificates.................43
3.5.1 basicConstraints is Present and cA Equals True.....44
3.5.2 Recognized Signature Algorithms....................44
3.5.3 keyUsage is Correct................................44
3.5.4 Time (T) Falls within the Certificate Validity.....45
3.5.5 Certificate Was Previously Validated...............45
3.5.6 Previously Verified Signatures.....................46
3.5.7 Path Length Constraints............................46
3.5.8 Name Constraints...................................47
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
3.5.9 Certificate is Not Revoked.........................47 . Certification Path Building January 2005
3.5.10 Issuer Found in the Path Cache.....................48
3.5.11 Issuer Found in the Application Protocol...........48 3.3.1 Node Representation For CA Entities................39
3.5.12 Matching Key Identifiers (KIDs)....................49 3.3.2 Using Nodes to Iterate Over All Paths..............39
3.4 Implementing Path Building Optimization...................42
3.5 Selected Methods for Sorting Certificates.................43
3.5.1 basicConstraints is Present and cA Equals True.....44
3.5.2 Recognized Signature Algorithms....................45
3.5.3 keyUsage is Correct................................45
3.5.4 Time (T) Falls within the Certificate Validity.....46
3.5.5 Certificate Was Previously Validated...............46
3.5.6 Previously Verified Signatures.....................47
3.5.7 Path Length Constraints............................47
3.5.8 Name Constraints...................................48
3.5.9 Certificate is Not Revoked.........................48
3.5.10 Issuer Found in the Path Cache.....................49
3.5.11 Issuer Found in the Application Protocol...........49
3.5.12 Matching Key Identifiers (KIDs)....................50
3.5.13 Policy Processing..................................50 3.5.13 Policy Processing..................................50
3.5.14 Policies Intersect The Sought Policy Set...........50 3.5.14 Policies Intersect The Sought Policy Set...........51
3.5.15 Endpoint Distinguished Name Matching...............51 3.5.15 Endpoint Distinguished Name (DN) Matching..........52
3.5.16 Relative Distinguished Name (RDN) Matching.........51 3.5.16 Relative Distinguished Name (RDN) Matching.........52
3.5.17 Certificates are Retrieved from cACertificate......52 3.5.17 Certificates are Retrieved from cACertificate Directory
3.5.18 Consistent Public Key and Signature Algorithms.....52 Attribute.................................................53
3.5.19 Similar Issuer and Subject Names...................53 3.5.18 Consistent Public Key and Signature Algorithms.....53
3.5.20 Certificates in the Certification Cache............53 3.5.19 Similar Issuer and Subject Names...................54
3.5.21 Current CRL Found in Local Cache...................54 3.5.20 Certificates in the Certification Cache............54
3.5.21 Current CRL Found in Local Cache...................55
3.6 Certificate Sorting Methods For Revocation Signer 3.6 Certificate Sorting Methods For Revocation Signer
Certification Paths...........................................54 Certification Paths...........................................55
3.6.1 Identical Trust Anchors............................55 3.6.1 Identical Trust Anchors............................56
3.6.2 Endpoint Distinguished Name Matching (3.5.15)......55 3.6.2 Endpoint Distinguished Name (DN) Matching..........56
3.6.3 Relative Distinguished Name (RDN) Matching (3.5.16)56 3.6.3 Relative Distinguished Name (RDN) Matching.........57
3.6.4 Identical Intermediate Names.......................56 3.6.4 Identical Intermediate Names.......................57
4. Forward Policy Chaining.......................................57 4. Forward Policy Chaining.......................................57
4.1 Simple Intersection.......................................57 4.1 Simple Intersection.......................................58
4.2 Policy Mapping............................................58 4.2 Policy Mapping............................................59
4.3 Assigning Scores for Forward Policy Chaining..............59 4.3 Assigning Scores for Forward Policy Chaining..............60
5. Avoiding Path Building Errors.................................60 5. Avoiding Path Building Errors.................................61
5.1 Dead-ends.................................................60 5.1 Dead-ends.................................................61
5.2 Loop Detection............................................61 5.2 Loop Detection............................................62
5.3 Use of Key Identifiers....................................62 5.3 Use of Key Identifiers....................................62
5.4 Distinguished Name Encoding...............................62 5.4 Distinguished Name Encoding...............................63
6. Retrieval Methods.............................................63 6. Retrieval Methods.............................................63
6.1 Directories Using LDAP....................................63 6.1 Directories Using LDAP....................................64
6.2 Authority Information Access..............................65 6.2 Certificate Store Access via HTTP.........................66
6.3 Subject Information Access................................65 6.3 Authority Information Access..............................66
6.4 CRL Distribution Points...................................66 6.4 Subject Information Access................................66
6.5 Data Obtained via Application Protocol....................66 6.5 CRL Distribution Points...................................67
6.6 Proprietary Mechanisms....................................66 6.6 Data Obtained via Application Protocol....................68
7. Improving Retrieval Performance...............................67
7.1 Caching...................................................67
7.2 Retrieval Order...........................................68
7.3 Parallel Fetching and Prefetching.........................69
8. Security Considerations.......................................69
8.1 General Considerations for Building Any Certification Path69
8.2 Specific Considerations for Building Revocation Signer
Certification Paths...........................................70
Normative References.............................................72
Informative References...........................................73
Acknowledgments..................................................74
Author's Addresses...............................................74
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
. Certification Path Building January 2005
6.7 Proprietary Mechanisms....................................68
7. Improving Retrieval Performance...............................68
7.1 Caching...................................................68
7.2 Retrieval Order...........................................69
7.3 Parallel Fetching and Prefetching.........................70
8. Security Considerations.......................................70
8.1 General Considerations for Building A Certification Path..70
8.2 Specific Considerations for Building Revocation Signer
Certification Paths...........................................72
9. IANA Considerations...........................................74
Normative References.............................................74
Informative References...........................................74
Acknowledgments..................................................75
Author's Addresses...............................................76
Full Copyright Statement.........................................76
1. Introduction 1. Introduction
[X.509] digital certificates have become an accepted method for [X.509] public key certificates have become an accepted method for
securely binding the identity of an individual or device to a public securely binding the identity of an individual or device to a public
key, for the purpose of supporting public key cryptographic key, for the purpose of supporting public key cryptographic
operations such as digital signature verification, and public key- operations such as digital signature verification, and public key-
based encryption and decryption. However, prior to using the public based encryption and decryption. However, prior to using the public
key contained in a digital certificate, an application has to first key contained in a certificate, an application has to first determine
determine the authenticity of that digital certificate, and the authenticity of that certificate, and specifically, the validity
specifically, the validity of all the certificates leading to a of all the certificates leading to a trusted public key, called a
trusted root certificate. It is through validating this trust anchor. It is through validating this certification path that
certification path that the assertion of the binding made between the the assertion of the binding made between the identity and the public
identity and the public key in each of the digital certificate can be key in each of the certificate can be traced back to a single trust
traced back to a single point of trust. anchor.
The process by which an application determines this authenticity of a The process by which an application determines this authenticity of a
digital certificate is called certification path processing. certificate is called certification path processing. Certification
Certification path processing establishes a chain of trust between a path processing establishes a chain of trust between a trust anchor
trusted public key and a digital certificate. This chain of trust is and a certificate. This chain of trust is composed of a series of
composed of a series of digital certificates known as a certification certificates known as a certification path. A certification path
path. A certification path begins with a certificate whose signature begins with a certificate whose signature can be verified using a
can be verified using a trusted public key and ends with the target trust anchor and ends with the target certificate. Path processing
digital certificate. Path processing entails building and validating entails building and validating the certification path to determine
the certification path to determine the degree of trust to place in whether a target certificate is appropriate for use in a particular
the target digital certificate(s). See section 3.2 of [RFC 3280] for application context. See section 3.2 of [RFC 3280] for more
more information on certification paths and trust. information on certification paths and trust.
1.1 Motivation 1.1 Motivation
Many other documents (such as [RFC 3280]) cover certification path Many other documents (such as [RFC 3280]) cover certification path
validation requirements and procedures in detail but do not discuss validation requirements and procedures in detail but do not discuss
certification path building because how the path is found does not certification path building because the means used to find the path
affect its validation. This document therefore is an effort to
provide useful guidance for developers of certification path building Cooper, Dzambasow,
implementations. Hesse, Joseph,
. Certification Path Building January 2005
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 Additionally, the need to develop complex certification paths is
becoming greater. Many PKIs are now using complex structures (see becoming greater. Many PKIs are now using complex structures (see
section 1.4) rather than simple hierarchies. Additionally, some section 1.5) rather than simple hierarchies. Additionally, some
enterprises are gradually moving away from trust lists filled with enterprises are gradually moving away from trust lists filled with
many trust anchors, and toward an infrastructure with one trust many trust anchors, and toward an infrastructure with one trust
anchor and many cross-certified relationships. This document anchor and many cross-certified relationships. This document
provides information that will be helpful in developing certification provides information that will be helpful in developing certification
paths in these more complicated situations. paths in these more complicated situations.
1.2 Purpose 1.2 Purpose
Cooper, Dzambasow,
Hesse, Joseph,
This document provides information and guidance for certification This document provides information and guidance for certification
path building. There are no requirements or protocol specifications path building. There are no requirements or protocol specifications
in this document. This document provides many options for performing in this document. This document provides many options for performing
certification path building, as opposed to one particular way to best certification path building, as opposed to one particular way to best
perform certification path building. This document draws upon the perform certification path building. This document draws upon the
authors' experience with existing complex certification paths to authors' experience with existing complex certification paths to
offer insights and recommendations to developers integrating support offer insights and recommendations to developers integrating support
for [X.509] digital certificates into their applications. for [X.509] certificates into their applications.
In addition, this document suggests using an effective general In addition, this document suggests using an effective general
approach to path building that involves a depth first tree traversal. approach to path building that involves a depth first tree traversal.
While the authors believe this approach offers the balance of While the authors believe this approach offers the balance of
simplicity in design with very effective and infrastructure neutral simplicity in design with very effective and infrastructure neutral
path building capabilities, the algorithm is no more than a suggested path building capabilities, the algorithm is no more than a suggested
approach. Other approaches (e.g., breadth first tree traversals) approach. Other approaches (e.g., breadth first tree traversals)
exist and may be shown to be more effective under certain conditions. exist and may be shown to be more effective under certain conditions.
Certification path validation is described in detail in both [X.509] Certification path validation is described in detail in both [X.509]
and [RFC 3280] and is not repeated in this document. and [RFC 3280] 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 [RFC 3820].
1.3 Terminology 1.3 Terminology
Terms used throughout this document will be used in the following Terms used throughout this document will be used in the following
ways: ways:
Building in the Forward direction: The process of building a Building in the Forward direction: The process of building a
certification path from the target certificate to a trust anchor. certification path from the target certificate to a trust anchor.
'Forward' is the former name of the crossCertificatePair element 'Forward' is the former name of the crossCertificatePair element
'issuedToThisCA'. 'issuedToThisCA'.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Building in the Reverse direction: The process of building a Building in the Reverse direction: The process of building a
certification path from a trust anchor to the target certificate. certification path from a trust anchor to the target certificate.
'Reverse' is the former name of the crossCertificatePair element 'Reverse' is the former name of the crossCertificatePair element
'issuedByThisCA'. 'issuedByThisCA'.
Certificate: A digital binding that cannot be counterfeited between Certificate: A digital binding that cannot be counterfeited between
a named entity and a public key. a named entity and a public key.
Certificate Graph: A graph that represents the entire PKI (or all Certificate Graph: A graph that represents the entire PKI (or all
cross-certified PKIs) in which all named entities are viewed as nodes cross-certified PKIs) in which all named entities are viewed as nodes
and all certificates are viewed as lines between nodes. and all certificates are viewed as arcs between nodes.
Certificate Processing System: An application or device that Certificate Processing System: An application or device that
performs the functions of certification path building and performs the functions of certification path building and
certification path validation. certification path validation.
Certification Authority (CA): An entity that issues and manages Certification Authority (CA): An entity that issues and manages
digital certificates. certificates.
Cooper, Dzambasow,
Hesse, Joseph,
Certification Path: An ordered list of certificates starting with a Certification Path: An ordered list of certificates starting with a
certificate signed by a trusted public key and ending with the target certificate signed by a trust anchor and ending with the target
certificate. certificate.
Certification Path Building: The process used to assemble the Certification Path Building: The process used to assemble the
certification path between the trust anchor and the target certification path between the trust anchor and the target
certificate. certificate.
Certification Path Validation: The process that verifies the binding Certification Path Validation: The process that verifies the binding
between the subject and the subject-public-key defined in the target between the subject and the subject-public-key defined in the target
certificate, using a trusted public key and set of known constraints. 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 CRL Signer Certificate: The specific certificate that may be used for
verifying the signature on a CRL issued by, or on behalf of, a verifying the signature on a CRL issued by, or on behalf of, a
specific Certification Authority. specific CA.
Cross-Certificate: A certificate issued by one CA to another CA for Cross-Certificate: A certificate issued by one CA to another CA for
the purpose of establishing a trust relationship between the two CAs. the purpose of establishing a trust relationship between the two CAs.
Cross-Certification: The act of issuing cross-certificates. Cross-Certification: The act of issuing cross-certificates.
Decision Tree: When the path building software has multiple Decision Tree: When the path building software has multiple
certificates to choose from, and must make a decision, the collection certificates to choose from, and must make a decision, the collection
of possible choices is called a decision tree. of possible choices is called a decision tree.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Directory: Generally used to refer an LDAP accessible repository for Directory: Generally used to refer an LDAP accessible repository for
certificates and PKI information. The term may also be used certificates and PKI information. The term may also be used
generically to refer to any certificate storing repository. generically to refer to any certificate storing repository.
End Entity: The holder of a private key and corresponding End Entity: The holder of a private key and corresponding
certificate, and whose identity is defined as the Subject of the certificate, and whose identity is defined as the Subject of the
certificate. Human end entities are often called "subscribers". certificate. Human end entities are often called "subscribers".
Is-revocation-signer indicator: A Boolean flag furnished to the path Is-revocation-signer indicator: A boolean flag furnished to the path
building software. If set, this indicates that the Target Certificate building software. If set, this indicates that the target certificate
is a Revocation Signer Certificate for a specific Certification is a Revocation Signer certificate for a specific CA. For example, if
Authority. For example, if building a certification path for an building a certification path for an indirect CRL Signer certificate,
indirect CRL Signer Certificate, this flag would be set. this flag would be set.
Local PKI: The set of PKI components and data (certificates, Local PKI: The set of PKI components and data (certificates,
directories, CRLs, etc.) that are created and used by the certificate directories, CRLs, etc.) that are created and used by the certificate
using organization. In general, this concept refers to the using organization. In general, this concept refers to the
components that are in close proximity to the certificate using components that are in close proximity to the certificate using
application. The assumption is that the local data is more easily application. The assumption is that the local data is more easily
accessible and/or inexpensive to retrieve than non-local PKI data. accessible and/or inexpensive to retrieve than non-local PKI data.
Local Realm: See Local PKI. Local Realm: See Local PKI.
Cooper, Dzambasow, Node (in a certificate graph): The collection of certificates having
Hesse, Joseph,
Node (In a certificate graph): The collection of certificates having
identical subject distinguished names. 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 OCSP Response Signer Certificate: The specific certificate that may
be used for verifying the signature on an OCSP response. This be used for verifying the signature on an OCSP response. This
response may be provided by the Certificate Authority, on behalf of response may be provided by the CA, on behalf of the CA, or by a
the Certificate Authority, or by a different signer as determined by different signer as determined by the Relying Party's local policy.
the Relying Party's local policy.
Public Key Infrastructure (PKI): The set of hardware, software, Public Key Infrastructure (PKI): The set of hardware, software,
personnel, policy, and procedures used by a Certification Authority personnel, policy, and procedures used by a CA to issue and manage
to issue and manage certificates. certificates.
Relying Party (RP): An application or entity that processes Relying Party (RP): An application or entity that processes
certificates for the purpose of 1) verifying a digital signature, 2) certificates for the purpose of 1) verifying a digital signature, 2)
authenticating another entity, or 3) establishing confidential authenticating another entity, or 3) establishing confidential
communications. communications.
Revocation Signer Certificate: Refers collectively to either a CRL Revocation Signer Certificate: Refers collectively to either a CRL
Signer Certificate or OCSP Response Signer Certificate. Signer Certificate or OCSP Response Signer Certificate.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Target Certificate: The certificate that is to be validated by a Target Certificate: The certificate that is to be validated by a
relying party. It is the "Certificate targeted for validation." relying party. It is the "Certificate targeted for validation."
Although frequently this is the End Entity or a leaf node in the PKI 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 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 being validated. (e.g. This could be for the purpose of building and
validating a certification path for the signer of a CRL.) validating a certification path for the signer of a CRL.)
Trust (of public keys): In the scope of this document, a public key Trust (of public keys): In the scope of this document, a public key
is considered trustworthy if the certificate containing the public is considered trustworthy if the certificate containing the public
key can be validated according to the procedures in [RFC 3280]. key can be validated according to the procedures in [RFC 3280].
Trust List: A list of certificates or combinations of public keys and Trust List: A list of trust anchors.
names that are considered trustworthy.
Trust Anchor: The combination of a trusted public key and the name of Trust Anchor: The combination of a trusted public key and the name of
the entity to which the corresponding private key belongs. the entity to which the corresponding private key belongs.
Trusted Root Certificate: A certificate issued to a trust anchor Trust Anchor Certificate: A self-signed certificate for a trust
which is used in certification path processing. anchor which is used in certification path processing.
User: An individual that is using a certificate processing system. User: An individual that is using a certificate processing system.
This document refers to some cases in which users may or may not be This document refers to some cases in which users may or may not be
prompted with information or requests, depending upon the prompted with information or requests, depending upon the
implementation of the certificate processing system. implementation of the certificate processing system.
1.4 Overview of PKI Structures 1.4 Notation
This document makes use of a few common notations which 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
Cooper, Dzambasow,
Hesse, Joseph,
When verifying [X.509] public key certificates, often the application When verifying [X.509] public key certificates, often the application
performing the verification has no knowledge of the underlying Public performing the verification has no knowledge of the underlying Public
Key Infrastructure (PKI) that issued the certificate. PKI structures Key Infrastructure (PKI) that issued the certificate. PKI structures
can range from very simple, hierarchical structures to complex can range from very simple, hierarchical structures to complex
structures such as multi-bridged mesh architectures. These structures such as mesh architectures involving multiple bridges (see
structures define the types of certification paths that might be section 1.5.4). These structures define the types of certification
built and validated by an application. This section describes four
common PKI structures.
1.4.1 Hierarchical Structures Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
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 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 end entities and relying parties use a single "Root CA" as their
hierarchy has multiple levels, the root CA certifies the public keys trust anchor. If the hierarchy has multiple levels, the Root CA
of intermediate CAs (also known as subordinate CAs). These CAs then certifies the public keys of intermediate CAs (also known as
certify end entities' (subscribers') public keys or may, in a large subordinate CAs). These CAs then certify end entities'
PKI, certify other CAs. In this architecture, certificates are (subscribers') public keys or may, in a large PKI, certify other CAs.
issued in only one direction, and a CA never certifies another CA In this architecture, certificates are issued in only one direction,
"superior" to itself. Typically, only one superior CA certifies each and a CA never certifies another CA "superior" to itself. Typically,
CA. only one superior CA certifies each CA.
+---------+ +---------+
+---| root CA |---+ +---| Root CA |---+
| +---------+ | | +---------+ |
| | | |
| | | |
v v v v
+----+ +----+ +----+ +----+
+-----| CA | +-----| CA |------+ +-----| CA | +-----| CA |------+
| +----+ | +----+ | | +----+ | +----+ |
| | | | | |
v v v v v v
+----+ +----+ +----+ +----+ +----+ +----+
skipping to change at page 8, line 51 skipping to change at page 9, line 47
v v v v v v v v v v v v v v v v
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
Figure 1 - Sample Hierarchical PKI Figure 1 - Sample Hierarchical PKI
Certification path building in a hierarchical PKI is a Certification path building in a hierarchical PKI is a
straightforward process that simply requires the relying party to straightforward process that simply requires the relying party to
successively retrieve issuer certificates until a certificate that successively retrieve issuer certificates until a certificate that
was issued by the trust anchor is located. was issued by the trust anchor (the "Root CA" in Figure 1) is
located.
Cooper, Dzambasow,
Hesse, Joseph,
A widely used variation on the single-rooted hierarchical PKI is the A widely used variation on the single-rooted hierarchical PKI is the
inclusion of multiple CAs as trust anchors. [See Figure 2.] Here, inclusion of multiple CAs as trust anchors. [See Figure 2.] Here,
end entity certificates are validated using the same approach as with end entity certificates are validated using the same approach as with
any hierarchical PKI. The difference is that a certificate will be any hierarchical PKI. The difference is that a certificate will be
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
accepted if it can be verified back to any of the set of trust accepted if it can be verified back to any of the set of trust
anchors. Popular web browsers use this approach, and are shipped anchors. Popular web browsers use this approach, and are shipped
with trust lists containing dozens to more than one hundred CAs. with trust lists containing dozens to more than one hundred CAs.
While this approach simplifies the implementation of a limited form While this approach simplifies the implementation of a limited form
of certificate verification, it also may introduce certain security of certificate verification, it also may introduce certain security
vulnerabilities. For example, the user may have little or no idea of vulnerabilities. For example, the user may have little or no idea of
the policies or operating practices of the various trust anchors, and the policies or operating practices of the various trust anchors, and
may not be aware of which root was used to verify a given may not be aware of which root was used to verify a given
certificate. Additionally, the compromise of any trusted certificate certificate. Additionally, the compromise of any trusted CA private
may compromise the entire system. Conversely, if the trust list is 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 properly managed and kept to a reasonable size, it can be an
efficient solution to building and validating certification paths. efficient solution to building and validating certification paths.
+-------------------------------------------------------+ +-------------------------------------------------------+
| Trust List | | Trust List |
| | | |
| +---------+ +---------+ +---------+ | | +---------+ +---------+ +---------+ |
| +--| Root CA | | Root CA | | Root CA | | | +--| Root CA | | Root CA | | Root CA | |
| | +---------+ +---------+ +---------+ | | | +---------+ +---------+ +---------+ |
| | | | | | | | | | | |
skipping to change at page 9, line 49 skipping to change at page 10, line 48
| | +----+ | +----+ | +----+ | | | +----+ | +----+ | +----+ |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
v v v v v v v v v v v v v v v v
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
Figure 2 - Multi-Rooted Hierarchical PKI Figure 2 - Multi-Rooted Hierarchical PKI
1.4.2 Mesh Structures 1.5.2 Mesh Structures
Cooper, Dzambasow,
Hesse, Joseph,
In a typical mesh style PKI (depicted in Figure 3), each end entity 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 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 no 'Root CA' for the entire PKI. The CAs in this environment have
peer relationships; they are neither superior nor subordinate to one peer relationships; they are neither superior nor subordinate to one
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
another. In a mesh, CAs in the PKI cross-certify. That is, each CA 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 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 the PKI. The figure depicts a mesh PKI that is fully cross-certified
(sometimes called a full mesh); however it is possible to architect (sometimes called a full mesh); however it is possible to architect
and deploy a mesh PKI with a mixture of unidirectional and bi- and deploy a mesh PKI with a mixture of unidirectional and bi-
directional cross-certifications (called a partial mesh). Partial directional cross-certifications (called a partial mesh). Partial
meshes may also include CAs that are not cross-certified with other meshes may also include CAs that are not cross-certified with other
CAs in the mesh. CAs in the mesh.
+---------------------------------+ +---------------------------------+
skipping to change at page 10, line 49 skipping to change at page 11, line 47
+----+ +----------------| CA F |-----------------+ +----+ +----+ +----------------| CA F |-----------------+ +----+
+------+ +------+
Figure 3 - Mesh PKI Figure 3 - Mesh PKI
Certification path building in a mesh PKI is more complex than in a Certification path building in a mesh PKI is more complex than in a
hierarchical PKI due to the likely existence of multiple paths hierarchical PKI due to the likely existence of multiple paths
between a relying party's trust anchor and the certificate to be between a relying party's trust anchor and the certificate to be
verified. These multiple paths increase the potential for creating verified. These multiple paths increase the potential for creating
"loops", "dead ends", or invalid paths while building the "loops", "dead ends", or invalid paths while building the
certification path between a trusted root certificate and a target certification path between a trust anchor and a target certificate.
certificate. In addition, in cases where no valid path exists, the In addition, in cases where no valid path exists, the total number of
total number of paths traversed by the path building software in 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
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
order to conclude "no path exists" can grow exceedingly large. For . Certification Path Building January 2005
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 CA F and the EE issued by D
without repeating any certificates.
1.4.3 Bi-lateral Cross-Certified Structures 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 PKIs can be connected via cross-certification to enable the relying
parties of each to verify and accept certificates issued by the other parties of each to verify and accept certificates issued by the other
PKI. If the PKIs are hierarchical, cross-certification will PKI. If the PKIs are hierarchical, cross-certification will
typically be accomplished by each root CA issuing a certificate for typically be accomplished by each Root CA issuing a certificate for
the other PKI's root CA. This results in a slightly more complex, the other PKI's Root CA. This results in a slightly more complex,
but still essentially hierarchical environment. If the PKIs are mesh but still essentially hierarchical environment. If the PKIs are mesh
style, then a CA within each PKI is selected, more or less style, then a CA within each PKI is selected, more or less
arbitrarily, to establish the cross-certification, effectively arbitrarily, to establish the cross-certification, effectively
creating a larger mesh PKI. Figure 4 depicts a hybrid situation creating a larger mesh PKI. Figure 4 depicts a hybrid situation
resulting from a hierarchical PKI cross-certifying with a mesh PKI. resulting from a hierarchical PKI cross-certifying with a mesh PKI.
PKI 1 and 2 cross certificates PKI 1 and 2 cross certificates
+-------------------------------+ +-------------------------------+
| | | |
| v | v
| +------+ | +---------+
| +-----| CA |-----+ | +----| Root CA |---+
| | +------+ | | | +---------+ |
| | PKI 1 Root | | | PKI 1 |
| v v | v v
| +------+ +------+ | +------+ +------+
v PKI 2 Root +-| CA |-+ | CA | v PKI 2 +-| CA |-+ | CA |
+------+ | +------+ | +------+ +------+ | +------+ | +------+
+------->| CA |<-----+ | | | | | +------->| CA |<-----+ | | | | |
| +------+ | | | | | | | +------+ | | | | | |
| | | | v v v v v | | | | v v v v v
| | | | +----+ +----+ +----+ +----+ +----+ | | | | +----+ +----+ +----+ +----+ +----+
| v v | | EE | | EE | | EE | | EE | | EE | | v v | | EE | | EE | | EE | | EE | | EE |
| +----+ +----+ | +----+ +----+ +----+ +----+ +----+ | +----+ +----+ | +----+ +----+ +----+ +----+ +----+
| | EE | | EE | | | | EE | | EE | |
| +----+ +----+ | | +----+ +----+ |
v v v v
+------+ +------+ +------+ +------+
| CA |<-------------->| CA |------+ | CA |<-------------->| CA |------+
+------+ +------+ | +------+ +------+ |
| | | | | | | | | |
| | | | | | | | | |
v v v v v v v v v v
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
Cooper, Dzambasow,
Hesse, Joseph,
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
Figure 4 - Hybrid PKI Figure 4 - Hybrid PKI
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
In current implementations, this situation creates a concern that the In current implementations, this situation creates a concern that the
applications used under the hierarchical PKIs will not have path applications used under the hierarchical PKIs will not have path
building capabilities robust enough to handle this more complex building capabilities robust enough to handle this more complex
certificate graph. As the number of cross-certified PKIs grows, the certificate graph. As the number of cross-certified PKIs grows, the
number of the relationships between them grows exponentially. Two number of the relationships between them grows exponentially. Two
principal concerns about cross-certification are the creation of principal concerns about cross-certification are the creation of
unintended certification paths through transitive trust, and the unintended certification paths through transitive trust, and the
dilution of assurance when a high-assurance PKI with restrictive dilution of assurance when a high-assurance PKI with restrictive
operating policies is cross-certified with a PKI with less operating policies is cross-certified with a PKI with less
restrictive policies. (Proper name constraints and certificate restrictive policies. (Proper name constraints and certificate
policies processing can help mitigate the problem of assurance policies processing can help mitigate the problem of assurance
dilution.) dilution.)
1.4.4 Bridge Structures 1.5.4 Bridge Structures
Another approach to the interconnection of PKIs is the use of a Another approach to the interconnection of PKIs is the use of a
"bridge" certification authority (BCA). A BCA is a nexus to "bridge" certification authority (BCA). A BCA is a nexus to
establish trust paths among multiple PKIs. The BCA cross-certifies establish trust paths among multiple PKIs. The BCA cross-certifies
with one CA (known as a "principal" CA [PCA]) in each participating with one CA in each participating PKI. Each PKI only cross-certifies
PKI. Each PKI only cross-certifies with one other CA (i.e., the with one other CA (i.e., the BCA), and the BCA cross-certifies only
BCA), and the BCA cross-certifies only once with each participating once with each participating PKI. As a result, the number of cross
PKI. As a result, the number of cross certified relationships in the certified relationships in the bridged environment grows linearly
bridged environment grows linearly with the number of PKIs whereas with the number of PKIs whereas the number of cross certified
the number of cross certified relationships in mesh architectures relationships in mesh architectures grows exponentially. However,
grows exponentially. However, when connecting PKIs in this way, the when connecting PKIs in this way, the number and variety of PKIs
number and variety of PKIs involved results in a non-hierarchical involved results in a non-hierarchical environment, such as the one
environment, such as the one as depicted in Figure 5. (Note: as as depicted in Figure 5. (Note: as discussed in section 2.3, non-
discussed in section 2.3, non-hierarchical PKIs can be considered hierarchical PKIs can be considered hierarchical, depending upon
hierarchical, depending upon perspective.) perspective.)
PKI 1 cross certified with Bridge PKI 1 cross certified with Bridge
+-------------------------------+ +-------------------------------+
| | | |
v v v v
+-----------+ +------+ +-----------+ +---------+
| Bridge CA | +-----| CA |-----+ | Bridge CA | +---| Root CA |-----+
+-----------+ | +------+ | +-----------+ | +---------+ |
^ | PKI 1 Root | ^ | PKI 1 |
PKI 2 cross|cert with Bridge v v PKI 2 cross|cert with Bridge v v
| +------+ +------+ | +------+ +------+
v PKI 2 Root +-| CA |-+ | CA | v PKI 2 +-| CA |-+ | CA |
+------+ | +------+ | +------+ +------+ | +------+ | +------+
+------->| CA |<-----+ | | | | | +------->| CA |<-----+ | | | | |
Cooper, Dzambasow,
Hesse, Joseph,
| +------+ | | | | | | | +------+ | | | | | |
| | | | v v v v v | | | | v v v v v
| | | | +----+ +----+ +----+ +----+ +----+ | | | | +----+ +----+ +----+ +----+ +----+
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
| v v | | EE | | EE | | EE | | EE | | EE | | v v | | EE | | EE | | EE | | EE | | EE |
| +----+ +----+ | +----+ +----+ +----+ +----+ +----+ | +----+ +----+ | +----+ +----+ +----+ +----+ +----+
| | EE | | EE | | | | EE | | EE | |
| +----+ +----+ | | +----+ +----+ |
v v v v
+------+ +------+ +------+ +------+
| CA |<-------------->| CA |------+ | CA |<-------------->| CA |------+
+------+ +------+ | +------+ +------+ |
| | | | | | | | | |
| | | | | | | | | |
v v v v v v v v v v
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
Figure 5 - Cross-Certification with a Bridge CA Figure 5 - Cross-Certification with a Bridge CA
1.5 Bridge Structures and Certification Path Processing 1.6 Bridge Structures and Certification Path Processing
Developers building certificate-enabled applications intended for Developers building certificate-enabled applications intended for
widespread use throughout various sectors are encouraged to consider widespread use throughout various sectors are encouraged to consider
supporting a Bridge PKI structure because implementation of supporting a Bridge PKI structure because implementation of
certification path processing functions to support a Bridge PKI certification path processing functions to support a Bridge PKI
structure requires support of all the PKI structures which the Bridge structure requires support of all the PKI structures (e.g.,
may connect. (e.g., hierarchical, mesh, hybrid) An application that hierarchical, mesh, hybrid) which the Bridge may connect. An
can successfully build valid certification paths in all Bridge PKIs application that can successfully build valid certification paths in
will therefore have implemented all of the processing logic required all Bridge PKIs will therefore have implemented all of the processing
to support the less complicated PKI structures. Thus, if an logic required to support the less complicated PKI structures.
application fully supports the Bridge PKI structure, it can be Thus, if an application fully supports the Bridge PKI structure, it
deployed in any standards compliant PKI environment and will perform can be deployed in any standards compliant PKI environment and will
the required certification path processing properly. perform the required certification path processing properly.
2. Certification Path Building 2. Certification Path Building
Certification path building is the process by which the certificate Certification path building is the process by which the certificate
processing system obtains the certification path between a trusted processing system obtains the certification path between a trust
public key and the target certificate. Different implementations can anchor and the target certificate. Different implementations can
build the certification path in different ways; therefore, it is not build the certification path in different ways; therefore, it is not
the intent of this paper to recommend a single "best" way to perform the intent of this paper to recommend a single "best" way to perform
this function. Rather, guidance is provided on the technical issues this function. Rather, guidance is provided on the technical issues
that surround the path building process, and on the capabilities path that surround the path building process, and on the capabilities path
building implementations need in order to build certification paths building implementations need in order to build certification paths
successfully, irrespective of PKI structures. successfully, irrespective of PKI structures.
2.1 Introduction to Certification Path Building 2.1 Introduction to Certification Path Building
Cooper, Dzambasow,
Hesse, Joseph,
A certification path is an ordered list of certificates starting with A certification path is an ordered list of certificates starting with
a certificate that can be validated by one of the relying party's a certificate that can be validated by one of the relying party's
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
trust anchors, and ending with the certificate to be validated. (The trust anchors, and ending with the certificate to be validated. (The
certificate to be validated is referred to as the "target certificate to be validated is referred to as the "target
certificate" throughout this document.) Though not required, as a certificate" throughout this document.) Though not required, as a
matter of convenience these trust anchors are typically stored in matter of convenience these trust anchors are typically stored in
self signed certificates which are frequently called trusted root trust anchor certificates. The intermediate certificates that
certificates. The intermediate certificates that comprise the comprise the certification path may be retrieved by any means
certification path may be retrieved by any means available to the available to the validating application. These sources may include
validating application. These sources may include LDAP, HTTP, SQL, a LDAP, HTTP, SQL, a local cache or certificate store, or as part of
local cache or certificate store, or as part of the security protocol the security protocol itself as is common practice with signed S/MIME
itself as is common practice with signed S/MIME messages and SSL/TLS messages and SSL/TLS sessions.
sessions.
Figure 6 shows an example of a certification path. In this figure, Figure 6 shows an example of a certification path. In this figure,
the horizontal arrows represent certificates, and the notation B(A) the horizontal arrows represent certificates, and the notation B(A)
signifies a certificate issued to B, signed by A. signifies a certificate issued to B, signed by A.
+---------+ +-----+ +-----+ +-----+ +--------+ +---------+ +-----+ +-----+ +-----+ +--------+
| Trust |----->| CA |---->| CA |---->| CA |---->| Target | | Trust |----->| CA |---->| CA |---->| CA |---->| Target |
| Anchor | | | A | | | B | | | C | | | EE | | Anchor | : | A | : | B | : | C | : | EE |
+---------+ | +-----+ | +-----+ | +-----+ | +--------+ +---------+ : +-----+ : +-----+ : +-----+ : +--------+
| | | | : : : :
| | | | : : : :
v v v v
Cert 1 Cert 2 Cert 3 Cert 4 Cert 1 Cert 2 Cert 3 Cert 4
A(Trust Anchor) B(A) C(B) Target(C) A(Trust Anchor) B(A) C(B) Target(C)
Figure 6 - Example Certification Path Figure 6 - Example Certification Path
Unlike certification path validation, certification path building is Unlike certification path validation, certification path building is
not addressed by the standards that define the semantics and not addressed by the standards that define the semantics and
structure of a PKI. This is because the validation of a structure of a PKI. This is because the validation of a
certification path is unaffected by the method in which the certification path is unaffected by the method in which the
certification path was built. However, the ability to build a valid certification path was built. However, the ability to build a valid
skipping to change at page 14, line 50 skipping to change at page 15, line 48
rely on a PKI. Absent valid certification paths, certificates cannot rely on a PKI. Absent valid certification paths, certificates cannot
be validated according to [RFC 3280] and therefore cannot be trusted. 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 Thus the ability to build a path is every bit as important as the
ability to properly validate them. ability to properly validate them.
There are many issues that can complicate the path building process. There are many issues that can complicate the path building process.
For example, building a path through a cross-certified environment For example, building a path through a cross-certified environment
could require the path-building module to traverse multiple PKI could require the path-building module to traverse multiple PKI
domains spanning multiple directories, using multiple algorithms, and domains spanning multiple directories, using multiple algorithms, and
employing varying key lengths. A path-building client may also, for employing varying key lengths. A path-building client may also, for
example, need to manage a number of trusted root certificates, example, need to manage a number of trust anchors, partially
populated directory entries (e.g., missing issuedToThisCA entries in
the crossCertificatePair attribute.), parsing of certain certificate
extensions (e.g., authorityInformationAccess) and directory
attributes (e.g., crossCertificatePair), and error handling such as
loop detection.
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
partially populated directory entries (e.g., missing issuedToThisCA . Certification Path Building January 2005
entries in the crossCertificatePair attribute.), parsing of certain
certificate extensions (e.g., authorityInformationAccess) and
directory attributes (e.g., crossCertificatePair), and error handling
such as loop detection.
In addition, a developer has to decide whether to build paths from a In addition, a developer has to decide whether to build paths from a
trust anchor (the reverse direction) to the target certificate or trust anchor (the reverse direction) to the target certificate or
from the target certificate (the forward direction) to a trust from the target certificate (the forward direction) to a trust
anchor. Some implementations may even decide to use both. The choice anchor. Some implementations may even decide to use both. The choice
a developer makes should be dependent on the environment and the a developer makes should be dependent on the environment and the
underlying PKI for that environment. More information on making this underlying PKI for that environment. More information on making this
choice can be found in section 2.3. choice can be found in section 2.3.
2.2 Criteria for Path Building 2.2 Criteria for Path Building
skipping to change at page 15, line 52 skipping to change at page 16, line 48
certificate, this is most likely the 'right' path. If other paths certificate, this is most likely the 'right' path. If other paths
are developed which are invalid for multiple obscure reasons, this are developed which are invalid for multiple obscure reasons, this
provides little useful information. provides little useful information.
The algorithms and mechanisms discussed henceforth are chosen because The algorithms and mechanisms discussed henceforth are chosen because
they are considered by the authors to be good methods to meet the they are considered by the authors to be good methods to meet the
above criteria. above criteria.
2.3 Path Building Algorithms 2.3 Path Building Algorithms
Cooper, Dzambasow,
Hesse, Joseph,
It is intuitive for people familiar with the Bridge CA concept or It is intuitive for people familiar with the Bridge CA concept or
mesh type PKIs to view path building as traversing a complex graph. mesh type PKIs to view path building as traversing a complex graph.
However, from the simplest viewpoint, writing a path-building module However, from the simplest viewpoint, writing a path-building module
can be nothing more than traversal of a spanning tree, even in a very can be nothing more than traversal of a spanning tree, even in a very
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
complex cross-certified environment. Complex environments as well as complex cross-certified environment. Complex environments as well as
hierarchical PKIs can be represented as trees because certificates hierarchical PKIs can be represented as trees because certificates
are not permitted to repeat in a path. If certificates could be are not permitted to repeat in a path. If certificates could be
repeated, loops can be formed such that the number of paths and repeated, loops can be formed such that the number of paths and
number of certificates in a path both increase without bound (e.g. A number of certificates in a path both increase without bound (e.g. A
issues to B, B issues to C, and C issues to A). Figure 7 below issues to B, B issues to C, and C issues to A). Figure 7 below
illustrates this concept from the trust anchor's perspective. illustrates this concept from the trust anchor's perspective.
+---------+ +---------+ +---------+ +---------+
| Trust | | Trust | | Trust | | Trust |
| Anchor | | Anchor | | Anchor | | Anchor |
+---------+ +---------+ +---------+ +---------+
| | | | | | | |
| | | |
v v v v v v v v
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| A |<-->| C | +--| A | | C |--+ | A |<-->| C | +--| A | | C |--+
+---+ +---+ | +---+ +---+ | +---+ +---+ | +---+ +---+ |
| | | | | | | | | | | |
| +---+ | v v v v | +---+ | v v v v
+->| B |<-+ +---+ +---+ +---+ +---+ +->| B |<-+ +---+ +---+ +---+ +---+
+---+ | B | | C | | A | | B | +---+ | B | | C | | A | | B |
| +---+ +---+ +---+ +---+ | +---+ +---+ +---+ +---+
| | | | | v | | | |
| | | | | +----+ v v v v
v v | | v | EE | +----+ +---+ +---+ +----+
+----+ +----+ | | +----+ +----+ | EE | | B | | B | | EE |
| EE | | EE | | | | EE | +----+ +---+ +---+ +----+
+----+ +----+ | | +----+ A certificate graph with | |
v v bi-directional cross cert. v v
A certificate graph with +---+ +---+ Between CAs A and C. +----+ +----+
bi-directional cross cert. | B | | B |
Between CAs A and C. +---+ +---+
| |
| |
v v
+----+ +----+
| EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+
The same certificate graph The same certificate graph
rendered as a tree - the rendered as a tree - the
Cooper, Dzambasow,
Hesse, Joseph,
way path building software way path building software
could see it. could see it.
Figure 7 - Simple Certificate Graph - From Anchor Tree Depiction Figure 7 - Simple Certificate Graph - From Anchor Tree Depiction
When viewed from this perspective, all PKIs look like hierarchies When viewed from this perspective, all PKIs look like hierarchies
emanating from the trust anchor. An infrastructure can be depicted emanating from the trust anchor. An infrastructure can be depicted
in this way regardless of how complex it is. In Figure 8, the same in this way regardless of how complex it is. In Figure 8, the same
graph is depicted from the end entity (EE) (the target certificate in graph is depicted from the end entity (EE) (the target certificate in
this example). It would appear this way if building in the forward this example). It would appear this way if building in the forward
(from EE or from target) direction. In this example, without knowing (from EE or from target) direction. In this example, without knowing
any particulars of the certificates, it appears at first that any particulars of the certificates, it appears at first that
building from EE has a smaller decision tree than building from the building from EE has a smaller decision tree than building from the
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
trust anchor. While it is true that there are fewer nodes in the trust anchor. While it is true that there are fewer nodes in the
tree, it is not necessarily more efficient in this example. tree, it is not necessarily more efficient in this example.
+---------+ +---------+ +---------+ +---------+
| Trust | | Trust | | Trust | | Trust |
| Anchor | | Anchor | | Anchor | | Anchor |
+---------+ +---------+ +---------+ +---------+
^ ^ ^ ^
| | | |
| | | |
skipping to change at page 17, line 50 skipping to change at page 18, line 39
| +---+ | | +---+ |
+---------| B |------+ +---------| B |------+
+---+ +---+
^ ^
| |
| |
+----+ +----+
| EE | | EE |
+----+ +----+
Cooper, Dzambasow,
Hesse, Joseph,
The same certificate graph rendered The same certificate graph rendered
as a tree but from the end entity as a tree but from the end entity
rather than the trust anchor. rather than the trust anchor.
Figure 8 - Certificate Graph - From Target Certificate Depiction Figure 8 - Certificate Graph - From Target Certificate Depiction
Suppose a path building algorithm performed no optimizations - that Suppose a path building algorithm performed no optimizations - that
is, it is only capable of detecting that the current certificate in 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 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 (EE). From the tree above, building from the target
certificate will require going through two intermediate certificates certificate will require going through two intermediate certificates
before encountering a certificate issued by the trust anchor 100% of 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 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 issued by the Trust Anchor). The path building module would not
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
chain C to A because it can recognize that C has a certificate issued chain C to A because it can recognize that C has a certificate issued
by the Trust Anchor (TA). by the Trust Anchor (TA).
On the other hand, in the first tree (Figure 7: from anchor On the other hand, in the first tree (Figure 7: from anchor
depiction), there is a 50% probability of building a path longer than 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 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 to B to EE). However, even given our simplistic example, the path
building software - when at A - could be designed to recognize that building software - when at A - could be designed to recognize that
B's subject distinguished name matches the issuer distinguished name B's subject distinguished name (DN) matches the issuer DN of the EE.
of the EE. Given this one optimization, the builder could prefer B Given this one optimization, the builder could prefer B to C. (B's
to C. (B's subject distinguished name matches that of the EE's subject DN matches that of the EE's issuer whereas C's subject DN
issuer whereas C's subject distinguished name does not.) So, for does not.) So, for this example, assuming the issuedByThisCA
this example, assuming the issuedByThisCA (reverse) and (reverse) and issuedToThisCA (forward) elements were fully populated
issuedToThisCA (forward) elements were fully populated in the in the directory and our path building module implemented the
directory and our path building module implemented the aforementioned aforementioned DN matching optimization method, path building from
distinguished name matching optimization method, path building from
either the trust anchor or the target certificate could be made either the trust anchor or the target certificate could be made
roughly equivalent. A list of possible optimization methods is roughly equivalent. A list of possible optimization methods is
provided later in this document. provided later in this document.
A more complicated example is created when the path building software A more complicated example is created when the path building software
encounters a situation when there are multiple certificates to choose encounters a situation when there are multiple certificates to choose
from while building a path. We refer to this as a large decision from while building a path. We refer to this as a large decision
tree, or a situation with high fanout. This might occur if an tree, or a situation with high fanout. This might occur if an
implementation has multiple trust anchors to choose from, and is implementation has multiple trust anchors to choose from, and is
building in the 'from root' direction. Or, it may occur in either building in the reverse (from trust anchor) direction. Or, it may
direction if a Bridge CA is encountered. Large decision trees are occur in either direction if a Bridge CA is encountered. Large
the enemy of efficient path building software. To combat this decision trees are the enemy of efficient path building software. To
problem, implementations should make careful decisions about the path combat this problem, implementations should make careful decisions
building direction, and should utilize optimizations such as those about the path building direction, and should utilize optimizations
discussed in section 3.1 when confronted with a large decision tree. such as those discussed in section 3.1 when confronted with a large
decision tree.
Irrespective of the path building approach for any path-building Irrespective of the path building approach for any path-building
algorithm, cases can be constructed that make the algorithm perform algorithm, cases can be constructed that make the algorithm perform
Cooper, Dzambasow,
Hesse, Joseph,
poorly. The following questions should help a developer decide from poorly. The following questions should help a developer decide from
which direction to build certification paths for their application: which direction to build certification paths for their application:
1) What is required to accommodate the local PKI environment and the 1) What is required to accommodate the local PKI environment and the
PKI environments with which interoperability will be required? PKI environments with which interoperability will be required?
a. If using a directory, is the directory [RFC 2587] compliant a. If using a directory, is the directory [RFC 2587] compliant
(Specifically, are the issuedToThisCA [forward] cross- (Specifically, are the issuedToThisCA [forward] cross-
certificates and/or the cACertificate attributes fully certificates and/or the cACertificate attributes fully
populated in the directory? If yes, you are able to build in populated in the directory? If yes, you are able to build in
the forward direction. the forward direction.
b. If using a directory, does the directory contain all the b. If using a directory, does the directory contain all the
issuedByThisCA (reverse) cross certificates in the issuedByThisCA (reverse) cross certificates in the
crossCertificatePair attribute, or, alternately, are all crossCertificatePair attribute, or, alternately, are all
certificates issued from each CA available via some other certificates issued from each CA available via some other
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
means? If yes, it is possible to build in the reverse means? If yes, it is possible to build in the reverse
direction. Note: [RFC 2587] does not require the direction. Note: [RFC 2587] does not require the
issuedByThisCA (reverse) cross certificates to be populated; issuedByThisCA (reverse) cross certificates to be populated;
if they are absent it will not be possible to build solely in if they are absent it will not be possible to build solely in
the reverse direction. the reverse direction.
c. Are all issuer certificates available via some means other c. Are all issuer certificates available via some means other
than a directory? (E.g. the authorityInformationAccess than a directory? (E.g. the authorityInformationAccess
extension is present and populated in all certificates.) If extension is present and populated in all certificates.) If
yes, you are able to build in the forward direction. yes, you are able to build in the forward direction.
2) How many trust anchors will the path building and validation 2) How many trust anchors will the path building and validation
software be using? software be using?
a. Are there (or will there be) multiple trust anchors in the a. Are there (or will there be) multiple trust anchors in the
local PKI? If yes, forward path building may offer better local PKI? If yes, forward path building may offer better
performance. performance.
b. Will the path building and validation software need to trust b. Will the path building and validation software need to place
root certificates from PKIs that do not populate reverse trust in trust anchors from PKIs that do not populate reverse
cross certificates for all intermediate CAs? If no, and the cross certificates for all intermediate CAs? If no, and the
local PKI populates reverse cross certificates, reverse path local PKI populates reverse cross certificates, reverse path
building is an option. building is an option.
2.4 How to Build a Certification Path 2.4 How to Build a Certification Path
As was discussed in the prior section, path building is essentially a 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 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 example, but how about a more complicated one? Before taking a look
at more a complicated scenario, it is worthwhile to address loops and at more a complicated scenario, it is worthwhile to address loops and
what constitutes a loop in a certification path. [X.509] specifies what constitutes a loop in a certification path. [X.509] specifies
that the same certificate may not repeat in a path. In a strict 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 sense, this works well as it is not possible to create an endless
loop without repeating one or more certificates in the path. loop without repeating one or more certificates in the path.
However, this requirement fails to adequately address Bridged PKI However, this requirement fails to adequately address Bridged PKI
environments. environments.
+---+ +---+ +---+ +---+
Cooper, Dzambasow,
Hesse, Joseph,
| F |--->| H | | F |--->| H |
+---+ +---+ +---+ +---+
^ ^ ^ ^ ^ ^
| \ \ | \ \
| \ \ | \ \
| v v | v v
| +---+ +---+ | +---+ +---+
| | G |--->| I | | | G |--->| I |
| +---+ +---+ | +---+ +---+
| ^ | ^
| / | /
| / | /
+------+ +-----------+ +------+ +---+ +---+ +------+ +-----------+ +------+ +---+ +---+
| TA W |<----->| Bridge CA |<------>| TA X |-->| L |-->| M | | TA W |<----->| Bridge CA |<------>| TA X |-->| L |-->| M |
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
+------+ +-----------+ +------+ +---+ +---+ +------+ +-----------+ +------+ +---+ +---+
^ ^ \ \ ^ ^ \ \
/ \ \ \ / \ \ \
/ \ \ \ / \ \ \
v v v v v v v v
+------+ +------+ +---+ +---+ +------+ +------+ +---+ +---+
| TA Y | | TA Z | | J | | N | | TA Y | | TA Z | | J | | N |
+------+ +------+ +---+ +---+ +------+ +------+ +---+ +---+
/ \ / \ | | / \ / \ | |
/ \ / \ | | / \ / \ | |
skipping to change at page 20, line 51 skipping to change at page 21, line 39
/ \ | / \ |
v v v v v v
+---+ +---+ +---+ +---+ +---+ +---+
| E | | D | | T | | E | | D | | T |
+---+ +---+ +---+ +---+ +---+ +---+
Figure 9 - Four Bridged PKIs Figure 9 - Four Bridged PKIs
Figure 9 depicts four root certification authorities cross-certified Figure 9 depicts four root certification authorities cross-certified
with a Bridge CA (BCA). While multiple trust anchors are shown in with a Bridge CA (BCA). While multiple trust anchors are shown in
the Figure, our examples all consider TA W as the trust anchor. The the Figure, our examples all consider TA Z as the trust anchor. The
Cooper, Dzambasow,
Hesse, Joseph,
other trust anchors serve different relying parties. By building other trust anchors serve different relying parties. By building
certification paths through the BCA, trust can be extended across the certification paths through the BCA, trust can be extended across the
four infrastructures. In Figure 9, the BCA has four certificates four infrastructures. In Figure 9, the BCA has four certificates
issued to it; one issued from each of the trust anchors in the graph. 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 If stored in the BCA directory system, the four certificates issued
to the BCA would be stored in the issuedToThisCA (forward) entry of to the BCA would be stored in the issuedToThisCA (forward) entry of
four different crossCertificatePair structures. The BCA also has four different crossCertificatePair structures. The BCA also has
issued four certificates, one to each of the trust anchors. If issued four certificates, one to each of the trust anchors. If
stored in the BCA directory system, those certificates would be stored in the BCA directory system, those certificates would be
stored in the issuedByThisCA (reverse) entry of the same four stored in the issuedByThisCA (reverse) entry of the same four
crossCertificatePair structures. (Note that the cross certificates crossCertificatePair structures. (Note that the cross certificates
are stored as matched pairs in the crossCertificatePair attribute. are stored as matched pairs in the crossCertificatePair attribute.
For example, a crossCertificatePair structure might contain both A(B) For example, a crossCertificatePair structure might contain both A(B)
and B(A), but not contain A(C) and B(A).) The four and B(A), but not contain A(C) and B(A).) The four
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
crossCertificatePair structures would then be stored in the BCA's crossCertificatePair structures would then be stored in the BCA's
directory entry in the crossCertificatePair attribute. directory entry in the crossCertificatePair attribute.
2.4.1 Certificate Repetition 2.4.1 Certificate Repetition
[X.509] requires that certificates are not repeated when building [X.509] requires that certificates are not repeated when building
paths. For instance, from the figure above, do not build the path E- paths. For instance, from the figure above, do not build the path TA
>B->C->A->C->A->Y. Not only is the repetition unnecessary to build Z->BCA->Y->A->C->A->C->B->D. Not only is the repetition unnecessary
the path from E to Y, but it also requires the reuse of a certificate to build the path from Z to D, but it also requires the reuse of a
(the one issued from C to A), which makes the path non-compliant with certificate (the one issued from C to A), which makes the path non-
[X.509]. compliant with [X.509].
What about the following path from EE to TA Z? What about the following path from TA Z to EE?
EE->N->L->X->BCA->W->BCA->Y->BCA->Z TA Z->BCA->Y->BCA->W->BCA->X->L->N->EE
Unlike the first example, this path does not require a developer to Unlike the first example, this path does not require a developer to
repeat any certificates - therefore, it is compliant with [X.509]. repeat any certificates - therefore, it is compliant with [X.509].
Each of the BCA certificates is issued from a different source and is Each of the BCA certificates is issued from a different source and is
therefore a different certificate. Suppose now that the bottom left therefore a different certificate. Suppose now that the bottom left
PKI (in Figure 9) had double arrows between Y and C, as well as PKI (in Figure 9) had double arrows between Y and C, as well as
between Y and A. The following path could then be built: between Y and A. The following path could then be built:
EE->N->L->X->BCA->W->BCA->Y->C->A->Y->BCA->Z TA Z->BCA->Y->A->C->Y->BCA->W->BCA->X->L->N->EE
A path such as this could become arbitrarily complex and traverse A path such as this could become arbitrarily complex and traverse
every cross certified CA in every PKI in a cross-certified every cross certified CA in every PKI in a cross-certified
environment while still remaining compliant with [X.509]. As a environment while still remaining compliant with [X.509]. As a
practical matter, the path above is not something an application practical matter, the path above is not something an application
would typically want or need to build for a variety of reasons: would typically want or need to build for a variety of reasons:
- First, certification paths like the example above are generally - First, certification paths like the example above are generally
not intended by the PKI designers and should not be necessary not intended by the PKI designers and should not be necessary
in order to validate any given certificate. If a convoluted in order to validate any given certificate. If a convoluted
Cooper, Dzambasow,
Hesse, Joseph,
path such as the example above is required (there is no path such as the example above is required (there is no
corresponding simple path) in order to validate a given corresponding simple path) in order to validate a given
certificate, this is most likely indicative of a flaw in the certificate, this is most likely indicative of a flaw in the
PKI design. PKI design.
- Second, the longer a path becomes, the greater the potential - Second, the longer a path becomes, the greater the potential
dilution of trust in the certification path. That is, with dilution of trust in the certification path. That is, with
each successive link in the infrastructure (i.e., certification each successive link in the infrastructure (i.e., certification
by CAs and cross-certification between CAs) some amount of by CAs and cross-certification between CAs) some amount of
assurance may be considered lost. assurance may be considered lost.
- Third, the longer and more complicated a path, the less likely - Third, the longer and more complicated a path, the less likely
it is to validate because of basic constraints, policies or it is to validate because of basic constraints, policies or
policy constraints, name constraints, CRL availability, or even policy constraints, name constraints, CRL availability, or even
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
revocation. revocation.
- Lastly, and certainly not least important from a developer's or - Lastly, and certainly not least important from a developer's or
user's perspective, is performance. Allowing paths like the user's perspective, is performance. Allowing paths like the
one above dramatically increases the number of possible paths one above dramatically increases the number of possible paths
for every certificate in a mesh or cross-certified environment. for every certificate in a mesh or cross-certified environment.
Every path built may require one or more of the following: Every path built may require one or more of the following:
validation of certificate properties, CPU intensive signature validation of certificate properties, CPU intensive signature
validations, CRL retrievals, increased network load, and local validations, CRL retrievals, increased network load, and local
memory caching. Eliminating the superfluous paths can greatly memory caching. Eliminating the superfluous paths can greatly
skipping to change at page 22, line 45 skipping to change at page 23, line 33
2.4.2 Introduction to Path Building Optimization 2.4.2 Introduction to Path Building Optimization
How can these superfluous paths be eliminated? Rather than only How can these superfluous paths be eliminated? Rather than only
disallowing identical certificates from repeating, it is recommended disallowing identical certificates from repeating, it is recommended
that a developer disallow the same public key and subject name pair that a developer disallow the same public key and subject name pair
from being repeated. For maximum flexibility, the subject name from being repeated. For maximum flexibility, the subject name
should collectively include any subject alternative names. Using should collectively include any subject alternative names. Using
this approach, all of the intended and needed paths should be this approach, all of the intended and needed paths should be
available, and the excess and diluted paths should be eliminated. available, and the excess and diluted paths should be eliminated.
For example, using this approach, only one path exists from the EE to For example, using this approach, only one path exists from the TA Z
Z in the diagram above: EE->N->L->X->BCA->Z. to EE in the diagram above: TA Z->BCA->X->L->N->EE.
Given the simplifying rule of not repeating pairs of subject names Given the simplifying rule of not repeating pairs of subject names
(including subject alternative names) and public keys, and only using (including subject alternative names) and public keys, and only using
certificates found in the cACertificate and forward (issuedToThisCA) certificates found in the cACertificate and forward (issuedToThisCA)
element of the crossCertificatePair attributes, Figure 10 depicts all element of the crossCertificatePair attributes, Figure 10 depicts the
forward path building decision tree from the EE to all reachable
Cooper, Dzambasow, nodes in the graph. This is the ideal graph for a path builder
Hesse, Joseph, attempting to build a path from TA Z to EE.
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 | | TA W |<------| Bridge CA |<-------| TA X |<--| L |
+------+ +-----------+ +------+ +---+ +------+ +-----------+ +------+ +---+
/ \ ^ / \ ^
/ \ \ / \ \
/ \ \ / \ \
v v \ v v \
+------+ +------+ +---+ +------+ +------+ +---+
| TA Y | | TA Z | | N | | TA Y | | TA Z | | N |
+------+ +------+ +---+ +------+ +------+ +---+
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
^ ^
\ \
\ \
+----+ +----+
| EE | | EE |
+----+ +----+
Figure 10 - Forward (From Entity) Decision Tree Figure 10 - Forward (From Entity) Decision Tree
It is not possible to build forward direction paths into the 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 infrastructures behind CAs W, Y, and Z, because W, Y, and Z have not
been issued certificates by their subordinate CAs. (The subordinate been issued certificates by their subordinate CAs. (The subordinate
CAs are F and G, A and C, and O and P, respectively). If simplicity CAs are F and G, A and C, and O and P, respectively). If simplicity
and speed is desirable, the graph in Figure 10 is a very appealing and speed is desirable, the graph in Figure 10 is a very appealing
way to structure the path-building algorithm. Finding a path from way to structure the path-building algorithm. Finding a path from
the EE to one of the four trust anchors is reasonably simple. the EE to one of the four trust anchors is reasonably simple.
Alternately, a developer could choose to build in the opposite Alternately, a developer could choose to build in the opposite
direction, using the reverse cross-certificates from any one of the direction, using the reverse cross-certificates from any one of the
four trust anchors around the BCA. The graph in Figure 11 depicts four trust anchors around the BCA. The graph in Figure 11 depicts
all possible paths as a tree emanating from Z. (Note: it is not all possible paths as a tree emanating from TA Z. (Note: it is not
recommended that implementations attempt to determine all possible recommended that implementations attempt to determine all possible
paths, this would require retrieval and storage of all PKI data paths, this would require retrieval and storage of all PKI data
including certificates and CRLs! This example is provided to including certificates and CRLs! This example is provided to
demonstrate the complexity which might be encountered.) demonstrate the complexity which might be encountered.)
+---+ +---+ +---+ +---+
| I |--->| H | | I |--->| H |
+---+ +---+ +---+ +---+
^ ^
| +---+ +---+ | +---+ +---+
| | H |--->| I | | | H |--->| I |
| +---+ +---+ | +---+ +---+
+---+ ^ +---+ ^
| G | / +---+ +---+ +---+ | G | / +---+ +---+ +---+
Cooper, Dzambasow,
Hesse, Joseph,
+---+ / | F |--->| H |--->| I | +---+ / | F |--->| H |--->| I |
^ / +---+ +---+ +---+ ^ / +---+ +---+ +---+
\ / ^ \ / ^
\/ / \/ /
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| F | | G |--->| I |--->| H | | M | | F | | G |--->| I |--->| H | | M |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
^ ^ ^ ^ ^ ^
| / | | / |
+------+ +-----------+ +------+ +---+ +------+ +-----------+ +------+ +---+
| TA W |<------| Bridge CA |-------->| TA X |-->| L | | TA W |<------| Bridge CA |-------->| TA X |-->| L |
+------+ +-----------+ +------+ +---+ +------+ +-----------+ +------+ +---+
/ ^ \ \ / ^ \ \
v \ v v v \ v v
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
+------+ +------+ +---+ +---+ +------+ +------+ +---+ +---+
| TA Y | | TA Z | | J | | N | | TA Y | | TA Z | | J | | N |
+------+ +------+ +---+ +---+ +------+ +------+ +---+ +---+
/ \ / \ \ \ / \ / \ \ \
v v v v v v v v v v v v
+---+ +---+ +---+ +---+ +---+ +----+ +---+ +---+ +---+ +---+ +---+ +----+
| A | | C | | O | | P | | K | | EE | | A | | C | | O | | P | | K | | EE |
+---+ +---+ +---+ +---+ +---+ +----+ +---+ +---+ +---+ +---+ +---+ +----+
/ \ / \ / \ \ / \ / \ / \ \
v v v v v v v v v v v v v v
skipping to change at page 24, line 48 skipping to change at page 25, line 36
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| E | | D | | E | | D | | E | | D | | E | | D |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
Figure 11 - Reverse (From Anchor) Decision Tree Figure 11 - Reverse (From Anchor) Decision Tree
Given the relative complexity of this decision tree, it becomes clear Given the relative complexity of this decision tree, it becomes clear
that making the right choices while navigating the tree can make a that making the right choices while navigating the tree can make a
large difference in how quickly a valid path is returned. The path large difference in how quickly a valid path is returned. The path
building software could potentially traverse the entire graph before building software could potentially traverse the entire graph before
choosing the shortest path: Z->BCA->X->L->N->EE. With a decision choosing the shortest path: TA Z->BCA->X->L->N->EE. With a decision
tree like the one above, the basic depth first traversal approach tree like the one above, the basic depth first traversal approach
introduces obvious inefficiencies in the path building process. To introduces obvious inefficiencies in the path building process. To
compensate for this, a path building module not only needs to decide compensate for this, a path building module not only needs to decide
Cooper, Dzambasow,
Hesse, Joseph,
in which direction to traverse the tree, but it should also 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. which branches of the tree are more likely to yield a valid path.
The path building algorithm then ideally becomes a tree traversal The path building algorithm then ideally becomes a tree traversal
algorithm with weights or priorities assigned to each branch point to algorithm with weights or priorities assigned to each branch point to
guide the decision making. If properly designed, such an approach guide the decision making. If properly designed, such an approach
would effectively yield the "best path first" more often than not. would effectively yield the "best path first" more often than not.
(The terminology "best path first" is quoted because the definition (The terminology "best path first" is quoted because the definition
of the "best" path may differ from PKI to PKI. That is ultimately to 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 be determined by the developer, not by this document.) Finding the
"best path first" is an effort to make the implementation efficient, "best path first" is an effort to make the implementation efficient,
which is stated as one of our criteria in section 2.2. which is stated as one of our criteria in section 2.2.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
So how would a developer go about finding the best path first? Given So how would a developer go about finding the best path first? Given
the simplifying idea of addressing path building as a tree traversal, the simplifying idea of addressing path building as a tree traversal,
path building could be structured as a depth first search. A simple path building could be structured as a depth first search. A simple
example of depth first tree traversal path building is depicted in example of depth first tree traversal path building is depicted in
Figure 12, with no preference given to sort order. Figure 12, with no preference given to sort order.
Note: The arrows in the lower portion of the figure do not indicate Note: The arrows in the lower portion of the figure do not indicate
the direction of certificate issuance - they indicate the direction the direction of certificate issuance - they indicate the direction
of the tree traversal from the target certificate (EE). of the tree traversal from the target certificate (EE).
skipping to change at page 25, line 52 skipping to change at page 26, line 41
/ \ +---+ +---+ / \ +---+ +---+
/ \ | C | | A | / \ | C | | A |
v v +---+ +---+ v v +---+ +---+
+---+ +---+ ^ ^ +---+ +---+ ^ ^
| E | | D | | / | E | | D | | /
+---+ +---+ | / +---+ +---+ | /
+---+ +---+
Infrastructure | B | Infrastructure | B |
+---+ +---+
^ ^
Cooper, Dzambasow,
Hesse, Joseph,
| |
+----+ +----+
| EE | | EE |
+----+ +----+
The Same Infrastructure The Same Infrastructure
Represented as a Tree Represented as a Tree
+----+ +----+ +----+ +----+
| TA | | TA | | TA | | TA |
+----+ +----+ +----+ +----+
^ ^ ^ ^
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
| | | |
+---+ +---+ +---+ +---+
| A | | C | | A | | C |
+---+ +---+ +---+ +---+
+----+ ^ ^ +----+ +----+ ^ ^ +----+
| TA | | | | TA | | TA | | | | TA |
+----+ | | +----+ +----+ | | +----+
^ | | ^ ^ | | ^
\ | | / \ | | /
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
skipping to change at page 26, line 42 skipping to change at page 27, line 32
| B | | B | | B | | B | | B | | B | | B | | B |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | |
| | | | | | | |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
All possible paths from EE to TA All possible paths from EE to TA
using a depth first tree traversal using a depth first decision tree traversal
Figure 12 - Path Building Using a Depth First Tree Traversal Figure 12 - Path Building Using a Depth First Tree Traversal
Figure 12 illustrates that four possible paths exist for this Figure 12 illustrates that four possible paths exist for this
example. Suppose that the last path (TA->A->B->EE) is the only path 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 that will validate. This could be for any combination of reasons
such as name constraints, policy processing, validity periods, or such as name constraints, policy processing, validity periods, or
path length constraints. The goal of an efficient path-building path length constraints. The goal of an efficient path-building
Cooper, Dzambasow,
Hesse, Joseph,
component is to select the fourth path first by testing properties of component is to select the fourth path first by testing properties of
the certificates as the tree is traversed. For example, when the the certificates as the tree is traversed. For example, when the
path building software is at entity B in the graph, it should examine 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 both choices A and C to determine which certificate is the most
likely best choice. An efficient module would conclude that A is the likely best choice. An efficient module would conclude that A is the
more likely correct path. Then, at A, the module compares more likely correct path. Then, at A, the module compares
terminating the path at TA, or moving to C. Again, an efficient terminating the path at TA, or moving to C. Again, an efficient
module will make the better choice (TA) and thereby find the "best module will make the better choice (TA) and thereby find the "best
path first". path first".
What if the choice between CA certificates is not binary as it was in What if the choice between CA certificates is not binary as it was in
the previous example? What if the path building software encounters the previous example? What if the path building software encounters
a branch point with some arbitrary number of CA certificates thereby a branch point with some arbitrary number of CA certificates thereby
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
creating the same arbitrary number of tree branches? (This would be 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 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 each will have multiple certificates issued to itself from other
CAs.) This actually does not change the algorithm at all if it is CAs.) This actually does not change the algorithm at all if it is
structured properly. In our example, rather than treating each structured properly. In our example, rather than treating each
decision as binary (i.e., choosing A or C), the path building decision as binary (i.e., choosing A or C), the path building
software should sort all the available possibilities at any given software should sort all the available possibilities at any given
branch point, and then select the best choice from the list. In the 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 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 second choice should be tried next upon traversing back to that point
in the tree. Continue following this pattern until a path is found 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 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 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 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 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 memory resident representation of the entire tree. Just like any
other recursive depth first search algorithm, the only information other recursive depth first search algorithm, the only information
the algorithm needs to keep track of is what nodes (entities) in the 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, tree lie behind it on the current path, and for each of those nodes,
which edges (certificates) have already been tried. which arcs (certificates) have already been tried.
2.5 Building Certification Paths for Revocation Signer Certificates 2.5 Building Certification Paths for Revocation Signer Certificates
Special consideration is given to building a certification path for Special consideration is given to building a certification path for
the Revocation Signer certificate because it may or may not be the the Revocation Signer certificate because it may or may not be the
same as the Certification Authority certificate. For example, after a same as the Certification Authority certificate. For example, after a
CA performs a key rollover, the new CA certificate will be the CRL CA performs a key rollover, the new CA certificate will be the CRL
Signer certificate, whereas the old CA certificate is the Signer certificate, whereas the old CA certificate is the
Certification Authority certificate for previously issued Certification Authority certificate for previously issued
certificates. In the case of indirect CRLs, the CRL Signer certificates. In the case of indirect CRLs, the CRL Signer
certificate will contain a different name and key than the certificate will contain a different name and key than the
Certification Authority certificate. In the case of OCSP, the Certification Authority certificate. In the case of OCSP, the
Revocation Signer certificate may represent an OCSP Responder that is Revocation Signer certificate may represent an OCSP Responder that is
not the same entity as the Certification Authority. not the same entity as the Certification Authority.
Cooper, Dzambasow,
Hesse, Joseph,
When the Revocation Signer certificate and the Certification When the Revocation Signer certificate and the Certification
Authority certificate are identical, no additional consideration is Authority certificate are identical, no additional consideration is
required from a certification path building standpoint. That is, the required from a certification path building standpoint. That is, the
certification path built (and validated) for the Certification certification path built (and validated) for the Certification
Authority certificate can also be used as the certification path for Authority certificate can also be used as the certification path for
the Revocation Signer certificate. In this case, the signature on the the Revocation Signer certificate. In this case, the signature on the
revocation data (E.g., CRL or OCSP response) is verified using the revocation data (e.g., CRL or OCSP response) is verified using the
same certificate, and no other certification path building is same certificate, and no other certification path building is
required. An efficient certification path validation algorithm should required. An efficient certification path validation algorithm should
first try all possible CRLs issued by the Certification Authority to first try all possible CRLs issued by the Certification Authority to
determine if any of the CRLs (a) cover the certificate in question, determine if any of the CRLs (a) cover the certificate in question,
(b) are current, and (c) are signed using the same key used to sign (b) are current, and (c) are signed using the same key used to sign
the certificate. the certificate.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
When the Revocation Signer certificate is not identical to the When the Revocation Signer certificate is not identical to the
Certification Authority certificate, a certification path must be Certification Authority certificate, a certification path must be
built (and validated) for the Revocation Signer certificate. In built (and validated) for the Revocation Signer certificate. In
general, the certification path building software may build the path general, the certification path building software may build the path
as it would for any other certificate. However, this document also as it would for any other certificate. However, this document also
outlines methods in later sections for greatly improving path outlines methods in later sections for greatly improving path
building efficiency for Revocation Signer certificate case. building efficiency for Revocation Signer certificate case.
2.6 Suggested Path Building Software Components 2.6 Suggested Path Building Software Components
skipping to change at page 28, line 52 skipping to change at page 29, line 40
following components: following components:
1) The logic for building and traversing the certificate graph. 1) The logic for building and traversing the certificate graph.
2) Logic for retrieving the necessary certificates (and CRLs and/or 2) Logic for retrieving the necessary certificates (and CRLs and/or
other revocation status information if the path is to be other revocation status information if the path is to be
validated) from the available source(s). validated) from the available source(s).
Assuming a more efficient and agile path building module is desired, Assuming a more efficient and agile path building module is desired,
the following is a good starting point and will tie into the the following is a good starting point and will tie into the
remainder of this document. For a path-building module to take full remainder of this document. For a path-building module to take full
Cooper, Dzambasow,
Hesse, Joseph,
advantage of all the suggested optimizations listed in this document, advantage of all the suggested optimizations listed in this document,
it will need all of the components listed below. it will need all of the components listed below.
1) A local certificate and CRL cache. 1) A local certificate and CRL cache.
a. This may be used by all certificate-using components - it a. This may be used by all certificate-using components - it
does not need to be specific to the path building software. does not need to be specific to the path building software.
A local cache could be memory resident, stored in an A local cache could be memory resident, stored in an
operating system or application certificate store, stored in operating system or application certificate store, stored in
a database, or even stored in individual files on the hard a database, or even stored in individual files on the hard
disk. While the implementation of this cache is beyond the disk. While the implementation of this cache is beyond the
scope of this document, some design considerations are listed scope of this document, some design considerations are listed
below. below.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
2) The logic for building and traversing the certificate graph / 2) The logic for building and traversing the certificate graph /
tree. tree.
a. This performs sorting functionality for prioritizing a. This performs sorting functionality for prioritizing
certificates (and thereby optimizing path building) while certificates (and thereby optimizing path building) while
traversing the tree. traversing the tree.
b. There is no need to build a complete graph prior to b. There is no need to build a complete graph prior to
commencing path building. Since path building can be commencing path building. Since path building can be
implemented as a depth first tree traversal, the path builder implemented as a depth first tree traversal, the path builder
only needs to store the current location in the tree along only needs to store the current location in the tree along
skipping to change at page 29, line 52 skipping to change at page 30, line 40
for split crossCertificatePair attributes) each for split crossCertificatePair attributes) each
certificate was found in may be useful. This allows for certificate was found in may be useful. This allows for
functionality such as retrieving only forward cross functionality such as retrieving only forward cross
certificates, etc. certificates, etc.
iii. A "freshness" timestamp (cache expiry time) can be used iii. A "freshness" timestamp (cache expiry time) can be used
to determine when the directory should be searched to determine when the directory should be searched
again. again.
b. LDAPv3 directory for certificates and CRLs. b. LDAPv3 directory for certificates and CRLs.
Cooper, Dzambasow,
Hesse, Joseph,
i. Consider supporting multiple directories for general i. Consider supporting multiple directories for general
queries. queries.
ii. Consider supporting dynamic LDAP connections for ii. Consider supporting dynamic LDAP connections for
retrieving CRLs using an LDAP URI in the CRL retrieving CRLs using an LDAP URI [RFC 2396] in the CRL
distribution point certificate extension. distribution point certificate extension.
iii. Support LDAP referrals. This is typically only a matter iii. Support LDAP referrals. This is typically only a matter
of activating the appropriate flag in the LDAP API. of activating the appropriate flag in the LDAP API.
c. HTTP support for CRL distribution points and AIA support. c. HTTP support for CRL distribution points and AIA support.
i. Consider HTTPS support, but be aware that this may create i. Consider HTTPS support, but be aware that this may create
an unbounded recursion when the implementation tries to an unbounded recursion when the implementation tries to
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
build a certification path for the server's certificate build a certification path for the server's certificate
if this in turn requires an additional HTTPS lookup. if this in turn requires an additional HTTPS lookup.
4) A certification path cache that stores previously validated 4) A certification path cache that stores previously validated
relationships between certificates. This cache should include: relationships between certificates. This cache should include:
a. A configurable expiration date for each entry. This date can a. A configurable expiration date for each entry. This date can
be configured based upon factors such as the expiry of the be configured based upon factors such as the expiry of the
information used to determine the validity of an entry, information used to determine the validity of an entry,
bandwidth, assurance level, storage space, etc. bandwidth, assurance level, storage space, etc.
skipping to change at page 30, line 50 skipping to change at page 31, line 40
[X.509] specifically addresses the list of inputs required for path [X.509] specifically addresses the list of inputs required for path
validation but makes no specific suggestions as to what could be validation but makes no specific suggestions as to what could be
useful inputs to path building. However, given that the goal of path useful inputs to path building. However, given that the goal of path
building is to find certification paths that will validate, it building is to find certification paths that will validate, it
follows that the same inputs used for validation could be used to follows that the same inputs used for validation could be used to
optimize path building. optimize path building.
2.7.1 Required Inputs 2.7.1 Required Inputs
Cooper, Dzambasow,
Hesse, Joseph,
Setting aside configuration information such as repository or cache Setting aside configuration information such as repository or cache
locations, the following are required inputs to the certification locations, the following are required inputs to the certification
path building process: path building process:
1) The Target Certificate - The certificate that is to be validated. 1) The Target Certificate - The certificate that is to be validated.
This is one end point for the path. (It is also possible to This is one end point for the path. (It is also possible to
provide information used to retrieve a certificate for a target, provide information used to retrieve a certificate for a target,
rather than the certificate itself.) rather than the certificate itself.)
2) Trust List - This is the other endpoint of the path, and can 2) Trust List - This is the other endpoint of the path, and can
consist of either: consist of either:
a. Trusted CA certificates a. Trusted CA certificates
b. Trusted keys and distinguished names - a certificate is not
necessarily required Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
b. Trusted keys and DNs - a certificate is not necessarily
required
2.7.2 Optional Inputs 2.7.2 Optional Inputs
In addition to the inputs listed in Section 2.7.1, the following In addition to the inputs listed in Section 2.7.1, the following
optional inputs can also be useful for optimizing path building. optional inputs can also be useful for optimizing path building.
However, if the path building software takes advantage of all of the However, if the path building software takes advantage of all of the
optimization methods described later in this document, all of the optimization methods described later in this document, all of the
following optional inputs will be required. following optional inputs will be required.
1) Time (T) - The time for which the certificate is to be validated 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 (e.g., if validating a historical signature from 1 year ago, T is
needed to build a valid path). needed to build a valid path)
a. If not included as an input, the path building software a. If not included as an input, the path building software
should always build for T equal to the current system time. should always build for T equal to the current system time
2) Initial-inhibit-policy-mapping indicator 2) Initial-inhibit-policy-mapping indicator
3) Initial-require-explicit-policy indicator 3) Initial-require-explicit-policy indicator
4) Initial-any-policy-inhibit indicator 4) Initial-any-policy-inhibit indicator
5) Initial user acceptable policy set 5) Initial user acceptable policy set
6) Error handlers (call backs or virtual classes) 6) Error handlers (call backs or virtual classes)
7) Handlers for custom certificate extensions 7) Handlers for custom certificate extensions
8) Is-revocation-provider indicator 8) Is-revocation-provider indicator
a. IMPORTANT: When building a certification path for an OCSP a. IMPORTANT: When building a certification path for an OCSP
Responder certificate specified as part of the local Responder certificate specified as part of the local
configuration, this flag should not be set. It is set when configuration, this flag should not be set. It is set when
Cooper, Dzambasow,
Hesse, Joseph,
building a certification path for a CRL Signer certificate or building a certification path for a CRL Signer certificate or
for an OCSP Responder Signer certificate discovered using the for an OCSP Responder Signer certificate discovered using the
information asserted in an authorityInformationAccess information asserted in an authorityInformationAccess
certificate extension. certificate extension
9) The complete certification path for the Certification Authority 9) The complete certification path for the Certification Authority
(if Is-revocation-provider is set) (if Is-revocation-provider is set)
10) Collection of certificates that may be useful in building the 10) Collection of certificates that may be useful in building the
path path
11) Collection of certificate revocation lists and/or other 11) Collection of certificate revocation lists and/or other
revocation data revocation data
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
The last two items are a matter of convenience. Alternately, The last two items are a matter of convenience. Alternately,
certificates and revocation information could be placed in a local certificates and revocation information could be placed in a local
cache accessible to the path building module prior to attempting to cache accessible to the path building module prior to attempting to
build a path. build a path.
3. Optimizing Path Building 3. Optimizing Path Building
This section recommends methods for optimizing path building This section recommends methods for optimizing path building
processes. processes.
3.1 Optimized Path Building 3.1 Optimized Path Building
Path building can be optimized by sorting the certificates at every Path building can be optimized by sorting the certificates at every
decision point (at every node in the tree) and then selecting the decision point (at every node in the tree) and then selecting the
most promising certificate not yet selected in the manner described most promising certificate not yet selected in the manner described
in section 2.4.2. This process continues until the path terminates. in section 2.4.2. This process continues until the path terminates.
This is roughly equivalent to the concept of creating a weighted edge This is roughly equivalent to the concept of creating a weighted edge
tree, where the edges are represented by certificates and nodes tree, where the edges are represented by certificates and nodes
represent subject distinguished names. However, unlike the weighted represent subject DNs. However, unlike the weighted edge graph
edge graph concept, a certification path builder need not have the concept, a certification path builder need not have the entire graph
entire graph available in order to function efficiently. In available in order to function efficiently. In addition, the path
addition, the path builder can be stateless with respect to nodes of builder can be stateless with respect to nodes of the graph not
the graph not present in the current path, so the working data set present in the current path, so the working data set can be
can be relatively small. relatively small.
The concept of statelessness with respect to nodes not in the current The concept of statelessness with respect to nodes not in the current
path is instrumental to using the sorting optimizations listed in path is instrumental to using the sorting optimizations listed in
this document. Initially, it may seem that sorting a given group of this document. Initially, it may seem that sorting a given group of
certificates for a CA once and then preserving that sorted order for certificates for a CA once and then preserving that sorted order for
later use would be an efficient way to write the path builder. later use would be an efficient way to write the path builder.
However, maintaining this state can quickly eliminate the efficiency However, maintaining this state can quickly eliminate the efficiency
which sorting provides. Consider the following diagram: which sorting provides. Consider the following diagram:
+---+ +---+
Cooper, Dzambasow,
Hesse, Joseph,
| R | | R |
+---+ +---+
^ ^
/ /
v v
+---+ +---+ +---+ +---+ +----+ +---+ +---+ +---+ +---+ +----+
| A |<----->| E |<---->| D |--->| Z |--->| EE | | A |<----->| E |<---->| D |--->| Z |--->| EE |
+---+ +---+ +---+ +---+ +----+ +---+ +---+ +---+ +---+ +----+
^ ^ ^ ^ ^ ^ ^ ^
\ / \ / \ / \ /
\ / \ / \ / \ /
v v v v v v v v
+---+ +---+ +---+ +---+
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
| B |<----->| C | | B |<----->| C |
+---+ +---+ +---+ +---+
Figure 13 - Example of Path Building Optimization Figure 13 - Example of Path Building Optimization
In this example, the path builder is building in the forward (from 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 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 also opted to allow subject name & key to repeat. (This will allow
multiple traversals through any of the cross certified CAs, creating multiple traversals through any of the cross certified CAs, creating
enough complexity in this small example to illustrate proper state enough complexity in this small example to illustrate proper state
skipping to change at page 33, line 52 skipping to change at page 34, line 41
order [E(C), E(B), E(A), E(D)]. The current path is now E(C)->D(E)- 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. >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 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)- (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, >E(C)->D(E)->Z(D)->EE(Z) and the path has five nodes; EE, Z, D, E,
and C. and C.
Now the builder finds itself back at node E with four certificates. 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 If the builder were to use the prior sort order from the first
Cooper, Dzambasow,
Hesse, Joseph,
encounter with E, it would have [E(C), E(B), E(A), E(D)]. In the 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 current path's context, this ordering may be inappropriate. To begin
with, the certificate E(C) is already in the path so it certainly with, the certificate E(C) is already in the path so it certainly
does not deserve first place. does not deserve first place.
The best way to handle this situation is for the path builder to 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 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 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 - 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 new node are sorted based upon the current path content and the first
certificate is then selected. For example, the builder may examine certificate is then selected. For example, the builder may examine
E(B) and note that it contains a name constraint prohibiting "C". At 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 this point in the decision tree, E(B) could not be added to the path
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
and produce a valid result since "C" is already in the path. As a 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 result, the certificate E(B) should placed at the bottom of the
prioritized list. prioritized list.
Alternatively, E(B) could be eliminated from this new node in the Alternatively, E(B) could be eliminated from this new node in the
tree. It is very important to see that this certificate is tree. It is very important to see that this certificate is
eliminated ONLY at this node and ONLY for the current path. If path 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 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 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 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. node should not alter the state of previous or subsequent nodes.
(Except for prioritizing certificates in the subsequent nodes.) (Except for prioritizing certificates in the subsequent nodes.)
In this example, the builder should also note that E(C) is already in 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 the path and make it last or eliminate it from this node since
certificates can not be repeated in a path. certificates can not be repeated in a path.
If the builder eliminates both certificates E(B) and E(C) at this 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 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 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 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)- [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 >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 path and the path terminated because one of the trust anchors has
been found. been found.
In the event the first path fails to validate, the path builder will In the event the first path fails to validate, the path builder will
still have the seven nodes and associated state information to work still have the seven nodes and associated state information to work
with. On the next iteration, the path builder is able to traverse 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 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 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, 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) 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 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 backs all the way up to EE or a valid path is found. If the tree
Cooper, Dzambasow,
Hesse, Joseph,
traversal returns to EE, all possible paths have been exhausted and traversal returns to EE, all possible paths have been exhausted and
the builder can conclude no valid path exists. the builder can conclude no valid path exists.
This approach of sorting certificates in order to optimize path This approach of sorting certificates in order to optimize path
building will yield better results than not optimizing the tree building will yield better results than not optimizing the tree
traversal. However, the path building process can be further traversal. However, the path building process can be further
streamlined by eliminating certificates, and entire branches of the streamlined by eliminating certificates, and entire branches of the
tree as a result, as paths are built. tree as a result, as paths are built.
3.2 Sorting vs. Elimination 3.2 Sorting vs. Elimination
Consider a situation when building a path in which three CA Consider a situation when building a path in which three CA
certificates are found for a given target certificate and must be certificates are found for a given target certificate and must be
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
prioritized. When the certificates are examined, as in the previous prioritized. When the certificates are examined, as in the previous
example, one of the three has a name constraint present that will example, one of the three has a name constraint present that will
invalidate the path built thus far. When sorting the three invalidate the path built thus far. When sorting the three
certificates, that one would certainly go to the back of the line. certificates, that one would certainly go to the back of the line.
However, the path building software could decide that this condition However, the path building software could decide that this condition
eliminates the certificate from consideration at this point in the eliminates the certificate from consideration at this point in the
graph, thereby reducing the number of certificate choices by 33% at graph, thereby reducing the number of certificate choices by 33% at
this point. this point.
NOTE: It is important to understand that the elimination of a NOTE: It is important to understand that the elimination of a
skipping to change at page 35, line 51 skipping to change at page 36, line 40
not be able to see what went wrong. The user may only see the not be able to see what went wrong. The user may only see the
unrevealing error message: "No certification path found." unrevealing error message: "No certification path found."
On the other hand, the path building module could opt to not rule out On the other hand, the path building module could opt to not rule out
any certification paths. The path building software could then any certification paths. The path building software could then
return any and all paths it can build from the certificate graph. It 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 is then up to the validation engine to determine which are valid and
which are invalid. The user or calling application can then have which are invalid. The user or calling application can then have
complete details on why each and every path fails to validate. The complete details on why each and every path fails to validate. The
drawback is obviously one of performance, as an application or end drawback is obviously one of performance, as an application or end
Cooper, Dzambasow,
Hesse, Joseph,
user may wait for an extended period of time while cross-certified user may wait for an extended period of time while cross-certified
PKIs are navigated in order to build paths that will never validate. PKIs are navigated in order to build paths that will never validate.
Neither option is a very desirable approach. One option provides Neither option is a very desirable approach. One option provides
good performance for users, which is beneficial. The other option good performance for users, which is beneficial. The other option
though allows administrators to diagnose problems with the PKI, though allows administrators to diagnose problems with the PKI,
directory, or software. Below are some recommendations to reach a directory, or software. Below are some recommendations to reach a
middle ground on this issue. middle ground on this issue.
First, developers are strongly encouraged to output detailed log First, developers are strongly encouraged to output detailed log
information from the path building software. The log should information from the path building software. The log should
explicitly indicate every choice the builder makes and why. It explicitly indicate every choice the builder makes and why. It
should clearly identify which certificates are found and used at each 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, step in building the path. If care is taken to produce a useful log,
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
PKI administrators and help desk personnel will have ample PKI administrators and help desk personnel will have ample
information to diagnose a problem with the PKI. Ideally, there would 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 be a mechanism for turning this logging on and off, so that it is not
running all the time. Additionally, it is recommended that the log running all the time. Additionally, it is recommended that the log
contain information so that a developer or tester can recreate the contain information so that a developer or tester can recreate the
paths tried by the path building software, to assist with diagnostics paths tried by the path building software, to assist with diagnostics
and testing. and testing.
Secondly, it is desirable to return something useful to the user. Secondly, it is desirable to return something useful to the user.
The easiest approach is probably to implement a "dual mode" path The easiest approach is probably to implement a "dual mode" path
skipping to change at page 36, line 52 skipping to change at page 37, line 40
path first", the paths most likely to validate would be returned path first", the paths most likely to validate would be returned
before this limit is reached. Once the limit is reached the module before this limit is reached. Once the limit is reached the module
can stop building paths, providing a more rapid response to the can stop building paths, providing a more rapid response to the
caller than one which builds all possible paths. caller than one which builds all possible paths.
Ultimately, it is up to the developer to determine how to handle the Ultimately, it is up to the developer to determine how to handle the
tradeoff between efficiency and provision of information. A tradeoff between efficiency and provision of information. A
developer could choose the middle ground by opting to implement some developer could choose the middle ground by opting to implement some
optimizations as elimination rules and others as not. A developer optimizations as elimination rules and others as not. A developer
could validate certificate signatures, or even check revocation could validate certificate signatures, or even check revocation
Cooper, Dzambasow,
Hesse, Joseph,
status while building the path, and then make decisions based upon status while building the path, and then make decisions based upon
the outcome of those checks as to whether to eliminate the the outcome of those checks as to whether to eliminate the
certificate in question. certificate in question.
This document suggests the following approach: This document suggests the following approach:
1) While building paths, eliminate any and all certificates that do 1) While building paths, eliminate any and all certificates that do
not satisfy all path validation requirements with the following not satisfy all path validation requirements with the following
exceptions: exceptions:
a. Do not check revocation status if it requires a directory a. Do not check revocation status if it requires a directory
lookup or network access lookup or network access
b. Do not check digital signatures
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
b. Do not check digital signatures (see Section 8.1 -- General
Considerations for Building A Certification Path û- for
additional considerations)
c. Do not check anything that can not be checked as part of the c. Do not check anything that can not be checked as part of the
iterative process of traversing the tree iterative process of traversing the tree
d. Create a detailed log, if this feature is enabled d. Create a detailed log, if this feature is enabled
e. If a path cannot be found, the path builder shifts to "mode e. If a path cannot be found, the path builder shifts to "mode
2" and allows the building of a single bad path. 2" and allows the building of a single bad path.
i. Return the path with a failure indicator as well as error i. Return the path with a failure indicator as well as error
information detailing why the path is bad. information detailing why the path is bad.
2) If path building succeeds, validate the path in accordance with 2) If path building succeeds, validate the path in accordance with
skipping to change at page 37, line 48 skipping to change at page 38, line 40
no valid path is found. Since the path building no valid path is found. Since the path building
software was designed to return the "best path first", software was designed to return the "best path first",
this is the path that should be shown to the user. this is the path that should be shown to the user.
As stated above, this document recommends that developers do not As stated above, this document recommends that developers do not
validate digital signatures or check revocation status as part of the validate digital signatures or check revocation status as part of the
path building process. This recommendation is based on two path building process. This recommendation is based on two
assumptions about PKI and its usage. First, signatures in a working assumptions about PKI and its usage. First, signatures in a working
PKI are usually good. Since signature validation is costly in terms PKI are usually good. Since signature validation is costly in terms
of processor time, it is better to delay signature checking until a of processor time, it is better to delay signature checking until a
complete path is found. Second, it is fairly uncommon in typical complete path is found and then check the signatures on each
certificate in the certification path starting with the trust anchor
(see section 8.1). Second, it is fairly uncommon in typical
application environments to encounter a revoked certificate; application environments to encounter a revoked certificate;
therefore, most certificates validated will not be revoked. As a therefore, most certificates validated will not be revoked. As a
result, it is better to delay retrieving CRLs or other revocation result, it is better to delay retrieving CRLs or other revocation
Cooper, Dzambasow,
Hesse, Joseph,
status information until a complete path has been found. This status information until a complete path has been found. This
reduces the probability of retrieving unneeded revocation status reduces the probability of retrieving unneeded revocation status
information while building paths. information while building paths.
3.3 Representing The Decision Tree Programmatically 3.3 Representing The Decision Tree
There are a multitude of ways to implement certification path There are a multitude of ways to implement certification path
building and as many ways to represent the decision tree in memory. building and as many ways to represent the decision tree in memory.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
The method described below is an approach that will work well with The method described below is an approach that will work well with
the optimization methods listed later in this document. Although the optimization methods listed later in this document. Although
this approach is the best the authors of this document have this approach is the best the authors of this document have
implemented, it is by no means the only way to implement it. implemented, it is by no means the only way to implement it.
Developers should tailor this approach to their own requirements or Developers should tailor this approach to their own requirements or
may find that another approach suits their environment, programming may find that another approach suits their environment, programming
language, or programming style. language, or programming style.
3.3.1 Node Representation For CA Entities 3.3.1 Node Representation For CA Entities
A "node" in the certification graph is a collection of CA A "node" in the certification graph is a collection of CA
certificates with identical subject distinguished names. Minimally, certificates with identical subject DNs. Minimally, for each node,
for each node, in order to fully implement the optimizations to in order to fully implement the optimizations to follow, the path
follow, the path building module will need to be able to keep track building module will need to be able to keep track of the following
of the following information: information:
1. Certificates contained in the node 1. Certificates contained in the node
2. Sorted order of the certificates 2. Sorted order of the certificates
3. "Current" certificate indicator 3. "Current" certificate indicator
4. The current policy set. (May be split into authority and user 4. The current policy set. (May be split into authority and user
constrained sets if desired.) constrained sets if desired.)
- It is suggested that encapsulating the policy set in an - It is suggested that encapsulating the policy set in an
object with logic for manipulating the set such as performing object with logic for manipulating the set such as performing
intersections, mappings, etc., will simplify implementation intersections, mappings, etc., will simplify implementation
5. Indicators (requireExplicitPolicy, inhibitPolicyMapping, 5. Indicators (requireExplicitPolicy, inhibitPolicyMapping,
anyPolicyInhibit) and corresponding skipCert values anyPolicyInhibit) and corresponding skipCert values
6. A method for indicating which certificates are eliminated or 6. A method for indicating which certificates are eliminated or
removing them from the node removing them from the node
- If nodes are recreated from the cache on demand, it may be - If nodes are recreated from the cache on demand, it may be
simpler to remove eliminated certificates from the node. simpler to remove eliminated certificates from the node.
7. A "next" indicator that allows the software to locate the next 7. A "next" indicator that points to the next node in the current
node in the current path path
8. A "previous" indicator that allows the software to locate the 8. A "previous" indicator that points to the previous node in the
previous node in the current path current path
3.3.2 Using Nodes to Iterate Over All Paths 3.3.2 Using Nodes to Iterate Over All Paths
In simplest form, a node is created, the certificates are sorted, the In simplest form, a node is created, the certificates are sorted, the
next subject distinguished name required is determined from the first next subject DN required is determined from the first certificate,
and a new node is attached to the certification path via the next
indicator. (Number seven above.) This process continues until the
path terminates. (Note: end entity certificates may not contain
subject DNs as allowed by [RFC 3280]. Since end entity certificates
by definition do not issue certificates, this has no impact on the
process.)
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
certificate, and a new node is attached to the certification path via . Certification Path Building January 2005
the next indicator. (Number seven above.) This process continues
until the path terminates.
Keeping in mind while that the following algorithm is designed to be Keeping in mind while that the following algorithm is designed to be
implemented using recursion, consider the example in Figure 12 and implemented using recursion, consider the example in Figure 12 and
assume that the only path in the diagram is valid for E is TA->A->B- assume that the only path in the diagram is valid for E is TA->A->B-
>E: >E:
If our path building module is building a path in the forward 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 direction for E, a node is first created for E. There are no
certificates to sort because only one certificate exists, so all certificates to sort because only one certificate exists, so all
initial values are loaded into the node from E. For example, the initial values are loaded into the node from E. For example, the
policy set is extracted from the certificate and stored in the node. 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 Next, the issuer DN (B) is read from E, and new node is created for B
is created for B containing both certificates issued to B. [B(A) and containing both certificates issued to B. [B(A) and B(C)]. The
B(C)]. The sorting rules are applied to these two certificates and sorting rules are applied to these two certificates and the sorting
the sorting algorithm returns B(C);B(A). This sorted order is stored algorithm returns B(C);B(A). This sorted order is stored and the
and the current indicator is set to B(C). Indicators are set and the current indicator is set to B(C). Indicators are set and the policy
policy sets are calculated to the extent possible with respect to sets are calculated to the extent possible with respect to B(C). The
B(C). The following diagram illustrates the current state with the following diagram illustrates the current state with the current
current certificate indicated with a "*". certificate indicated with a "*".
+-------------+ +---------------+ +-------------+ +---------------+
| Node 1 | | Node 2 | | Node 1 | | Node 2 |
| Subject: E |--->| Subject: B | | Subject: E |--->| Subject: B |
| Issuers: B* | | Issuers: C*,A | | Issuers: B* | | Issuers: C*,A |
+-------------+ +---------------+ +-------------+ +---------------+
Next, a node is created for C and all three certificates are added to Next, a node is created for C and all three certificates are added to
it. The sorting algorithm happens to return the certificates sorted it. The sorting algorithm happens to return the certificates sorted
in the following order: C(TA);C(A);C(B) in the following order: C(TA);C(A);C(B)
skipping to change at page 39, line 52 skipping to change at page 40, line 50
+-------------+ +---------------+ +------------------+ +-------------+ +---------------+ +------------------+
Recognizing that the trust anchor has been found, the path (TA->C->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 >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 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 current certificate indicator in node 3 to C(A), and adds the node
for A. for A.
+-------------+ +---------------+ +------------------+ +-------------+ +---------------+ +------------------+
| Node 1 | | Node 2 | | Node 3 | | Node 1 | | Node 2 | | Node 3 |
Cooper, Dzambasow,
Hesse, Joseph,
| Subject: E |--->| Subject: B |--->| Subject: C | | Subject: E |--->| Subject: B |--->| Subject: C |
| Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B | | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B |
+-------------+ +---------------+ +------------------+ +-------------+ +---------------+ +------------------+
| |
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
v v
+------------------+ +------------------+
| Node 4 | | Node 4 |
| Subject: A | | Subject: A |
| Issuers: TA*,C,B | | Issuers: TA*,C,B |
+------------------+ +------------------+
The path TA->A->C->B->E is validated and it fails. The path building 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 module now moves the current indicator in node 4 to A(C) and adds a
node for C. node for C.
skipping to change at page 40, line 52 skipping to change at page 41, line 50
node 3, and path building continues by first validating TA->C->A->C- 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 >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 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 current path and the current certificate indicator on node 4 is moved
to A(B). to A(B).
+-------------+ +---------------+ +------------------+ +-------------+ +---------------+ +------------------+
| Node 1 | | Node 2 | | Node 3 | | Node 1 | | Node 2 | | Node 3 |
| Subject: E |--->| Subject: B |--->| Subject: C | | Subject: E |--->| Subject: B |--->| Subject: C |
| Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B | | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B |
Cooper, Dzambasow,
Hesse, Joseph,
+-------------+ +---------------+ +------------------+ +-------------+ +---------------+ +------------------+
| |
v v
+------------------+ +------------------+
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
| Node 4 | | Node 4 |
| Subject: A | | Subject: A |
| Issuers: TA,C,B* | | Issuers: TA,C,B* |
+------------------+ +------------------+
Now a new node 5 is created for B. Just as with the prior node 5, if 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 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 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 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 have now been tried, so node 4 is removed from the path, and the
skipping to change at page 41, line 53 skipping to change at page 42, line 51
optimization methods a developer chooses to implement, and then optimization methods a developer chooses to implement, and then
adding the score for each test to a cumulative score for each adding the score for each test to a cumulative score for each
certificate. After this is completed for each certificate at a given certificate. After this is completed for each certificate at a given
branch point in the builder's decision tree, the certificates can be branch point in the builder's decision tree, the certificates can be
sorted so that the highest scoring certificate is selected first, the sorted so that the highest scoring certificate is selected first, the
second highest is selected second, etc. second highest is selected second, etc.
For example, suppose the path builder has only these two simple For example, suppose the path builder has only these two simple
sorting methods: sorting methods:
Cooper, Dzambasow,
Hesse, Joseph,
1) If the certificate has a subject key ID, +5 to score 1) If the certificate has a subject key ID, +5 to score
2) If the certificate has an authority key ID, +10 to score 2) If the certificate has an authority key ID, +10 to score
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
And it then examined three certificates: And it then examined three certificates:
1) Issued by CA 1; has authority key ID; score is 10 1) Issued by CA 1; has authority key ID; score is 10
2) Issued by CA 2; has subject key ID; score is 5 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 3) Issued by CA 1; has subject key ID and authority key ID; score is
15 15
The three certificates are sorted in descending order starting with The three certificates are sorted in descending order starting with
the highest score: 3, 1, and 2. The path building software should the highest score: 3, 1, and 2. The path building software should
first try building the path through certificate 3. Failing that, it first try building the path through certificate 3. Failing that, it
skipping to change at page 42, line 50 skipping to change at page 43, line 49
are cases where most any sorting method could lead to inefficient are cases where most any sorting method could lead to inefficient
path building. The desired behavior is that although one method may path building. The desired behavior is that although one method may
lead the algorithm in the wrong direction for a given situation or lead the algorithm in the wrong direction for a given situation or
configuration, the remaining methods will overcome the errant configuration, the remaining methods will overcome the errant
method(s) and send the path traversal down the correct branch of the 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 tree more often than not. This certainly will not be true for every
environment and configuration, and these methods may need to be environment and configuration, and these methods may need to be
tweaked for further optimization in the application's target tweaked for further optimization in the application's target
operating environment. operating environment.
Cooper, Dzambasow,
Hesse, Joseph,
As a final note, the list contained in this document is not intended As a final note, the list contained in this document is not intended
to be exhaustive. A developer may desire to define additional to be exhaustive. A developer may desire to define additional
sorting methods if the operating environment dictates the need. sorting methods if the operating environment dictates the need.
3.5 Selected Methods for Sorting Certificates 3.5 Selected Methods for Sorting Certificates
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
The reader should draw no specific conclusions as to the relative The reader should draw no specific conclusions as to the relative
merits or scores for each of the following methods based upon the merits or scores for each of the following methods based upon the
order in which they appear. The relative merit of any sorting order in which they appear. The relative merit of any sorting
criteria is completely dependent on the specifics of the operating criteria is completely dependent on the specifics of the operating
environment. For most any method, an example can be created to environment. For most any method, an example can be created to
demonstrate the method is effective and a counter-example could be demonstrate the method is effective and a counter-example could be
designed to demonstrate that it is ineffective. designed to demonstrate that it is ineffective.
Each sorting method is independent and may (or may not) be used to 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 assign additional scores to each certificate tested. It is up to the
skipping to change at page 43, line 51 skipping to change at page 44, line 47
certificate X may be invalidated due to name constraints by the certificate X may be invalidated due to name constraints by the
addition of certificate Y. At this decision point only, Y could be addition of certificate Y. At this decision point only, Y could be
eliminated from further consideration. At some future decision eliminated from further consideration. At some future decision
point, while building this same path, the addition of Y may not point, while building this same path, the addition of Y may not
invalidate the path. invalidate the path.
For some other sorting methods, certificates could be eliminated from For some other sorting methods, certificates could be eliminated from
the process entirely. For example, certificates with unsupported the process entirely. For example, certificates with unsupported
signature algorithms could not be included in any path and validated. signature algorithms could not be included in any path and validated.
While the path builder may certainly be designed to operate in this While the path builder may certainly be designed to operate in this
Cooper, Dzambasow,
Hesse, Joseph,
fashion, it is also sufficient to always discard certificates only fashion, it is also sufficient to always discard certificates only
for a given decision point regardless of cause. for a given decision point regardless of cause.
3.5.1 basicConstraints is Present and cA Equals True 3.5.1 basicConstraints is Present and cA Equals True
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Number of possible values: Binary Number of possible values: Binary
Components required: None Components required: None
Forward Method: Certificates with basicConstraints present and Forward Method: Certificates with basicConstraints present and
cA=TRUE, or those designated as CA certificates out-of-band have cA=TRUE, or those designated as CA certificates out-of-band have
priority. Certificates without basicConstraints, with priority. Certificates without basicConstraints, with
basicConstraints and cA=FALSE, or those that are not designated as CA basicConstraints and cA=FALSE, or those that are not designated as CA
certificates out-of-band may be eliminated or have zero priority. certificates out-of-band may be eliminated or have zero priority.
Reverse Method: Same as forward except with regard to end entity Reverse Method: Same as forward except with regard to end entity
skipping to change at page 44, line 34 skipping to change at page 45, line 30
verified via an out-of-band mechanism. A valid path cannot be built verified via an out-of-band mechanism. A valid path cannot be built
if this condition is not met. if this condition is not met.
3.5.2 Recognized Signature Algorithms 3.5.2 Recognized Signature Algorithms
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Number of possible values: Binary Number of possible values: Binary
Components required: None Components required: None
Forward Method: Certificates containing recognized signature and Forward Method: Certificates containing recognized signature and
public key algorithms have priority. public key algorithms [PKIXALGS] have priority.
Reverse Method: Same as forward. Reverse Method: Same as forward.
Justification: If the path building software is not capable of Justification: If the path building software is not capable of
processing the signatures associated with the certificate, the processing the signatures associated with the certificate, the
certification path cannot be validated. certification path cannot be validated.
3.5.3 keyUsage is Correct 3.5.3 keyUsage is Correct
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Number of possible values: Binary Number of possible values: Binary
Components required: None Components required: None
Forward Method: If keyUsage is present, certificates with Forward Method: If keyUsage is present, certificates with
keyCertSign set have 100% priority. If keyUsage is present and keyCertSign set have 100% priority. If keyUsage is present and
keyCertSign is not set, the certificate may be eliminated or have keyCertSign is not set, the certificate may be eliminated or have
zero priority. All others have zero priority. zero priority. All others have zero priority.
Cooper, Dzambasow,
Hesse, Joseph,
Reverse Method: Same as forward except with regard to end entity Reverse Method: Same as forward except with regard to end entity
certificates at the terminus of the path. certificates at the terminus of the path.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Justification: A valid certification path can not be built through a Justification: A valid certification path can not be built through a
CA certificate with inappropriate keyUsage. Note that CA certificate with inappropriate keyUsage. Note that
digitalSignature is NOT required to be set in a CA certificate. digitalSignature is not required to be set in a CA certificate.
3.5.4 Time (T) Falls within the Certificate Validity 3.5.4 Time (T) Falls within the Certificate Validity
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Number of possible values: Binary Number of possible values: Binary
Components required: None Components required: None
Forward Method: Certificates that contain the required time (T) Forward Method: Certificates that contain the required time (T)
within their validity period have 100% priority. Otherwise, the within their validity period have 100% priority. Otherwise, the
certificate is eliminated or has priority zero. certificate is eliminated or has priority zero.
Reverse Method: Same as forward. Reverse Method: Same as forward.
Justification: A valid certification path cannot be built if T falls Justification: A valid certification path cannot be built if T falls
outside of the certificate validity period. outside of the certificate validity period.
NOTE: Special care should be taken to return a meaningful error to NOTE: Special care should be taken to return a meaningful error to
the caller, especially in the event the target certificate does not the caller, especially in the event the target certificate does not
meet this criterion, if this sorting method is used for elimination. meet this criterion, if this sorting method is used for elimination.
(e.g., the certificate is expired). (e.g., the certificate is expired or is not yet valid).
3.5.5 Certificate Was Previously Validated 3.5.5 Certificate Was Previously Validated
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: Certification Path Cache Components required: Certification Path Cache
Forward Method: A certificate that is present in the certification Forward Method: A certificate that is present in the certification
path cache has priority. path cache has priority.
Reverse Method: Does not apply. (The validity of a certificate vs. Reverse Method: Does not apply. (The validity of a certificate vs.
unknown validity does not infer anything about the correct direction unknown validity does not infer anything about the correct direction
in the decision tree. In other words, knowing the validity of a CA in the decision tree. In other words, knowing the validity of a CA
certificate does not indicate that the target is more likely found certificate does not indicate that the target is more likely found
through that path than another.) through that path than another.)
Justification: Certificates in the path cache have been validated Justification: Certificates in the path cache have been validated
previously. Assuming the initial constraints have not changed, it is previously. Assuming the initial constraints have not changed, it is
highly likely that the path from that certificate to a trust anchor highly likely that the path from that certificate to a trust anchor
is still valid. (Changes to the initial constraints may cause a is still valid. (Changes to the initial constraints may cause a
Cooper, Dzambasow,
Hesse, Joseph,
certificate previously considered valid to no longer be considered certificate previously considered valid to no longer be considered
valid.) valid.)
Note: It is important that items in the path cache have appropriate Note: It is important that items in the path cache have appropriate
life times. For example, it could be inappropriate to cache a life times. For example, it could be inappropriate to cache a
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
relationship beyond the period the related CRL will be trusted by the relationship beyond the period the related CRL will be trusted by the
application. It is also critical to consider certificates and CRLs application. It is also critical to consider certificates and CRLs
farther up the path when setting cache lifetimes. For example, if the farther up the path when setting cache lifetimes. For example, if the
issuer certificate expires in ten days, but the issued certificate is issuer certificate expires in ten days, but the issued certificate is
valid for 20 days, caching the relationship beyond 10 days would be valid for 20 days, caching the relationship beyond 10 days would be
inappropriate. inappropriate.
3.5.6 Previously Verified Signatures 3.5.6 Previously Verified Signatures
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
skipping to change at page 46, line 51 skipping to change at page 47, line 48
3.5.7 Path Length Constraints 3.5.7 Path Length Constraints
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Number of possible values: Binary Number of possible values: Binary
Components required: None Components required: None
Forward Method: Certificates with basic constraints present and Forward Method: Certificates with basic constraints present and
containing a path length constraint that would invalidate the current containing a path length constraint that would invalidate the current
path (the current length is known since the software is building from path (the current length is known since the software is building from
Cooper, Dzambasow,
Hesse, Joseph,
the target certificate) may be eliminated or set to zero priority. the target certificate) may be eliminated or set to zero priority.
Otherwise, the priority is 100%. Otherwise, the priority is 100%.
Reverse Method: This method may be applied in reverse. To apply it, Reverse Method: This method may be applied in reverse. To apply it,
the builder keeps a current path length constraint variable and then the builder keeps a current path length constraint variable and then
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
sets zero priority for (or eliminates) certificates that would sets zero priority for (or eliminates) certificates that would
violate the constraint. violate the constraint.
Justification: A valid path cannot be built if the path length Justification: A valid path cannot be built if the path length
constraint has been violated. constraint has been violated.
3.5.8 Name Constraints 3.5.8 Name Constraints
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Number of possible values: Binary Number of possible values: Binary
skipping to change at page 47, line 52 skipping to change at page 48, line 49
OCSP response is available for a certificate, and identifies the OCSP response is available for a certificate, and identifies the
certificate as valid, the certificate has priority. If an OCSP certificate as valid, the certificate has priority. If an OCSP
response is available for a certificate, and identifies the response is available for a certificate, and identifies the
certificate as invalid, the certificate has zero priority. certificate as invalid, the certificate has zero priority.
Reverse Method: Same as Forward. Reverse Method: Same as Forward.
Alternately, the certificate may be eliminated if the CRL or OCSP Alternately, the certificate may be eliminated if the CRL or OCSP
response is verified. That is, fully verify the CRL or OCSP response response is verified. That is, fully verify the CRL or OCSP response
signature and relationship to the certificate in question in signature and relationship to the certificate in question in
Cooper, Dzambasow,
Hesse, Joseph,
accordance with [RFC 3280]. While this is viable, the signature accordance with [RFC 3280]. While this is viable, the signature
verification required make it less attractive as an elimination verification required make it less attractive as an elimination
method. It is suggested that this method only be used for sorting and method. It is suggested that this method only be used for sorting and
that CRLs and OCSP responses are validated post path building. that CRLs and OCSP responses are validated post path building.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Justification: Certificates known to be not revoked can be Justification: Certificates known to be not revoked can be
considered more likely to be valid than certificates for which the considered more likely to be valid than certificates for which the
revocation status is unknown. This is further justified if CRL or revocation status is unknown. This is further justified if CRL or
OCSP response validation is performed post path validation - CRLs or OCSP response validation is performed post path validation - CRLs or
OCSP responses are only retrieved when complete paths are found. OCSP responses are only retrieved when complete paths are found.
NOTE: Special care should be taken to allow meaningful errors to NOTE: Special care should be taken to allow meaningful errors to
propagate to the caller, especially in cases where the target propagate to the caller, especially in cases where the target
certificate is revoked. If a path builder eliminates certificates certificate is revoked. If a path builder eliminates certificates
using CRLs or OCSP responses, some status information should be using CRLs or OCSP responses, some status information should be
skipping to change at page 48, line 52 skipping to change at page 49, line 49
evaluate to true while the other method could evaluate to zero. evaluate to true while the other method could evaluate to zero.
3.5.11 Issuer Found in the Application Protocol 3.5.11 Issuer Found in the Application Protocol
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: Certification Path Cache Components required: Certification Path Cache
Forward Method: If the issuer of a certificate sent by the target Forward Method: If the issuer of a certificate sent by the target
matches the signer if the certificate you are looking at, issuer of a matches the signer if the certificate you are looking at, issuer of a
certificate sent by the target through the application protocol
(SSL/TLS, S/MIME, etc.), that certificate has priority.
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
certificate sent by the target through the application protocol . Certification Path Building January 2005
(SSL/TLS, S/MIME, etc.), that certificate has priority.
Reverse Method: If the subject of a certificate matches the issuer Reverse Method: If the subject of a certificate matches the issuer
of a certificate sent by the target through the application protocol of a certificate sent by the target through the application protocol
(SSL/TLS, S/MIME, etc.), that certificate has priority. (SSL/TLS, S/MIME, etc.), that certificate has priority.
Justification: The application protocol may contain certificates Justification: The application protocol may contain certificates
which the sender considers valuable to certification path building, which the sender considers valuable to certification path building,
and are more likely to lead to a path to the target certificate. and are more likely to lead to a path to the target certificate.
3.5.12 Matching Key Identifiers (KIDs) 3.5.12 Matching Key Identifiers (KIDs)
skipping to change at page 49, line 40 skipping to change at page 50, line 39
Reverse Method: Certificates whose AKID matches the current Reverse Method: Certificates whose AKID matches the current
certificate's SKID have highest priority. Certificates without an certificate's SKID have highest priority. Certificates without an
AKID have medium priority. Certificates whose AKID does not match AKID have medium priority. Certificates whose AKID does not match
the current certificate's SKID (if both are present) have zero the current certificate's SKID (if both are present) have zero
priority. If the certificate expresses the issuer name and serial priority. If the certificate expresses the issuer name and serial
number in the AKID, certificates that match both these identifiers in number in the AKID, certificates that match both these identifiers in
the current certificate have highest priority. Certificates that the current certificate have highest priority. Certificates that
match only the issuer name in the AKID have medium priority. match only the issuer name in the AKID have medium priority.
Justification: KID matching is a very useful mechanism for guiding Justification: Key Identifier (KID) matching is a very useful
path building (that is their purpose in the certificate) and should mechanism for guiding path building (that is their purpose in the
therefore be assigned a heavy weight. certificate) and should therefore be assigned a heavy weight.
NOTE: Although required to be present by [RFC 3280], it is extremely NOTE: Although required to be present by [RFC 3280], it is extremely
important that KIDs be used ONLY as sorting criteria or hint during important that KIDs be used only as sorting criteria or hint during
certification path building - KIDs are not required to match during certification path building - KIDs are not required to match during
certification path validation and cannot be used to eliminate certification path validation and cannot be used to eliminate
certificates. This is of critical importance for interoperating certificates. This is of critical importance for interoperating
across domains and multi-vendor implementations where the KIDs may across domains and multi-vendor implementations where the KIDs may
not be calculated in the same fashion. not be calculated in the same fashion.
Cooper, Dzambasow,
Hesse, Joseph,
3.5.13 Policy Processing 3.5.13 Policy Processing
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Number of possible values: Three Number of possible values: Three
Components required: None Components required: None
Forward Method: Certificates that satisfy Forward Policy Chaining Forward Method: Certificates that satisfy Forward Policy Chaining
have priority. (See section 4 entitled "Forward Policy Chaining" for have priority. (See section 4 entitled "Forward Policy Chaining" for
details.) If the caller provided an initial-policy-set and did not details.) If the caller provided an initial-policy-set and did not
set the initial-require-explicit flag, the weight of this sorting set the initial-require-explicit flag, the weight of this sorting
method should be increased. If the initial-require-explicit-policy method should be increased. If the initial-require-explicit-policy
flag was set by the caller or by a certificate, certificates may be flag was set by the caller or by a certificate, certificates may be
eliminated. eliminated.
skipping to change at page 50, line 52 skipping to change at page 51, line 51
policies will serve well in that case. In the case where require- policies will serve well in that case. In the case where require-
explicit-policy is set by certificates or the caller, certificates explicit-policy is set by certificates or the caller, certificates
can be eliminated with this method. can be eliminated with this method.
3.5.14 Policies Intersect The Sought Policy Set 3.5.14 Policies Intersect The Sought Policy Set
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Additive Number of possible values: Additive
Components required: None Components required: None
Cooper, Dzambasow,
Hesse, Joseph,
Forward Method: Certificates that assert policies found in the Forward Method: Certificates that assert policies found in the
initial-acceptable-policy-set have priority. Each additional initial-acceptable-policy-set have priority. Each additional
matching policy could have an additive affect on the total score. matching policy could have an additive affect on the total score.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Alternately, this could be binary; it matches 1 or more, or matches Alternately, this could be binary; it matches 1 or more, or matches
none. none.
Reverse Method: Certificates that assert policies found in the Reverse Method: Certificates that assert policies found in the
target certificate or map policies to those found in the target target certificate or map policies to those found in the target
certificate have priority. Each additional matching policy could certificate have priority. Each additional matching policy could
have an additive affect on the total score. Alternately, this could have an additive affect on the total score. Alternately, this could
be binary; it matches 1 or more, or matches none. be binary; it matches 1 or more, or matches none.
Justification: In the forward direction, as the path draws near to Justification: In the forward direction, as the path draws near to
the trusted root certificate in a cross certified environment, the the trust anchor in a cross certified environment, the policies
policies asserted in the CA certificates will match those in the asserted in the CA certificates will match those in the caller's
caller's domain. Since the initial acceptable policy set is domain. Since the initial acceptable policy set is specified in the
specified in the caller's domain, matches may indicate that the path caller's domain, matches may indicate that the path building is
building is drawing nearer to a desired trust anchor. In the reverse drawing nearer to a desired trust anchor. In the reverse direction,
direction, finding policies that match those of the target finding policies that match those of the target certificate may
certificate may indicate the path is drawing near to the target's indicate the path is drawing near to the target's domain.
domain.
3.5.15 Endpoint Distinguished Name Matching 3.5.15 Endpoint Distinguished Name (DN) Matching
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: None Components required: None
Forward Method: Certificates whose issuer exactly matches a trust Forward Method: Certificates whose issuer exactly matches a trust
anchor subject DN have priority. anchor subject DN have priority.
Reverse Method: Certificates whose subject exactly matches the Reverse Method: Certificates whose subject exactly matches the
target entity issuer DN have priority. target entity issuer DN have priority.
Justification: In the forward direction, if a certificate's issuer Justification: In the forward direction, if a certificate's issuer
DN matches a trust anchor's DN, then it may complete the path. In DN matches a trust anchor's DN [X.501], then it may complete the
the reverse direction, if the certificate's subject DN matches the path. In the reverse direction, if the certificate's subject DN
issuer DN of the target certificate, this may be the last certificate matches the issuer DN of the target certificate, this may be the last
required to complete the path. certificate required to complete the path.
3.5.16 Relative Distinguished Name (RDN) Matching 3.5.16 Relative Distinguished Name (RDN) Matching
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Sliding Scale Number of possible values: Sliding Scale
Components required: None Components required: None
Cooper, Dzambasow,
Hesse, Joseph,
Forward Method: Certificates that match more ordered RDNs between Forward Method: Certificates that match more ordered RDNs between
the issuer DN and a trust anchor DN have priority. When all the RDNs the issuer DN and a trust anchor DN have priority. When all the RDNs
match, this yields the highest priority. match, this yields the highest priority.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Reverse Method: Certificates with subject DNs that match more RDNs Reverse Method: Certificates with subject DNs that match more RDNs
with the target's issuer DN have higher priority. When all the RDNs with the target's issuer DN have higher priority. When all the RDNs
match, this yields the highest priority. match, this yields the highest priority.
Justification: In PKIs the DNs are frequently constructed in a tree Justification: In PKIs the DNs are frequently constructed in a tree
like fashion. Higher numbers of matches may indicate that the trust like fashion. Higher numbers of matches may indicate that the trust
anchor is to be found in that direction within the tree. Note that 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 in the case where all the RDNs match [X.501], this sorting method
mirror the preceding one. However, this sorting method should be appears to mirror the preceding one. However, this sorting method
capable of producing a 100% weight even if the issuer DN has more should be capable of producing a 100% weight even if the issuer DN
RDNs than the trust anchor. The Issuer DN need only contain all the has more RDNs than the trust anchor. The Issuer DN need only contain
RDNs (in order) of the trust anchor. all the RDNs (in order) of the trust anchor.
NOTE: In the case where all RDNs match, this sorting method mirrors NOTE: In the case where all RDNs match, this sorting method mirrors
the functionality of the preceding one. This allows for partial the functionality of the preceding one. This allows for partial
matches to be weighted differently from exact matches. Additionally, matches to be weighted differently from exact matches. Additionally,
it should be noted that this method can require a lot of processing it should be noted that this method can require a lot of processing
if many trust anchors are present. if many trust anchors are present.
3.5.17 Certificates are Retrieved from cACertificate 3.5.17 Certificates are Retrieved from cACertificate Directory Attribute
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: Certificate Cache with flags for the attribute Components required: Certificate Cache with flags for the attribute
from where the certificate was retrieved from where the certificate was retrieved and Remote Certificate
Storage / Retrieval using a directory
Forward Method: Certificates retrieved from the cACertificate Forward Method: Certificates retrieved from the cACertificate
attribute have priority over certificates retrieved from the directory attribute have priority over certificates retrieved from
crossCertificatePair attribute. (See [RFC 2587]) the crossCertificatePair attribute. (See [RFC 2587])
Reverse Method: Does not apply. Reverse Method: Does not apply.
Justification: The cACertificate attribute contains certificates Justification: The cACertificate directory attribute contains
issued from local sources and self issued certificates. By using the certificates issued from local sources and self issued certificates.
cACertificate attribute before the crossCertificatePair attribute, By using the cACertificate directory attribute before the
the path building algorithm will (depending on the local PKI crossCertificatePair attribute, the path building algorithm will
configuration) tend to demonstrate a preference for the local PKI (depending on the local PKI configuration) tend to demonstrate a
before venturing to external cross-certified PKIs. Not only do most preference for the local PKI before venturing to external cross-
of today's PKI applications spend most of their time processing certified PKIs. Not only do most of today's PKI applications spend
information from the local (user's own) PKI, but the local PKI is most of their time processing information from the local (user's own)
usually very efficient to traverse due to proximity and network PKI, but the local PKI is usually very efficient to traverse due to
speed. proximity and network speed.
3.5.18 Consistent Public Key and Signature Algorithms 3.5.18 Consistent Public Key and Signature Algorithms
Cooper, Dzambasow,
Hesse, Joseph,
May be used to eliminate certificates: Yes May be used to eliminate certificates: Yes
Number of possible values: Binary Number of possible values: Binary
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Components required: None Components required: None
Forward Method: If the public key in the issuer certificate matches Forward Method: If the public key in the issuer certificate matches
the algorithm used to sign the subject certificate, then it has the algorithm used to sign the subject certificate, then it has
priority. (Certificates with unmatched public key and signature priority. (Certificates with unmatched public key and signature
algorithms may be eliminated.) algorithms may be eliminated.)
Reverse Method: If the public key in the current certificate matches Reverse Method: If the public key in the current certificate matches
the algorithm used to sign the subject certificate, then it has the algorithm used to sign the subject certificate, then it has
priority. (Certificates with unmatched public key and signature priority. (Certificates with unmatched public key and signature
skipping to change at page 53, line 48 skipping to change at page 54, line 48
certificates with similar names first tends to make a more efficient certificates with similar names first tends to make a more efficient
path builder. Cross certificates issued from external domains will path builder. Cross certificates issued from external domains will
generally match fewer RDNs (if any), whereas certificates in the generally match fewer RDNs (if any), whereas certificates in the
local domain will frequently match multiple RDNs. local domain will frequently match multiple RDNs.
3.5.20 Certificates in the Certification Cache 3.5.20 Certificates in the Certification Cache
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Three Number of possible values: Three
Components required: Local Certificate Cache and Remote Certificate Components required: Local Certificate Cache and Remote Certificate
Storage / Retrieval (E.g., LDAP repository) Storage / Retrieval (e.g., LDAP directory as the repository)
Cooper, Dzambasow,
Hesse, Joseph,
Forward Method: A certificate whose issuer certificate is present in Forward Method: A certificate whose issuer certificate is present in
the certificate cache and populated with certificates has higher the certificate cache and populated with certificates has higher
priority. A certificate whose issuerÆs entry is fully populated with priority. A certificate whose issuerÆs entry is fully populated with
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
current data (all certificate attributes have been searched within current data (all certificate attributes have been searched within
the timeout period.) has higher priority. the timeout period.) has higher priority.
Reverse Method: If the subject of a certificate is present in the Reverse Method: If the subject of a certificate is present in the
certificate cache and populated with certificates then it has higher certificate cache and populated with certificates then it has higher
priority. If the entry is fully populated with current data (all priority. If the entry is fully populated with current data (all
certificate attributes have been searched within the timeout period.) certificate attributes have been searched within the timeout period.)
then it has higher priority. then it has higher priority.
Justification: The presence of required directory values populated Justification: The presence of required directory values populated
skipping to change at page 54, line 40 skipping to change at page 55, line 39
Forward Method: Certificates have priority if the issuer's CRL entry Forward Method: Certificates have priority if the issuer's CRL entry
exists and is populated with current data in the CRL cache. exists and is populated with current data in the CRL cache.
Reverse Method: Certificates have priority if the subject's CRL Reverse Method: Certificates have priority if the subject's CRL
entry exists and is populated with current data in the CRL cache. entry exists and is populated with current data in the CRL cache.
Justification: If revocation is checked only after a complete path Justification: If revocation is checked only after a complete path
has been found, this indicates that a complete path has been found has been found, this indicates that a complete path has been found
through this entity at some past point, so a path still likely through this entity at some past point, so a path still likely
exists. This also helps reduce LDAP lookups until necessary. exists. This also helps reduce remote retrievals until necessary.
3.6 Certificate Sorting Methods For Revocation Signer Certification 3.6 Certificate Sorting Methods For Revocation Signer Certification
Paths Paths
Unless using a locally configured OCSP responder or some other Unless using a locally configured OCSP responder or some other
locally configured trusted revocation status service, certificate locally configured trusted revocation status service, certificate
revocation information is expected to be provided by the PKI that revocation information is expected to be provided by the PKI that
issued the certificate. It follows that when building a certification issued the certificate. It follows that when building a certification
path for a Revocation Signer certificate that it is desirable to path for a Revocation Signer certificate that it is desirable to
confine the building algorithm to the PKI that issued the confine the building algorithm to the PKI that issued the
certificate. The following sorting methods seek to order possible certificate. The following sorting methods seek to order possible
paths so that the intended Revocation Signer certification path is
found first.
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
paths so that the intended Revocation Signer certification path is . Certification Path Building January 2005
found first.
These sorting methods are not intended to be used in lieu of the ones These sorting methods are not intended to be used in lieu of the ones
described in the previous section; they are most effective when used described in the previous section; they are most effective when used
in conjunction with those in section 3.5. Some sorting criteria below in conjunction with those in section 3.5. Some sorting criteria below
have identical names as those in the preceding section. This have identical names as those in the preceding section. This
indicates that the sorting criteria described in the preceding indicates that the sorting criteria described in the preceding
section are modified slightly when building the Revocation Signer section are modified slightly when building the Revocation Signer
certification path. certification path.
3.6.1 Identical Trust Anchors 3.6.1 Identical Trust Anchors
skipping to change at page 55, line 27 skipping to change at page 56, line 26
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: Is-revocation-signer indicator and the Components required: Is-revocation-signer indicator and the
Certification Authority's trust anchor Certification Authority's trust anchor
Forward Method: Not applicable. Forward Method: Not applicable.
Reverse Method: Path building should begin from the same trust Reverse Method: Path building should begin from the same trust
anchor used to validate the Certification Authority before trying any anchor used to validate the Certification Authority before trying any
other trust anchors. If any trust anchors exist with different public other trust anchors. If any trust anchors exist with different public
key but an identical subject distinguished name to that of the key but an identical subject DN to that of the Certification
Certification Authority's trust anchor, those should be tried prior Authority's trust anchor, those should be tried prior to those with
to those with mismatched names. mismatched names.
Justification: The revocation information for a given certificate Justification: The revocation information for a given certificate
should be produced by the PKI that issues the certificate, so should be produced by the PKI that issues the certificate, so
building a path from a different trust anchor than the Certification building a path from a different trust anchor than the Certification
Authority's is not desirable. Authority's is not desirable.
3.6.2 Endpoint Distinguished Name Matching (3.5.15) 3.6.2 Endpoint Distinguished Name (DN) Matching
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: Is-revocation-signer indicator and the Components required: Is-revocation-signer indicator and the
Certification Authority's trust anchor Certification Authority's trust anchor
Forward Method: Operates identically to the sorting method described Forward Method: Operates identically to the sorting method described
in 3.5.15 except that instead of performing the matching against all in 3.5.15 except that instead of performing the matching against all
trust anchors, the distinguished name matching is performed only trust anchors, the DN matching is performed only against the trust
against the trust anchor distinguished name for the Certification anchor DN used to validate the CA certificate.
Authority certificate.
Reverse Method: No change for Revocation Signer's certification Reverse Method: No change for Revocation Signer's certification
path. path.
Cooper, Dzambasow,
Hesse, Joseph,
Justification: The revocation information for a given certificate Justification: The revocation information for a given certificate
should be produced by the PKI that issues the certificate, so should be produced by the PKI that issues the certificate, so
building a path to a different trust anchor than the Certification building a path to a different trust anchor than the CA's is not
Authority's is not desirable. This sorting method helps to guide
forward direction path building toward the Certification Authority's
trust anchor.
3.6.3 Relative Distinguished Name (RDN) Matching (3.5.16) Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
desirable. This sorting method helps to guide forward direction path
building toward the trust anchor used to validate the CA certificate.
3.6.3 Relative Distinguished Name (RDN) Matching
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Sliding Scale Number of possible values: Sliding Scale
Components required: Is-revocation-signer indicator and the Components required: Is-revocation-signer indicator and the
Certification Authority's trust anchor Certification Authority's trust anchor
Forward Method: Operates identically to the sorting method described Forward Method: Operates identically to the sorting method described
in 3.5.16 except that instead of performing the RDN matching against in 3.5.16 except that instead of performing the RDN matching against
all trust anchors, the matching is performed only against the trust all trust anchors, the matching is performed only against the trust
anchor used to validate the Certification Authority certificate. anchor DN used to validate the CA certificate.
Reverse Method: No change for Revocation Signer's certification Reverse Method: No change for Revocation Signer's certification
path. path.
Justification: The revocation information for a given certificate Justification: The revocation information for a given certificate
should be produced by the PKI that issues the certificate, so should be produced by the PKI that issues the certificate, so
building a path to a different trust anchor than the Certification building a path to a different trust anchor than the CA's is not
Authority's is not desirable. This sorting method helps to guide desirable. This sorting method helps to guide forward direction path
forward direction path building toward the Certification Authority's building toward the trust anchor used to validate the CA certificate.
trust anchor.
3.6.4 Identical Intermediate Names 3.6.4 Identical Intermediate Names
May be used to eliminate certificates: No May be used to eliminate certificates: No
Number of possible values: Binary Number of possible values: Binary
Components required: Is-revocation-signer indicator and the Components required: Is-revocation-signer indicator and the
Certification Authority's complete certification path Certification Authority's complete certification path
Forward Method: If the issuer distinguished name in the certificate Forward Method: If the issuer DN in the certificate matches the
matches the issuer distinguished name of a certificate in the issuer DN of a certificate in the Certification Authority's path, it
Certification Authority's path, it has higher priority. has higher priority.
Reverse Method: If the subject distinguished name in the certificate Reverse Method: If the subject DN in the certificate matches the
matches the subject distinguished name of a certificate in the subject DN of a certificate in the Certification Authority's path, it
Certification Authority's path, it has higher priority. has higher priority.
Justification: Following the same path as the Certificate should Justification: Following the same path as the Certificate should
deter the path building algorithm from wandering in an inappropriate deter the path building algorithm from wandering in an inappropriate
direction. Note that this sorting method is indifferent to whether direction. Note that this sorting method is indifferent to whether
the certificate is self-issued. This is beneficial because it would the certificate is self-issued. This is beneficial because it would
Cooper, Dzambasow,
Hesse, Joseph,
be undesirable to lower the priority of a re-key certificate in this be undesirable to lower the priority of a re-key certificate in this
situation. situation.
4. Forward Policy Chaining 4. Forward Policy Chaining
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
It is tempting to jump to the conclusion that certificate policies It is tempting to jump to the conclusion that certificate policies
offer little assistance to path building when building from the offer little assistance to path building when building from the
target certificate. It's easy to understand the "validate as you go" 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 approach from the trust anchor and much less obvious that any value
value can be derived in the other direction. However, since policy can be derived in the other direction. However, since policy
validation consists of the intersection of the issuer policy set with validation consists of the intersection of the issuer policy set with
the subject policy set and the mapping of policies from the issuer the subject policy set and the mapping of policies from the issuer
set to the subject set, policy validation can be done while building 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 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 a matter of reversing the procedure. That is not to say this is
quite as ideal as policy validation when building from the trust quite as ideal as policy validation when building from the trust
anchor, but it does offer a method that can be used to mostly anchor, but it does offer a method that can be used to mostly
eliminate what has been long considered a weakness inherent to eliminate what has been long considered a weakness inherent to
building in the forward (from the target certificate) direction. building in the forward (from the target certificate) direction.
4.1 Simple Intersection 4.1 Simple Intersection
The most basic form of policy processing is the intersection of the The most basic form of policy processing is the intersection of the
policy sets from the first CA certificate through the target / end policy sets from the first CA certificate through the target
entity certificate. Fortunately, the intersection of policy sets certificate. Fortunately, the intersection of policy sets will
will always yield the same final set regardless of the order of always yield the same final set regardless of the order of
intersection. This allows processing of policy set intersections in intersection. This allows processing of policy set intersections in
either direction. For example, if the trust anchor issues a CA 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 (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 (B) with policies {X,Y}, and CA B then issues a third CA
certificate (C) with policy set {Y,G}, one normally calculates the certificate (C) with policy set {Y,G}, one normally calculates the
policy set from the trust anchor as follows: policy set from the trust anchor as follows:
1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y} 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 2) Intersect that result, {X,Y} with C{Y,G} to yield the final set
{Y} {Y}
skipping to change at page 57, line 53 skipping to change at page 58, line 50
The other direction is exactly the same procedure, only in reverse: 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} 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 2) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
{Y} {Y}
Just like in the reverse direction, it has been shown that Just like in the reverse direction, it has been shown that
certificate C is good for policy Y, but this time in the forward certificate C is good for policy Y, but this time in the forward
direction. direction.
Cooper, Dzambasow,
Hesse, Joseph,
When building in the forward direction, policy processing is handled When building in the forward direction, policy processing is handled
in much the same fashion as it is in reverse - the software lends in much the same fashion as it is in reverse - the software lends
preference to certificates that propagate policies. Neither approach preference to certificates that propagate policies. Neither approach
guarantees that a path with valid policies will be found, but rather guarantees that a path with valid policies will be found, but rather
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
both approaches help guide the path in the direction it should go in both approaches help guide the path in the direction it should go in
order for the policies to propagate. order for the policies to propagate.
If the caller has supplied an initial-acceptable-policy set, there is If the caller has supplied an initial-acceptable-policy set, there is
less value in using it when building in the forward direction unless less value in using it when building in the forward direction unless
the caller also set inhibit-policy-mapping. In that case, the path the caller also set inhibit-policy-mapping. In that case, the path
builder can further constrain the path building to propagating builder can further constrain the path building to propagating
policies that exist in the initial-acceptable-policy-set. However, policies that exist in the initial-acceptable-policy-set. However,
even if the inhibit-policy-mapping is not set, the initial-policy-set 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 can still be used to guide the path building toward the desired trust
skipping to change at page 58, line 51 skipping to change at page 59, line 49
reversing the mapping procedure. This procedure is limited by one reversing the mapping procedure. This procedure is limited by one
important aspect; if policy mapping has occurred in the forward important aspect; if policy mapping has occurred in the forward
direction, there is no mechanism by which it can be known in advance 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 whether or not a future addition to the current path will invalidate
the policy chain (assuming one exists) by setting inhibit-policy- the policy chain (assuming one exists) by setting inhibit-policy-
mapping. Fortunately, it is uncommon practice to set this flag. The mapping. Fortunately, it is uncommon practice to set this flag. The
following is the procedure for processing policy mapping in the following is the procedure for processing policy mapping in the
forward direction: forward direction:
1) Begin with C's policy set {Y,G} 1) Begin with C's policy set {Y,G}
Cooper, Dzambasow,
Hesse, Joseph,
2) Apply the policy mapping in B's certificate (X maps to G) in 2) Apply the policy mapping in B's certificate (X maps to G) in
reverse to yield {Y,X} (same as {X,Y}) reverse to yield {Y,X} (same as {X,Y})
3) Intersect the result {X,Y} with B{X,Y} to yield the set {X,Y} 3) Intersect the result {X,Y} with B{X,Y} to yield the set {X,Y}
4) Intersect that result, {X,Y}, with A{X,Y,Z} to yield the final 4) Intersect that result, {X,Y}, with A{X,Y,Z} to yield the final
set {X,Y} set {X,Y}
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Just like in the reverse direction, it is determined in the forward Just like in the reverse direction, it is determined in the forward
direction that certificate C is good for policies {X, Y}. If during direction that certificate C is good for policies {X,Y}. If during
this procedure, an inhibit-policy-mapping flag was encountered, what this procedure, an inhibit-policy-mapping flag was encountered, what
should be done? This is reasonably easy to keep track of as well. should be done? This is reasonably easy to keep track of as well.
The software simply maintains a flag on any policies that were The software simply maintains a flag on any policies that were
propagated as a result of a mapping; just a simple Boolean kept with 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 the policies in the set. Imagine now that the certificate issued to
A has the inhibit-policy-mapping constraint expressed with a skip A has the inhibit-policy-mapping constraint expressed with a skip
certificates value of zero. certificates value of zero.
1) Begin with C's policy set {Y,G} 1) Begin with C's policy set {Y,G}
2) Apply the policy mapping in B's certificate and mark X as 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, resulting from a mapping. (X maps to G) in reverse to yield
Xm} (same as {Xm,Y}) {Y,Xm} (same as {Xm,Y})
3) Intersect the result {Xm, Y} with B{X,Y} to yield the set {Xm, Y} 3) Intersect the result {Xm,Y} with B{X,Y} to yield the set {Xm,Y}
4) A's certificate expresses the inhibit policy mapping constraint, 4) A's certificate expresses the inhibit policy mapping constraint,
so eliminate any policies in the current set that were propagated so eliminate any policies in the current set that were propagated
due to mapping (which is Xm) to yield {Y} due to mapping (which is Xm) to yield {Y}
5) Intersect that result, {Y} with A{X,Y,Z} to yield the final set 5) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
{Y} {Y}
If in our example, the policy set had gone to empty at any point (and 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 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 try to traverse another branch of the tree. This is analogous to the
path building functionality utilized in the reverse direction when path building functionality utilized in the reverse direction when
skipping to change at page 59, line 51 skipping to change at page 60, line 47
1) For each CA certificate being scored; 1) For each CA certificate being scored;
a. Copy the current forward policy set a. Copy the current forward policy set
b. Process policy mappings in the CA certificate in order to b. Process policy mappings in the CA certificate in order to
"un-map" policies, if any "un-map" policies, if any
c. Intersect the resulting set with CA certificate's policies c. Intersect the resulting set with CA certificate's policies
The larger the policy set yielded, the larger the score for that CA The larger the policy set yielded, the larger the score for that CA
certificate. certificate.
Cooper, Dzambasow,
Hesse, Joseph,
2) If an initial acceptable set was supplied, intersect this set 2) If an initial acceptable set was supplied, intersect this set
with the resulting set for each CA certificate from (1). with the resulting set for each CA certificate from (1).
The larger the resultant set, the higher the score is for this The larger the resultant set, the higher the score is for this
certificate. certificate.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Other scoring schemes may work better if the operating environment Other scoring schemes may work better if the operating environment
dictates. dictates.
5. Avoiding Path Building Errors 5. Avoiding Path Building Errors
This section defines some errors that may occur during the path This section defines some errors that may occur during the path
building process, as well as ways to avoid these errors when building process, as well as ways to avoid these errors when
developing path building functions. developing path building functions.
5.1 Dead-ends 5.1 Dead-ends
skipping to change at page 60, line 51 skipping to change at page 61, line 47
Figure 14 - Dead-end Example Figure 14 - Dead-end Example
Note that in the example, C has two certificates: one issued by Y, 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 and the other issued by the Trust Anchor. Suppose that a simple
"find issuer" algorithm is used, and the order in which the path "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 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 this case, Z has no certificates issued by any other entities, and so
the simplistic path building process stops. Since Z is not the the simplistic path building process stops. Since Z is not the
relying party's trust anchor, the certification path is not complete, relying party's trust anchor, the certification path is not complete,
Cooper, Dzambasow,
Hesse, Joseph,
and will not validate. This example shows that in anything but the and will not validate. This example shows that in anything but the
simplest PKI structure, additional path building logic will need to simplest PKI structure, additional path building logic will need to
handle the cases in which entities are issued multiple certificates handle the cases in which entities are issued multiple certificates
from different issuers. The path building algorithm will also need from different issuers. The path building algorithm will also need
to have the ability to traverse back up the decision tree and try to have the ability to traverse back up the decision tree and try
another path in order to be robust. another path in order to be robust.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
5.2 Loop Detection 5.2 Loop Detection
In a non-hierarchical PKI structure, a path building algorithm may In a non-hierarchical PKI structure, a path building algorithm may
become caught in a loop without finding an existing path. Consider become caught in a loop without finding an existing path. Consider
the example below: the example below:
+----+ +----+
| TA | | TA |
+----+ +----+
| |
skipping to change at page 61, line 52 skipping to change at page 62, line 47
is Target(B), B(Y), Y(Z), Z(B), B(Y), Y(Z), Z(B), B(Y), ... A loop 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 has formed which will cause the correct path (Target, B, A) to never
be found. The certificate processing system will need to recognize be found. The certificate processing system will need to recognize
loops created by duplicate certificates (which are prohibited in a loops created by duplicate certificates (which are prohibited in a
path by [X.509]) before they form to allow the certification path path by [X.509]) before they form to allow the certification path
building process to continue and find valid paths. The authors of building process to continue and find valid paths. The authors of
this document recommend that the loop detection not only detect the this document recommend that the loop detection not only detect the
repetition of a certificate in the path, but also detect the presence repetition of a certificate in the path, but also detect the presence
of the same subject name / subject alternative name / subject public of the same subject name / subject alternative name / subject public
key combination occurring twice in the path. A name/key pair should key combination occurring twice in the path. A name/key pair should
Cooper, Dzambasow,
Hesse, Joseph,
only need to appear once in the path (see section 2.4.2 for more only need to appear once in the path (see section 2.4.2 for more
information on the reasoning behind this recommendation). information on the reasoning behind this recommendation).
5.3 Use of Key Identifiers 5.3 Use of Key Identifiers
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Inconsistent and/or incompatible approaches to computing the subject Inconsistent and/or incompatible approaches to computing the subject
key identifier and authority key identifier in public key key identifier and authority key identifier in public key
certificates can cause failures in certification path building certificates can cause failures in certification path building
algorithms that use those fields to identify certificates, even algorithms that use those fields to identify certificates, even
though otherwise valid certification paths may exist. Path building though otherwise valid certification paths may exist. Path building
implementations should use existing key identifiers and not attempt implementations should use existing key identifiers and not attempt
to re-compute subject key identifiers. It is extremely important to re-compute subject key identifiers. It is extremely important
that Key Identifiers be used ONLY as sorting criteria or hints - KIDs that Key Identifiers be used only as sorting criteria or hints - KIDs
are not required to match during certification path validation and are not required to match during certification path validation and
cannot be used to eliminate certificates. This is of critical cannot be used to eliminate certificates. This is of critical
importance for interoperating across domains and multi-vendor importance for interoperating across domains and multi-vendor
implementations where the KIDs may not be calculated in the same implementations where the KIDs may not be calculated in the same
fashion. fashion.
Path building and processing implementations should not rely on the Path building and processing implementations should not rely on the
form of authority key identifier which uses the authority form of authority key identifier which uses the authority DN and
distinguished name and serial number as a restrictive matching rule, serial number as a restrictive matching rule, because cross-
because cross-certification can lead to this value not being matched certification can lead to this value not being matched by the cross
by the cross certificates. certificates.
5.4 Distinguished Name Encoding 5.4 Distinguished Name Encoding
Certification Path Building software should not rely on distinguished Certification Path Building software should not rely on DNs being
names being encoded as PrintableString. Although frequently encoded encoded as PrintableString. Although frequently encoded as
as PrintableString, distinguished names may also appear as other PrintableString, DNs may also appear as other types, including
types, including BMPString or UTF8String. As a result, software BMPString or UTF8String. As a result, software systems that are
systems that are unable to process BMPString and UTF8String encoded unable to process BMPString and UTF8String encoded DNs may be unable
distinguished names may be unable to build and validate some to build and validate some certification paths.
certification paths.
Furthermore, looking forward, [RFC 3280] compliant certificates are Furthermore, [RFC 3280] compliant certificates are required to encode
required to encode distinguished names as UTF8String as of January 1, DNs as UTF8String as of January 1, 2004. Certification path building
2004. Certification path building software should be prepared to software should be prepared to handle "name rollover" certificates as
handle "name rollover" certificates as described in [RFC 3280]. Note described in [RFC 3280]. Note that the inclusion of a "name
that the inclusion of a "name rollover" certificate in a rollover" certificate in a certification path does not constitute
certification path does NOT constitute repetition of a distinguished repetition of a DN and key. Implementations that include the "name
name and key. Implementations that include the "name rollover" rollover" certificate in the path should ensure that the DNs with
certificate in the path should ensure that the distinguished names differing encoding are regarded as dissimilar. (Implementations may
with differing encoding are regarded as dissimilar. (Implementations instead handle matching DNs of different encodings and will therefore
may instead handle matching distinguished names of different not need to include "name rollover" certificates in the path.)
encodings and will therefore not need to include "name rollover"
certificates in the path.)
Cooper, Dzambasow,
Hesse, Joseph,
6. Retrieval Methods 6. Retrieval Methods
Building a certification path requires the availability of the Building a certification path requires the availability of the
certificates and CRLs that make up the path. There are many certificates and CRLs that make up the path. There are many
different methods for obtaining these certificates and CRLs. This different methods for obtaining these certificates and CRLs. This
section lists a few of the common ways to perform this retrieval, as section lists a few of the common ways to perform this retrieval, as
well as some suggested approaches for improving performance. This well as some suggested approaches for improving performance. This
section is not intended to provide a complete reference for section is not intended to provide a complete reference for
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
certificate and CRL retrieval methods or optimizations that would be certificate and CRL retrieval methods or optimizations that would be
useful in certification path building. useful in certification path building.
6.1 Directories Using LDAP 6.1 Directories Using LDAP
Most applications utilize the lightweight directory access protocol Most applications utilize the Lightweight Directory Access Protocol
(LDAP) when retrieving data from directories following the X.500 (LDAP) when retrieving data from directories following the X.500
model. The LDAP v3 specification is found in [RFC 2251]. model. Applications may encounter directories which support either
LDAP v2 [RFC 1777] or LDAP v3 [RFC 3377].
The LDAP v3 specification defines one attribute retrieval option, the The LDAP v3 specification defines one attribute retrieval option, the
"binary" option. This option, when specified in an LDAP retrieval "binary" option. This option, when specified in an LDAP retrieval
request, was intended to force the directory to ignore any string- request, was intended to force the directory to ignore any string-
based representations of directory information, and send the based representations of BER-encoded directory information, and send
requested attribute(s) in binary format. Since all PKI objects of the requested attribute(s) in BER format. Since all PKI objects of
concern are binary objects, the "binary" option should be used. concern are BER-encoded objects, the "binary" option should be used.
However, not all directories support the "binary" option. However, not all directories support the "binary" option. Therefore,
(Additionally, recent developments in the LDAP working group seem to applications should be capable of requesting attributes with and
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 without the "binary" option. For example, if an application wishes
to retrieve the userCertificate attribute, the retrieval request to retrieve the userCertificate attribute, the application should
should contain the following list of attributes to retrieve: request "userCertificate;binary". If the desired information is not
"userCertificate, and userCertificate;binary". returned, robust implementations may opt to request "userCertificate"
as well.
The following attributes should be considered by PKI application The following attributes should be considered by PKI application
developers when performing certificate retrieval from LDAP sources: developers when performing certificate retrieval from LDAP sources:
- userCertificate: contains certificates issued by one or more - userCertificate: contains certificates issued by one or more
certification authorities with a subject DN that matches that certification authorities with a subject DN that matches that
of the directory entry. This is a multi-valued attribute and of the directory entry. This is a multi-valued attribute and
all values should be received and considered during path all values should be received and considered during path
building. Although typically it is expected that only end building. Although typically it is expected that only end
entity certificates will be stored in this attribute, (e.g., entity certificates will be stored in this attribute, (e.g.,
this is the attribute an application would request to find a this is the attribute an application would request to find a
person's encryption certificate) implementers may opt to search person's encryption certificate) implementers may opt to search
this attribute when looking in CA entries to make their path this attribute when looking in CA entries to make their path
builder more robust. If it is empty, the overhead added by builder more robust. If it is empty, the overhead added by
including this attribute when already requesting one or both of including this attribute when already requesting one or both of
the two below is marginal. the two below is marginal.
Cooper, Dzambasow,
Hesse, Joseph,
- cACertificate: contains self-issued certificates (if any) and - cACertificate: contains self-issued certificates (if any) and
any certificates issued to this certification authority by any certificates issued to this certification authority by
other certification authorities in the same realm. (Realm is other certification authorities in the same realm. (Realm is
dependent upon local policy.) This is a multi-valued attribute dependent upon local policy.) This is a multi-valued attribute
and all values should be received and considered during path and all values should be received and considered during path
building. building.
- crossCertificatePair: the crossCertificatePair is used to Cooper, Dzambasow,
contain certificates issued to this certification authority by Hesse, Joseph,
other certification authorities in other realms, as well as . Certification Path Building January 2005
- crossCertificatePair: in conformant implementations, the
crossCertificatePair is used to contain all, except self-issued
certificates issued to this certification authority, as well as
certificates issued by this certification authority to other certificates issued by this certification authority to other
certification authorities in other realms. Each attribute certification authorities. Each attribute value is a structure
value is a structure containing two elements. The containing two elements. The issuedToThisCA element contains
issuedToThisCA element contains certificates issued to this certificates issued to this certification authority by other
certification authority by other certification authorities. certification authorities. The issuedByThisCA element contains
The issuedByThisCA element contains certificates issued by this certificates issued by this certification authority to other
certification authority to other certification authorities. certification authorities. Both elements of the
Both elements of the crossCertificatePair are labeled optional crossCertificatePair are labeled optional in the ASN.1
in the ASN.1 definition; however the LDAP v2 schema states that definition. If both elements are present in a single value,
the issuedToThisCA (once called the 'forward' element) is the issuer name in one certificate is required to match the
mandatory and the issuedByThisCA (once called the 'reverse' subject name in the other and vice versa, and the subject
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 public key in one certificate shall be capable of verifying the
digital signature on the other certificate and vice versa. digital signature on the other certificate and vice versa. As
this technology has evolved, different standards have had
differing requirements on where information could be found.
For example, the LDAP v2 schema [RFC2587] states that the
issuedToThisCA (once called 'forward') element of the
crossCertificatePair attribute is mandatory and the
issuedByThisCA (once called 'reverse') element is optional. In
contrast, section 11.2.3 of [X.509] requires the issuedByThisCA
element to be present if the CA issues a certificate to another
CA if the subject is not a subordinate CA in a hierarchy.
Conformant directories behave has required by [X.509], but
robust path building implementations may want to retrieve all
certificates from the cACertificate and crossCertificatePair
attributes to ensure all possible certification authority
certificates are obtained.
- certificateRevocationList: the certificateRevocationList - certificateRevocationList: the certificateRevocationList
attribute contains a certificate revocation list (CRL). A CRL attribute contains a certificate revocation list (CRL). A CRL
is defined in [RFC 3280] as a time stamped list identifying is defined in [RFC 3280] as a time stamped list identifying
revoked certificates, which is signed by a CA or CRL issuer and revoked certificates, which is signed by a CA or CRL issuer and
made freely available in a public repository. Each revoked made freely available in a public repository. Each revoked
certificate is identified in a CRL by its certificate serial certificate is identified in a CRL by its certificate serial
number. There may be one or more CRLs in this attribute, and number. There may be one or more CRLs in this attribute, and
the values should be processed in accordance with [RFC 3280]. the values should be processed in accordance with [RFC 3280].
- authorityRevocationList: the authorityRevocationList attribute - authorityRevocationList: the authorityRevocationList attribute
also contains CRLs. These CRLs contain revocation information also contains CRLs. These CRLs contain revocation information
regarding certificates issued to other CAs. There may be one regarding certificates issued to other CAs. There may be one
or more CRLs in this attribute, and the values should be or more CRLs in this attribute, and the values should be
processed in accordance with [RFC 3280]. processed in accordance with [RFC 3280].
Certification Path Processing Systems that plan to interoperate with Certification Path Processing Systems that plan to interoperate with
varying PKI structures and directory designs should at a minimum be 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, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
6.2 Authority Information Access . Certification Path Building January 2005
able to retrieve and process the userCertificate, cACertificate,
crossCertificatePair, certificateRevocationList, and
authorityRevocationList attributes from directory entries.
6.2 Certificate Store Access via HTTP
Another possible method of certificate retrieval is using HTTP as an
interface mechanism for retrieving certificates and CRLs from PKI
repositories. A current PKIX draft [CERTSTORE] provides a protocol
for a general-purpose interface capability for retrieving
certificates and CRLs from PKI repositories. Since the [CERTSTORE]
document is in draft status as of the writing of this document, no
details are given here on how to utilize this mechanism for
certificate and CRL retrieval. Instead, refer to the [CERTSTORE]
document or its current version. Certification Path Processing
systems may wish to implement support for this interface capability,
especially if they will be used in environments which will provide
HTTP-based access to certificates and CRLs.
6.3 Authority Information Access
The authority information access (AIA) extension, defined within [RFC The authority information access (AIA) extension, defined within [RFC
3280], indicates how to access CA information and services for the 3280], indicates how to access CA information and services for the
issuer of the certificate in which the extension appears. If a issuer of the certificate in which the extension appears. If a
certificate with an AIA extension contains an accessMethod defined certificate with an AIA extension contains an accessMethod defined
with the id-ad-caIssuers OID, the AIA may be used to retrieve one or with the id-ad-caIssuers OID, the AIA may be used to retrieve one or
more certificates for the CA that issued the certificate containing more certificates for the CA that issued the certificate containing
the AIA extension. The AIA will provide a uniform resource the AIA extension. The AIA will provide a uniform resource
identifier (URI) when certificates can be retrieved via LDAP, HTTP, identifier (URI) [RFC 2396] when certificates can be retrieved via
or FTP. The AIA will provide a directoryName when certificates can LDAP, HTTP, or FTP. The AIA will provide a directoryName when
be retrieved via directory access protocol (DAP). The AIA will certificates can be retrieved via directory access protocol (DAP).
provide an rfc822Name when certificates can be retrieved via The AIA will provide an rfc822Name when certificates can be retrieved
electronic mail. Additionally, the AIA may specify the location of via electronic mail. Additionally, the AIA may specify the location
an OCSP [RFC 2560] responder that is able to provide revocation of an OCSP [RFC 2560] responder that is able to provide revocation
information for the certificate. information for the certificate.
If present, AIA may provide forward path-building implementations If present, AIA may provide forward path-building implementations
with a direct link to a certificate for the issuer of a given with a direct link to a certificate for the issuer of a given
certificate. Therefore, implementations may wish to provide support certificate. Therefore, implementations may wish to provide support
for decoding the AIA extension and processing the LDAP, HTTP, FTP, for decoding the AIA extension and processing the LDAP, HTTP, FTP,
DAP, or e-mail locators. Support for AIA is optional; [RFC 3280] DAP, or e-mail locators. Support for AIA is optional; [RFC 3280]
compliant implementations are not required to populate the AIA compliant implementations are not required to populate the AIA
extension. However, implementers of path building and validation extension. However, implementers of path building and validation
modules are strongly encouraged to support AIA, especially the HTTP modules are strongly encouraged to support AIA, especially the HTTP
transport; this will provide for usability and interoperability with transport; this will provide for usability and interoperability with
many existing PKIs. many existing PKIs.
6.3 Subject Information Access 6.4 Subject Information Access
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
The subject information access (SIA) extension, defined within [RFC The subject information access (SIA) extension, defined within [RFC
3280], indicates how to access information and services for the 3280], indicates how to access information and services for the
subject of the certificate in which the extension appears. If a subject of the certificate in which the extension appears. If a
certificate with an SIA extension contains an accessMethod defined certificate with an SIA extension contains an accessMethod defined
with the id-ad-caRepository OID, the SIA may be used to locate one or with the id-ad-caRepository OID, the SIA may be used to locate one or
more certificates (and possibly CRLs) for entities issued more certificates (and possibly CRLs) for entities issued
certificates by the subject. The SIA will provide a uniform resource certificates by the subject. The SIA will provide a uniform resource
identifier (URI) when data can be retrieved via LDAP, HTTP, or FTP. identifier (URI) [RFC 2396] when data can be retrieved via LDAP,
The SIA will provide a directoryName when data can be retrieved via HTTP, or FTP. The SIA will provide a directoryName when data can be
directory access protocol (DAP). The SIA will provide an rfc822Name retrieved via directory access protocol (DAP). The SIA will provide
when data can be retrieved via electronic mail. an rfc822Name when data can be retrieved via electronic mail.
If present, the SIA extension may provide reverse path-building If present, the SIA extension may provide reverse path-building
implementations with the certificates required to continue building implementations with the certificates required to continue building
the path. Therefore, implementations may wish to provide support for the path. Therefore, implementations may wish to provide support for
decoding the SIA extension and processing the LDAP, HTTP, FTP, DAP, decoding the SIA extension and processing the LDAP, HTTP, FTP, DAP,
or e-mail locators. Support for SIA is optional; [RFC 3280] or e-mail locators. Support for SIA is optional; [RFC 3280]
Cooper, Dzambasow,
Hesse, Joseph,
compliant implementations are not required to populate the SIA compliant implementations are not required to populate the SIA
extension. However, implementers of path building and validation extension. However, implementers of path building and validation
modules are strongly encouraged to support SIA, especially the HTTP modules are strongly encouraged to support SIA, especially the HTTP
transport; this will provide for usability and interoperability with transport; this will provide for usability and interoperability with
many existing PKIs. many existing PKIs.
6.4 CRL Distribution Points 6.5 CRL Distribution Points
The CRL distribution points (CRLDP) extension, defined within [RFC The CRL distribution points (CRLDP) extension, defined within [RFC
3280], indicates how to access CRL information. If a CRLDP extension 3280], indicates how to access CRL information. If a CRLDP extension
appears within a certificate, the CRL(s) to which the CRLDP refer are appears within a certificate, the CRL(s) to which the CRLDP refer are
generally the CRLs that would contain revocation information for the generally the CRLs that would contain revocation information for the
certificate. The CRLDP extension may point to multiple distribution certificate. The CRLDP extension may point to multiple distribution
points from which the CRL information may be obtained; the points from which the CRL information may be obtained; the
certificate processing system should process the CRLDP extension in certificate processing system should process the CRLDP extension in
accordance with [RFC 3280]. The most common distribution points accordance with [RFC 3280]. The most common distribution points
contain URIs from which the appropriate CRL may be downloaded, and contain URIs from which the appropriate CRL may be downloaded, and
skipping to change at page 66, line 35 skipping to change at page 67, line 54
with a link to CRL information for a given certificate. Therefore, with a link to CRL information for a given certificate. Therefore,
implementations may wish to provide support for decoding the CRLDP implementations may wish to provide support for decoding the CRLDP
extension and using the information to retrieve CRLs. Support for extension and using the information to retrieve CRLs. Support for
CRLDP is optional and [RFC 3280] compliant implementations need not CRLDP is optional and [RFC 3280] compliant implementations need not
populate the CRLDP extension. However, implementers of path building populate the CRLDP extension. However, implementers of path building
and validation modules are strongly encouraged to support CRLDPs. At and validation modules are strongly encouraged to support CRLDPs. At
a minimum, developers are encouraged to consider supporting the LDAP a minimum, developers are encouraged to consider supporting the LDAP
and HTTP transports; this will provide for interoperability across a and HTTP transports; this will provide for interoperability across a
wide range of existing PKIs. wide range of existing PKIs.
6.5 Data Obtained via Application Protocol Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
6.6 Data Obtained via Application Protocol
Many application protocols, such as SSL/TLS and S/MIME, allow one Many application protocols, such as SSL/TLS and S/MIME, allow one
party to provide certificates and CRLs to another. Data provided in party to provide certificates and CRLs to another. Data provided in
this method is generally very valuable to path building software this method is generally very valuable to path building software
(will provide direction toward valid paths), and should be stored and (will provide direction toward valid paths), and should be stored and
used accordingly. Note: self-signed root certificates obtained via used accordingly. Note: self-signed certificates obtained via
application protocol are not trustworthy; implementations should only application protocol are not trustworthy; implementations should only
consider the relying party's trust anchors when building paths. consider the relying party's trust anchors when building paths.
6.6 Proprietary Mechanisms 6.7 Proprietary Mechanisms
Some certificate issuing systems and certificate processing systems Some certificate issuing systems and certificate processing systems
may utilize proprietary retrieval mechanisms, such as network mapped may utilize proprietary retrieval mechanisms, such as network mapped
drives, databases, or other methods that are not directly referenced drives, databases, or other methods that are not directly referenced
via the IETF standards. Certificate processing systems may wish to via the IETF standards. Certificate processing systems may wish to
support other proprietary mechanisms, but should only do so in support other proprietary mechanisms, but should only do so in
Cooper, Dzambasow,
Hesse, Joseph,
addition to supporting standard retrieval mechanisms such as LDAP, addition to supporting standard retrieval mechanisms such as LDAP,
AIA, and CRLDP (unless functioning in a closed environment). AIA, and CRLDP (unless functioning in a closed environment).
7. Improving Retrieval Performance 7. Improving Retrieval Performance
Retrieval performance can be improved through a few different Retrieval performance can be improved through a few different
mechanisms, including the use of caches and setting a specific mechanisms, including the use of caches and setting a specific
retrieval order. This section discusses a few methods by which the retrieval order. This section discusses a few methods by which the
performance of a certificate processing system may be improved during performance of a certificate processing system may be improved during
the retrieval of PKI objects. Certificate processing systems that the retrieval of PKI objects. Certificate processing systems that
skipping to change at page 67, line 26 skipping to change at page 68, line 45
processing systems are encouraged to do whatever possible to reduce processing systems are encouraged to do whatever possible to reduce
the delays associated with requesting and retrieving data from the delays associated with requesting and retrieving data from
external sources. external sources.
7.1 Caching 7.1 Caching
Certificate processing systems operating in a non-hierarchical PKI Certificate processing systems operating in a non-hierarchical PKI
will often need to retrieve certificates and certificate revocation will often need to retrieve certificates and certificate revocation
lists (CRLs) from a source outside the application protocol. lists (CRLs) from a source outside the application protocol.
Typically, these objects are retrieved from an X.500 or LDAP Typically, these objects are retrieved from an X.500 or LDAP
repository, an Internet URI, or some other non-local source. Due to repository, an Internet URI [RFC 2396], or some other non-local
the delays associated with both the establishing of connections as source. Due to the delays associated with both the establishing of
well as network transfers, certificate processing systems ought to be connections as well as network transfers, certificate processing
as efficient as possible when retrieving data from external sources. systems ought to be as efficient as possible when retrieving data
Perhaps the best way in which retrieval efficiency can often be from external sources. Perhaps the best way in which retrieval
improved is by the use of a caching mechanism. Certificate efficiency can often be improved is by the use of a caching
processing systems can cache data retrieved from external sources for mechanism. Certificate processing systems can cache data retrieved
some period of time, but not to exceed the useful period of the data from external sources for some period of time, but not to exceed the
(i.e., an expired certificate need not be cached). Although this
comes at a cost of increased memory/disk consumption by the system, Cooper, Dzambasow,
the cost and performance benefit of reducing network transmissions is Hesse, Joseph,
great. Also, CRLs are often issued and available in advance of the . Certification Path Building January 2005
nextUpdate date in the CRL. Implementations may wish to obtain these
'fresher' CRLs before the nextUpdate date has passed. useful period of the data (i.e., an expired certificate need not be
cached). Although this comes at a cost of increased memory/disk
consumption by the system, the cost and performance benefit of
reducing network transmissions is great. Also, CRLs are often issued
and available in advance of the nextUpdate date in the CRL.
Implementations may wish to obtain these 'fresher' CRLs before the
nextUpdate date has passed.
There are a number of different ways in which caching can be There are a number of different ways in which caching can be
implemented, and the specifics of these methods can be used as implemented, and the specifics of these methods can be used as
distinguishing characteristics between certificate processing distinguishing characteristics between certificate processing
systems. However, some things that implementers may wish to consider systems. However, some things that implementers may wish to consider
when developing caching systems are as follows: when developing caching systems are as follows:
- If PKI objects are cached, the certification path building - If PKI objects are cached, the certification path building
mechanism should be able to examine and retrieve from the cache mechanism should be able to examine and retrieve from the cache
during path building. This will allow the certificate during path building. This will allow the certificate
processing system to find or eliminate one or more paths processing system to find or eliminate one or more paths
quickly without requiring external contact with a directory or quickly without requiring external contact with a directory or
Cooper, Dzambasow,
Hesse, Joseph,
other retrieval mechanism. other retrieval mechanism.
- Sharing caches between multiple users (via a local area network - Sharing caches between multiple users (via a local area network
or LAN) may be useful if many users in one organization or LAN) may be useful if many users in one organization
consistently perform PKI operations with another organization. consistently perform PKI operations with another organization.
- Caching not only PKI objects (such as certificates and CRLs) - Caching not only PKI objects (such as certificates and CRLs)
but also relationships between PKI objects (storing a link but also relationships between PKI objects (storing a link
between a certificate and the issuer's certificate) may be between a certificate and the issuer's certificate) may be
useful. This linking may not always lead to the most correct useful. This linking may not always lead to the most correct
skipping to change at page 68, line 33 skipping to change at page 69, line 54
7.2 Retrieval Order 7.2 Retrieval Order
To optimize efficiency, certificate processing systems are encouraged To optimize efficiency, certificate processing systems are encouraged
to also consider the order in which different PKI objects are to also consider the order in which different PKI objects are
retrieved, as well as the mechanism from which they are retrieved. retrieved, as well as the mechanism from which they are retrieved.
If caching is utilized, the caches can be consulted for PKI objects If caching is utilized, the caches can be consulted for PKI objects
before attempting other retrieval mechanisms. If multiple caches are before attempting other retrieval mechanisms. If multiple caches are
present (such as local disk and network), the caches can be consulted 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 in the order in which they can be expected to return their result
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
from fastest to slowest. For example, if a certificate processing from fastest to slowest. For example, if a certificate processing
system wished to retrieve a certificate with a particular subject system wished to retrieve a certificate with a particular subject DN,
distinguished name, the system might first consult the local cache, the system might first consult the local cache, then the network
then the network cache, and then attempt directory retrieval. The cache, and then attempt directory retrieval. The specifics of the
specifics of the types of retrieval mechanisms and their relative types of retrieval mechanisms and their relative costs are left to
costs are left to the implementer. the implementer.
In addition to ordering retrieval mechanisms, the certificate In addition to ordering retrieval mechanisms, the certificate
processing system ought to order the relative merits of the different processing system ought to order the relative merits of the different
external sources from which a PKI object can be retrieved. If the 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 AIA is present within a certificate, with a URI [RFC 2396] for the
certificate, the certificate processing system (if able) may wish to issuer's certificate, the certificate processing system (if able) may
attempt to retrieve the certificate first from local cache and then wish to attempt to retrieve the certificate first from local cache
using that URI (because it is expected to point directly to the and then using that URI (because it is expected to point directly to
desired certificate) before attempting to retrieve the certificates the desired certificate) before attempting to retrieve the
that may exist within a directory. certificates that may exist within a directory.
If a directory is being consulted, it may be desirable to retrieve If a directory is being consulted, it may be desirable to retrieve
attributes in a particular order. A highly cross-certified PKI attributes in a particular order. A highly cross-certified PKI
Cooper, Dzambasow,
Hesse, Joseph,
structure will lead to multiple possibilities for certification structure will lead to multiple possibilities for certification
paths, which may mean multiple validation attempts before a paths, which may mean multiple validation attempts before a
successful path is retrieved. Therefore, cACertificate and successful path is retrieved. Therefore, cACertificate and
userCertificate (which typically contain certificates from within the userCertificate (which typically contain certificates from within the
same 'realm') could be consulted before attempting to retrieve the same 'realm') could be consulted before attempting to retrieve the
crossCertificatePair values for an entry. Alternately, all three crossCertificatePair values for an entry. Alternately, all three
attributes could be retrieved in one query, but cross certificates attributes could be retrieved in one query, but cross certificates
then tagged as such and used only after exhausting the possibilities then tagged as such and used only after exhausting the possibilities
from the cACertificate attribute. The best approach will depend on from the cACertificate attribute. The best approach will depend on
the nature of the application and PKI environment. the nature of the application and PKI environment.
7.3 Parallel Fetching and Prefetching 7.3 Parallel Fetching and Prefetching
Much of this document has focused on a path building algorithm that Much of this document has focused on a path building algorithm that
minimizes the performance impact of network retrievals, by preventing minimizes the performance impact of network retrievals, by preventing
those retrievals and utilization of caches. Another way to improve those retrievals and utilization of caches. Another way to improve
performance would be to allow network retrievals to be performed in performance would be to allow network retrievals to be performed in
advance (prefetching) or at the same time that other operations are advance (prefetching) or at the same time that other operations are
performed (parallel fetching). Implementations which provide the performed (parallel fetching). For example, if an email application
capability of parallel fetching and/or prefetching, along with a receives a signed email message, it could download the required
robust cache, can lead to greatly improved performance. certificates and CRLs prior to the recipient viewing (or attempting
to verify) the message. Implementations which provide the capability
of parallel fetching and/or prefetching, along with a robust cache,
can lead to greatly improved performance or user experience.
8. Security Considerations 8. Security Considerations
8.1 General Considerations for Building Any Certification Path 8.1 General Considerations for Building A Certification Path
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Although certification path building deals directly with security Although certification path building deals directly with security
relevant PKI data, the PKI data itself needs no special handling as relevant PKI data, the PKI data itself needs no special handling as
the PKI data integrity is secured with the digital signature applied the PKI data integrity is secured with the digital signature applied
to it. The only exception to this is the appropriate protection of 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 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 out of band (e.g., not from an electronic mail message or a
directory.) with respect to the path building module. directory.) with respect to the path building module.
The greatest security risks associated with this document revolve The greatest security risks associated with this document revolve
skipping to change at page 69, line 52 skipping to change at page 71, line 28
[X.509] is required in order for certification path building, [X.509] is required in order for certification path building,
certification path validation, and the certificate using application certification path validation, and the certificate using application
to be properly secured. All of the Security Considerations listed in to be properly secured. All of the Security Considerations listed in
Section 9 of [RFC 3280] apply equally here. Section 9 of [RFC 3280] apply equally here.
In addition, as with any application that consumes data from In addition, as with any application that consumes data from
potentially untrusted network locations, certification path building potentially untrusted network locations, certification path building
components should be carefully implemented so as to reduce or components should be carefully implemented so as to reduce or
eliminate the possibility of network based exploits. For example, a eliminate the possibility of network based exploits. For example, a
poorly implemented path building module may not check the length of poorly implemented path building module may not check the length of
the CRLDP URI [RFC 2396] before using the C language strcpy()
Cooper, Dzambasow, function to place the address in a 1024 byte buffer. A hacker could
Hesse, Joseph, use such a flaw to create a buffer overflow exploit by encoding
the CRLDP URI before using the C language strcpy() function to place malicious assembly code into the CRLDP of a certificate and then
the address in a 1024 byte buffer. A hacker could use such a flaw to using the certificate to attempt an authentication. Such an attack
create a buffer overflow exploit by encoding malicious assembly code could yield system level control to the attacker and expose the
into the CRLDP of a certificate and then using the certificate to sensitive data the PKI was meant to protect.
attempt an authentication. Such an attack could yield system level
control to the attacker and expose the sensitive data the PKI was
meant to protect.
Path Building may be used to mount a denial of service (DOS) attack. Path Building may be used to mount a denial of service (DOS) attack.
This might occur if multiple simple requests could be performed which This might occur if multiple simple requests could be performed which
cause a server to perform a number of path developments, each taking cause a server to perform a number of path developments, each taking
time and resources from the server. Servers can help avoid this by time and resources from the server. Servers can help avoid this by
limiting the resources they are willing to devote to path building, limiting the resources they are willing to devote to path building,
and being able to further limit those resources when the load is and being able to further limit those resources when the load is
heavy. Standard DOS protections such as systems which identify and heavy. Standard DOS protections such as systems which identify and
block attackers can also be useful. block attackers can also be useful.
A DOS attack can be also created by presenting spurious CA
certificates containing very large public keys. When the system
attempts to use the large public key to verify the digital signature
on additional certificates, a long processing delay may occur. This
can be mitigated by either of two strategies. The first strategy is
only perform signature verifications after a complete path is built,
and starting from the trust anchor. This will eliminate the spurious
CA certificate from consideration before the large public key is
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
used. The second strategy is to recognize and simply reject keys
longer than a certain size.
A similar DOS attack can occur with very large public keys in end
entity certificates. If a system uses the public key in a
certificate before building and validating that certificate's
certification path, long processing delays may occur. To mitigate
this threat, the public key in an end entity certificate should not
be used for any purpose until a complete certification path for that
certificate is built and validated.
8.2 Specific Considerations for Building Revocation Signer Certification 8.2 Specific Considerations for Building Revocation Signer Certification
Paths Paths
In the case where the CRL Signer certificate (and certification path) In the case where the CRL Signer certificate (and certification path)
is not identical to the Certification Authority certificate (and is not identical to the Certification Authority certificate (and
certification path), special care should be exercised when building certification path), special care should be exercised when building
the CRL Signer certification path. the CRL Signer certification path.
If special consideration is not given to building a CRL Signer If special consideration is not given to building a CRL Signer
certification path, that path could be constructed such that it certification path, that path could be constructed such that it
skipping to change at page 70, line 53 skipping to change at page 72, line 49
revoked, C is referred to as the Certification Authority certificate. revoked, C is referred to as the Certification Authority certificate.
The path builder finds that the CRL for checking the revocation 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" 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 to sign E. C2 is but with a different key than the key that was used to sign E. C2 is
referred to as the CRL Signer. An unrestrictive certification path referred to as the CRL Signer. An unrestrictive certification path
builder might then build a path such as the following for the CRL builder might then build a path such as the following for the CRL
Signer C2 certificate: Signer C2 certificate:
X->Y->Z->C2 X->Y->Z->C2
Cooper, Dzambasow,
Hesse, Joseph,
If a path such as the one above is permitted, nothing can be If a path such as the one above is permitted, nothing can be
concluded about the revocation status of E since C2 is a different CA concluded about the revocation status of E since C2 is a different CA
from C. from C.
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
Fortunately, preventing this security problem is not difficult and Fortunately, preventing this security problem is not difficult and
the solution also makes building CRL Signer certification paths very the solution also makes building CRL Signer certification paths very
efficient. In the event the CRL Signer certificate is identical to efficient. In the event the CRL Signer certificate is identical to
the Certification Authority certificate, the Certification Authority the Certification Authority certificate, the Certification Authority
certification path should be used to verify the CRL; no additional certification path should be used to verify the CRL; no additional
path building is required. If the CRL Signer certificate is not path building is required. If the CRL Signer certificate is not
identical to the Certification Authority certificate, a second path identical to the Certification Authority certificate, a second path
should be built for the CRL Signer certificate in exactly the same should be built for the CRL Signer certificate in exactly the same
fashion as for any certificate, but with the following additional fashion as for any certificate, but with the following additional
guidelines: guidelines:
1. Trust Anchor: The CRL Signer's certification path should start 1. Trust Anchor: The CRL Signer's certification path should start
with the same trust anchor as the Certification Authority's with the same trust anchor as the Certification Authority's
certification path. Any trust anchor certificate with a subject certification path. Any trust anchor certificate with a subject DN
distinguished name matching that of the Certification Authority's matching that of the Certification Authority's trust anchor should be
trust anchor should be considered acceptable though lower in priority considered acceptable though lower in priority than the one with a
than the one with a matching public key and subject distinguished matching public key and subject DN. While different trust anchor
name. While different trust anchor public keys are acceptable at the public keys are acceptable at the beginning of the CRL signer's
beginning of the CRL signer's certification path and the certification path and the Certification Authority's certification
Certification Authority's certification path, both keys must be path, both keys must be trusted by the relying party per the
trusted by the relying party per the recommendations in section 8.1. recommendations in section 8.1.
2. CA Name Matching: The subject distinguished names for all CA 2. CA Name Matching: The subject DNs for all CA certificates in the
certificates in the two certification paths should match on a one-to- two certification paths should match on a one-to-one basis (ignoring
one basis (ignoring self-issued certificates) for the entire length self-issued certificates) for the entire length of the shorter of the
of the shorter of the two paths. two paths.
3. CRL Signer Certification Path Length: The length of the CRL 3. CRL Signer Certification Path Length: The length of the CRL
Signer certification path (ignoring self-issued certificates) should Signer certification path (ignoring self-issued certificates) should
be equal to or less than the length of the Certification Authority be equal to or less than the length of the Certification Authority
certification path plus (+) one. This allows a given Certification certification path plus (+) one. This allows a given Certification
Authority to issue a certificate to a delegated/subordinate CRL Authority to issue a certificate to a delegated/subordinate CRL
Signer. The latter configuration represents the maximum certification Signer. The latter configuration represents the maximum certification
path length for a CRL Signer certificate. path length for a CRL Signer certificate.
The reasoning behind the first guideline is readily apparent. Lacking The reasoning behind the first guideline is readily apparent. Lacking
this and the second guideline, any trusted CA could issue CRLs for 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 any other CA, even if the PKIs are not related in any fashion. For
example, one company could revoke certificates issued by another example, one company could revoke certificates issued by another
company if the relying party trusted the trust anchors from both company if the relying party trusted the trust anchors from both
companies. The two guidelines also prevent erroneous CRL checks since companies. The two guidelines also prevent erroneous CRL checks since
Global uniqueness of names is not guaranteed. Global uniqueness of names is not guaranteed.
Cooper, Dzambasow,
Hesse, Joseph,
The second guideline prevents roaming certification paths such as the The second guideline prevents roaming certification paths such as the
previously described example CRL Signer certification path for A->B- previously described example CRL Signer certification path for A->B-
>C->E. It is especially important that the "ignoring self-issued >C->E. It is especially important that the "ignoring self-issued
certificates" is implemented properly. Self-issued certificates are certificates" is implemented properly. Self-issued certificates are
cast out of the one-to-one name comparison in order to allow for key cast out of the one-to-one name comparison in order to allow for key
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
rollover. The path building algorithm may be optimized to only rollover. The path building algorithm may be optimized to only
consider certificates with the acceptable subject distinguished name consider certificates with the acceptable subject DN for the given
for the given point in the CRL Signer certification path while point in the CRL Signer certification path while building the path.
building the path.
The third and final guideline ensures that the CRL used is the The third and final guideline ensures that the CRL used is the
intended one. Without a restriction on the length of the CRL Signer intended one. Without a restriction on the length of the CRL Signer
certification path, the path could roam uncontrolled into another certification path, the path could roam uncontrolled into another
domain and still meet the first two guidelines. For example, again domain and still meet the first two guidelines. For example, again
using the path A->B->C->E, the Certification Authority C, and a CRL using the path A->B->C->E, the Certification Authority C, and a CRL
Signer C2, a CRL Signer certification path such as the following Signer C2, a CRL Signer certification path such as the following
could pass the first two guidelines: could pass the first two guidelines:
A->B->C->D->X->Y->RogueCA->C2 A->B->C->D->X->Y->RogueCA->C2
In the preceding example, the trust anchor is identical for both 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. paths and the one-to-one name matching test passes for A->B->C.
However, accepting such a path has obvious security consequences, so However, accepting such a path has obvious security consequences, so
the third guideline is used to prevent this situation. Applying the the third guideline is used to prevent this situation. Applying the
second and third guideline to the certification path above, the path second and third guideline to the certification path above, the path
builder could have immediately detected this path was not acceptable builder could have immediately detected this path was not acceptable
(prior to building it) by examining the issuer distinguished name in (prior to building it) by examining the issuer DN in C2. Given the
C2. Given the length and name guidelines, the path builder could length and name guidelines, the path builder could detect that
detect that "RogueCA" is not in the set of possible names by "RogueCA" is not in the set of possible names by comparing it to the
comparing it to the set of possible CRL Signer issuer distinguished set of possible CRL Signer issuer DNs, specifically, A, B, or C.
names, specifically, A, B, or C.
Similar consideration should be given when building the path for the Similar consideration should be given when building the path for the
OCSP Responder certificate when the CA is the OCSP Response Signer or OCSP Responder certificate when the CA is the OCSP Response Signer or
the CA has delegated the OCSP Response signing to another entity. the CA has delegated the OCSP Response signing to another entity.
9. IANA Considerations
There are no IANA number assignments required for this document.
Normative References Normative References
[RFC 3280] Housley, R., W. Ford, W. Polk and D. Solo, "Internet [RFC 3280] Housley, R., W. Ford, W. Polk and D. Solo, "Internet
X.509 Public Key Infrastructure: Certificate and CRL X.509 Public Key Infrastructure: Certificate and CRL
Profile", RFC 2459, January 1999. Profile", RFC 3280, April 2002.
[X.509] ITU-T Recommendation X.509 (1997 E): Information
Technology - Open Systems Interconnection - The
Directory: Authentication Framework, June 1997.
Cooper, Dzambasow,
Hesse, Joseph,
Informative References Informative References
[MINHPKIS] Hesse, P., Lemire, D., "Managing Interoperability [MINHPKIS] Hesse, P., and D. Lemire, "Managing Interoperability
in Non-Hierarchical Public Key Infrastructures", in Non-Hierarchical Public Key Infrastructures",
2002 Conference Proceedings of the Internet Society 2002 Conference Proceedings of the Internet Society
Network and Distributed System Security Symposium, Network and Distributed System Security Symposium,
February 2002. February 2002.
[RFC 1738] Berners-Lee, T., L. Masinter and M. McCahill, "Uniform Cooper, Dzambasow,
Resource Locators (URL)", RFC 1738, December 1994. Hesse, Joseph,
. Certification Path Building January 2005
[RFC 1777] Yeong, W., T. Howes and S. Kille, "Lightweight
Directory Access Protocol", RFC 1777, March 1995
[RFC 2026] Bradner, S., "The Internet Standards Process - [RFC 2026] Bradner, S., "The Internet Standards Process -
Revision 3", RFC 2026, October 1996 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.
[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. [RFC 2396] Berners-Lee, T., Fielding, R., Irving, U.C., and L.
Masinter, "Uniform Resource Identifiers (URI): Generic Masinter, "Uniform Resource Identifiers (URI): Generic
Syntax", RFC 2396, August 1998. Syntax", RFC 2396, August 1998.
[RFC 2560] Myers, M., R. Ankney, A. Malpani, S. Galperin and C. [RFC 2560] Myers, M., R. Ankney, A. Malpani, S. Galperin and C.
Adams, "Online Certificate Status Protocal - OCSP", Adams, "Online Certificate Status Protocal - OCSP",
June 1999. June 1999.
[RFC 2587] S. Boeyen, T. Howes, P. Richard, "Internet X.509 [RFC 2587] S. Boeyen, T. Howes, P. Richard, "Internet X.509
Public Key Infrastructure LDAPv2 Schema", RFC 2587, Public Key Infrastructure LDAPv2 Schema", RFC 2587,
June 1999 June 1999
[RFC 3377] Hodges, J., and R. Morgan,
"Lightweight Directory Access Protocol (v3): Technical
Specification", RFC 3377, September 2002.
[RFC 3820] Tuecke, S., V. Welch, D. Engert, L. Pearlman, and M.
Thompson, "Internet X.509 Public Key Infrastructure:
Proxy Certificate Profile", RFC 3820, June 2004.
[X.501] ITU-T Recommendation X.501: Information Technology - [X.501] ITU-T Recommendation X.501: Information Technology -
Open Systems Interconnection - The Directory: Models, Open Systems Interconnection - The Directory: Models,
1993. 1993.
[X.520] ITU-T Recommendation X.520: Information Technology - [X.509] ITU-T Recommendation X.509 (1997 E): Information
Open Systems Interconnection - The Directory: Selected Technology - Open Systems Interconnection - The
Attribute Types, 1993. Directory: Authentication Framework, June 1997.
[PKIXALGS] Bassham, L., Polk, W. and R. Housley, "Algorithms and [PKIXALGS] Bassham, L., Polk, W. and R. Housley, "Algorithms and
Cooper, Dzambasow,
Hesse, Joseph,
Identifiers for the Internet X.509 Public Key Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation Infrastructure Certificate and Certificate Revocation
Lists (CRL) Profile", RFC 3279, April 2002. Lists (CRL) Profile", RFC 3279, April 2002.
[CERTSTORE] P. Gutmann, "Internet X.509 Public Key Infrastructure
Operational Protocols: Certificate Store Access via
HTTP", draft-ietf-pkix-certstore-http-08.txt,
August 2004.
Acknowledgments Acknowledgments
Cooper, Dzambasow,
Hesse, Joseph,
. Certification Path Building January 2005
The authors extend their appreciation to David Lemire for his efforts The authors extend their appreciation to David Lemire for his efforts
coauthoring "Managing Interoperability in Non-Hierarchical Public Key coauthoring "Managing Interoperability in Non-Hierarchical Public Key
Infrastructures" from which material was borrowed heavily for use in Infrastructures" from which material was borrowed heavily for use in
the introductory sections. the introductory sections.
This document has also greatly benefited from the review and This document has also greatly benefited from the review and
additional technical insight provided by Dr. Santosh Chokhani, Carl additional technical insight provided by Dr. Santosh Chokhani, Carl
Wallace, Denis Pinkas, Steve Hanna, and Alice Sturgeon. Wallace, Denis Pinkas, Steve Hanna, Alice Sturgeon, Russ Housley, and
Tim Polk.
Author's Addresses Author's Addresses
Matt Cooper Matt Cooper
Orion Security Solutions, Inc. Orion Security Solutions, Inc.
1489 Chain Bridge Rd, Ste. 300 1489 Chain Bridge Rd, Ste. 300
McLean, VA 22101, USA McLean, VA 22101, USA
Phone: +1-703-917-0060 Phone: +1-703-917-0060
Email: mcooper@orionsec.com Email: mcooper@orionsec.com
Yuriy Dzambasow Yuriy Dzambasow
A&N Associates, Inc. A&N Associates, Inc.
999 Corporate Blvd Ste. 100 999 Corporate Blvd Ste. 100
Linthicum, MD 21090, USA Linthicum, MD 21090, USA
Phone: +1-410-859-5449 x107 Phone: +1-410-859-5449 x107
Email: yuriy@anassoc.com Email: yuriy@anassoc.com
Peter Hesse Peter Hesse
Gemini Security Solutions, Inc. Gemini Security Solutions, Inc.
4031 University Dr. Ste. 200 4451 Brookfield Corporate Dr. Ste. 200
Fairfax, VA 22030, USA Chantilly, VA 20151, USA
Phone: +1-703-934-2031 Phone: +1-703-378-5808 x105
Email: pmhesse@geminisecurity.com Email: pmhesse@geminisecurity.com
Susan Joseph Susan Joseph
DigitalNet Government Solutions, LLC. BAE Systems Information Technology
141 National Business Parkway, Ste. 210 141 National Business Parkway, Ste. 210
Annapolis Junction, MD 20701, USA Annapolis Junction, MD 20701, USA
Phone: +1-301-939-2705 Phone: +1-301-939-2705
Email: susan.joseph@digitalnet.com Email: susan.joseph@it.baesystems.com
Richard Nicholas Richard Nicholas
DigitalNet Government Solutions, LLC. BAE Systems Information Technology
141 National Business Parkway, Ste. 210 141 National Business Parkway, Ste. 210
Annapolis Junction, MD 20701, USA
Phone: +1-301-939-2722
Email: richard.nicholas@it.baesystems.com
Full Copyright Statement
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
Annapolis Junction, MD 20701, USA . Certification Path Building January 2005
Phone: +1-301-939-2722
Email: richard.nicholas@digitalnet.com "Copyright (C) The Internet Society (2004). This document is
subject to the rights, licenses and restrictions contained in BCP
78, and except as set forth therein, the authors retain all their
rights."
"This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
Cooper, Dzambasow, Cooper, Dzambasow,
Hesse, Joseph, Hesse, Joseph,
 End of changes. 287 change blocks. 
704 lines changed or deleted 960 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/