| blob | 52716e1063763acca2ec3806bbd4e5ea8c93f462 |
7 Network Working Group M. Cooper
8 Request for Comments: 4158 Orion Security Solutions
9 Category: Informational Y. Dzambasow
10 A&N Associates
11 P. Hesse
12 Gemini Security Solutions
13 S. Joseph
14 Van Dyke Technologies
15 R. Nicholas
16 BAE Systems
17 September 2005
20 Internet X.509 Public Key Infrastructure:
21 Certification Path Building
23 Status of This Memo
25 This memo provides information for the Internet community. It does
26 not specify an Internet standard of any kind. Distribution of this
27 memo is unlimited.
29 Copyright Notice
31 Copyright (C) The Internet Society (2005).
33 Abstract
35 This document provides guidance and recommendations to developers
36 building X.509 public-key certification paths within their
37 applications. By following the guidance and recommendations defined
38 in this document, an application developer is more likely to develop
39 a robust X.509 certificate-enabled application that can build valid
40 certification paths across a wide range of PKI environments.
42 Table of Contents
44 1. Introduction ....................................................3
45 1.1. Motivation .................................................4
46 1.2. Purpose ....................................................4
47 1.3. Terminology ................................................5
48 1.4. Notation ...................................................8
49 1.5. Overview of PKI Structures .................................8
50 1.5.1. Hierarchical Structures .............................8
51 1.5.2. Mesh Structures ....................................10
52 1.5.3. Bi-Lateral Cross-Certified Structures ..............11
53 1.5.4. Bridge Structures ..................................13
54 1.6. Bridge Structures and Certification Path Processing .......14
58 Cooper, et al. Informational [Page 1]
59 \f
60 RFC 4158 Certification Path Building September 2005
63 2. Certification Path Building ....................................15
64 2.1. Introduction to Certification Path Building ...............15
65 2.2. Criteria for Path Building ................................16
66 2.3. Path-Building Algorithms ..................................17
67 2.4. How to Build a Certification Path .........................21
68 2.4.1. Certificate Repetition .............................23
69 2.4.2. Introduction to Path-Building Optimization .........24
70 2.5. Building Certification Paths for Revocation Signer
71 Certificates ..............................................30
72 2.6. Suggested Path-Building Software Components ...............31
73 2.7. Inputs to the Path-Building Module ........................33
74 2.7.1. Required Inputs ....................................33
75 2.7.2. Optional Inputs ....................................34
76 3. Optimizing Path Building .......................................35
77 3.1. Optimized Path Building ...................................35
78 3.2. Sorting vs. Elimination ...................................38
79 3.3. Representing the Decision Tree ............................41
80 3.3.1. Node Representation for CA Entities ................41
81 3.3.2. Using Nodes to Iterate Over All Paths ..............42
82 3.4. Implementing Path-Building Optimization ...................45
83 3.5. Selected Methods for Sorting Certificates .................46
84 3.5.1. basicConstraints Is Present and cA Equals True .....47
85 3.5.2. Recognized Signature Algorithms ....................48
86 3.5.3. keyUsage Is Correct ................................48
87 3.5.4. Time (T) Falls within the Certificate Validity .....48
88 3.5.5. Certificate Was Previously Validated ...............49
89 3.5.6. Previously Verified Signatures .....................49
90 3.5.7. Path Length Constraints ............................50
91 3.5.8. Name Constraints ...................................50
92 3.5.9. Certificate Is Not Revoked .........................51
93 3.5.10. Issuer Found in the Path Cache ....................52
94 3.5.11. Issuer Found in the Application Protocol ..........52
95 3.5.12. Matching Key Identifiers (KIDs) ...................52
96 3.5.13. Policy Processing .................................53
97 3.5.14. Policies Intersect the Sought Policy Set ..........54
98 3.5.15. Endpoint Distinguished Name (DN) Matching .........55
99 3.5.16. Relative Distinguished Name (RDN) Matching ........55
100 3.5.17. Certificates are Retrieved from
101 cACertificate Directory Attribute .................56
102 3.5.18. Consistent Public Key and Signature Algorithms ....56
103 3.5.19. Similar Issuer and Subject Names ..................57
104 3.5.20. Certificates in the Certification Cache ...........57
105 3.5.21. Current CRL Found in Local Cache ..................58
106 3.6. Certificate Sorting Methods for Revocation Signer
107 Certification Paths .......................................58
108 3.6.1. Identical Trust Anchors ............................58
109 3.6.2. Endpoint Distinguished Name (DN) Matching ..........59
110 3.6.3. Relative Distinguished Name (RDN) Matching .........59
114 Cooper, et al. Informational [Page 2]
115 \f
116 RFC 4158 Certification Path Building September 2005
119 3.6.4. Identical Intermediate Names .......................60
120 4. Forward Policy Chaining ........................................60
121 4.1. Simple Intersection .......................................61
122 4.2. Policy Mapping ............................................62
123 4.3. Assigning Scores for Forward Policy Chaining ..............63
124 5. Avoiding Path-Building Errors ..................................64
125 5.1. Dead Ends .................................................64
126 5.2. Loop Detection ............................................65
127 5.3. Use of Key Identifiers ....................................66
128 5.4. Distinguished Name Encoding ...............................66
129 6. Retrieval Methods ..............................................67
130 6.1. Directories Using LDAP ....................................67
131 6.2. Certificate Store Access via HTTP .........................69
132 6.3. Authority Information Access ..............................69
133 6.4. Subject Information Access ................................70
134 6.5. CRL Distribution Points ...................................70
135 6.6. Data Obtained via Application Protocol ....................71
136 6.7. Proprietary Mechanisms ....................................71
137 7. Improving Retrieval Performance ................................71
138 7.1. Caching ...................................................72
139 7.2. Retrieval Order ...........................................73
140 7.3. Parallel Fetching and Prefetching .........................73
141 8. Security Considerations ........................................74
142 8.1. General Considerations for Building a Certification Path ..74
143 8.2. Specific Considerations for Building Revocation
144 Signer Paths ..............................................75
145 9. Acknowledgements ...............................................78
146 10. Normative References ..........................................78
147 11. Informative References ........................................78
149 1. Introduction
151 [X.509] public key certificates have become an accepted method for
152 securely binding the identity of an individual or device to a public
153 key, in order to support public key cryptographic operations such as
154 digital signature verification and public key-based encryption.
155 However, prior to using the public key contained in a certificate, an
156 application first has to determine the authenticity of that
157 certificate, and specifically, the validity of all the certificates
158 leading to a trusted public key, called a trust anchor. Through
159 validating this certification path, the assertion of the binding made
160 between the identity and the public key in each of the certificates
161 can be traced back to a single trust anchor.
163 The process by which an application determines this authenticity of a
164 certificate is called certification path processing. Certification
165 path processing establishes a chain of trust between a trust anchor
166 and a certificate. This chain of trust is composed of a series of
170 Cooper, et al. Informational [Page 3]
171 \f
172 RFC 4158 Certification Path Building September 2005
175 certificates known as a certification path. A certification path
176 begins with a certificate whose signature can be verified using a
177 trust anchor and ends with the target certificate. Path processing
178 entails building and validating the certification path to determine
179 whether a target certificate is appropriate for use in a particular
180 application context. See Section 3.2 of [RFC3280] for more
181 information on certification paths and trust.
183 1.1. Motivation
185 Many other documents (such as [RFC3280]) cover certification path
186 validation requirements and procedures in detail but do not discuss
187 certification path building because the means used to find the path
188 does not affect its validation. This document therefore is an effort
189 to provide useful guidance for developers of certification path-
190 building implementations.
192 Additionally, the need to develop complex certification paths is
193 increasing. Many PKIs are now using complex structures (see Section
194 1.5) rather than simple hierarchies. Additionally, some enterprises
195 are gradually moving away from trust lists filled with many trust
196 anchors, and toward an infrastructure with one trust anchor and many
197 cross-certified relationships. This document provides helpful
198 information for developing certification paths in these more
199 complicated situations.
201 1.2. Purpose
203 This document provides information and guidance for certification
204 path building. There are no requirements or protocol specifications
205 in this document. This document provides many options for performing
206 certification path building, as opposed to just one particular way.
207 This document draws upon the authors' experiences with existing
208 complex certification paths to offer insights and recommendations to
209 developers who are integrating support for [X.509] certificates into
210 their applications.
212 In addition, this document suggests using an effective general
213 approach to path building that involves a depth first tree traversal.
214 While the authors believe this approach offers the balance of
215 simplicity in design with very effective and infrastructure-neutral
216 path-building capabilities, the algorithm is no more than a suggested
217 approach. Other approaches (e.g., breadth first tree traversals)
218 exist and may be shown to be more effective under certain conditions.
219 Certification path validation is described in detail in both [X.509]
220 and [RFC3280] and is not repeated in this document.
226 Cooper, et al. Informational [Page 4]
227 \f
228 RFC 4158 Certification Path Building September 2005
231 This document does not provide guidance for building the
232 certification path from an end entity certificate to a proxy
233 certificate as described in [RFC3820].
235 1.3. Terminology
237 Terms used throughout this document will be used in the following
238 ways:
240 Building in the Forward direction: The process of building a
241 certification path from the target certificate to a trust anchor.
242 'Forward' is the former name of the crossCertificatePair element
243 'issuedToThisCA'.
245 Building in the Reverse direction: The process of building a
246 certification path from a trust anchor to the target certificate.
247 'Reverse' is the former name of the crossCertificatePair element
248 'issuedByThisCA'.
250 Certificate: A digital binding that cannot be counterfeited between
251 a named entity and a public key.
253 Certificate Graph: A graph that represents the entire PKI (or all
254 cross-certified PKIs) in which all named entities are viewed as
255 nodes and all certificates are viewed as arcs between nodes.
257 Certificate Processing System: An application or device that
258 performs the functions of certification path building and
259 certification path validation.
261 Certification Authority (CA): An entity that issues and manages
262 certificates.
264 Certification Path: An ordered list of certificates starting with a
265 certificate signed by a trust anchor and ending with the target
266 certificate.
268 Certification Path Building: The process used to assemble the
269 certification path between the trust anchor and the target
270 certificate.
272 Certification Path Validation: The process that verifies the binding
273 between the subject and the subject-public-key defined in the
274 target certificate, using a trust anchor and set of known
275 constraints.
282 Cooper, et al. Informational [Page 5]
283 \f
284 RFC 4158 Certification Path Building September 2005
287 Certificate Revocation List (CRL): A signed, time stamped list
288 identifying a set of certificates that are no longer considered
289 valid by the certificate issuer.
291 CRL Signer Certificate: The specific certificate that may be used for
292 verifying the signature on a CRL issued by, or on behalf of, a
293 specific CA.
295 Cross-Certificate: A certificate issued by one CA to another CA for
296 the purpose of establishing a trust relationship between the two
297 CAs.
299 Cross-Certification: The act of issuing cross-certificates.
301 Decision Tree: When the path-building software has multiple
302 certificates to choose from, and must make a decision, the
303 collection of possible choices is called a decision tree.
305 Directory: Generally used to refer an LDAP accessible repository for
306 certificates and PKI information. The term may also be used
307 generically to refer to any certificate storing repository.
309 End Entity: The holder of a private key and corresponding
310 certificate, whose identity is defined as the Subject of the
311 certificate. Human end entities are often called "subscribers".
313 Is-revocation-signer indicator: A boolean flag furnished to the
314 path-building software. If set, this indicates that the target
315 certificate is a Revocation Signer certificate for a specific CA.
316 For example, if building a certification path for an indirect CRL
317 Signer certificate, this flag would be set.
319 Local PKI: The set of PKI components and data (certificates,
320 directories, CRLs, etc.) that are created and used by the
321 certificate using organization. In general, this concept refers
322 to the components that are in close proximity to the certificate
323 using application. The assumption is that the local data is more
324 easily accessible and/or inexpensive to retrieve than non-local
325 PKI data.
327 Local Realm: See Local PKI.
329 Node (in a certificate graph): The collection of certificates having
330 identical subject distinguished names.
332 Online Certificate Status Protocol (OCSP): An Internet protocol used
333 by a client to obtain the revocation status of a certificate from
334 a server.
338 Cooper, et al. Informational [Page 6]
339 \f
340 RFC 4158 Certification Path Building September 2005
343 OCSP Response Signer Certificate: The specific certificate that may
344 be used for verifying the signature on an OCSP response. This
345 response may be provided by the CA, on behalf of the CA, or by a
346 different signer as determined by the Relying Party's local
347 policy.
349 Public Key Infrastructure (PKI): The set of hardware, software,
350 personnel, policy, and procedures used by a CA to issue and manage
351 certificates.
353 Relying Party (RP): An application or entity that processes
354 certificates for the purpose of 1) verifying a digital signature,
355 2) authenticating another entity, or 3) establishing confidential
356 communications.
358 Revocation Signer Certificate: Refers collectively to either a CRL
359 Signer Certificate or OCSP Response Signer Certificate.
361 Target Certificate: The certificate that is to be validated by a
362 Relying Party. It is the "Certificate targeted for validation".
363 Although frequently this is the End Entity or a leaf node in the
364 PKI structure, this could also be a CA certificate if a CA
365 certificate is being validated. (e.g., This could be for the
366 purpose of building and validating a certification path for the
367 signer of a CRL.)
369 Trust (of public keys): In the scope of this document, a public key
370 is considered trustworthy if the certificate containing the public
371 key can be validated according to the procedures in [RFC3280].
373 Trust List: A list of trust anchors.
375 Trust Anchor: The combination of a trusted public key and the name of
376 the entity to which the corresponding private key belongs.
378 Trust Anchor Certificate: A self-signed certificate for a trust
379 anchor that is used in certification path processing.
381 User: An individual that is using a certificate processing system.
382 This document refers to some cases in which users may or may not
383 be prompted with information or requests, depending upon the
384 implementation of the certificate processing system.
394 Cooper, et al. Informational [Page 7]
395 \f
396 RFC 4158 Certification Path Building September 2005
399 1.4. Notation
401 This document makes use of a few common notations that are used in
402 the diagrams and examples.
404 The first is the arrow symbol (->) which represents the issuance of a
405 certificate from one entity to another. For example, if entity H
406 were to issue a certificate to entity K, this is denoted as H->K.
408 Sometimes it is necessary to specify the subject and issuer of a
409 given certificate. If entity H were to issue a certificate to entity
410 K this can be denoted as K(H).
412 These notations can be combined to denote complicated certification
413 paths such as C(D)->B(C)->A(B).
415 1.5. Overview of PKI Structures
417 When verifying [X.509] public key certificates, often the application
418 performing the verification has no knowledge of the underlying Public
419 Key Infrastructure (PKI) that issued the certificate. PKI structures
420 can range from very simple, hierarchical structures to complex
421 structures such as mesh architectures involving multiple bridges (see
422 Section 1.5.4). These structures define the types of certification
423 paths that might be built and validated by an application [MINHPKIS].
424 This section describes four common PKI structures.
426 1.5.1. Hierarchical Structures
428 A hierarchical PKI, depicted in Figure 1, is one in which all of the
429 end entities and relying parties use a single "Root CA" as their
430 trust anchor. If the hierarchy has multiple levels, the Root CA
431 certifies the public keys of intermediate CAs (also known as
432 subordinate CAs). These CAs then certify end entities'
433 (subscribers') public keys or may, in a large PKI, certify other CAs.
434 In this architecture, certificates are issued in only one direction,
435 and a CA never certifies another CA "superior" to itself. Typically,
436 only one superior CA certifies each CA.
450 Cooper, et al. Informational [Page 8]
451 \f
452 RFC 4158 Certification Path Building September 2005
455 +---------+
456 +---| Root CA |---+
457 | +---------+ |
458 | |
459 | |
460 v v
461 +----+ +----+
462 +-----| CA | +-----| CA |------+
463 | +----+ | +----+ |
464 | | |
465 v v v
466 +----+ +----+ +----+
467 +--| CA |-----+ | CA |-+ +---| CA |---+
468 | +----+ | +----+ | | +----+ |
469 | | | | | | | |
470 | | | | | | | |
471 v v v v v v v v
472 +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
473 | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
474 +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
476 Figure 1 - Sample Hierarchical PKI
478 Certification path building in a hierarchical PKI is a
479 straightforward process that simply requires the relying party to
480 successively retrieve issuer certificates until a certificate that
481 was issued by the trust anchor (the "Root CA" in Figure 1) is
482 located.
484 A widely used variation on the single-rooted hierarchical PKI is the
485 inclusion of multiple CAs as trust anchors. (See Figure 2.) Here,
486 end entity certificates are validated using the same approach as with
487 any hierarchical PKI. The difference is that a certificate will be
488 accepted if it can be verified back to any of the set of trust
489 anchors. Popular web browsers use this approach, and are shipped
490 with trust lists containing dozens to more than one hundred CAs.
491 While this approach simplifies the implementation of a limited form
492 of certificate verification, it also may introduce certain security
493 vulnerabilities. For example, the user may have little or no idea of
494 the policies or operating practices of the various trust anchors, and
495 may not be aware of which root was used to verify a given
496 certificate. Additionally, the compromise of any trusted CA private
497 key or the insertion of a rogue CA certificate to the trust list may
498 compromise the entire system. Conversely, if the trust list is
499 properly managed and kept to a reasonable size, it can be an
500 efficient solution to building and validating certification paths.
506 Cooper, et al. Informational [Page 9]
507 \f
508 RFC 4158 Certification Path Building September 2005
511 +-------------------------------------------------------+
512 | Trust List |
513 | |
514 | +---------+ +---------+ +---------+ |
515 | +--| Root CA | | Root CA | | Root CA | |
516 | | +---------+ +---------+ +---------+ |
517 | | | | | |
518 +--|------|----------------|---------------- |----------+
519 | | | |
520 | | | |
521 | | v |
522 | | +----+ |
523 | | +----| CA |---+ |
524 | | | +----+ | |
525 | | | | |
526 | | v v v
527 | | +----+ +----+ +----+
528 | | | CA |---+ | CA |-+ | CA |---+
529 | | +----+ | +----+ | +----+ |
530 | | | | | | | |
531 | | | | | | | |
532 v v v v v v v v
533 +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
534 | EE | | EE | | EE | | EE | | EE | | EE | | EE | | EE |
535 +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
537 Figure 2 - Multi-Rooted Hierarchical PKI
539 1.5.2. Mesh Structures
541 In a typical mesh style PKI (depicted in Figure 3), each end entity
542 trusts the CA that issued their own certificate(s). Thus, there is
543 no 'Root CA' for the entire PKI. The CAs in this environment have
544 peer relationships; they are neither superior nor subordinate to one
545 another. In a mesh, CAs in the PKI cross-certify. That is, each CA
546 issues a certificate to, and is issued a certificate by, peer CAs in
547 the PKI. The figure depicts a mesh PKI that is fully cross-certified
548 (sometimes called a full mesh). However, it is possible to architect
549 and deploy a mesh PKI with a mixture of uni-directional and bi-
550 directional cross-certifications (called a partial mesh). Partial
551 meshes may also include CAs that are not cross-certified with other
552 CAs in the mesh.
562 Cooper, et al. Informational [Page 10]
563 \f
564 RFC 4158 Certification Path Building September 2005
567 +---------------------------------+
568 | |
569 +-----------+----------------------+ |
570 | v v |
571 | +-------+ +------+ |
572 | +--->| CA B |<------------->| CA C |<--+ |
573 | | +-------+ +------+ | |
574 | | | ^ ^ | | |
575 | | v | | | | |
576 | | +----+ | | | | |
577 | | | EE | +----+ +--------+ v | |
578 | | +----+ | | +----+ | |
579 | | | | | EE | | |
580 v v v v +----+ v v
581 +------+ +------+ +------+
582 | CA E |<----------->| CA A |<----------->| CA D |
583 +------+ +------+ +------+
584 | ^ ^ ^ ^ |
585 | | | | | |
586 v | +------------------------------------+ | v
587 +----+ | | +----+
588 | EE | | +------+ | | EE |
589 +----+ +----------------| CA F |-----------------+ +----+
590 +------+
592 Figure 3 - Mesh PKI
594 Certification path building in a mesh PKI is more complex than in a
595 hierarchical PKI due to the likely existence of multiple paths
596 between a relying party's trust anchor and the certificate to be
597 verified. These multiple paths increase the potential for creating
598 "loops", "dead ends", or invalid paths while building the
599 certification path between a trust anchor and a target certificate.
600 In addition, in cases where no valid path exists, the total number of
601 paths traversed by the path-building software in order to conclude
602 "no path exists" can grow exceedingly large. For example, if
603 ignoring everything except the structure of the graph, the Mesh PKI
604 figure above has 22 non-self issued CA certificates and a total of
605 5,092,429 certification paths between CA F and the EE issued by CA D
606 without repeating any certificates.
608 1.5.3. Bi-Lateral Cross-Certified Structures
610 PKIs can be connected via cross-certification to enable the relying
611 parties of each to verify and accept certificates issued by the other
612 PKI. If the PKIs are hierarchical, cross-certification will
613 typically be accomplished by each Root CA issuing a certificate for
614 the other PKI's Root CA. This results in a slightly more complex,
618 Cooper, et al. Informational [Page 11]
619 \f
620 RFC 4158 Certification Path Building September 2005
623 but still essentially hierarchical environment. If the PKIs are mesh
624 style, then a CA within each PKI is selected, more or less
625 arbitrarily, to establish the cross-certification, effectively
626 creating a larger mesh PKI. Figure 4 depicts a hybrid situation
627 resulting from a hierarchical PKI cross-certifying with a mesh PKI.
629 PKI 1 and 2 cross-certificates
630 +-------------------------------+
631 | |
632 | v
633 | +---------+
634 | +----| Root CA |---+
635 | | +---------+ |
636 | | PKI 1 |
637 | v v
638 | +------+ +------+
639 v PKI 2 +-| CA |-+ | CA |
640 +------+ | +------+ | +------+
641 +------->| CA |<-----+ | | | | |
642 | +------+ | | | | | |
643 | | | | v v v v v
644 | | | | +----+ +----+ +----+ +----+ +----+
645 | v v | | EE | | EE | | EE | | EE | | EE |
646 | +----+ +----+ | +----+ +----+ +----+ +----+ +----+
647 | | EE | | EE | |
648 | +----+ +----+ |
649 v v
650 +------+ +------+
651 | CA |<-------------->| CA |------+
652 +------+ +------+ |
653 | | | | |
654 | | | | |
655 v v v v v
656 +----+ +----+ +----+ +----+ +----+
657 | EE | | EE | | EE | | EE | | EE |
658 +----+ +----+ +----+ +----+ +----+
660 Figure 4 - Hybrid PKI
662 In current implementations, this situation creates a concern that the
663 applications used under the hierarchical PKIs will not have path
664 building capabilities robust enough to handle this more complex
665 certificate graph. As the number of cross-certified PKIs grows, the
666 number of the relationships between them grows exponentially. Two
667 principal concerns about cross-certification are the creation of
668 unintended certification paths through transitive trust, and the
669 dilution of assurance when a high-assurance PKI with restrictive
670 operating policies is cross-certified with a PKI with less
674 Cooper, et al. Informational [Page 12]
675 \f
676 RFC 4158 Certification Path Building September 2005
679 restrictive policies. (Proper name constraints and certificate
680 policies processing can help mitigate the problem of assurance
681 dilution.)
683 1.5.4. Bridge Structures
685 Another approach to the interconnection of PKIs is the use of a
686 "bridge" certification authority (BCA). A BCA is a nexus to
687 establish trust paths among multiple PKIs. The BCA cross-certifies
688 with one CA in each participating PKI. Each PKI only cross-certifies
689 with one other CA (i.e., the BCA), and the BCA cross-certifies only
690 once with each participating PKI. As a result, the number of cross
691 certified relationships in the bridged environment grows linearly
692 with the number of PKIs whereas the number of cross-certified
693 relationships in mesh architectures grows exponentially. However,
694 when connecting PKIs in this way, the number and variety of PKIs
695 involved results in a non-hierarchical environment, such as the one
696 as depicted in Figure 5. (Note: as discussed in Section 2.3, non-
697 hierarchical PKIs can be considered hierarchical, depending upon
698 perspective.)
730 Cooper, et al. Informational [Page 13]
731 \f
732 RFC 4158 Certification Path Building September 2005
735 PKI 1 cross-certified with Bridge
736 +-------------------------------+
737 | |
738 v v
739 +-----------+ +---------+
740 | Bridge CA | +---| Root CA |-----+
741 +-----------+ | +---------+ |
742 ^ | PKI 1 |
743 PKI 2 cross|cert with Bridge v v
744 | +------+ +------+
745 v PKI 2 +-| CA |-+ | CA |
746 +------+ | +------+ | +------+
747 +------->| CA |<-----+ | | | | |
748 | +------+ | | | | | |
749 | | | | v v v v v
750 | | | | +----+ +----+ +----+ +----+ +----+
751 | v v | | EE | | EE | | EE | | EE | | EE |
752 | +----+ +----+ | +----+ +----+ +----+ +----+ +----+
753 | | EE | | EE | |
754 | +----+ +----+ |
755 v v
756 +------+ +------+
757 | CA |<-------------->| CA |------+
758 +------+ +------+ |
759 | | | | |
760 | | | | |
761 v v v v v
762 +----+ +----+ +----+ +----+ +----+
763 | EE | | EE | | EE | | EE | | EE |
764 +----+ +----+ +----+ +----+ +----+
766 Figure 5 - Cross-Certification with a Bridge CA
768 1.6. Bridge Structures and Certification Path Processing
770 Developers building certificate-enabled applications intended for
771 widespread use throughout various sectors are encouraged to consider
772 supporting a Bridge PKI structure because implementation of
773 certification path processing functions to support a Bridge PKI
774 structure requires support of all the PKI structures (e.g.,
775 hierarchical, mesh, hybrid) which the Bridge may connect. An
776 application that can successfully build valid certification paths in
777 all Bridge PKIs will therefore have implemented all of the processing
778 logic required to support the less complicated PKI structures. Thus,
779 if an application fully supports the Bridge PKI structure, it can be
780 deployed in any standards-compliant PKI environment and will perform
781 the required certification path processing properly.
786 Cooper, et al. Informational [Page 14]
787 \f
788 RFC 4158 Certification Path Building September 2005
791 2. Certification Path Building
793 Certification path building is the process by which the certificate
794 processing system obtains the certification path between a trust
795 anchor and the target certificate. Different implementations can
796 build the certification path in different ways; therefore, it is not
797 the intent of this document to recommend a single "best" way to
798 perform this function. Rather, guidance is provided on the technical
799 issues that surround the path-building process, and on the
800 capabilities path-building implementations need in order to build
801 certification paths successfully, irrespective of PKI structures.
803 2.1. Introduction to Certification Path Building
805 A certification path is an ordered list of certificates starting with
806 a certificate that can be validated by one of the relying party's
807 trust anchors, and ending with the certificate to be validated. (The
808 certificate to be validated is referred to as the "target
809 certificate" throughout this document.) Though not required, as a
810 matter of convenience these trust anchors are typically stored in
811 trust anchor certificates. The intermediate certificates that
812 comprise the certification path may be retrieved by any means
813 available to the validating application. These sources may include
814 LDAP, HTTP, SQL, a local cache or certificate store, or as part of
815 the security protocol itself as is common practice with signed S/MIME
816 messages and SSL/TLS sessions.
818 Figure 6 shows an example of a certification path. In this figure,
819 the horizontal arrows represent certificates, and the notation B(A)
820 signifies a certificate issued to B, signed by A.
822 +---------+ +-----+ +-----+ +-----+ +--------+
823 | Trust |----->| CA |---->| CA |---->| CA |---->| Target |
824 | Anchor | : | A | : | B | : | C | : | EE |
825 +---------+ : +-----+ : +-----+ : +-----+ : +--------+
826 : : : :
827 : : : :
828 Cert 1 Cert 2 Cert 3 Cert 4
829 A(Trust Anchor) B(A) C(B) Target(C)
831 Figure 6 - Example Certification Path
833 Unlike certification path validation, certification path building is
834 not addressed by the standards that define the semantics and
835 structure of a PKI. This is because the validation of a
836 certification path is unaffected by the method in which the
837 certification path was built. However, the ability to build a valid
838 certification path is of paramount importance for applications that
842 Cooper, et al. Informational [Page 15]
843 \f
844 RFC 4158 Certification Path Building September 2005
847 rely on a PKI. Without valid certification paths, certificates
848 cannot be validated according to [RFC3280] and therefore cannot be
849 trusted. Thus, the ability to build a path is every bit as important
850 as the ability to validate it properly.
852 There are many issues that can complicate the path-building process.
853 For example, building a path through a cross-certified environment
854 could require the path-building module to traverse multiple PKI
855 domains spanning multiple directories, using multiple algorithms, and
856 employing varying key lengths. A path-building client may also need
857 to manage a number of trust anchors, partially populated directory
858 entries (e.g., missing issuedToThisCA entries in the
859 crossCertificatePair attribute), parsing of certain certificate
860 extensions (e.g., authorityInformationAccess) and directory
861 attributes (e.g., crossCertificatePair), and error handling such as
862 loop detection.
864 In addition, a developer has to decide whether to build paths from a
865 trust anchor (the reverse direction) to the target certificate or
866 from the target certificate (the forward direction) to a trust
867 anchor. Some implementations may even decide to use both. The
868 choice a developer makes should be dependent on the environment and
869 the underlying PKI for that environment. More information on making
870 this choice can be found in Section 2.3.
872 2.2. Criteria for Path Building
874 From this point forward, this document will be discussing specific
875 algorithms and mechanisms to assist developers of certification
876 path-building implementations. To provide justification for these
877 mechanisms, it is important to denote what the authors considered the
878 criteria for a path-building implementation.
880 Criterion 1: The implementation is able to find all possible paths,
881 excepting paths containing repeated subject name/public key pairs.
882 This means that all potentially valid certification paths between the
883 trust anchor and the target certificate which may be valid paths can
884 be built by the algorithm. As discussed in Section 2.4.2, we
885 recommend that subject names and public key pairs are not repeated in
886 paths.
888 Criterion 2: The implementation is as efficient as possible. An
889 efficient certification path-building implementation is defined to be
890 one that builds paths that are more likely to validate following
891 [RFC3280], before building paths that are not likely to validate,
892 with the understanding that there is no way to account for all
893 possible configurations and infrastructures. This criterion is
894 intended to ensure implementations that can produce useful error
898 Cooper, et al. Informational [Page 16]
899 \f
900 RFC 4158 Certification Path Building September 2005
903 information. If a particular path is entirely valid except for a
904 single expired certificate, this is most likely the 'right' path. If
905 other paths are developed that are invalid for multiple obscure
906 reasons, this provides little useful information.
908 The algorithms and mechanisms discussed henceforth are chosen because
909 the authors consider them to be good methods for meeting the above
910 criteria.
912 2.3. Path-Building Algorithms
914 It is intuitive for people familiar with the Bridge CA concept or
915 mesh type PKIs to view path building as traversing a complex graph.
916 However, from the simplest viewpoint, writing a path-building module
917 can be nothing more than traversal of a spanning tree, even in a very
918 complex cross-certified environment. Complex environments as well as
919 hierarchical PKIs can be represented as trees because certificates
920 are not permitted to repeat in a path. If certificates could be
921 repeated, loops can be formed such that the number of paths and
922 number of certificates in a path both increase without bound (e.g., A
923 issues to B, B issues to C, and C issues to A). Figure 7 below
924 illustrates this concept from the trust anchor's perspective.
954 Cooper, et al. Informational [Page 17]
955 \f
956 RFC 4158 Certification Path Building September 2005
959 +---------+ +---------+
960 | Trust | | Trust |
961 | Anchor | | Anchor |
962 +---------+ +---------+
963 | | | |
964 v v v v
965 +---+ +---+ +---+ +---+
966 | A |<-->| C | +--| A | | C |--+
967 +---+ +---+ | +---+ +---+ |
968 | | | | | |
969 | +---+ | v v v v
970 +->| B |<-+ +---+ +---+ +---+ +---+
971 +---+ | B | | C | | A | | B |
972 | +---+ +---+ +---+ +---+
973 v | | | |
974 +----+ v v v v
975 | EE | +----+ +---+ +---+ +----+
976 +----+ | EE | | B | | B | | EE |
977 +----+ +---+ +---+ +----+
978 A certificate graph with | |
979 bi-directional cross-cert. v v
980 between CAs A and C. +----+ +----+
981 | EE | | EE |
982 +----+ +----+
984 The same certificate graph
985 rendered as a tree - the
986 way path-building software
987 could see it.
989 Figure 7 - Simple Certificate Graph - From Anchor Tree Depiction
991 When viewed from this perspective, all PKIs look like hierarchies
992 emanating from the trust anchor. An infrastructure can be depicted
993 in this way regardless of its complexity. In Figure 8, the same
994 graph is depicted from the end entity (EE) (the target certificate in
995 this example). It would appear this way if building in the forward
996 (from EE or from target) direction. In this example, without knowing
997 any particulars of the certificates, it appears at first that
998 building from EE has a smaller decision tree than building from the
999 trust anchor. While it is true that there are fewer nodes in the
1000 tree, it is not necessarily more efficient in this example.
1010 Cooper, et al. Informational [Page 18]
1011 \f
1012 RFC 4158 Certification Path Building September 2005
1015 +---------+ +---------+
1016 | Trust | | Trust |
1017 | Anchor | | Anchor |
1018 +---------+ +---------+
1019 ^ ^
1020 | |
1021 | |
1022 +---+ +---+
1023 | A | | C |
1024 +---+ +---+
1025 +---------+ ^ ^ +---------+
1026 | Trust | | | | Trust |
1027 | Anchor | | | | Anchor |
1028 +---------+ | | +---------+
1029 ^ | | ^
1030 | +---+ +---+ |
1031 +-------| C | | A |---------+
1032 +---+ +---+
1033 ^ ^
1034 | |
1035 | +---+ |
1036 +---------| B |------+
1037 +---+
1038 ^
1039 |
1040 |
1041 +----+
1042 | EE |
1043 +----+
1045 The same certificate graph rendered
1046 as a tree but from the end entity
1047 rather than the trust anchor.
1049 Figure 8 - Certificate Graph - From Target Certificate Depiction
1051 Suppose a path-building algorithm performed no optimizations. That
1052 is, the algorithm is only capable of detecting that the current
1053 certificate in the tree was issued by the trust anchor, or that it
1054 issued the target certificate (EE). From the tree above, building
1055 from the target certificate will require going through two
1056 intermediate certificates before encountering a certificate issued by
1057 the trust anchor 100% of the time (e.g., EE chains to B, which then
1058 chains to C, which is issued by the Trust Anchor). The path-building
1059 module would not chain C to A because it can recognize that C has a
1060 certificate issued by the Trust Anchor (TA).
1066 Cooper, et al. Informational [Page 19]
1067 \f
1068 RFC 4158 Certification Path Building September 2005
1071 On the other hand, in the first tree (Figure 7: from anchor
1072 depiction), there is a 50% probability of building a path longer than
1073 needed (e.g., TA to A to C to B to EE rather than the shorter TA to A
1074 to B to EE). However, even given our simplistic example, the path-
1075 building software, when at A, could be designed to recognize that B's
1076 subject distinguished name (DN) matches the issuer DN of the EE.
1077 Given this one optimization, the builder could prefer B to C. (B's
1078 subject DN matches that of the EE's issuer whereas C's subject DN
1079 does not.) So, for this example, assuming the issuedByThisCA
1080 (reverse) and issuedToThisCA (forward) elements were fully populated
1081 in the directory and our path-building module implemented the
1082 aforementioned DN matching optimization method, path building from
1083 either the trust anchor or the target certificate could be made
1084 roughly equivalent. A list of possible optimization methods is
1085 provided later in this document.
1087 A more complicated example is created when the path-building software
1088 encounters a situation when there are multiple certificates from
1089 which to choose while building a path. We refer to this as a large
1090 decision tree, or a situation with high fan-out. This might occur if
1091 an implementation has multiple trust anchors to choose from, and is
1092 building in the reverse (from trust anchor) direction. Or, it may
1093 occur in either direction if a Bridge CA is encountered. Large
1094 decision trees are the enemy of efficient path-building software. To
1095 combat this problem, implementations should make careful decisions
1096 about the path-building direction, and should utilize optimizations
1097 such as those discussed in Section 3.1 when confronted with a large
1098 decision tree.
1100 Irrespective of the path-building approach for any path-building
1101 algorithm, cases can be constructed that make the algorithm perform
1102 poorly. The following questions should help a developer decide from
1103 which direction to build certification paths for their application:
1105 1) What is required to accommodate the local PKI environment and the
1106 PKI environments with which interoperability will be required?
1108 a. If using a directory, is the directory [RFC2587] compliant
1109 (specifically, are the issuedToThisCA [forward] cross-
1110 certificates and/or the cACertificate attributes fully
1111 populated in the directory)? If yes, you are able to build in
1112 the forward direction.
1114 b. If using a directory, does the directory contain all the
1115 issuedByThisCA (reverse) cross-certificates in the
1116 crossCertificatePair attribute, or, alternately, are all
1117 certificates issued from each CA available via some other
1118 means? If yes, it is possible to build in the reverse
1122 Cooper, et al. Informational [Page 20]
1123 \f
1124 RFC 4158 Certification Path Building September 2005
1127 direction. Note: [RFC2587] does not require the issuedByThisCA
1128 (reverse) cross-certificates to be populated; if they are
1129 absent it will not be possible to build solely in the reverse
1130 direction.
1132 c. Are all issuer certificates available via some means other than
1133 a directory (e.g., the authorityInformationAccess extension is
1134 present and populated in all certificates)? If yes, you are
1135 able to build in the forward direction.
1137 2) How many trust anchors will the path-building and validation
1138 software be using?
1140 a. Are there (or will there be) multiple trust anchors in the
1141 local PKI? If yes, forward path building may offer better
1142 performance.
1144 b. Will the path-building and validation software need to place
1145 trust in trust anchors from PKIs that do not populate reverse
1146 cross-certificates for all intermediate CAs? If no, and the
1147 local PKI populates reverse cross-certificates, reverse path
1148 building is an option.
1150 2.4. How to Build a Certification Path
1152 As was discussed in the prior section, path building is essentially a
1153 tree traversal. It was easy to see how this is true in a simple
1154 example, but how about a more complicated one? Before taking a look
1155 at more a complicated scenario, it is worthwhile to address loops and
1156 what constitutes a loop in a certification path. [X.509] specifies
1157 that the same certificate may not repeat in a path. In a strict
1158 sense, this works well as it is not possible to create an endless
1159 loop without repeating one or more certificates in the path.
1160 However, this requirement fails to adequately address Bridged PKI
1161 environments.
1178 Cooper, et al. Informational [Page 21]
1179 \f
1180 RFC 4158 Certification Path Building September 2005
1183 +---+ +---+
1184 | F |--->| H |
1185 +---+ +---+
1186 ^ ^ ^
1187 | \ \
1188 | \ \
1189 | v v
1190 | +---+ +---+
1191 | | G |--->| I |
1192 | +---+ +---+
1193 | ^
1194 | /
1195 | /
1196 +------+ +-----------+ +------+ +---+ +---+
1197 | TA W |<----->| Bridge CA |<------>| TA X |-->| L |-->| M |
1198 +------+ +-----------+ +------+ +---+ +---+
1199 ^ ^ \ \
1200 / \ \ \
1201 / \ \ \
1202 v v v v
1203 +------+ +------+ +---+ +---+
1204 | TA Y | | TA Z | | J | | N |
1205 +------+ +------+ +---+ +---+
1206 / \ / \ | |
1207 / \ / \ | |
1208 / \ / \ v v
1209 v v v v +---+ +----+
1210 +---+ +---+ +---+ +---+ | K | | EE |
1211 | A |<--->| C | | O | | P | +---+ +----+
1212 +---+ +---+ +---+ +---+
1213 \ / / \ \
1214 \ / / \ \
1215 \ / v v v
1216 v v +---+ +---+ +---+
1217 +---+ | Q | | R | | S |
1218 | B | +---+ +---+ +---+
1219 +---+ |
1220 /\ |
1221 / \ |
1222 v v v
1223 +---+ +---+ +---+
1224 | E | | D | | T |
1225 +---+ +---+ +---+
1227 Figure 9 - Four Bridged PKIs
1234 Cooper, et al. Informational [Page 22]
1235 \f
1236 RFC 4158 Certification Path Building September 2005
1239 Figure 9 depicts four root certification authorities cross-certified
1240 with a Bridge CA (BCA). While multiple trust anchors are shown in
1241 the Figure, our examples all consider TA Z as the trust anchor. The
1242 other trust anchors serve different relying parties. By building
1243 certification paths through the BCA, trust can be extended across the
1244 four infrastructures. In Figure 9, the BCA has four certificates
1245 issued to it; one issued from each of the trust anchors in the graph.
1246 If stored in the BCA directory system, the four certificates issued
1247 to the BCA would be stored in the issuedToThisCA (forward) entry of
1248 four different crossCertificatePair structures. The BCA also has
1249 issued four certificates, one to each of the trust anchors. If
1250 stored in the BCA directory system, those certificates would be
1251 stored in the issuedByThisCA (reverse) entry of the same four
1252 crossCertificatePair structures. (Note that the cross-certificates
1253 are stored as matched pairs in the crossCertificatePair attribute.
1254 For example, a crossCertificatePair structure might contain both A(B)
1255 and B(A), but not contain A(C) and B(A).) The four
1256 crossCertificatePair structures would then be stored in the BCA's
1257 directory entry in the crossCertificatePair attribute.
1259 2.4.1. Certificate Repetition
1261 [X.509] requires that certificates are not repeated when building
1262 paths. For instance, from the figure above, do not build the path TA
1263 Z->BCA->Y->A->C->A->C->B->D. Not only is the repetition unnecessary
1264 to build the path from Z to D, but it also requires the reuse of a
1265 certificate (the one issued from C to A), which makes the path non-
1266 compliant with [X.509].
1268 What about the following path from TA Z to EE?
1270 TA Z->BCA->Y->BCA->W->BCA->X->L->N->EE
1272 Unlike the first example, this path does not require a developer to
1273 repeat any certificates; therefore, it is compliant with [X.509].
1274 Each of the BCA certificates is issued from a different source and is
1275 therefore a different certificate. Suppose now that the bottom left
1276 PKI (in Figure 9) had double arrows between Y and C, as well as
1277 between Y and A. The following path could then be built:
1279 TA Z->BCA->Y->A->C->Y->BCA->W->BCA->X->L->N->EE
1281 A path such as this could become arbitrarily complex and traverse
1282 every cross-certified CA in every PKI in a cross-certified
1283 environment while still remaining compliant with [X.509]. As a
1284 practical matter, the path above is not something an application
1285 would typically want or need to build for a variety of reasons:
1290 Cooper, et al. Informational [Page 23]
1291 \f
1292 RFC 4158 Certification Path Building September 2005
1295 - First, certification paths like the example above are generally
1296 not intended by the PKI designers and should not be necessary in
1297 order to validate any given certificate. If a convoluted path
1298 such as the example above is required (there is no corresponding
1299 simple path) in order to validate a given certificate, this is
1300 most likely indicative of a flaw in the PKI design.
1302 - Second, the longer a path becomes, the greater the potential
1303 dilution of trust in the certification path. That is, with each
1304 successive link in the infrastructure (i.e., certification by
1305 CAs and cross-certification between CAs) some amount of
1306 assurance may be considered lost.
1308 - Third, the longer and more complicated a path, the less likely
1309 it is to validate because of basic constraints, policies or
1310 policy constraints, name constraints, CRL availability, or even
1311 revocation.
1313 - Lastly, and certainly not least important from a developer's or
1314 user's perspective, is performance. Allowing paths like the one
1315 above dramatically increases the number of possible paths for
1316 every certificate in a mesh or cross-certified environment.
1317 Every path built may require one or more of the following:
1318 validation of certificate properties, CPU intensive signature
1319 validations, CRL retrievals, increased network load, and local
1320 memory caching. Eliminating the superfluous paths can greatly
1321 improve performance, especially in the case where no path
1322 exists.
1324 There is a special case involving certificates with the same
1325 distinguished names but differing encodings required by [RFC3280].
1326 This case should not be considered a repeated certificate. See
1327 Section 5.4 for more information.
1329 2.4.2. Introduction to Path-Building Optimization
1331 How can these superfluous paths be eliminated? Rather than only
1332 disallowing identical certificates from repeating, it is recommended
1333 that a developer disallow the same public key and subject name pair
1334 from being repeated. For maximum flexibility, the subject name
1335 should collectively include any subject alternative names. Using
1336 this approach, all of the intended and needed paths should be
1337 available, and the excess and diluted paths should be eliminated.
1338 For example, using this approach, only one path exists from the TA Z
1339 to EE in the diagram above: TA Z->BCA->X->L->N->EE.
1346 Cooper, et al. Informational [Page 24]
1347 \f
1348 RFC 4158 Certification Path Building September 2005
1351 Given the simplifying rule of not repeating pairs of subject names
1352 (including subject alternative names) and public keys, and only using
1353 certificates found in the cACertificate and forward (issuedToThisCA)
1354 element of the crossCertificatePair attributes, Figure 10 depicts the
1355 forward path-building decision tree from the EE to all reachable
1356 nodes in the graph. This is the ideal graph for a path builder
1357 attempting to build a path from TA Z to EE.
1359 +------+ +-----------+ +------+ +---+
1360 | TA W |<------| Bridge CA |<-------| TA X |<--| L |
1361 +------+ +-----------+ +------+ +---+
1362 / \ ^
1363 / \ \
1364 / \ \
1365 v v \
1366 +------+ +------+ +---+
1367 | TA Y | | TA Z | | N |
1368 +------+ +------+ +---+
1369 ^
1370 \
1371 \
1372 +----+
1373 | EE |
1374 +----+
1376 Figure 10 - Forward (From Entity) Decision Tree
1378 It is not possible to build forward direction paths into the
1379 infrastructures behind CAs W, Y, and Z, because W, Y, and Z have not
1380 been issued certificates by their subordinate CAs. (The subordinate
1381 CAs are F and G, A and C, and O and P, respectively.) If simplicity
1382 and speed are desirable, the graph in Figure 10 is a very appealing
1383 way to structure the path-building algorithm. Finding a path from
1384 the EE to one of the four trust anchors is reasonably simple.
1385 Alternately, a developer could choose to build in the opposite
1386 direction, using the reverse cross-certificates from any one of the
1387 four trust anchors around the BCA. The graph in Figure 11 depicts
1388 all possible paths as a tree emanating from TA Z. (Note: it is not
1389 recommended that implementations attempt to determine all possible
1390 paths, this would require retrieval and storage of all PKI data
1391 including certificates and CRLs! This example is provided to
1392 demonstrate the complexity which might be encountered.)
1402 Cooper, et al. Informational [Page 25]
1403 \f
1404 RFC 4158 Certification Path Building September 2005
1407 +---+ +---+
1408 | I |--->| H |
1409 +---+ +---+
1410 ^
1411 | +---+ +---+
1412 | | H |--->| I |
1413 | +---+ +---+
1414 +---+ ^
1415 | G | / +---+ +---+ +---+
1416 +---+ / | F |--->| H |--->| I |
1417 ^ / +---+ +---+ +---+
1418 \ / ^
1419 \/ /
1420 +---+ +---+ +---+ +---+ +---+
1421 | F | | G |--->| I |--->| H | | M |
1422 +---+ +---+ +---+ +---+ +---+
1423 ^ ^ ^
1424 | / |
1425 +------+ +-----------+ +------+ +---+
1426 | TA W |<------| Bridge CA |-------->| TA X |-->| L |
1427 +------+ +-----------+ +------+ +---+
1428 / ^ \ \
1429 v \ v v
1430 +------+ +------+ +---+ +---+
1431 | TA Y | | TA Z | | J | | N |
1432 +------+ +------+ +---+ +---+
1433 / \ / \ \ \
1434 v v v v v v
1435 +---+ +---+ +---+ +---+ +---+ +----+
1436 | A | | C | | O | | P | | K | | EE |
1437 +---+ +---+ +---+ +---+ +---+ +----+
1438 / \ / \ / \ \
1439 v v v v v v v
1440 +---+ +---+ +---+ +---+ +---+ +---+ +---+
1441 | B | | C | | A | | B | | Q | | R | | S |
1442 +---+ +---+ +---+ +---+ +---+ +---+ +---+
1443 / \ \ \ \ \ \
1444 v v v v v v v
1445 +---+ +---+ +---+ +---+ +---+ +---+ +---+
1446 | E | | D | | B | | B | | E | | D | | T |
1447 +---+ +---+ +---+ +---+ +---+ +---+ +---+
1448 / | | \
1449 v v v v
1450 +---+ +---+ +---+ +---+
1451 | E | | D | | E | | D |
1452 +---+ +---+ +---+ +---+
1454 Figure 11 - Reverse (From Anchor) Decision Tree
1458 Cooper, et al. Informational [Page 26]
1459 \f
1460 RFC 4158 Certification Path Building September 2005
1463 Given the relative complexity of this decision tree, it becomes clear
1464 that making the right choices while navigating the tree can make a
1465 large difference in how quickly a valid path is returned. The path-
1466 building software could potentially traverse the entire graph before
1467 choosing the shortest path: TA Z->BCA->X->L->N->EE. With a decision
1468 tree like the one above, the basic depth first traversal approach
1469 introduces obvious inefficiencies in the path-building process. To
1470 compensate for this, a path-building module needs to decide not only
1471 in which direction to traverse the tree, but also which branches of
1472 the tree are more likely to yield a valid path.
1474 The path-building algorithm then ideally becomes a tree traversal
1475 algorithm with weights or priorities assigned to each branch point to
1476 guide the decision making. If properly designed, such an approach
1477 would effectively yield the "best path first" more often than not.
1478 (The terminology "best path first" is quoted because the definition
1479 of the "best" path may differ from PKI to PKI. That is ultimately to
1480 be determined by the developer, not by this document.) Finding the
1481 "best path first" is an effort to make the implementation efficient,
1482 which is one of our criteria as stated in Section 2.2.
1484 So how would a developer go about finding the best path first? Given
1485 the simplifying idea of addressing path building as a tree traversal,
1486 path building could be structured as a depth first search. A simple
1487 example of depth first tree traversal path building is depicted in
1488 Figure 12, with no preference given to sort order.
1490 Note: The arrows in the lower portion of the figure do not indicate
1491 the direction of certificate issuance; they indicate the direction of
1492 the tree traversal from the target certificate (EE).
1514 Cooper, et al. Informational [Page 27]
1515 \f
1516 RFC 4158 Certification Path Building September 2005
1519 +----+ +----+ +----+
1520 | TA | | TA | | TA |
1521 +----+ +----+ +----+
1522 / \ ^ ^
1523 / \ | |
1524 v v +---+ +---+
1525 +---+ +---+ | A | | C |
1526 | A |<->| C | +---+ +---+
1527 +---+ +---+ ^ ^
1528 ^ ^ +----+ | | +----+
1529 \ / | TA | | | | TA |
1530 v v +----+ | | +----+
1531 +---+ ^ | | ^
1532 | B | \ | | /
1533 +---+ \ | | /
1534 / \ +---+ +---+
1535 / \ | C | | A |
1536 v v +---+ +---+
1537 +---+ +---+ ^ ^
1538 | E | | D | | /
1539 +---+ +---+ | /
1540 +---+
1541 Infrastructure | B |
1542 +---+
1543 ^
1544 |
1545 +----+
1546 | EE |
1547 +----+
1549 The Same Infrastructure
1550 Represented as a Tree
1570 Cooper, et al. Informational [Page 28]
1571 \f
1572 RFC 4158 Certification Path Building September 2005
1575 +----+ +----+
1576 | TA | | TA |
1577 +----+ +----+
1578 ^ ^
1579 | |
1580 +---+ +---+
1581 | A | | C |
1582 +---+ +---+
1583 +----+ ^ ^ +----+
1584 | TA | | | | TA |
1585 +----+ | | +----+
1586 ^ | | ^
1587 \ | | /
1588 +---+ +---+ +---+ +---+
1589 | C | | C | | A | | A |
1590 +---+ +---+ +---+ +---+
1591 ^ ^ ^ ^
1592 | | / /
1593 | | / /
1594 +---+ +---+ +---+ +---+
1595 | B | | B | | B | | B |
1596 +---+ +---+ +---+ +---+
1597 ^ ^ ^ ^
1598 | | | |
1599 | | | |
1600 +----+ +----+ +----+ +----+
1601 | EE | | EE | | EE | | EE |
1602 +----+ +----+ +----+ +----+
1604 All possible paths from EE to TA
1605 using a depth first decision tree traversal
1607 Figure 12 - Path Building Using a Depth First Tree Traversal
1609 Figure 12 illustrates that four possible paths exist for this
1610 example. Suppose that the last path (TA->A->B->EE) is the only path
1611 that will validate. This could be for any combination of reasons
1612 such as name constraints, policy processing, validity periods, or
1613 path length constraints. The goal of an efficient path-building
1614 component is to select the fourth path first by testing properties of
1615 the certificates as the tree is traversed. For example, when the
1616 path-building software is at entity B in the graph, it should examine
1617 both choices A and C to determine which certificate is the most
1618 likely best choice. An efficient module would conclude that A is the
1619 more likely correct path. Then, at A, the module compares
1620 terminating the path at TA, or moving to C. Again, an efficient
1621 module will make the better choice (TA) and thereby find the "best
1622 path first".
1626 Cooper, et al. Informational [Page 29]
1627 \f
1628 RFC 4158 Certification Path Building September 2005
1631 What if the choice between CA certificates is not binary as it was in
1632 the previous example? What if the path-building software encounters
1633 a branch point with some arbitrary number of CA certificates thereby
1634 creating the same arbitrary number of tree branches? (This would be
1635 typical in a mesh style PKI CA, or at a Bridge CA directory entry, as
1636 each will have multiple certificates issued to itself from other
1637 CAs.) This situation actually does not change the algorithm at all,
1638 if it is structured properly. In our example, rather than treating
1639 each decision as binary (i.e., choosing A or C), the path-building
1640 software should sort all the available possibilities at any given
1641 branch point, and then select the best choice from the list. In the
1642 event the path could not be built through the first choice, then the
1643 second choice should be tried next upon traversing back to that point
1644 in the tree. Continue following this pattern until a path is found
1645 or all CA nodes in the tree have been traversed. Note that the
1646 certificates at any given point in the tree should only be sorted at
1647 the time a decision is first made. Specifically, in the example, the
1648 sorting of A and C is done when the algorithm reached B. There is no
1649 memory resident representation of the entire tree. Just like any
1650 other recursive depth first search algorithm, the only information
1651 the algorithm needs to keep track of is what nodes (entities) in the
1652 tree lie behind it on the current path, and for each of those nodes,
1653 which arcs (certificates) have already been tried.
1655 2.5. Building Certification Paths for Revocation Signer Certificates
1657 Special consideration is given to building a certification path for
1658 the Revocation Signer certificate because it may or may not be the
1659 same as the Certification Authority certificate. For example, after
1660 a CA performs a key rollover, the new CA certificate will be the CRL
1661 Signer certificate, whereas the old CA certificate is the
1662 Certification Authority certificate for previously issued
1663 certificates. In the case of indirect CRLs, the CRL Signer
1664 certificate will contain a different name and key than the
1665 Certification Authority certificate. In the case of OCSP, the
1666 Revocation Signer certificate may represent an OCSP Responder that is
1667 not the same entity as the Certification Authority.
1669 When the Revocation Signer certificate and the Certification
1670 Authority certificate are identical, no additional consideration is
1671 required from a certification path-building standpoint. That is, the
1672 certification path built (and validated) for the Certification
1673 Authority certificate can also be used as the certification path for
1674 the Revocation Signer certificate. In this case, the signature on
1675 the revocation data (e.g., CRL or OCSP response) is verified using
1676 the same certificate, and no other certification path building is
1677 required. An efficient certification path validation algorithm
1678 should first try all possible CRLs issued by the Certification
1682 Cooper, et al. Informational [Page 30]
1683 \f
1684 RFC 4158 Certification Path Building September 2005
1687 Authority to determine if any of the CRLs (a) cover the certificate
1688 in question, (b) are current, and (c) are signed using the same key
1689 used to sign the certificate.
1691 When the Revocation Signer certificate is not identical to the
1692 Certification Authority certificate, a certification path must be
1693 built (and validated) for the Revocation Signer certificate. In
1694 general, the certification path-building software may build the path
1695 as it would for any other certificate. However, this document also
1696 outlines methods in later sections for greatly improving path
1697 building efficiency for Revocation Signer certificate case.
1699 2.6. Suggested Path-Building Software Components
1701 There is no single way to define an interface to a path-building
1702 module. It is not the intent of this document to prescribe a
1703 particular method or semantic; rather, it is up to the implementer to
1704 decide. There are many ways this could be done. For example, a
1705 path-building module could build every conceivable path and return
1706 the entire list to the caller. Or, the module could build until it
1707 finds just one that validates and then terminate the procedure. Or,
1708 it could build paths in an iterative fashion, depending on validation
1709 outside of the builder and successive calls to the builder to get
1710 more paths until one valid path is found or all possible paths have
1711 been found. All of these are possible approaches, and each of these
1712 may offer different benefits to a particular environment or
1713 application.
1715 Regardless of semantics, a path-building module needs to contain the
1716 following components:
1718 1) The logic for building and traversing the certificate graph.
1720 2) Logic for retrieving the necessary certificates (and CRLs and/or
1721 other revocation status information if the path is to be
1722 validated) from the available source(s).
1724 Assuming a more efficient and agile path-building module is desired,
1725 the following is a good starting point and will tie into the
1726 remainder of this document. For a path-building module to take full
1727 advantage of all the suggested optimizations listed in this document,
1728 it will need all of the components listed below.
1730 1) A local certificate and CRL cache.
1732 a. This may be used by all certificate-using components; it does
1733 not need to be specific to the path-building software. A local
1734 cache could be memory resident, stored in an operating system
1738 Cooper, et al. Informational [Page 31]
1739 \f
1740 RFC 4158 Certification Path Building September 2005
1743 or application certificate store, stored in a database, or even
1744 stored in individual files on the hard disk. While the
1745 implementation of this cache is beyond the scope of this
1746 document, some design considerations are listed below.
1748 2) The logic for building and traversing the certificate graph/tree.
1750 a. This performs sorting functionality for prioritizing
1751 certificates (thereby optimizing path building) while
1752 traversing the tree.
1754 b. There is no need to build a complete graph prior to commencing
1755 path building. Since path building can be implemented as a
1756 depth first tree traversal, the path builder only needs to
1757 store the current location in the tree along with the points
1758 traversed to the current location. All completed branches can
1759 be discarded from memory and future branches are discovered as
1760 the tree is traversed.
1762 3) Logic for retrieving the necessary certificates from the available
1763 certificate source(s):
1765 a. Local cache.
1767 i. Be able to retrieve all certificates for an entity by
1768 subject name, as well as individual certificates by
1769 issuer and serial number tuple.
1771 ii. Tracking which directory attribute (including
1772 issuedToThisCA <forward> and issuedByThisCA <reverse>
1773 for split crossCertificatePair attributes) each
1774 certificate was found in may be useful. This allows for
1775 functionality such as retrieving only forward cross-
1776 certificates, etc.
1778 iii. A "freshness" timestamp (cache expiry time) can be used
1779 to determine when the directory should be searched
1780 again.
1782 b. LDAPv3 directory for certificates and CRLs.
1784 i. Consider supporting multiple directories for general
1785 queries.
1787 ii. Consider supporting dynamic LDAP connections for
1788 retrieving CRLs using an LDAP URI [RFC3986] in the CRL
1789 distribution point certificate extension.
1794 Cooper, et al. Informational [Page 32]
1795 \f
1796 RFC 4158 Certification Path Building September 2005
1799 iii. Support LDAP referrals. This is typically only a matter
1800 of activating the appropriate flag in the LDAP API.
1802 c. HTTP support for CRL distribution points and authority
1803 information access (AIA) support.
1805 i. Consider HTTPS support, but be aware that this may create
1806 an unbounded recursion when the implementation tries to
1807 build a certification path for the server's certificate if
1808 this in turn requires an additional HTTPS lookup.
1810 4) A certification path cache that stores previously validated
1811 relationships between certificates. This cache should include:
1813 a. A configurable expiration date for each entry. This date can
1814 be configured based upon factors such as the expiry of the
1815 information used to determine the validity of an entry,
1816 bandwidth, assurance level, storage space, etc.
1818 b. Support to store previously verified issuer certificate to
1819 subject certificate relationships.
1821 i. Since the issuer DN and serial number tuple uniquely
1822 identifies a certificate, a pair of these tuples (one for
1823 both the issuer and subject) is an effective method of
1824 storing this relationship.
1826 c. Support for storing "known bad" paths and certificates. Once a
1827 certificate is determined to be invalid, implementations can
1828 decide not to retry path development and validation.
1830 2.7. Inputs to the Path-Building Module
1832 [X.509] specifically addresses the list of inputs required for path
1833 validation but makes no specific suggestions concerning useful inputs
1834 to path building. However, given that the goal of path building is
1835 to find certification paths that will validate, it follows that the
1836 same inputs used for validation could be used to optimize path
1837 building.
1839 2.7.1. Required Inputs
1841 Setting aside configuration information such as repository or cache
1842 locations, the following are required inputs to the certification
1843 path-building process:
1845 1) The Target Certificate: The certificate that is to be validated.
1846 This is one endpoint for the path. (It is also possible to
1850 Cooper, et al. Informational [Page 33]
1851 \f
1852 RFC 4158 Certification Path Building September 2005
1855 provide information used to retrieve a certificate for a target,
1856 rather than the certificate itself.)
1858 2) Trust List: This is the other endpoint of the path, and can
1859 consist of either:
1861 a. Trusted CA certificates
1863 b. Trusted keys and DNs; a certificate is not necessarily required
1865 2.7.2. Optional Inputs
1867 In addition to the inputs listed in Section 2.7.1, the following
1868 optional inputs can also be useful for optimizing path building.
1869 However, if the path-building software takes advantage of all of the
1870 optimization methods described later in this document, all of the
1871 following optional inputs will be required.
1873 1) Time (T): The time for which the certificate is to be validated
1874 (e.g., if validating a historical signature from one year ago, T
1875 is needed to build a valid path)
1877 a. If not included as an input, the path-building software should
1878 always build for T equal to the current system time.
1880 2) Initial-inhibit-policy-mapping indicator
1882 3) Initial-require-explicit-policy indicator
1884 4) Initial-any-policy-inhibit indicator
1886 5) Initial user acceptable policy set
1888 6) Error handlers (call backs or virtual classes)
1890 7) Handlers for custom certificate extensions
1892 8) Is-revocation-provider indicator
1894 a. IMPORTANT: When building a certification path for an OCSP
1895 Responder certificate specified as part of the local
1896 configuration, this flag should not be set. It is set when
1897 building a certification path for a CRL Signer certificate or
1898 for an OCSP Responder Signer certificate discovered using the
1899 information asserted in an authorityInformationAccess
1900 certificate extension.
1906 Cooper, et al. Informational [Page 34]
1907 \f
1908 RFC 4158 Certification Path Building September 2005
1911 9) The complete certification path for the Certification Authority
1912 (if Is-revocation-provider is set)
1914 10) Collection of certificates that may be useful in building the
1915 path
1917 11) Collection of certificate revocation lists and/or other
1918 revocation data
1920 The last two items are a matter of convenience. Alternately,
1921 certificates and revocation information could be placed in a local
1922 cache accessible to the path-building module prior to attempting to
1923 build a path.
1925 3. Optimizing Path Building
1927 This section recommends methods for optimizing path-building
1928 processes.
1930 3.1. Optimized Path Building
1932 Path building can be optimized by sorting the certificates at every
1933 decision point (at every node in the tree) and then selecting the
1934 most promising certificate not yet selected as described in Section
1935 2.4.2. This process continues until the path terminates. This is
1936 roughly equivalent to the concept of creating a weighted edge tree,
1937 where the edges are represented by certificates and nodes represent
1938 subject DNs. However, unlike the weighted edge graph concept, a
1939 certification path builder need not have the entire graph available
1940 in order to function efficiently. In addition, the path builder can
1941 be stateless with respect to nodes of the graph not present in the
1942 current path, so the working data set can be relatively small.
1944 The concept of statelessness with respect to nodes not in the current
1945 path is instrumental to using the sorting optimizations listed in
1946 this document. Initially, it may seem that sorting a given group of
1947 certificates for a CA once and then preserving that sorted order for
1948 later use would be an efficient way to write the path builder.
1949 However, maintaining this state can quickly eliminate the efficiency
1950 that sorting provides. Consider the following diagram:
1962 Cooper, et al. Informational [Page 35]
1963 \f
1964 RFC 4158 Certification Path Building September 2005
1967 +---+
1968 | R |
1969 +---+
1970 ^
1971 /
1972 v
1973 +---+ +---+ +---+ +---+ +----+
1974 | A |<----->| E |<---->| D |--->| Z |--->| EE |
1975 +---+ +---+ +---+ +---+ +----+
1976 ^ ^ ^ ^
1977 \ / \ /
1978 \ / \ /
1979 v v v v
1980 +---+ +---+
1981 | B |<----->| C |
1982 +---+ +---+
1984 Figure 13 - Example of Path-Building Optimization
1986 In this example, the path builder is building in the forward (from
1987 target) direction for a path between R and EE. The path builder has
1988 also opted to allow subject name and key to repeat. (This will allow
1989 multiple traversals through any of the cross-certified CAs, creating
1990 enough complexity in this small example to illustrate proper state
1991 maintenance. Note that a similarly complex example could be designed
1992 by using multiple keys for each entity and prohibiting repetition.)
1994 The first step is simple; the builder builds the path Z(D)->EE(Z).
1995 Next the builder adds D and faces a decision between two
1996 certificates. (Choose between D(C) or D(E)). The builder now sorts
1997 the two choices in order of priority. The sorting is partially based
1998 upon what is currently in the path.
2000 Suppose the order the builder selects is [D(E), D(C)]. The current
2001 path is now D(E)->Z(D)->EE(Z). Currently the builder has three nodes
2002 in the graph (EE, Z, and D) and should maintain the state, including
2003 sort order of the certificates at D, when adding the next node, E.
2004 When E is added, the builder now has four certificates to sort: E(A),
2005 E(B), E(C), and E(D). In this case, the example builder opts for the
2006 order [E(C), E(B), E(A), E(D)]. The current path is now E(C)->D(E)->
2007 Z(D)->EE(Z) and the path has four nodes; EE, Z, D, and E.
2009 Upon adding the fifth node, C, the builder sorts the certificates
2010 (C(B), C(D), and C(E)) at C, and selects C(E). The path is now
2011 C(E)->E(C)->D(E)->Z(D)->EE(Z) and the path has five nodes: EE, Z, D,
2012 E, and C.
2018 Cooper, et al. Informational [Page 36]
2019 \f
2020 RFC 4158 Certification Path Building September 2005
2023 Now the builder finds itself back at node E with four certificates.
2024 If the builder were to use the prior sort order from the first
2025 encounter with E, it would have [E(C), E(B), E(A), E(D)]. In the
2026 current path's context, this ordering may be inappropriate. To begin
2027 with, the certificate E(C) is already in the path so it certainly
2028 does not deserve first place.
2030 The best way to handle this situation is for the path builder to
2031 handle this instance of E as a new (sixth) node in the tree. In
2032 other words, there is no state information for this new instance of E
2033 - it is treated just as any other new node. The certificates at the
2034 new node are sorted based upon the current path content and the first
2035 certificate is then selected. For example, the builder may examine
2036 E(B) and note that it contains a name constraint prohibiting "C". At
2037 this point in the decision tree, E(B) could not be added to the path
2038 and produce a valid result since "C" is already in the path. As a
2039 result, the certificate E(B) should placed at the bottom of the
2040 prioritized list.
2042 Alternatively, E(B) could be eliminated from this new node in the
2043 tree. It is very important to see that this certificate is
2044 eliminated only at this node and only for the current path. If path
2045 building fails through C and traverses back up the tree to the first
2046 instance of E, E(B) could still produce a valid path that does not
2047 include C; specifically R->A->B->E->D->Z->EE. Thus the state at any
2048 node should not alter the state of previous or subsequent nodes.
2049 (Except for prioritizing certificates in the subsequent nodes.)
2051 In this example, the builder should also note that E(C) is already in
2052 the path and should make it last or eliminate it from this node since
2053 certificates cannot be repeated in a path.
2055 If the builder eliminates both certificates E(B) and E(C) at this
2056 node, it is now only left to select between E(A) and E(D). Now the
2057 path has six nodes: EE, Z, D, E(1), C, and E(2). E(1) has four
2058 certificates, and E(2) has two, which the builder sorts to yield
2059 [E(A), E(D)]. The current path is now E(A)->C(E)->E(C)->D(E)->
2060 Z(D)->EE(Z). A(R) will be found when the seventh node is added to
2061 the path and the path terminated because one of the trust anchors has
2062 been found.
2064 In the event the first path fails to validate, the path builder will
2065 still have the seven nodes and associated state information to work
2066 with. On the next iteration, the path builder is able to traverse
2067 back up the tree to a working decision point, such as A, and select
2068 the next certificate in the sorted list at A. In this example, that
2069 would be A(B). (A(R) has already been tested.) This would dead end,
2070 and the builder traverse back up to the next decision point, E(2)
2074 Cooper, et al. Informational [Page 37]
2075 \f
2076 RFC 4158 Certification Path Building September 2005
2079 where it would try D(E). This process repeats until the traversal
2080 backs all the way up to EE or a valid path is found. If the tree
2081 traversal returns to EE, all possible paths have been exhausted and
2082 the builder can conclude no valid path exists.
2084 This approach of sorting certificates in order to optimize path
2085 building will yield better results than not optimizing the tree
2086 traversal. However, the path-building process can be further
2087 streamlined by eliminating certificates, and entire branches of the
2088 tree as a result, as paths are built.
2090 3.2. Sorting vs. Elimination
2092 Consider a situation when building a path in which three CA
2093 certificates are found for a given target certificate and must be
2094 prioritized. When the certificates are examined, as in the previous
2095 example, one of the three has a name constraint present that will
2096 invalidate the path built thus far. When sorting the three
2097 certificates, that one would certainly go to the back of the line.
2098 However, the path-building software could decide that this condition
2099 eliminates the certificate from consideration at this point in the
2100 graph, thereby reducing the number of certificate choices by 33% at
2101 this point.
2103 NOTE: It is important to understand that the elimination of a
2104 certificate only applies to a single decision point during the tree
2105 traversal. The same certificate may appear again at another point in
2106 the tree; at that point it may or may not be eliminated. The
2107 previous section details an example of this behavior.
2109 Elimination of certificates could potentially eliminate the traversal
2110 of a large, time-consuming infrastructure that will never lead to a
2111 valid path. The question of whether to sort or eliminate is one that
2112 pits the flexibility of the software interface against efficiency.
2114 To be clear, if one eliminates invalid paths as they are built,
2115 returning only likely valid paths, the end result will be an
2116 efficient path-building module. The drawback to this is that unless
2117 the software makes allowances for it, the calling application will
2118 not be able to see what went wrong. The user may only see the
2119 unrevealing error message: "No certification path found."
2121 On the other hand, the path-building module could opt to not rule out
2122 any certification paths. The path-building software could then
2123 return any and all paths it can build from the certificate graph. It
2124 is then up to the validation engine to determine which are valid and
2125 which are invalid. The user or calling application can then have
2126 complete details on why each and every path fails to validate. The
2130 Cooper, et al. Informational [Page 38]
2131 \f
2132 RFC 4158 Certification Path Building September 2005
2135 drawback is obviously one of performance, as an application or end
2136 user may wait for an extended period of time while cross-certified
2137 PKIs are navigated in order to build paths that will never validate.
2139 Neither option is a very desirable approach. One option provides
2140 good performance for users, which is beneficial. The other option
2141 though allows administrators to diagnose problems with the PKI,
2142 directory, or software. Below are some recommendations to reach a
2143 middle ground on this issue.
2145 First, developers are strongly encouraged to output detailed log
2146 information from the path-building software. The log should
2147 explicitly indicate every choice the builder makes and why. It
2148 should clearly identify which certificates are found and used at each
2149 step in building the path. If care is taken to produce a useful log,
2150 PKI administrators and help desk personnel will have ample
2151 information to diagnose a problem with the PKI. Ideally, there would
2152 be a mechanism for turning this logging on and off, so that it is not
2153 running all the time. Additionally, it is recommended that the log
2154 contain information so that a developer or tester can recreate the
2155 paths tried by the path-building software, to assist with diagnostics
2156 and testing.
2158 Secondly, it is desirable to return something useful to the user.
2159 The easiest approach is probably to implement a "dual mode" path-
2160 building module. In the first mode [mode 1], the software eliminates
2161 any and all paths that will not validate, making it very efficient.
2162 In the second mode [mode 2], all the sorting methods are still
2163 applied, but no paths are eliminated based upon the sorting methods.
2164 Having this dual mode allows the module to first fail to find a valid
2165 path, but still return one invalid path (assuming one exists) by
2166 switching over to the second mode long enough to generate a single
2167 path. This provides a middle ground -- the software is very fast,
2168 but still returns something that gives the user a more specific error
2169 than "no path found".
2171 Third, it may be useful to not rule out any paths, but instead limit
2172 the number of paths that may be built given a particular input.
2173 Assuming the path-building module is designed to return the "best
2174 path first", the paths most likely to validate would be returned
2175 before this limit is reached. Once the limit is reached the module
2176 can stop building paths, providing a more rapid response to the
2177 caller than one which builds all possible paths.
2179 Ultimately, the developer determines how to handle the trade-off
2180 between efficiency and provision of information. A developer could
2181 choose the middle ground by opting to implement some optimizations as
2182 elimination rules and others as not. A developer could validate
2186 Cooper, et al. Informational [Page 39]
2187 \f
2188 RFC 4158 Certification Path Building September 2005
2191 certificate signatures, or even check revocation status while
2192 building the path, and then make decisions based upon the outcome of
2193 those checks as to whether to eliminate the certificate in question.
2195 This document suggests the following approach:
2197 1) While building paths, eliminate any and all certificates that do
2198 not satisfy all path validation requirements with the following
2199 exceptions:
2201 a. Do not check revocation status if it requires a directory
2202 lookup or network access
2204 b. Do not check digital signatures (see Section 8.1, General
2205 Considerations for Building A Certification Path, for
2206 additional considerations).
2208 c. Do not check anything that cannot be checked as part of the
2209 iterative process of traversing the tree.
2211 d. Create a detailed log, if this feature is enabled.
2213 e. If a path cannot be found, the path builder shifts to "mode 2"
2214 and allows the building of a single bad path.
2216 i. Return the path with a failure indicator, as well as
2217 error information detailing why the path is bad.
2219 2) If path building succeeds, validate the path in accordance with
2220 [X.509] and [RFC3280] with the following recommendations:
2222 a. For a performance boost, do not re-check items already checked
2223 by the path builder. (Note: if pre-populated paths are supplied
2224 to the path-building system, the entire path has to be fully
2225 re-validated.)
2227 b. If the path validation failed, call the path builder again to
2228 build another path.
2230 i. Always store the error information and path from the
2231 first iteration and return this to the user in the event
2232 that no valid path is found. Since the path-building
2233 software was designed to return the "best path first",
2234 this path should be shown to the user.
2236 As stated above, this document recommends that developers do not
2237 validate digital signatures or check revocation status as part of the
2238 path-building process. This recommendation is based on two
2242 Cooper, et al. Informational [Page 40]
2243 \f
2244 RFC 4158 Certification Path Building September 2005
2247 assumptions about PKI and its usage. First, signatures in a working
2248 PKI are usually good. Since signature validation is costly in terms
2249 of processor time, it is better to delay signature checking until a
2250 complete path is found and then check the signatures on each
2251 certificate in the certification path starting with the trust anchor
2252 (see Section 8.1). Second, it is fairly uncommon in typical
2253 application environments to encounter a revoked certificate;
2254 therefore, most certificates validated will not be revoked. As a
2255 result, it is better to delay retrieving CRLs or other revocation
2256 status information until a complete path has been found. This
2257 reduces the probability of retrieving unneeded revocation status
2258 information while building paths.
2260 3.3. Representing the Decision Tree
2262 There are a multitude of ways to implement certification path
2263 building and as many ways to represent the decision tree in memory.
2265 The method described below is an approach that will work well with
2266 the optimization methods listed later in this document. Although
2267 this approach is the best the authors of this document have
2268 implemented, it is by no means the only way to implement it.
2269 Developers should tailor this approach to their own requirements or
2270 may find that another approach suits their environment, programming
2271 language, or programming style.
2273 3.3.1. Node Representation for CA Entities
2275 A "node" in the certification graph is a collection of CA
2276 certificates with identical subject DNs. Minimally, for each node,
2277 in order to fully implement the optimizations to follow, the path-
2278 building module will need to be able to keep track of the following
2279 information:
2281 1. Certificates contained in the node
2283 2. Sorted order of the certificates
2285 3. "Current" certificate indicator
2287 4. The current policy set (It may be split into authority and user
2288 constrained sets, if desired.)
2290 - It is suggested that encapsulating the policy set in an object
2291 with logic for manipulating the set such as performing
2292 intersections, mappings, etc., will simplify implementation.
2298 Cooper, et al. Informational [Page 41]
2299 \f
2300 RFC 4158 Certification Path Building September 2005
2303 5. Indicators (requireExplicitPolicy, inhibitPolicyMapping,
2304 anyPolicyInhibit) and corresponding skipCert values
2306 6. A method for indicating which certificates are eliminated or
2307 removing them from the node.
2309 - If nodes are recreated from the cache on demand, it may be
2310 simpler to remove eliminated certificates from the node.
2312 7. A "next" indicator that points to the next node in the current
2313 path
2315 8. A "previous" indicator that points to the previous node in the
2316 current path
2318 3.3.2. Using Nodes to Iterate Over All Paths
2320 In simplest form, a node is created, the certificates are sorted, the
2321 next subject DN required is determined from the first certificate,
2322 and a new node is attached to the certification path via the next
2323 indicator (Number 7 above). This process continues until the path
2324 terminates. (Note: end entity certificates may not contain subject
2325 DNs as allowed by [RFC3280]. Since end entity certificates by
2326 definition do not issue certificates, this has no impact on the
2327 process.)
2329 Keeping in mind that the following algorithm is designed to be
2330 implemented using recursion, consider the example in Figure 12 and
2331 assume that the only path in the diagram is valid for E is TA->A->
2332 B->E:
2334 If our path-building module is building a path in the forward
2335 direction for E, a node is first created for E. There are no
2336 certificates to sort because only one certificate exists, so all
2337 initial values are loaded into the node from E. For example, the
2338 policy set is extracted from the certificate and stored in the node.
2340 Next, the issuer DN (B) is read from E, and new node is created for B
2341 containing both certificates issued to B -- B(A) and B(C). The
2342 sorting rules are applied to these two certificates and the sorting
2343 algorithm returns B(C);B(A). This sorted order is stored and the
2344 current indicator is set to B(C). Indicators are set and the policy
2345 sets are calculated to the extent possible with respect to B(C). The
2346 following diagram illustrates the current state with the current
2347 certificate indicated with a "*".
2354 Cooper, et al. Informational [Page 42]
2355 \f
2356 RFC 4158 Certification Path Building September 2005
2359 +-------------+ +---------------+
2360 | Node 1 | | Node 2 |
2361 | Subject: E |--->| Subject: B |
2362 | Issuers: B* | | Issuers: C*,A |
2363 +-------------+ +---------------+
2365 Next, a node is created for C and all three certificates are added to
2366 it. The sorting algorithm happens to return the certificates sorted
2367 in the following order: C(TA);C(A);C(B)
2369 +-------------+ +---------------+ +------------------+
2370 | Node 1 | | Node 2 | | Node 3 |
2371 | Subject: E |--->| Subject: B |--->| Subject: C |
2372 | Issuers: B | | Issuers: C*,A | | Issuers: TA*,A,B |
2373 +-------------+ +---------------+ +------------------+
2375 Recognizing that the trust anchor has been found, the path
2376 (TA->C->B->E) is validated but fails. (Remember that the only valid
2377 path happens to be TA->A->B->E.) The path-building module now moves
2378 the current certificate indicator in node 3 to C(A), and adds the
2379 node for A.
2381 +-------------+ +---------------+ +------------------+
2382 | Node 1 | | Node 2 | | Node 3 |
2383 | Subject: E |--->| Subject: B |--->| Subject: C |
2384 | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B |
2385 +-------------+ +---------------+ +------------------+
2386 |
2387 v
2388 +------------------+
2389 | Node 4 |
2390 | Subject: A |
2391 | Issuers: TA*,C,B |
2392 +------------------+
2394 The path TA->A->C->B->E is validated and it fails. The path-building
2395 module now moves the current indicator in node 4 to A(C) and adds a
2396 node for C.
2410 Cooper, et al. Informational [Page 43]
2411 \f
2412 RFC 4158 Certification Path Building September 2005
2415 +-------------+ +---------------+ +------------------+
2416 | Node 1 | | Node 2 | | Node 3 |
2417 | Subject: E |--->| Subject: B |--->| Subject: C |
2418 | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B |
2419 +-------------+ +---------------+ +------------------+
2420 |
2421 v
2422 +------------------+ +------------------+
2423 | Node 5 | | Node 4 |
2424 | Subject: C |<---| Subject: A |
2425 | Issuers: TA*,A,B | | Issuers: TA,C*,B |
2426 +------------------+ +------------------+
2428 At this juncture, the decision of whether to allow repetition of name
2429 and key comes to the forefront. If the certification path-building
2430 module will NOT allow repetition of name and key, there are no
2431 certificates in node 5 that can be used. (C and the corresponding
2432 public key is already in the path at node 3.) At this point, node 5
2433 is removed from the current path and the current certificate
2434 indicator on node 4 is moved to A(B).
2436 If instead, the module is only disallowing repetition of
2437 certificates, C(A) is eliminated from node 5 since it is in use in
2438 node 3, and path building continues by first validating TA->C->A->
2439 C->B->E, and then continuing to try to build paths through C(B).
2440 After this also fails to provide a valid path, node 5 is removed from
2441 the current path and the current certificate indicator on node 4 is
2442 moved to A(B).
2444 +-------------+ +---------------+ +------------------+
2445 | Node 1 | | Node 2 | | Node 3 |
2446 | Subject: E |--->| Subject: B |--->| Subject: C |
2447 | Issuers: B | | Issuers: C*,A | | Issuers: TA,A*,B |
2448 +-------------+ +---------------+ +------------------+
2449 |
2450 v
2451 +------------------+
2452 | Node 4 |
2453 | Subject: A |
2454 | Issuers: TA,C,B* |
2455 +------------------+
2457 Now a new node 5 is created for B. Just as with the prior node 5, if
2458 not repeating name and key, B also offers no certificates that can be
2459 used (B and B's public key is in use in node 2) so the new node 5 is
2460 also removed from the path. At this point all certificates in node 4
2461 have now been tried, so node 4 is removed from the path, and the
2462 current indicator on node 3 is moved to C(B).
2466 Cooper, et al. Informational [Page 44]
2467 \f
2468 RFC 4158 Certification Path Building September 2005
2471 Also as above, if allowing repetition of name and key, B(C) is
2472 removed from the new node 5 (B(C) is already in use in node 3) and
2473 paths attempted through the remaining certificate B(A). After this
2474 fails, it will lead back to removing node 5 from the path. At this
2475 point all certificates in node 4 have now been tried, so node 4 is
2476 removed from the path, and the current indicator on node 3 is moved
2477 to C(B).
2479 This process continues until all certificates in node 1 (if there
2480 happened to be more than one) have been tried, or until a valid path
2481 has been found. Once the process ends and in the event no valid path
2482 was found, it may be concluded that no path can be found from E to
2483 TA.
2485 3.4. Implementing Path-Building Optimization
2487 The following section describes methods that may be used for
2488 optimizing the certification path-building process by sorting
2489 certificates. Optimization as described earlier seeks to prioritize
2490 a list of certificates, effectively prioritizing (weighting) branches
2491 of the graph/tree. The optimization methods can be used to assign a
2492 cumulative score to each certificate. The process of scoring the
2493 certificates amounts to testing each certificate against the
2494 optimization methods a developer chooses to implement, and then
2495 adding the score for each test to a cumulative score for each
2496 certificate. After this is completed for each certificate at a given
2497 branch point in the builder's decision tree, the certificates can be
2498 sorted so that the highest scoring certificate is selected first, the
2499 second highest is selected second, etc.
2501 For example, suppose the path builder has only these two simple
2502 sorting methods:
2504 1) If the certificate has a subject key ID, +5 to score.
2505 2) If the certificate has an authority key ID, +10 to score.
2507 And it then examined three certificates:
2509 1) Issued by CA 1; has authority key ID; score is 10.
2510 2) Issued by CA 2; has subject key ID; score is 5.
2511 3) Issued by CA 1; has subject key ID and authority key ID; score is
2512 15.
2514 The three certificates are sorted in descending order starting with
2515 the highest score: 3, 1, and 2. The path-building software should
2516 first try building the path through certificate 3. Failing that, it
2517 should try certificate 1. Lastly, it should try building a path
2518 through certificate 2.
2522 Cooper, et al. Informational [Page 45]
2523 \f
2524 RFC 4158 Certification Path Building September 2005
2527 The following optimization methods specify tests developers may
2528 choose to perform, but does not suggest scores for any of the
2529 methods. Rather, developers should evaluate each method with respect
2530 to the environment in which the application will operate, and assign
2531 weights to each accordingly in the path-building software.
2532 Additionally, many of the optimization methods are not binary in
2533 nature. Some are tri-valued, and some may be well suited to sliding
2534 or exponential scales. Ultimately, the implementer decides the
2535 relative merits of each optimization with respect to his or her own
2536 software or infrastructure.
2538 Over and above the scores for each method, many methods can be used
2539 to eliminate branches during the tree traversal rather than simply
2540 scoring and weighting them. All cases where certificates could be
2541 eliminated based upon an optimization method are noted with the
2542 method descriptions.
2544 Many of the sorting methods described below are based upon what has
2545 been perceived by the authors as common in PKIs. Many of the methods
2546 are aimed at making path building for the common PKI fast, but there
2547 are cases where most any sorting method could lead to inefficient
2548 path building. The desired behavior is that although one method may
2549 lead the algorithm in the wrong direction for a given situation or
2550 configuration, the remaining methods will overcome the errant
2551 method(s) and send the path traversal down the correct branch of the
2552 tree more often than not. This certainly will not be true for every
2553 environment and configuration, and these methods may need to be
2554 tweaked for further optimization in the application's target
2555 operating environment.
2557 As a final note, the list contained in this document is not intended
2558 to be exhaustive. A developer may desire to define additional
2559 sorting methods if the operating environment dictates the need.
2561 3.5. Selected Methods for Sorting Certificates
2563 The reader should draw no specific conclusions as to the relative
2564 merits or scores for each of the following methods based upon the
2565 order in which they appear. The relative merit of any sorting
2566 criteria is completely dependent on the specifics of the operating
2567 environment. For most any method, an example can be created to
2568 demonstrate the method is effective and a counter-example could be
2569 designed to demonstrate that it is ineffective.
2571 Each sorting method is independent and may (or may not) be used to
2572 assign additional scores to each certificate tested. The implementer
2573 decides which methods to use and what weights to assign them. As
2574 noted previously, this list is also not exhaustive.
2578 Cooper, et al. Informational [Page 46]
2579 \f
2580 RFC 4158 Certification Path Building September 2005
2583 In addition, name chaining (meaning the subject name of the issuer
2584 certificate matches the issuer name of the issued certificate) is not
2585 addressed as a sorting method since adherence to this is required in
2586 order to build the decision tree to which these methods will be
2587 applied. Also, unaddressed in the sorting methods is the prevention
2588 of repeating certificates. Path builders should handle name chaining
2589 and certificate repetition irrespective of the optimization approach.
2591 Each sorting method description specifies whether the method may be
2592 used to eliminate certificates, the number of possible numeric values
2593 (sorting weights) for the method, components from Section 2.6 that
2594 are required for implementing the method, forward and reverse methods
2595 descriptions, and finally a justification for inclusion of the
2596 method.
2598 With regard to elimination of certificates, it is important to
2599 understand that certificates are eliminated only at a given decision
2600 point for many methods. For example, the path built up to
2601 certificate X may be invalidated due to name constraints by the
2602 addition of certificate Y. At this decision point only, Y could be
2603 eliminated from further consideration. At some future decision
2604 point, while building this same path, the addition of Y may not
2605 invalidate the path.
2607 For some other sorting methods, certificates could be eliminated from
2608 the process entirely. For example, certificates with unsupported
2609 signature algorithms could not be included in any path and validated.
2610 Although the path builder may certainly be designed to operate in
2611 this fashion, it is sufficient to always discard certificates only
2612 for a given decision point regardless of cause.
2614 3.5.1. basicConstraints Is Present and cA Equals True
2616 May be used to eliminate certificates: Yes
2617 Number of possible values: Binary
2618 Components required: None
2620 Forward Method: Certificates with basicConstraints present and
2621 cA=TRUE, or those designated as CA certificates out-of-band have
2622 priority. Certificates without basicConstraints, with
2623 basicConstraints and cA=FALSE, or those that are not designated as CA
2624 certificates out-of-band may be eliminated or have zero priority.
2626 Reverse Method: Same as forward except with regard to end entity
2627 certificates at the terminus of the path.
2629 Justification: According to [RFC3280], basicConstraints is required
2630 to be present with cA=TRUE in all CA certificates, or must be
2634 Cooper, et al. Informational [Page 47]
2635 \f
2636 RFC 4158 Certification Path Building September 2005
2639 verified via an out-of-band mechanism. A valid path cannot be built
2640 if this condition is not met.
2642 3.5.2. Recognized Signature Algorithms
2644 May be used to eliminate certificates: Yes
2645 Number of possible values: Binary
2646 Components required: None
2648 Forward Method: Certificates containing recognized signature and
2649 public key algorithms [PKIXALGS] have priority.
2651 Reverse Method: Same as forward.
2653 Justification: If the path-building software is not capable of
2654 processing the signatures associated with the certificate, the
2655 certification path cannot be validated.
2657 3.5.3. keyUsage Is Correct
2659 May be used to eliminate certificates: Yes
2660 Number of possible values: Binary
2661 Components required: None
2663 Forward Method: If keyUsage is present, certificates with
2664 keyCertSign set have 100% priority. If keyUsage is present and
2665 keyCertSign is not set, the certificate may be eliminated or have
2666 zero priority. All others have zero priority.
2668 Reverse Method: Same as forward except with regard to end entity
2669 certificates at the terminus of the path.
2671 Justification: A valid certification path cannot be built through a
2672 CA certificate with inappropriate keyUsage. Note that
2673 digitalSignature is not required to be set in a CA certificate.
2675 3.5.4. Time (T) Falls within the Certificate Validity
2677 May be used to eliminate certificates: Yes
2678 Number of possible values: Binary
2679 Components required: None
2681 Forward Method: Certificates that contain the required time (T)
2682 within their validity period have 100% priority. Otherwise, the
2683 certificate is eliminated or has priority zero.
2685 Reverse Method: Same as forward.
2690 Cooper, et al. Informational [Page 48]
2691 \f
2692 RFC 4158 Certification Path Building September 2005
2695 Justification: A valid certification path cannot be built if T falls
2696 outside of the certificate validity period.
2698 NOTE: Special care should be taken to return a meaningful error to
2699 the caller, especially in the event the target certificate does not
2700 meet this criterion, if this sorting method is used for elimination.
2701 (e.g., the certificate is expired or is not yet valid).
2703 3.5.5. Certificate Was Previously Validated
2705 May be used to eliminate certificates: No
2706 Number of possible values: Binary
2707 Components required: Certification Path Cache
2709 Forward Method: A certificate that is present in the certification
2710 path cache has priority.
2712 Reverse Method: Does not apply. (The validity of a certificate vs.
2713 unknown validity does not infer anything about the correct direction
2714 in the decision tree. In other words, knowing the validity of a CA
2715 certificate does not indicate that the target is more likely found
2716 through that path than another.)
2718 Justification: Certificates in the path cache have been validated
2719 previously. Assuming the initial constraints have not changed, it is
2720 highly likely that the path from that certificate to a trust anchor
2721 is still valid. (Changes to the initial constraints may cause a
2722 certificate previously considered valid to no longer be considered
2723 valid.)
2725 Note: It is important that items in the path cache have appropriate
2726 life times. For example, it could be inappropriate to cache a
2727 relationship beyond the period the related CRL will be trusted by the
2728 application. It is also critical to consider certificates and CRLs
2729 farther up the path when setting cache lifetimes. For example, if
2730 the issuer certificate expires in ten days, but the issued
2731 certificate is valid for 20 days, caching the relationship beyond 10
2732 days would be inappropriate.
2734 3.5.6. Previously Verified Signatures
2736 May be used to eliminate certificates: Yes
2737 Number of possible values: Binary
2738 Components required: Path Cache
2740 Forward Method: If a previously verified relationship exists in the
2741 path cache between the subject certificate and a public key present
2742 in one or more issuer certificates, all the certificates containing
2746 Cooper, et al. Informational [Page 49]
2747 \f
2748 RFC 4158 Certification Path Building September 2005
2751 said public key have higher priority. Other certificates may be
2752 eliminated or set to zero priority.
2754 Reverse Method: If known bad signature relationships exist between
2755 certificates, these relationships can be used to eliminate potential
2756 certificates from the decision tree. Nothing can be concluded about
2757 the likelihood of finding a given target certificate down one branch
2758 versus another using known good signature relationships.
2760 Justification: If the public key in a certificate (A) was previously
2761 used to verify a signature on a second certificate (B), any and all
2762 certificates containing the same key as (A) may be used to verify the
2763 signature on (B). Likewise, any certificates that do not contain the
2764 same key as (A) cannot be used to verify the signature on (B). This
2765 forward direction method is especially strong for multiply cross-
2766 certified CAs after a key rollover has occurred.
2768 3.5.7. Path Length Constraints
2770 May be used to eliminate certificates: Yes
2771 Number of possible values: Binary
2772 Components required: None
2774 Forward Method: Certificates with basic constraints present and
2775 containing a path length constraint that would invalidate the current
2776 path (the current length is known since the software is building from
2777 the target certificate) may be eliminated or set to zero priority.
2778 Otherwise, the priority is 100%.
2780 Reverse Method: This method may be applied in reverse. To apply it,
2781 the builder keeps a current path length constraint variable and then
2782 sets zero priority for (or eliminates) certificates that would
2783 violate the constraint.
2785 Justification: A valid path cannot be built if the path length
2786 constraint has been violated.
2788 3.5.8. Name Constraints
2790 May be used to eliminate certificates: Yes
2791 Number of possible values: Binary
2792 Components required: None
2794 Forward Method: Certificates that contain nameConstraints that would
2795 be violated by certificates already in the path to this point are
2796 given zero priority or eliminated.
2802 Cooper, et al. Informational [Page 50]
2803 \f
2804 RFC 4158 Certification Path Building September 2005
2807 Reverse Method: Certificates that will allow successful processing
2808 of any name constraints present in the path to this point are given
2809 higher priority.
2811 Justification: A valid path cannot be built if name constraints are
2812 violated.
2814 3.5.9. Certificate Is Not Revoked
2816 May be used to eliminate certificates: No
2817 Number of possible values: Three
2818 Components required: CRL Cache
2820 Forward Method: If a current CRL for a certificate is present in the
2821 CRL cache, and the certificate serial number is not on the CRL, the
2822 certificate has priority. If the certificate serial number is
2823 present on the CRL, it has zero priority. If an (acceptably fresh)
2824 OCSP response is available for a certificate, and identifies the
2825 certificate as valid, the certificate has priority. If an OCSP
2826 response is available for a certificate, and identifies the
2827 certificate as invalid, the certificate has zero priority.
2829 Reverse Method: Same as Forward.
2831 Alternately, the certificate may be eliminated if the CRL or OCSP
2832 response is verified. That is, fully verify the CRL or OCSP response
2833 signature and relationship to the certificate in question in
2834 accordance with [RFC3280]. While this is viable, the signature
2835 verification required makes it less attractive as an elimination
2836 method. It is suggested that this method only be used for sorting
2837 and that CRLs and OCSP responses are validated post path building.
2839 Justification: Certificates known to be not revoked can be
2840 considered more likely to be valid than certificates for which the
2841 revocation status is unknown. This is further justified if CRL or
2842 OCSP response validation is performed post path validation - CRLs or
2843 OCSP responses are only retrieved when complete paths are found.
2845 NOTE: Special care should be taken to allow meaningful errors to
2846 propagate to the caller, especially in cases where the target
2847 certificate is revoked. If a path builder eliminates certificates
2848 using CRLs or OCSP responses, some status information should be
2849 preserved so that a meaningful error may be returned in the event no
2850 path is found.
2858 Cooper, et al. Informational [Page 51]
2859 \f
2860 RFC 4158 Certification Path Building September 2005
2863 3.5.10. Issuer Found in the Path Cache
2865 May be used to eliminate certificates: No
2866 Number of possible values: Binary
2867 Components required: Certification Path Cache
2869 Forward Method: A certificate whose issuer has an entry (or entries)
2870 in the path cache has priority.
2872 Reverse Method: Does not apply.
2874 Justification: Since the path cache only contains entries for
2875 certificates that were previously validated back to a trust anchor,
2876 it is more likely than not that the same or a new path may be built
2877 from that point to the (or one of the) trust anchor(s). For
2878 certificates whose issuers are not found in the path cache, nothing
2879 can be concluded.
2881 NOTE: This method is not the same as the method named "Certificate
2882 Was Previously Validated". It is possible for this sorting method to
2883 evaluate to true while the other method could evaluate to zero.
2885 3.5.11. Issuer Found in the Application Protocol
2887 May be used to eliminate certificates: No
2888 Number of possible values: Binary
2889 Components required: Certification Path Cache
2891 Forward Method: If the issuer of a certificate sent by the target
2892 through the application protocol (SSL/TLS, S/MIME, etc.), matches the
2893 signer of the certificate you are looking at, then that certificate
2894 has priority.
2896 Reverse Method: If the subject of a certificate matches the issuer
2897 of a certificate sent by the target through the application protocol
2898 (SSL/TLS, S/MIME, etc.), then that certificate has priority.
2900 Justification: The application protocol may contain certificates
2901 that the sender considers valuable to certification path building,
2902 and are more likely to lead to a path to the target certificate.
2904 3.5.12. Matching Key Identifiers (KIDs)
2906 May be used to eliminate certificates: No
2907 Number of possible values: Three
2908 Components required: None
2910 Forward Method: Certificates whose subject key identifier (SKID)
2914 Cooper, et al. Informational [Page 52]
2915 \f
2916 RFC 4158 Certification Path Building September 2005
2919 matches the current certificate's authority key identifier (AKID)
2920 have highest priority. Certificates without a SKID have medium
2921 priority. Certificates whose SKID does not match the current
2922 certificate's AKID (if both are present) have zero priority. If the
2923 current certificate expresses the issuer name and serial number in
2924 the AKID, certificates that match both these identifiers have highest
2925 priority. Certificates that match only the issuer name in the AKID
2926 have medium priority.
2928 Reverse Method: Certificates whose AKID matches the current
2929 certificate's SKID have highest priority. Certificates without an
2930 AKID have medium priority. Certificates whose AKID does not match
2931 the current certificate's SKID (if both are present) have zero
2932 priority. If the certificate expresses the issuer name and serial
2933 number in the AKID, certificates that match both these identifiers in
2934 the current certificate have highest priority. Certificates that
2935 match only the issuer name in the AKID have medium priority.
2937 Justification: Key Identifier (KID) matching is a very useful
2938 mechanism for guiding path building (that is their purpose in the
2939 certificate) and should therefore be assigned a heavy weight.
2941 NOTE: Although required to be present by [RFC3280], it is extremely
2942 important that KIDs be used only as sorting criteria or as hints
2943 during certification path building. KIDs are not required to match
2944 during certification path validation and cannot be used to eliminate
2945 certificates. This is of critical importance for interoperating
2946 across domains and multi-vendor implementations where the KIDs may
2947 not be calculated in the same fashion.
2949 3.5.13. Policy Processing
2951 May be used to eliminate certificates: Yes
2952 Number of possible values: Three
2953 Components required: None
2955 Forward Method: Certificates that satisfy Forward Policy Chaining
2956 have priority. (See Section 4 entitled "Forward Policy Chaining" for
2957 details.) If the caller provided an initial-policy-set and did not
2958 set the initial-require-explicit flag, the weight of this sorting
2959 method should be increased. If the initial-require-explicit-policy
2960 flag was set by the caller or by a certificate, certificates may be
2961 eliminated.
2963 Reverse Method: Certificates that contain policies/policy mappings
2964 that will allow successful policy processing of the path to this
2965 point have priority. If the caller provided an initial-policy-set
2966 and did not set the initial-require-explicit flag, the weight of this
2970 Cooper, et al. Informational [Page 53]
2971 \f
2972 RFC 4158 Certification Path Building September 2005
2975 sorting method should be increased. Certificates may be eliminated
2976 only if initial-require-explicit was set by the caller or if
2977 require-explicit-policy was set by a certificate in the path to this
2978 point.
2980 Justification: In a policy-using environment, certificates that
2981 successfully propagate policies are more likely part of an intended
2982 certification path than those that do not.
2984 When building in the forward direction, it is always possible that a
2985 certificate closer to the trust anchor will set the require-
2986 explicit-policy indicator; so giving preference to certification
2987 paths that propagate policies may increase the probability of finding
2988 a valid path first. If the caller (or a certificate in the current
2989 path) has specified or set the initial-require-explicit-policy
2990 indicator as true, this sorting method can also be used to eliminate
2991 certificates when building in the forward direction.
2993 If building in reverse, it is always possible that a certificate
2994 farther along the path will set the require-explicit-policy
2995 indicator; so giving preference to those certificates that propagate
2996 policies will serve well in that case. In the case where require-
2997 explicit-policy is set by certificates or the caller, certificates
2998 can be eliminated with this method.
3000 3.5.14. Policies Intersect the Sought Policy Set
3002 May be used to eliminate certificates: No
3003 Number of possible values: Additive
3004 Components required: None
3006 Forward Method: Certificates that assert policies found in the
3007 initial-acceptable-policy-set have priority. Each additional
3008 matching policy could have an additive affect on the total score.
3010 Alternately, this could be binary; it matches 1 or more, or matches
3011 none.
3013 Reverse Method: Certificates that assert policies found in the
3014 target certificate or map policies to those found in the target
3015 certificate have priority. Each additional matching policy could
3016 have an additive affect on the total score. Alternately, this could
3017 be binary; it matches 1 or more, or matches none.
3019 Justification: In the forward direction, as the path draws near to
3020 the trust anchor in a cross-certified environment, the policies
3021 asserted in the CA certificates will match those in the caller's
3022 domain. Since the initial acceptable policy set is specified in the
3026 Cooper, et al. Informational [Page 54]
3027 \f
3028 RFC 4158 Certification Path Building September 2005
3031 caller's domain, matches may indicate that the path building is
3032 drawing nearer to a desired trust anchor. In the reverse direction,
3033 finding policies that match those of the target certificate may
3034 indicate that the path is drawing near to the target's domain.
3036 3.5.15. Endpoint Distinguished Name (DN) Matching
3038 May be used to eliminate certificates: No
3039 Number of possible values: Binary
3040 Components required: None
3042 Forward Method: Certificates whose issuer exactly matches a trust
3043 anchor subject DN have priority.
3045 Reverse Method: Certificates whose subject exactly matches the
3046 target entity issuer DN have priority.
3048 Justification: In the forward direction, if a certificate's issuer
3049 DN matches a trust anchor's DN [X.501], then it may complete the
3050 path. In the reverse direction, if the certificate's subject DN
3051 matches the issuer DN of the target certificate, it may be the last
3052 certificate required to complete the path.
3054 3.5.16. Relative Distinguished Name (RDN) Matching
3056 May be used to eliminate certificates: No
3057 Number of possible values: Sliding Scale
3058 Components required: None
3060 Forward Method: Certificates that match more ordered RDNs between
3061 the issuer DN and a trust anchor DN have priority. When all the RDNs
3062 match, this yields the highest priority.
3064 Reverse Method: Certificates with subject DNs that match more RDNs
3065 with the target's issuer DN have higher priority. When all the RDNs
3066 match, this yields the highest priority.
3068 Justification: In PKIs the DNs are frequently constructed in a tree
3069 like fashion. Higher numbers of matches may indicate that the trust
3070 anchor is to be found in that direction within the tree. Note that
3071 in the case where all the RDNs match [X.501], this sorting method
3072 appears to mirror the preceding one. However, this sorting method
3073 should be capable of producing a 100% weight even if the issuer DN
3074 has more RDNs than the trust anchor. The Issuer DN need only contain
3075 all the RDNs (in order) of the trust anchor.
3077 NOTE: In the case where all RDNs match, this sorting method mirrors
3078 the functionality of the preceding one. This allows for partial
3082 Cooper, et al. Informational [Page 55]
3083 \f
3084 RFC 4158 Certification Path Building September 2005
3087 matches to be weighted differently from exact matches. Additionally,
3088 this method can require a lot of processing if many trust anchors are
3089 present.
3091 3.5.17. Certificates are Retrieved from cACertificate Directory
3092 Attribute
3094 May be used to eliminate certificates: No
3095 Number of possible values: Binary
3096 Components required: Certificate Cache with flags for the attribute
3097 from where the certificate was retrieved and Remote Certificate
3098 Storage/Retrieval using a directory
3100 Forward Method: Certificates retrieved from the cACertificate
3101 directory attribute have priority over certificates retrieved from
3102 the crossCertificatePair attribute. (See [RFC2587].)
3104 Reverse Method: Does not apply.
3106 Justification: The cACertificate directory attribute contains
3107 certificates issued from local sources and self issued certificates.
3108 By using the cACertificate directory attribute before the
3109 crossCertificatePair attribute, the path-building algorithm will
3110 (depending on the local PKI configuration) tend to demonstrate a
3111 preference for the local PKI before venturing to external cross-
3112 certified PKIs. Most of today's PKI applications spend most of their
3113 time processing information from the local (user's own) PKI, and the
3114 local PKI is usually very efficient to traverse due to proximity and
3115 network speed.
3117 3.5.18. Consistent Public Key and Signature Algorithms
3119 May be used to eliminate certificates: Yes
3120 Number of possible values: Binary
3121 Components required: None
3123 Forward Method: If the public key in the issuer certificate matches
3124 the algorithm used to sign the subject certificate, then it has
3125 priority. (Certificates with unmatched public key and signature
3126 algorithms may be eliminated.)
3128 Reverse Method: If the public key in the current certificate matches
3129 the algorithm used to sign the subject certificate, then it has
3130 priority. (Certificates with unmatched public key and signature
3131 algorithms may be eliminated.)
3133 Justification: Since the public key and signature algorithms are not
3134 consistent, the signature on the subject certificate will not verify
3138 Cooper, et al. Informational [Page 56]
3139 \f
3140 RFC 4158 Certification Path Building September 2005
3143 successfully. For example, if the issuer certificate contains an RSA
3144 public key, then it could not have issued a subject certificate
3145 signed with the DSA-with-SHA-1 algorithm.
3147 3.5.19. Similar Issuer and Subject Names
3149 May be used to eliminate certificates: No
3150 Number of possible values: Sliding Scale
3151 Components required: None
3153 Forward Method: Certificates encountered with a subject DN that
3154 matches more RDNs with the issuer DN of the target certificate have
3155 priority.
3157 Reverse Method: Same as forward.
3159 Justification: As it is generally more efficient to search the local
3160 domain prior to branching to cross-certified domains, using
3161 certificates with similar names first tends to make a more efficient
3162 path builder. Cross-certificates issued from external domains will
3163 generally match fewer RDNs (if any), whereas certificates in the
3164 local domain will frequently match multiple RDNs.
3166 3.5.20. Certificates in the Certification Cache
3168 May be used to eliminate certificates: No
3169 Number of possible values: Three
3170 Components required: Local Certificate Cache and Remote Certificate
3171 Storage/Retrieval (e.g., LDAP directory as the repository)
3173 Forward Method: A certificate whose issuer certificate is present in
3174 the certificate cache and populated with certificates has higher
3175 priority. A certificate whose issuer's entry is fully populated with
3176 current data (all certificate attributes have been searched within
3177 the timeout period) has higher priority.
3179 Reverse Method: If the subject of a certificate is present in the
3180 certificate cache and populated with certificates, then it has higher
3181 priority. If the entry is fully populated with current data (all
3182 certificate attributes have been searched within the timeout period)
3183 then it has higher priority.
3185 Justification: The presence of required directory values populated
3186 in the cache increases the likelihood that all the required
3187 certificates and CRLs needed to complete the path from this
3188 certificate to the trust anchor (or target if building in reverse)
3189 are present in the cache from a prior path being developed, thereby
3194 Cooper, et al. Informational [Page 57]
3195 \f
3196 RFC 4158 Certification Path Building September 2005
3199 eliminating the need for directory access to complete the path. In
3200 the event no path can be found, the performance cost is low since the
3201 certificates were likely not retrieved from the network.
3203 3.5.21. Current CRL Found in Local Cache
3205 May be used to eliminate certificates: No
3206 Number of possible values: Binary
3207 Components Required: CRL Cache
3209 Forward Method: Certificates have priority if the issuer's CRL entry
3210 exists and is populated with current data in the CRL cache.
3212 Reverse Method: Certificates have priority if the subject's CRL
3213 entry exists and is populated with current data in the CRL cache.
3215 Justification: If revocation is checked only after a complete path
3216 has been found, this indicates that a complete path has been found
3217 through this entity at some past point, so a path still likely
3218 exists. This also helps reduce remote retrievals until necessary.
3220 3.6. Certificate Sorting Methods for Revocation Signer Certification
3221 Paths
3223 Unless using a locally-configured OCSP responder or some other
3224 locally-configured trusted revocation status service, certificate
3225 revocation information is expected to be provided by the PKI that
3226 issued the certificate. It follows that when building a
3227 certification path for a Revocation Signer certificate, it is
3228 desirable to confine the building algorithm to the PKI that issued
3229 the certificate. The following sorting methods seek to order
3230 possible paths so that the intended Revocation Signer certification
3231 path is found first.
3233 These sorting methods are not intended to be used in lieu of the ones
3234 described in the previous section; they are most effective when used
3235 in conjunction with those in Section 3.5. Some sorting criteria below
3236 have identical names as those in the preceding section. This
3237 indicates that the sorting criteria described in the preceding
3238 section are modified slightly when building the Revocation Signer
3239 certification path.
3241 3.6.1. Identical Trust Anchors
3243 May be used to eliminate certificates: No
3244 Number of possible values: Binary
3245 Components required: Is-revocation-signer indicator and the
3246 Certification Authority's trust anchor
3250 Cooper, et al. Informational [Page 58]
3251 \f
3252 RFC 4158 Certification Path Building September 2005
3255 Forward Method: Not applicable.
3257 Reverse Method: Path building should begin from the same trust
3258 anchor used to validate the Certification Authority before trying any
3259 other trust anchors. If any trust anchors exist with a different
3260 public key but an identical subject DN to that of the Certification
3261 Authority's trust anchor, they should be tried prior to those with
3262 mismatched names.
3264 Justification: The revocation information for a given certificate
3265 should be produced by the PKI that issues the certificate.
3266 Therefore, building a path from a different trust anchor than the
3267 Certification Authority's is not desirable.
3269 3.6.2. Endpoint Distinguished Name (DN) Matching
3271 May be used to eliminate certificates: No
3272 Number of possible values: Binary
3273 Components required: Is-revocation-signer indicator and the
3274 Certification Authority's trust anchor
3276 Forward Method: Operates identically to the sorting method described
3277 in 3.5.15, except that instead of performing the matching against all
3278 trust anchors, the DN matching is performed only against the trust
3279 anchor DN used to validate the CA certificate.
3281 Reverse Method: No change for Revocation Signer's certification
3282 path.
3284 Justification: The revocation information for a given certificate
3285 should be produced by the PKI that issues the certificate.
3286 Therefore, building a path to a different trust anchor than the CA's
3287 is not desirable. This sorting method helps to guide forward
3288 direction path building toward the trust anchor used to validate the
3289 CA certificate.
3291 3.6.3. Relative Distinguished Name (RDN) Matching
3293 May be used to eliminate certificates: No
3294 Number of possible values: Sliding Scale
3295 Components required: Is-revocation-signer indicator and the
3296 Certification Authority's trust anchor
3298 Forward Method: Operates identically to the sorting method described
3299 in 3.5.16 except that instead of performing the RDN matching against
3300 all trust anchors, the matching is performed only against the trust
3301 anchor DN used to validate the CA certificate.
3306 Cooper, et al. Informational [Page 59]
3307 \f
3308 RFC 4158 Certification Path Building September 2005
3311 Reverse Method: No change for Revocation Signer's certification
3312 path.
3314 Justification: The revocation information for a given certificate
3315 should be produced by the PKI that issues the certificate.
3316 Therefore, building a path to a different trust anchor than the CA's
3317 is not desirable. This sorting method helps to guide forward
3318 direction path building toward the trust anchor used to validate the
3319 CA certificate.
3321 3.6.4. Identical Intermediate Names
3323 May be used to eliminate certificates: No
3324 Number of possible values: Binary
3325 Components required: Is-revocation-signer indicator and the
3326 Certification Authority's complete certification path
3328 Forward Method: If the issuer DN in the certificate matches the
3329 issuer DN of a certificate in the Certification Authority's path, it
3330 has higher priority.
3332 Reverse Method: If the subject DN in the certificate matches the
3333 subject DN of a certificate in the Certification Authority's path, it
3334 has higher priority.
3336 Justification: Following the same path as the Certificate should
3337 deter the path-building algorithm from wandering in an inappropriate
3338 direction. Note that this sorting method is indifferent to whether
3339 the certificate is self-issued. This is beneficial in this situation
3340 because it would be undesirable to lower the priority of a re-key
3341 certificate.
3343 4. Forward Policy Chaining
3345 It is tempting to jump to the conclusion that certificate policies
3346 offer little assistance to path building when building from the
3347 target certificate. It's easy to understand the "validate as you go"
3348 approach from the trust anchor, and much less obvious that any value
3349 can be derived in the other direction. However, since policy
3350 validation consists of the intersection of the issuer policy set with
3351 the subject policy set and the mapping of policies from the issuer
3352 set to the subject set, policy validation can be done while building
3353 a path in the forward direction as well as the reverse. It is simply
3354 a matter of reversing the procedure. That is not to say this is as
3355 ideal as policy validation when building from the trust anchor, but
3356 it does offer a method that can be used to mostly eliminate what has
3357 long been considered a weakness inherent to building in the forward
3358 (from the target certificate) direction.
3362 Cooper, et al. Informational [Page 60]
3363 \f
3364 RFC 4158 Certification Path Building September 2005
3367 4.1. Simple Intersection
3369 The most basic form of policy processing is the intersection of the
3370 policy sets from the first CA certificate through the target
3371 certificate. Fortunately, the intersection of policy sets will
3372 always yield the same final set regardless of the order of
3373 intersection. This allows processing of policy set intersections in
3374 either direction. For example, if the trust anchor issues a CA
3375 certificate (A) with policies {X,Y,Z}, and that CA issues another CA
3376 certificate (B) with policies {X,Y}, and CA B then issues a third CA
3377 certificate (C) with policy set {Y,G}, one normally calculates the
3378 policy set from the trust anchor as follows:
3380 1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}
3382 2) Intersect that result, {X,Y} with C{Y,G} to yield the final set
3383 {Y}
3385 Now it has been shown that certificate C is good for policy Y.
3387 The other direction is exactly the same procedure, only in reverse:
3389 1) Intersect C{Y,G} with B{X,Y} to yield the set {Y}
3391 2) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
3392 {Y}
3394 Just like in the reverse direction, it has been shown that
3395 certificate C is good for policy Y, but this time in the forward
3396 direction.
3398 When building in the forward direction, policy processing is handled
3399 much like it is in reverse -- the software lends preference to
3400 certificates that propagate policies. Neither approach guarantees
3401 that a path with valid policies will be found, but rather both
3402 approaches help guide the path in the direction it should go in order
3403 for the policies to propagate.
3405 If the caller has supplied an initial-acceptable-policy set, there is
3406 less value in using it when building in the forward direction unless
3407 the caller also set inhibit-policy-mapping. In that case, the path
3408 builder can further constrain the path building to propagating
3409 policies that exist in the initial-acceptable-policy-set. However,
3410 even if the inhibit-policy-mapping is not set, the initial-policy-set
3411 can still be used to guide the path building toward the desired trust
3412 anchor.
3418 Cooper, et al. Informational [Page 61]
3419 \f
3420 RFC 4158 Certification Path Building September 2005
3423 4.2. Policy Mapping
3425 When a CA issues a certificate into another domain, an environment
3426 with disparate policy identifiers to its own, the CA may make use of
3427 policy mappings to map equivalence from the local domain's policy to
3428 the non-local domain's policy. If in the prior example, A had
3429 included a policy mapping that mapped X to G in the certificate it
3430 issued to B, C would be good for X and Y:
3432 1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}
3434 2) Process Policy Mappings in B's certificate (X maps to G) to yield
3435 {G,Y} (same as {Y,G})
3437 3) Intersect that result, {G,Y} with C{Y,G} to yield the final set
3438 {G,Y}
3440 Since policies are always expressed in the relying party's domain,
3441 the certificate C is said to be good for {X, Y}, not {Y, G}. This is
3442 because "G" doesn't mean anything in the context of the trust anchor
3443 that issued A without the policy mapping.
3445 When building in the forward direction, policies can be "unmapped" by
3446 reversing the mapping procedure. This procedure is limited by one
3447 important aspect: if policy mapping has occurred in the forward
3448 direction, there is no mechanism by which it can be known in advance
3449 whether or not a future addition to the current path will invalidate
3450 the policy chain (assuming one exists) by setting inhibit-policy-
3451 mapping. Fortunately, it is uncommon practice to set this flag. The
3452 following is the procedure for processing policy mapping in the
3453 forward direction:
3455 1) Begin with C's policy set {Y,G}
3457 2) Apply the policy mapping in B's certificate (X maps to G) in
3458 reverse to yield {Y,X} (same as {X,Y})
3460 3) Intersect the result {X,Y} with B{X,Y} to yield the set {X,Y}
3462 4) Intersect that result, {X,Y}, with A{X,Y,Z} to yield the final set
3463 {X,Y}
3465 Just like in the reverse direction, it is determined in the forward
3466 direction that certificate C is good for policies {X,Y}. If during
3467 this procedure, an inhibit-policy-mapping flag was encountered, what
3468 should be done? This is reasonably easy to keep track of as well.
3469 The software simply maintains a flag on any policies that were
3470 propagated as a result of a mapping; just a simple Boolean kept with
3474 Cooper, et al. Informational [Page 62]
3475 \f
3476 RFC 4158 Certification Path Building September 2005
3479 the policies in the set. Imagine now that the certificate issued to
3480 A has the inhibit-policy-mapping constraint expressed with a skip
3481 certificates value of zero.
3483 1) Begin with C's policy set {Y,G}
3485 2) Apply the policy mapping in B's certificate and mark X as
3486 resulting from a mapping. (X maps to G) in reverse to yield {Y,Xm}
3487 (same as {Xm,Y})
3489 3) Intersect the result {Xm,Y} with B{X,Y} to yield the set {Xm,Y}
3491 4) A's certificate expresses the inhibit policy mapping constraint,
3492 so eliminate any policies in the current set that were propagated
3493 due to mapping (which is Xm) to yield {Y}
3495 5) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
3496 {Y}
3498 If in our example, the policy set had gone to empty at any point (and
3499 require-explicit-policy was set), the path building would back up and
3500 try to traverse another branch of the tree. This is analogous to the
3501 path-building functionality utilized in the reverse direction when
3502 the policy set goes to empty.
3504 4.3. Assigning Scores for Forward Policy Chaining
3506 Assuming the path-building module is maintaining the current forward
3507 policy set, weights may be assigned using the following procedure:
3509 1) For each CA certificate being scored:
3511 a. Copy the current forward policy set.
3513 b. Process policy mappings in the CA certificate in order to
3514 "un-map" policies, if any.
3516 c. Intersect the resulting set with CA certificate's policies.
3518 The larger the policy set yielded, the larger the score for that CA
3519 certificate.
3521 2) If an initial acceptable set was supplied, intersect this set with
3522 the resulting set for each CA certificate from (1).
3524 The larger the resultant set, the higher the score is for this
3525 certificate.
3530 Cooper, et al. Informational [Page 63]
3531 \f
3532 RFC 4158 Certification Path Building September 2005
3535 Other scoring schemes may work better if the operating environment
3536 dictates.
3538 5. Avoiding Path-Building Errors
3540 This section defines some errors that may occur during the path-
3541 building process, as well as ways to avoid these errors when
3542 developing path-building functions.
3544 5.1. Dead Ends
3546 When building certification paths in a non-hierarchical PKI
3547 structure, a simple path-building algorithm could fail prematurely
3548 without finding an existing path due to a "dead end". Consider the
3549 example in Figure 14.
3551 +----+ +---+
3552 | TA | | Z |
3553 +----+ +---+
3554 | |
3555 | |
3556 V V
3557 +---+ +---+
3558 | C |<-----| Y |
3559 +---+ +---+
3560 |
3561 |
3562 V
3563 +--------+
3564 | Target |
3565 +--------+
3567 Figure 14 - Dead End Example
3569 Note that in the example, C has two certificates: one issued by Y,
3570 and the other issued by the Trust Anchor. Suppose that a simple
3571 "find issuer" algorithm is used, and the order in which the path
3572 builder found the certificates was Target(C), C(Y), Y(Z), Z(Z). In
3573 this case, Z has no certificates issued by any other entities, and so
3574 the simplistic path-building process stops. Since Z is not the
3575 relying party's trust anchor, the certification path is not complete,
3576 and will not validate. This example shows that in anything but the
3577 simplest PKI structure, additional path-building logic will need to
3578 handle the cases in which entities are issued multiple certificates
3579 from different issuers. The path-building algorithm will also need
3580 to have the ability to traverse back up the decision tree and try
3581 another path in order to be robust.
3586 Cooper, et al. Informational [Page 64]
3587 \f
3588 RFC 4158 Certification Path Building September 2005
3591 5.2. Loop Detection
3593 In a non-hierarchical PKI structure, a path-building algorithm may
3594 become caught in a loop without finding an existing path. Consider
3595 the example below:
3597 +----+
3598 | TA |
3599 +----+
3600 |
3601 |
3602 +---+ +---+
3603 | A | ->| Z |
3604 +---+ / +---+
3605 | / |
3606 | / |
3607 V / V
3608 +---+ +---+
3609 | B |<-----| Y |
3610 +---+ +---+
3611 |
3612 |
3613 V
3614 +--------+
3615 | Target |
3616 +--------+
3618 Figure 15 - Loop Example
3620 Let us suppose that in this example the simplest "find issuer"
3621 algorithm is used, and the order in which certificates are retrieved
3622 is Target(B), B(Y), Y(Z), Z(B), B(Y), Y(Z), Z(B), B(Y), ... A loop
3623 has formed that will cause the correct path (Target, B, A) to never
3624 be found. The certificate processing system will need to recognize
3625 loops created by duplicate certificates (which are prohibited in a
3626 path by [X.509]) before they form to allow the certification path-
3627 building process to continue and find valid paths. The authors of
3628 this document recommend that the loop detection not only detect the
3629 repetition of a certificate in the path, but also detect the presence
3630 of the same subject name / subject alternative name/ subject public
3631 key combination occurring twice in the path. A name/key pair should
3632 only need to appear once in the path. (See Section 2.4.2 for more
3633 information on the reasoning behind this recommendation.)
3642 Cooper, et al. Informational [Page 65]
3643 \f
3644 RFC 4158 Certification Path Building September 2005
3647 5.3. Use of Key Identifiers
3649 Inconsistent and/or incompatible approaches to computing the subject
3650 key identifier and authority key identifier in public key
3651 certificates can cause failures in certification path-building
3652 algorithms that use those fields to identify certificates, even
3653 though otherwise valid certification paths may exist. Path-building
3654 implementations should use existing key identifiers and not attempt
3655 to re-compute subject key identifiers. It is extremely important
3656 that Key Identifiers be used only as sorting criteria or hints. KIDs
3657 are not required to match during certification path validation and
3658 cannot be used to eliminate certificates. This is of critical
3659 importance for interoperating across domains and multi-vendor
3660 implementations where the KIDs may not be calculated in the same
3661 fashion.
3663 Path-building and processing implementations should not rely on the
3664 form of authority key identifier that uses the authority DN and
3665 serial number as a restrictive matching rule, because cross-
3666 certification can lead to this value not being matched by the cross-
3667 certificates.
3669 5.4. Distinguished Name Encoding
3671 Certification path-building software should not rely on DNs being
3672 encoded as PrintableString. Although frequently encoded as
3673 PrintableString, DNs may also appear as other types, including
3674 BMPString or UTF8String. As a result, software systems that are
3675 unable to process BMPString and UTF8String encoded DNs may be unable
3676 to build and validate some certification paths.
3678 Furthermore, [RFC3280] compliant certificates are required to encode
3679 DNs as UTF8String as of January 1, 2004. Certification path-building
3680 software should be prepared to handle "name rollover" certificates as
3681 described in [RFC3280]. Note that the inclusion of a "name rollover"
3682 certificate in a certification path does not constitute repetition of
3683 a DN and key. Implementations that include the "name rollover"
3684 certificate in the path should ensure that the DNs with differing
3685 encoding are regarded as dissimilar. (Implementations may instead
3686 handle matching DNs of different encodings and will therefore not
3687 need to include "name rollover" certificates in the path.)
3698 Cooper, et al. Informational [Page 66]
3699 \f
3700 RFC 4158 Certification Path Building September 2005
3703 6. Retrieval Methods
3705 Building a certification path requires the availability of the
3706 certificates and CRLs that make up the path. There are many
3707 different methods for obtaining these certificates and CRLs. This
3708 section lists a few of the common ways to perform this retrieval, as
3709 well as some suggested approaches for improving performance. This
3710 section is not intended to provide a complete reference for
3711 certificate and CRL retrieval methods or optimizations that would be
3712 useful in certification path building.
3714 6.1. Directories Using LDAP
3716 Most applications utilize the Lightweight Directory Access Protocol
3717 (LDAP) when retrieving data from directories following the X.500
3718 model. Applications may encounter directories which support either
3719 LDAP v2 [RFC1777] or LDAP v3 [RFC3377].
3721 The LDAP v3 specification defines one attribute retrieval option, the
3722 "binary" option. When specified in an LDAP retrieval request, this
3723 option was intended to force the directory to ignore any string-based
3724 representations of BER-encoded directory information, and send the
3725 requested attribute(s) in BER format. Since all PKI objects of
3726 concern are BER-encoded objects, the "binary" option should be used.
3727 However, not all directories support the "binary" option. Therefore,
3728 applications should be capable of requesting attributes with and
3729 without the "binary" option. For example, if an application wishes
3730 to retrieve the userCertificate attribute, the application should
3731 request "userCertificate;binary". If the desired information is not
3732 returned, robust implementations may opt to request "userCertificate"
3733 as well.
3735 The following attributes should be considered by PKI application
3736 developers when performing certificate retrieval from LDAP sources:
3738 userCertificate: contains certificates issued by one or more
3739 certification authorities with a subject DN that matches that of
3740 the directory entry. This is a multi-valued attribute and all
3741 values should be received and considered during path building.
3742 Although typically it is expected that only end entity
3743 certificates will be stored in this attribute, (e.g., this is the
3744 attribute an application would request to find a person's
3745 encryption certificate) implementers may opt to search this
3746 attribute when looking in CA entries to make their path builder
3747 more robust. If it is empty, the overhead added by including this
3748 attribute when already requesting one or both of the two below is
3749 marginal.
3754 Cooper, et al. Informational [Page 67]
3755 \f
3756 RFC 4158 Certification Path Building September 2005
3759 cACertificate: contains self-issued certificates (if any) and any
3760 certificates issued to this certification authority by other
3761 certification authorities in the same realm. (Realm is dependent
3762 upon local policy.) This is a multi-valued attribute and all
3763 values should be received and considered during path building.
3765 crossCertificatePair: in conformant implementations, the
3766 crossCertificatePair is used to contain all, except self-issued
3767 certificates issued to this certification authority, as well as
3768 certificates issued by this certification authority to other
3769 certification authorities. Each attribute value is a structure
3770 containing two elements. The issuedToThisCA element contains
3771 certificates issued to this certification authority by other
3772 certification authorities. The issuedByThisCA element contains
3773 certificates issued by this certification authority to other
3774 certification authorities. Both elements of the
3775 crossCertificatePair are labeled optional in the ASN.1 definition.
3776 If both elements are present in a single value, the issuer name in
3777 one certificate is required to match the subject name in the other
3778 and vice versa, and the subject public key in one certificate
3779 shall be capable of verifying the digital signature on the other
3780 certificate and vice versa. As this technology has evolved,
3781 different standards have had differing requirements on where
3782 information could be found. For example, the LDAP v2 schema
3783 [RFC2587] states that the issuedToThisCA (once called 'forward')
3784 element of the crossCertificatePair attribute is mandatory and the
3785 issuedByThisCA (once called 'reverse') element is optional. In
3786 contrast, Section 11.2.3 of [X.509] requires the issuedByThisCA
3787 element to be present if the CA issues a certificate to another CA
3788 if the subject is not a subordinate CA in a hierarchy. Conformant
3789 directories behave as required by [X.509], but robust path-
3790 building implementations may want to retrieve all certificates
3791 from the cACertificate and crossCertificatePair attributes to
3792 ensure all possible certification authority certificates are
3793 obtained.
3795 certificateRevocationList: the certificateRevocationList attribute
3796 contains a certificate revocation list (CRL). A CRL is defined in
3797 [RFC3280] as a time stamped list identifying revoked certificates,
3798 which is signed by a CA or CRL issuer and made freely available in
3799 a public repository. Each revoked certificate is identified in a
3800 CRL by its certificate serial number. There may be one or more
3801 CRLs in this attribute, and the values should be processed in
3802 accordance with [RFC3280].
3810 Cooper, et al. Informational [Page 68]
3811 \f
3812 RFC 4158 Certification Path Building September 2005
3815 authorityRevocationList: the authorityRevocationList attribute also
3816 contains CRLs. These CRLs contain revocation information
3817 regarding certificates issued to other CAs. There may be one or
3818 more CRLs in this attribute, and the values should be processed in
3819 accordance with [RFC3280].
3821 Certification path processing systems that plan to interoperate with
3822 varying PKI structures and directory designs should at a minimum be
3823 able to retrieve and process the userCertificate, cACertificate,
3824 crossCertificatePair, certificateRevocationList, and
3825 authorityRevocationList attributes from directory entries.
3827 6.2. Certificate Store Access via HTTP
3829 Another possible method of certificate retrieval is using HTTP as an
3830 interface mechanism for retrieving certificates and CRLs from PKI
3831 repositories. A current PKIX document [CERTSTORE] provides a
3832 protocol for a general-purpose interface capability for retrieving
3833 certificates and CRLs from PKI repositories. Since the [CERTSTORE]
3834 document is a work in progress as of the writing of this document, no
3835 details are given here on how to utilize this mechanism for
3836 certificate and CRL retrieval. Instead, refer to the [CERTSTORE]
3837 document or its current version. Certification path processing
3838 systems may wish to implement support for this interface capability,
3839 especially if they will be used in environments that will provide
3840 HTTP-based access to certificates and CRLs.
3842 6.3. Authority Information Access
3844 The authority information access (AIA) extension, defined within
3845 [RFC3280], indicates how to access CA information and services for
3846 the issuer of the certificate in which the extension appears. If a
3847 certificate with an AIA extension contains an accessMethod defined
3848 with the id-ad-caIssuers OID, the AIA may be used to retrieve one or
3849 more certificates for the CA that issued the certificate containing
3850 the AIA extension. The AIA will provide a uniform resource
3851 identifier (URI) [RFC3986] when certificates can be retrieved via
3852 LDAP, HTTP, or FTP. The AIA will provide a directoryName when
3853 certificates can be retrieved via directory access protocol (DAP).
3854 The AIA will provide an rfc822Name when certificates can be retrieved
3855 via electronic mail. Additionally, the AIA may specify the location
3856 of an OCSP [RFC2560] responder that is able to provide revocation
3857 information for the certificate.
3859 If present, AIA may provide forward path-building implementations
3860 with a direct link to a certificate for the issuer of a given
3861 certificate. Therefore, implementations may wish to provide support
3862 for decoding the AIA extension and processing the LDAP, HTTP, FTP,
3866 Cooper, et al. Informational [Page 69]
3867 \f
3868 RFC 4158 Certification Path Building September 2005
3871 DAP, or e-mail locators. Support for AIA is optional; [RFC3280]
3872 compliant implementations are not required to populate the AIA
3873 extension. However, implementers of path-building and validation
3874 modules are strongly encouraged to support AIA, especially the HTTP
3875 transport; this will provide for usability and interoperability with
3876 many existing PKIs.
3878 6.4. Subject Information Access
3880 The subject information access (SIA) extension, defined within
3881 [RFC3280], indicates how to access information and services for the
3882 subject of the certificate in which the extension appears. If a
3883 certificate with an SIA extension contains an accessMethod defined
3884 with the id-ad-caRepository OID, the SIA may be used to locate one or
3885 more certificates (and possibly CRLs) for entities issued
3886 certificates by the subject. The SIA will provide a uniform resource
3887 identifier (URI) [RFC3986] when data can be retrieved via LDAP, HTTP,
3888 or FTP. The SIA will provide a directoryName when data can be
3889 retrieved via directory access protocol (DAP). The SIA will provide
3890 an rfc822Name when data can be retrieved via electronic mail.
3892 If present, the SIA extension may provide reverse path-building
3893 implementations with the certificates required to continue building
3894 the path. Therefore, implementations may wish to provide support for
3895 decoding the SIA extension and processing the LDAP, HTTP, FTP, DAP,
3896 or e-mail locators. Support for SIA is optional; [RFC3280] compliant
3897 implementations are not required to populate the SIA extension.
3898 However, implementers of path-building and validation modules are
3899 strongly encouraged to support SIA, especially the HTTP transport;
3900 this will provide for usability and interoperability with many
3901 existing PKIs.
3903 6.5. CRL Distribution Points
3905 The CRL distribution points (CRLDP) extension, defined within
3906 [RFC3280], indicates how to access CRL information. If a CRLDP
3907 extension appears within a certificate, the CRL(s) to which the CRLDP
3908 refer are generally the CRLs that would contain revocation
3909 information for the certificate. The CRLDP extension may point to
3910 multiple distribution points from which the CRL information may be
3911 obtained; the certificate processing system should process the CRLDP
3912 extension in accordance with [RFC3280]. The most common distribution
3913 points contain URIs from which the appropriate CRL may be downloaded,
3914 and directory names, which can be queried in a directory to retrieve
3915 the CRL attributes from the corresponding entry.
3922 Cooper, et al. Informational [Page 70]
3923 \f
3924 RFC 4158 Certification Path Building September 2005
3927 If present, CRLDP can provide certificate processing implementations
3928 with a link to CRL information for a given certificate. Therefore,
3929 implementations may wish to provide support for decoding the CRLDP
3930 extension and using the information to retrieve CRLs. Support for
3931 CRLDP is optional and [RFC3280] compliant implementations need not
3932 populate the CRLDP extension. However, implementers of path-building
3933 and validation modules are strongly encouraged to support CRLDPs. At
3934 a minimum, developers are encouraged to consider supporting the LDAP
3935 and HTTP transports; this will provide for interoperability across a
3936 wide range of existing PKIs.
3938 6.6. Data Obtained via Application Protocol
3940 Many application protocols, such as SSL/TLS and S/MIME, allow one
3941 party to provide certificates and CRLs to another. Data provided in
3942 this method is generally very valuable to path-building software
3943 (will provide direction toward valid paths), and should be stored and
3944 used accordingly. Note: self-signed certificates obtained via
3945 application protocol are not trustworthy; implementations should only
3946 consider the relying party's trust anchors when building paths.
3948 6.7. Proprietary Mechanisms
3950 Some certificate issuing systems and certificate processing systems
3951 may utilize proprietary retrieval mechanisms, such as network mapped
3952 drives, databases, or other methods that are not directly referenced
3953 via the IETF standards. Certificate processing systems may wish to
3954 support other proprietary mechanisms, but should only do so in
3955 addition to supporting standard retrieval mechanisms such as LDAP,
3956 AIA, and CRLDP (unless functioning in a closed environment).
3958 7. Improving Retrieval Performance
3960 Retrieval performance can be improved through a few different
3961 mechanisms, including the use of caches and setting a specific
3962 retrieval order. This section discusses a few methods by which the
3963 performance of a certificate processing system may be improved during
3964 the retrieval of PKI objects. Certificate processing systems that
3965 are consistently very slow during processing will be disliked by
3966 users and will be slow to be adopted into organizations. Certificate
3967 processing systems are encouraged to do whatever possible to reduce
3968 the delays associated with requesting and retrieving data from
3969 external sources.
3978 Cooper, et al. Informational [Page 71]
3979 \f
3980 RFC 4158 Certification Path Building September 2005
3983 7.1. Caching
3985 Certificate processing systems operating in a non-hierarchical PKI
3986 will often need to retrieve certificates and certificate revocation
3987 lists (CRLs) from a source outside the application protocol.
3988 Typically, these objects are retrieved from an X.500 or LDAP
3989 repository, an Internet URI [RFC3986], or some other non-local
3990 source. Due to the delays associated with establishing connections
3991 as well as network transfers, certificate processing systems ought to
3992 be as efficient as possible when retrieving data from external
3993 sources. Perhaps the best way to improve retrieval efficiency is by
3994 using a caching mechanism. Certificate processing systems can cache
3995 data retrieved from external sources for some period of time, but not
3996 to exceed the useful period of the data (i.e., an expired certificate
3997 need not be cached). Although this comes at a cost of increased
3998 memory/disk consumption by the system, the cost and performance
3999 benefit of reducing network transmissions is great. Also, CRLs are
4000 often issued and available in advance of the nextUpdate date in the
4001 CRL. Implementations may wish to obtain these "fresher" CRLs before
4002 the nextUpdate date has passed.
4004 There are a number of different ways in which caching can be
4005 implemented; the specifics of these methods can be used as
4006 distinguishing characteristics between certificate processing
4007 systems. However, some things that implementers may wish to consider
4008 when developing caching systems are as follows:
4010 - If PKI objects are cached, the certification path-building
4011 mechanism should be able to examine and retrieve from the cache
4012 during path building. This will allow the certificate
4013 processing system to find or eliminate one or more paths quickly
4014 without requiring external contact with a directory or other
4015 retrieval mechanism.
4017 - Sharing caches between multiple users (via a local area network
4018 or LAN) may be useful if many users in one organization
4019 consistently perform PKI operations with another organization.
4021 - Caching not only PKI objects (such as certificates and CRLs) but
4022 also relationships between PKI objects (storing a link between a
4023 certificate and the issuer's certificate) may be useful. This
4024 linking may not always lead to the most correct or best
4025 relationship, but could represent a linking that worked in
4026 another scenario.
4028 - Previously built paths and partial paths are quite useful to
4029 cache, because they will provide information on previous
4030 successes or failures. Additionally, if the cache is safe from
4034 Cooper, et al. Informational [Page 72]
4035 \f
4036 RFC 4158 Certification Path Building September 2005
4039 unauthorized modifications, caching validation and signature
4040 checking status for certificates, CRLs, and paths can also be
4041 stored.
4043 7.2. Retrieval Order
4045 To optimize efficiency, certificate processing systems are encouraged
4046 to also consider the order in which different PKI objects are
4047 retrieved, as well as the mechanism from which they are retrieved.
4048 If caching is utilized, the caches can be consulted for PKI objects
4049 before attempting other retrieval mechanisms. If multiple caches are
4050 present (such as local disk and network), the caches can be consulted
4051 in the order in which they can be expected to return their result
4052 from fastest to slowest. For example, if a certificate processing
4053 system wishes to retrieve a certificate with a particular subject DN,
4054 the system might first consult the local cache, then the network
4055 cache, and then attempt directory retrieval. The specifics of the
4056 types of retrieval mechanisms and their relative costs are left to
4057 the implementer.
4059 In addition to ordering retrieval mechanisms, the certificate
4060 processing system ought to order the relative merits of the different
4061 external sources from which a PKI object can be retrieved. If the
4062 AIA is present within a certificate, with a URI [RFC3986] for the
4063 issuer's certificate, the certificate processing system (if able) may
4064 wish to attempt to retrieve the certificate first from local cache
4065 and then by using that URI (because it is expected to point directly
4066 to the desired certificate) before attempting to retrieve the
4067 certificates that may exist within a directory.
4069 If a directory is being consulted, it may be desirable to retrieve
4070 attributes in a particular order. A highly cross-certified PKI
4071 structure will lead to multiple possibilities for certification
4072 paths, which may mean multiple validation attempts before a
4073 successful path is retrieved. Therefore, cACertificate and
4074 userCertificate (which typically contain certificates from within the
4075 same 'realm') could be consulted before attempting to retrieve the
4076 crossCertificatePair values for an entry. Alternately, all three
4077 attributes could be retrieved in one query, but cross-certificates
4078 then tagged as such and used only after exhausting the possibilities
4079 from the cACertificate attribute. The best approach will depend on
4080 the nature of the application and PKI environment.
4082 7.3. Parallel Fetching and Prefetching
4084 Much of this document has focused on a path-building algorithm that
4085 minimizes the performance impact of network retrievals, by preventing
4086 those retrievals and utilization of caches. Another way to improve
4090 Cooper, et al. Informational [Page 73]
4091 \f
4092 RFC 4158 Certification Path Building September 2005
4095 performance would be to allow network retrievals to be performed in
4096 advance (prefetching) or at the same time that other operations are
4097 performed (parallel fetching). For example, if an email application
4098 receives a signed email message, it could download the required
4099 certificates and CRLs prior to the recipient viewing (or attempting
4100 to verify) the message. Implementations that provide the capability
4101 of parallel fetching and/or prefetching, along with a robust cache,
4102 can lead to greatly improved performance or user experience.
4104 8. Security Considerations
4106 8.1. General Considerations for Building a Certification Path
4108 Although certification path building deals directly with security
4109 relevant PKI data, the PKI data itself needs no special handling
4110 because its integrity is secured with the digital signature applied
4111 to it. The only exception to this is the appropriate protection of
4112 the trust anchor public keys. These are to be kept safe and obtained
4113 out of band (e.g., not from an electronic mail message or a
4114 directory) with respect to the path-building module.
4116 The greatest security risks associated with this document revolve
4117 around performing certification path validation while certification
4118 paths are built. It is therefore noted here that fully implemented
4119 certification path validation in accordance with [RFC3280] and
4120 [X.509] is required in order for certification path building,
4121 certification path validation, and the certificate using application
4122 to be properly secured. All of the Security Considerations listed in
4123 Section 9 of [RFC3280] apply equally here.
4125 In addition, as with any application that consumes data from
4126 potentially untrusted network locations, certification path-building
4127 components should be carefully implemented so as to reduce or
4128 eliminate the possibility of network based exploits. For example, a
4129 poorly implemented path-building module may not check the length of
4130 the CRLDP URI [RFC3986] before using the C language strcpy() function
4131 to place the address in a 1024 byte buffer. A hacker could use such
4132 a flaw to create a buffer overflow exploit by encoding malicious
4133 assembly code into the CRLDP of a certificate and then use the
4134 certificate to attempt an authentication. Such an attack could yield
4135 system level control to the attacker and expose the sensitive data
4136 the PKI was meant to protect.
4138 Path building may be used to mount a denial of service (DOS) attack.
4139 This might occur if multiple simple requests could be performed that
4140 cause a server to perform a number of path developments, each taking
4141 time and resources from the server. Servers can help avoid this by
4142 limiting the resources they are willing to devote to path building,
4146 Cooper, et al. Informational [Page 74]
4147 \f
4148 RFC 4158 Certification Path Building September 2005
4151 and being able to further limit those resources when the load is
4152 heavy. Standard DOS protections such as systems that identify and
4153 block attackers can also be useful.
4155 A DOS attack can be also created by presenting spurious CA
4156 certificates containing very large public keys. When the system
4157 attempts to use the large public key to verify the digital signature
4158 on additional certificates, a long processing delay may occur. This
4159 can be mitigated by either of two strategies. The first strategy is
4160 to perform signature verifications only after a complete path is
4161 built, starting from the trust anchor. This will eliminate the
4162 spurious CA certificate from consideration before the large public
4163 key is used. The second strategy is to recognize and simply reject
4164 keys longer than a certain size.
4166 A similar DOS attack can occur with very large public keys in end
4167 entity certificates. If a system uses the public key in a
4168 certificate before building and validating that certificate's
4169 certification path, long processing delays may occur. To mitigate
4170 this threat, the public key in an end entity certificate should not
4171 be used for any purpose until a complete certification path for that
4172 certificate is built and validated.
4174 8.2. Specific Considerations for Building Revocation Signer
4175 Certification Paths
4177 If the CRL Signer certificate (and certification path) is not
4178 identical to the Certification Authority certificate (and
4179 certification path), special care should be exercised when building
4180 the CRL Signer certification path.
4182 If special consideration is not given to building a CRL Signer
4183 certification path, that path could be constructed such that it
4184 terminates with a different root or through a different certification
4185 path to the same root. If this behavior is not prevented, the
4186 relying party may end up checking the wrong revocation data, or even
4187 maliciously substituted data, resulting in denial of service or
4188 security breach.
4190 For example, suppose the following certification path is built for E
4191 and is valid for an example "high assurance" policy.
4193 A->B->C->E
4195 When the building/validation routine attempts to verify that E is not
4196 revoked, C is referred to as the Certification Authority certificate.
4197 The path builder finds that the CRL for checking the revocation
4198 status of E is issued by C2; a certificate with the subject name "C",
4202 Cooper, et al. Informational [Page 75]
4203 \f
4204 RFC 4158 Certification Path Building September 2005
4207 but with a different key than the key that was used to sign E. C2 is
4208 referred to as the CRL Signer. An unrestrictive certification path
4209 builder might then build a path such as the following for the CRL
4210 Signer C2 certificate:
4212 X->Y->Z->C2
4214 If a path such as the one above is permitted, nothing can be
4215 concluded about the revocation status of E since C2 is a different CA
4216 from C.
4218 Fortunately, preventing this security problem is not difficult and
4219 the solution also makes building CRL Signer certification paths very
4220 efficient. In the event the CRL Signer certificate is identical to
4221 the Certification Authority certificate, the Certification Authority
4222 certification path should be used to verify the CRL; no additional
4223 path building is required. If the CRL Signer certificate is not
4224 identical to the Certification Authority certificate, a second path
4225 should be built for the CRL Signer certificate in exactly the same
4226 fashion as for any certificate, but with the following additional
4227 guidelines:
4229 1. Trust Anchor: The CRL Signer's certification path should start
4230 with the same trust anchor as the Certification Authority's
4231 certification path. Any trust anchor certificate with a subject
4232 DN matching that of the Certification Authority's trust anchor
4233 should be considered acceptable though lower in priority than the
4234 one with a matching public key and subject DN. While different
4235 trust anchor public keys are acceptable at the beginning of the
4236 CRL signer's certification path and the Certification Authority's
4237 certification path, both keys must be trusted by the relying
4238 party per the recommendations in Section 8.1.
4240 2. CA Name Matching: The subject DNs for all CA certificates in the
4241 two certification paths should match on a one-to-one basis
4242 (ignoring self-issued certificates) for the entire length of the
4243 shorter of the two paths.
4245 3. CRL Signer Certification Path Length: The length of the CRL
4246 Signer certification path (ignoring self-issued certificates)
4247 should be equal to or less than the length of the Certification
4248 Authority certification path plus (+) one. This allows a given
4249 Certification Authority to issue a certificate to a
4250 delegated/subordinate CRL Signer. The latter configuration
4251 represents the maximum certification path length for a CRL Signer
4252 certificate.
4258 Cooper, et al. Informational [Page 76]
4259 \f
4260 RFC 4158 Certification Path Building September 2005
4263 The reasoning behind the first guideline is readily apparent.
4264 Lacking this and the second guideline, any trusted CA could issue
4265 CRLs for any other CA, even if the PKIs are not related in any
4266 fashion. For example, one company could revoke certificates issued
4267 by another company if the relying party trusted the trust anchors
4268 from both companies. The two guidelines also prevent erroneous CRL
4269 checks since Global uniqueness of names is not guaranteed.
4271 The second guideline prevents roaming certification paths such as the
4272 previously described example CRL Signer certification path for
4273 A->B->C->E. It is especially important that the "ignoring self-
4274 issued certificates" is implemented properly. Self-issued
4275 certificates are cast out of the one-to-one name comparison in order
4276 to allow for key rollover. The path-building algorithm may be
4277 optimized to only consider certificates with the acceptable subject
4278 DN for the given point in the CRL Signer certification path while
4279 building the path.
4281 The third and final guideline ensures that the CRL used is the
4282 intended one. Without a restriction on the length of the CRL Signer
4283 certification path, the path could roam uncontrolled into another
4284 domain and still meet the first two guidelines. For example, again
4285 using the path A->B->C->E, the Certification Authority C, and a CRL
4286 Signer C2, a CRL Signer certification path such as the following
4287 could pass the first two guidelines:
4289 A->B->C->D->X->Y->RogueCA->C2
4291 In the preceding example, the trust anchor is identical for both
4292 paths and the one-to-one name matching test passes for A->B->C.
4293 However, accepting such a path has obvious security consequences, so
4294 the third guideline is used to prevent this situation. Applying the
4295 second and third guideline to the certification path above, the path
4296 builder could have immediately detected this path was not acceptable
4297 (prior to building it) by examining the issuer DN in C2. Given the
4298 length and name guidelines, the path builder could detect that
4299 "RogueCA" is not in the set of possible names by comparing it to the
4300 set of possible CRL Signer issuer DNs, specifically, A, B, or C.
4302 Similar consideration should be given when building the path for the
4303 OCSP Responder certificate when the CA is the OCSP Response Signer or
4304 the CA has delegated the OCSP Response signing to another entity.
4314 Cooper, et al. Informational [Page 77]
4315 \f
4316 RFC 4158 Certification Path Building September 2005
4319 9. Acknowledgements
4321 The authors extend their appreciation to David Lemire for his efforts
4322 coauthoring "Managing Interoperability in Non-Hierarchical Public Key
4323 Infrastructures" from which material was borrowed heavily for use in
4324 the introductory sections.
4326 This document has also greatly benefited from the review and
4327 additional technical insight provided by Dr. Santosh Chokhani, Carl
4328 Wallace, Denis Pinkas, Steve Hanna, Alice Sturgeon, Russ Housley, and
4329 Tim Polk.
4331 10. Normative References
4333 [RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet
4334 X.509 Public Key Infrastructure Certificate and
4335 Certificate Revocation List (CRL) Profile", RFC 3280,
4336 April 2002.
4338 11. Informative References
4340 [MINHPKIS] Hesse, P., and D. Lemire, "Managing Interoperability in
4341 Non-Hierarchical Public Key Infrastructures", 2002
4342 Conference Proceedings of the Internet Society Network
4343 and Distributed System Security Symposium, February 2002.
4345 [RFC1777] Yeong, W., Howes, T., and S. Kille, "Lightweight
4346 Directory Access Protocol", RFC 1777, March 1995.
4348 [RFC2560] Myers, M., Ankney, R., Malpani, A., Galperin, S., and C.
4349 Adams, "X.509 Internet Public Key Infrastructure Online
4350 Certificate Status Protocol - OCSP", RFC 2560, June 1999.
4352 [RFC2587] Boeyen, S., Howes, T., and P. Richard, "Internet X.509
4353 Public Key Infrastructure LDAPv2 Schema", RFC 2587, June
4354 1999.
4356 [RFC3377] Hodges, J. and R. Morgan, "Lightweight Directory Access
4357 Protocol (v3): Technical Specification", RFC 3377,
4358 September 2002.
4360 [RFC3820] Tuecke, S., Welch, V., Engert, D., Pearlman, L., and M.
4361 Thompson, "Internet X.509 Public Key Infrastructure (PKI)
4362 Proxy Certificate Profile", RFC 3820, June 2004.
4364 [RFC3986] Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform
4365 Resource Identifier (URI): Generic Syntax", STD 66, RFC
4366 3986, January 2005.
4370 Cooper, et al. Informational [Page 78]
4371 \f
4372 RFC 4158 Certification Path Building September 2005
4375 [X.501] ITU-T Recommendation X.501: Information Technology - Open
4376 Systems Interconnection - The Directory: Models, 1993.
4378 [X.509] ITU-T Recommendation X.509 (2000 E): Information
4379 Technology - Open Systems Interconnection - The
4380 Directory: Authentication Framework, March 2000.
4382 [PKIXALGS] Bassham, L., Polk, W. and R. Housley, "Algorithms and
4383 Identifiers for the Internet X.509 Public Key
4384 Infrastructure Certificate and Certificate Revocation
4385 Lists (CRL) Profile", RFC 3279, April 2002.
4387 [CERTSTORE] P. Gutmann, "Internet X.509 Public Key Infrastructure
4388 Operational Protocols: Certificate Store Access via
4389 HTTP", Work in Progress, August 2004.
4426 Cooper, et al. Informational [Page 79]
4427 \f
4428 RFC 4158 Certification Path Building September 2005
4431 Authors' Addresses
4433 Matt Cooper
4434 Orion Security Solutions, Inc.
4435 1489 Chain Bridge Rd, Ste. 300
4436 McLean, VA 22101, USA
4438 Phone: +1-703-917-0060
4439 EMail: mcooper@orionsec.com
4442 Yuriy Dzambasow
4443 A&N Associates, Inc.
4444 999 Corporate Blvd Ste. 100
4445 Linthicum, MD 21090, USA
4447 Phone: +1-410-859-5449 x107
4448 EMail: yuriy@anassoc.com
4451 Peter Hesse
4452 Gemini Security Solutions, Inc.
4453 4451 Brookfield Corporate Dr. Ste. 200
4454 Chantilly, VA 20151, USA
4456 Phone: +1-703-378-5808 x105
4457 EMail: pmhesse@geminisecurity.com
4460 Susan Joseph
4461 Van Dyke Technologies
4462 6716 Alexander Bell Drive
4463 Columbia, MD 21046
4465 EMail: susan.joseph@vdtg.com
4468 Richard Nicholas
4469 BAE Systems Information Technology
4470 141 National Business Parkway, Ste. 210
4471 Annapolis Junction, MD 20701, USA
4473 Phone: +1-301-939-2722
4474 EMail: richard.nicholas@it.baesystems.com
4482 Cooper, et al. Informational [Page 80]
4483 \f
4484 RFC 4158 Certification Path Building September 2005
4487 Full Copyright Statement
4489 Copyright (C) The Internet Society (2005).
4491 This document is subject to the rights, licenses and restrictions
4492 contained in BCP 78, and except as set forth therein, the authors
4493 retain all their rights.
4495 This document and the information contained herein are provided on an
4496 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
4497 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
4498 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
4499 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
4500 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
4501 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
4503 Intellectual Property
4505 The IETF takes no position regarding the validity or scope of any
4506 Intellectual Property Rights or other rights that might be claimed to
4507 pertain to the implementation or use of the technology described in
4508 this document or the extent to which any license under such rights
4509 might or might not be available; nor does it represent that it has
4510 made any independent effort to identify any such rights. Information
4511 on the procedures with respect to rights in RFC documents can be
4512 found in BCP 78 and BCP 79.
4514 Copies of IPR disclosures made to the IETF Secretariat and any
4515 assurances of licenses to be made available, or the result of an
4516 attempt made to obtain a general license or permission for the use of
4517 such proprietary rights by implementers or users of this
4518 specification can be obtained from the IETF on-line IPR repository at
4519 http://www.ietf.org/ipr.
4521 The IETF invites any interested party to bring to its attention any
4522 copyrights, patents or patent applications, or other proprietary
4523 rights that may cover technology that may be required to implement
4524 this standard. Please address the information to the IETF at ietf-
4525 ipr@ietf.org.
4527 Acknowledgement
4529 Funding for the RFC Editor function is currently provided by the
4530 Internet Society.
4538 Cooper, et al. Informational [Page 81]
4539 \f