4.  Forward Policy Chaining

   It is tempting to jump to the conclusion that certificate policies
   offer little assistance to path building when building from the
   target certificate.  It's easy to understand the "validate as you go"
   approach from the trust anchor, and much less obvious that any value
   can be derived in the other direction.  However, since policy
   validation consists of the intersection of the issuer policy set with
   the subject policy set and the mapping of policies from the issuer
   set to the subject set, policy validation can be done while building
   a path in the forward direction as well as the reverse.  It is simply
   a matter of reversing the procedure.  That is not to say this is as
   ideal as policy validation when building from the trust anchor, but
   it does offer a method that can be used to mostly eliminate what has
   long been considered a weakness inherent to building in the forward
   (from the target certificate) direction.

4.1.  Simple Intersection

   The most basic form of policy processing is the intersection of the
   policy sets from the first CA certificate through the target
   certificate.  Fortunately, the intersection of policy sets will
   always yield the same final set regardless of the order of
   intersection.  This allows processing of policy set intersections in
   either direction.  For example, if the trust anchor issues a CA
   certificate (A) with policies {X,Y,Z}, and that CA issues another CA
   certificate (B) with policies {X,Y}, and CA B then issues a third CA
   certificate (C) with policy set {Y,G}, one normally calculates the
   policy set from the trust anchor as follows:

   1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}

   2) Intersect that result, {X,Y} with C{Y,G} to yield the final set
      {Y}

   Now it has been shown that certificate C is good for policy Y.

   The other direction is exactly the same procedure, only in reverse:

   1) Intersect C{Y,G} with B{X,Y} to yield the set {Y}

   2) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
      {Y}

   Just like in the reverse direction, it has been shown that
   certificate C is good for policy Y, but this time in the forward
   direction.

   When building in the forward direction, policy processing is handled
   much like it is in reverse -- the software lends preference to
   certificates that propagate policies.  Neither approach guarantees
   that a path with valid policies will be found, but rather both
   approaches help guide the path in the direction it should go in order
   for the policies to propagate.

   If the caller has supplied an initial-acceptable-policy set, there is
   less value in using it when building in the forward direction unless
   the caller also set inhibit-policy-mapping.  In that case, the path
   builder can further constrain the path building to propagating
   policies that exist in the initial-acceptable-policy-set.  However,
   even if the inhibit-policy-mapping is not set, the initial-policy-set
   can still be used to guide the path building toward the desired trust
   anchor.

4.2.  Policy Mapping

   When a CA issues a certificate into another domain, an environment
   with disparate policy identifiers to its own, the CA may make use of
   policy mappings to map equivalence from the local domain's policy to
   the non-local domain's policy.  If in the prior example, A had
   included a policy mapping that mapped X to G in the certificate it
   issued to B, C would be good for X and Y:

   1) Intersect A{X,Y,Z} with B{X,Y} to yield the set {X,Y}

   2) Process Policy Mappings in B's certificate (X maps to G) to yield
      {G,Y} (same as {Y,G})

   3) Intersect that result, {G,Y} with C{Y,G} to yield the final set
      {G,Y}

   Since policies are always expressed in the relying party's domain,
   the certificate C is said to be good for {X, Y}, not {Y, G}.  This is
   because "G" doesn't mean anything in the context of the trust anchor
   that issued A without the policy mapping.

   When building in the forward direction, policies can be "unmapped" by
   reversing the mapping procedure.  This procedure is limited by one
   important aspect: if policy mapping has occurred in the forward
   direction, there is no mechanism by which it can be known in advance
   whether or not a future addition to the current path will invalidate
   the policy chain (assuming one exists) by setting inhibit-policy-
   mapping.  Fortunately, it is uncommon practice to set this flag.  The
   following is the procedure for processing policy mapping in the
   forward direction:

   1) Begin with C's policy set {Y,G}

   2) Apply the policy mapping in B's certificate (X maps to G) in
      reverse to yield {Y,X} (same as {X,Y})

   3) Intersect the result {X,Y} with B{X,Y} to yield the set {X,Y}

   4) Intersect that result, {X,Y}, with A{X,Y,Z} to yield the final set
      {X,Y}

   Just like in the reverse direction, it is determined in the forward
   direction that certificate C is good for policies {X,Y}.  If during
   this procedure, an inhibit-policy-mapping flag was encountered, what
   should be done?  This is reasonably easy to keep track of as well.
   The software simply maintains a flag on any policies that were
   propagated as a result of a mapping; just a simple Boolean kept with

   the policies in the set.  Imagine now that the certificate issued to
   A has the inhibit-policy-mapping constraint expressed with a skip
   certificates value of zero.

   1) Begin with C's policy set {Y,G}

   2) Apply the policy mapping in B's certificate and mark X as
      resulting from a mapping. (X maps to G) in reverse to yield {Y,Xm}
      (same as {Xm,Y})

   3) Intersect the result {Xm,Y} with B{X,Y} to yield the set {Xm,Y}

   4) A's certificate expresses the inhibit policy mapping constraint,
      so eliminate any policies in the current set that were propagated
      due to mapping (which is Xm) to yield {Y}

   5) Intersect that result, {Y} with A{X,Y,Z} to yield the final set
      {Y}

   If in our example, the policy set had gone to empty at any point (and
   require-explicit-policy was set), the path building would back up and
   try to traverse another branch of the tree.  This is analogous to the
   path-building functionality utilized in the reverse direction when
   the policy set goes to empty.

4.3.  Assigning Scores for Forward Policy Chaining

   Assuming the path-building module is maintaining the current forward
   policy set, weights may be assigned using the following procedure:

   1) For each CA certificate being scored:

      a. Copy the current forward policy set.

      b. Process policy mappings in the CA certificate in order to
         "un-map" policies, if any.

      c. Intersect the resulting set with CA certificate's policies.

   The larger the policy set yielded, the larger the score for that CA
   certificate.

   2) If an initial acceptable set was supplied, intersect this set with
      the resulting set for each CA certificate from (1).

   The larger the resultant set, the higher the score is for this
   certificate.

   Other scoring schemes may work better if the operating environment
   dictates.

5.  Avoiding Path-Building Errors

   This section defines some errors that may occur during the path-
   building process, as well as ways to avoid these errors when
   developing path-building functions.

5.1.  Dead Ends

   When building certification paths in a non-hierarchical PKI
   structure, a simple path-building algorithm could fail prematurely
   without finding an existing path due to a "dead end".  Consider the
   example in Figure 14.

            +----+      +---+
            | TA |      | Z |
            +----+      +---+
               |          |
               |          |
               V          V
             +---+      +---+
             | C |<-----| Y |
             +---+      +---+
               |
               |
               V
             +--------+
             | Target |
             +--------+

      Figure 14 - Dead End Example

   Note that in the example, C has two certificates: one issued by Y,
   and the other issued by the Trust Anchor.  Suppose that a simple
   "find issuer" algorithm is used, and the order in which the path
   builder found the certificates was Target(C), C(Y), Y(Z), Z(Z).  In
   this case, Z has no certificates issued by any other entities, and so
   the simplistic path-building process stops.  Since Z is not the
   relying party's trust anchor, the certification path is not complete,
   and will not validate.  This example shows that in anything but the
   simplest PKI structure, additional path-building logic will need to
   handle the cases in which entities are issued multiple certificates
   from different issuers.  The path-building algorithm will also need
   to have the ability to traverse back up the decision tree and try
   another path in order to be robust.

5.2.  Loop Detection

   In a non-hierarchical PKI structure, a path-building algorithm may
   become caught in a loop without finding an existing path.  Consider
   the example below:

             +----+
             | TA |
             +----+
               |
               |
             +---+      +---+
             | A |    ->| Z |
             +---+   /  +---+
               |    /     |
               |   /      |
               V  /       V
             +---+      +---+
             | B |<-----| Y |
             +---+      +---+
               |
               |
               V
             +--------+
             | Target |
             +--------+

      Figure 15 - Loop Example

   Let us suppose that in this example the simplest "find issuer"
   algorithm is used, and the order in which certificates are retrieved
   is Target(B), B(Y), Y(Z), Z(B), B(Y), Y(Z), Z(B), B(Y), ... A loop
   has formed that will cause the correct path (Target, B, A) to never
   be found.  The certificate processing system will need to recognize
   loops created by duplicate certificates (which are prohibited in a
   path by [X.509]) before they form to allow the certification path-
   building process to continue and find valid paths.  The authors of
   this document recommend that the loop detection not only detect the
   repetition of a certificate in the path, but also detect the presence
   of the same subject name / subject alternative name/ subject public
   key combination occurring twice in the path.  A name/key pair should
   only need to appear once in the path.  (See Section 2.4.2 for more
   information on the reasoning behind this recommendation.)

5.3.  Use of Key Identifiers

   Inconsistent and/or incompatible approaches to computing the subject
   key identifier and authority key identifier in public key
   certificates can cause failures in certification path-building
   algorithms that use those fields to identify certificates, even
   though otherwise valid certification paths may exist.  Path-building
   implementations should use existing key identifiers and not attempt
   to re-compute subject key identifiers.  It is extremely important
   that Key Identifiers be used only as sorting criteria or hints.  KIDs
   are not required to match during certification path validation and
   cannot be used to eliminate certificates.  This is of critical
   importance for interoperating across domains and multi-vendor
   implementations where the KIDs may not be calculated in the same
   fashion.

   Path-building and processing implementations should not rely on the
   form of authority key identifier that uses the authority DN and
   serial number as a restrictive matching rule, because cross-
   certification can lead to this value not being matched by the cross-
   certificates.

5.4.  Distinguished Name Encoding

   Certification path-building software should not rely on DNs being
   encoded as PrintableString.  Although frequently encoded as
   PrintableString, DNs may also appear as other types, including
   BMPString or UTF8String.  As a result, software systems that are
   unable to process BMPString and UTF8String encoded DNs may be unable
   to build and validate some certification paths.

   Furthermore, [RFC3280] compliant certificates are required to encode
   DNs as UTF8String as of January 1, 2004.  Certification path-building
   software should be prepared to handle "name rollover" certificates as
   described in [RFC3280].  Note that the inclusion of a "name rollover"
   certificate in a certification path does not constitute repetition of
   a DN and key.  Implementations that include the "name rollover"
   certificate in the path should ensure that the DNs with differing
   encoding are regarded as dissimilar.  (Implementations may instead
   handle matching DNs of different encodings and will therefore not
   need to include "name rollover" certificates in the path.)

6.  Retrieval Methods

   Building a certification path requires the availability of the
   certificates and CRLs that make up the path.  There are many
   different methods for obtaining these certificates and CRLs.  This
   section lists a few of the common ways to perform this retrieval, as
   well as some suggested approaches for improving performance.  This
   section is not intended to provide a complete reference for
   certificate and CRL retrieval methods or optimizations that would be
   useful in certification path building.

6.1.  Directories Using LDAP

   Most applications utilize the Lightweight Directory Access Protocol
   (LDAP) when retrieving data from directories following the X.500
   model.  Applications may encounter directories which support either
   LDAP v2 [RFC1777] or LDAP v3 [RFC3377].

   The LDAP v3 specification defines one attribute retrieval option, the
   "binary" option.  When specified in an LDAP retrieval request, this
   option was intended to force the directory to ignore any string-based
   representations of BER-encoded directory information, and send the
   requested attribute(s) in BER format.  Since all PKI objects of
   concern are BER-encoded objects, the "binary" option should be used.
   However, not all directories support the "binary" option.  Therefore,
   applications should be capable of requesting attributes with and
   without the "binary" option.  For example, if an application wishes
   to retrieve the userCertificate attribute, the application should
   request "userCertificate;binary".  If the desired information is not
   returned, robust implementations may opt to request "userCertificate"
   as well.

   The following attributes should be considered by PKI application
   developers when performing certificate retrieval from LDAP sources:

   userCertificate: contains certificates issued by one or more
      certification authorities with a subject DN that matches that of
      the directory entry.  This is a multi-valued attribute and all
      values should be received and considered during path building.
      Although typically it is expected that only end entity
      certificates will be stored in this attribute, (e.g., this is the
      attribute an application would request to find a person's
      encryption certificate) implementers may opt to search this
      attribute when looking in CA entries to make their path builder
      more robust.  If it is empty, the overhead added by including this
      attribute when already requesting one or both of the two below is
      marginal.

   cACertificate: contains self-issued certificates (if any) and any
      certificates issued to this certification authority by other
      certification authorities in the same realm.  (Realm is dependent
      upon local policy.)  This is a multi-valued attribute and all
      values should be received and considered during path building.

   crossCertificatePair: in conformant implementations, the
      crossCertificatePair is used to contain all, except self-issued
      certificates issued to this certification authority, as well as
      certificates issued by this certification authority to other
      certification authorities.  Each attribute value is a structure
      containing two elements.  The issuedToThisCA element contains
      certificates issued to this certification authority by other
      certification authorities.  The issuedByThisCA element contains
      certificates issued by this certification authority to other
      certification authorities.  Both elements of the
      crossCertificatePair are labeled optional in the ASN.1 definition.
      If both elements are present in a single value, the issuer name in
      one certificate is required to match the subject name in the other
      and vice versa, and the subject public key in one certificate
      shall be capable of verifying the digital signature on the other
      certificate and vice versa.  As this technology has evolved,
      different standards have had differing requirements on where
      information could be found.  For example, the LDAP v2 schema
      [RFC2587] states that the issuedToThisCA (once called 'forward')
      element of the crossCertificatePair attribute is mandatory and the
      issuedByThisCA (once called 'reverse') element is optional.  In
      contrast, Section 11.2.3 of [X.509] requires the issuedByThisCA
      element to be present if the CA issues a certificate to another CA
      if the subject is not a subordinate CA in a hierarchy.  Conformant
      directories behave as required by [X.509], but robust path-
      building implementations may want to retrieve all certificates
      from the cACertificate and crossCertificatePair attributes to
      ensure all possible certification authority certificates are
      obtained.

   certificateRevocationList: the certificateRevocationList attribute
      contains a certificate revocation list (CRL).  A CRL is defined in
      [RFC3280] as a time stamped list identifying revoked certificates,
      which is signed by a CA or CRL issuer and made freely available in
      a public repository.  Each revoked certificate is identified in a
      CRL by its certificate serial number.  There may be one or more
      CRLs in this attribute, and the values should be processed in
      accordance with [RFC3280].

   authorityRevocationList: the authorityRevocationList attribute also
      contains CRLs.  These CRLs contain revocation information
      regarding certificates issued to other CAs.  There may be one or
      more CRLs in this attribute, and the values should be processed in
      accordance with [RFC3280].

   Certification path processing systems that plan to interoperate with
   varying PKI structures and directory designs should at a minimum be
   able to retrieve and process the userCertificate, cACertificate,
   crossCertificatePair, certificateRevocationList, and
   authorityRevocationList attributes from directory entries.

6.2.  Certificate Store Access via HTTP

   Another possible method of certificate retrieval is using HTTP as an
   interface mechanism for retrieving certificates and CRLs from PKI
   repositories.  A current PKIX document [CERTSTORE] provides a
   protocol for a general-purpose interface capability for retrieving
   certificates and CRLs from PKI repositories.  Since the [CERTSTORE]
   document is a work in progress as of the writing of this document, no
   details are given here on how to utilize this mechanism for
   certificate and CRL retrieval.  Instead, refer to the [CERTSTORE]
   document or its current version.  Certification path processing
   systems may wish to implement support for this interface capability,
   especially if they will be used in environments that will provide
   HTTP-based access to certificates and CRLs.

6.3.  Authority Information Access

   The authority information access (AIA) extension, defined within
   [RFC3280], indicates how to access CA information and services for
   the issuer of the certificate in which the extension appears.  If a
   certificate with an AIA extension contains an accessMethod defined
   with the id-ad-caIssuers OID, the AIA may be used to retrieve one or
   more certificates for the CA that issued the certificate containing
   the AIA extension.  The AIA will provide a uniform resource
   identifier (URI) [RFC3986] when certificates can be retrieved via
   LDAP, HTTP, or FTP.  The AIA will provide a directoryName when
   certificates can be retrieved via directory access protocol (DAP).
   The AIA will provide an rfc822Name when certificates can be retrieved
   via electronic mail.  Additionally, the AIA may specify the location
   of an OCSP [RFC2560] responder that is able to provide revocation
   information for the certificate.

   If present, AIA may provide forward path-building implementations
   with a direct link to a certificate for the issuer of a given
   certificate.  Therefore, implementations may wish to provide support
   for decoding the AIA extension and processing the LDAP, HTTP, FTP,

   DAP, or e-mail locators.  Support for AIA is optional; [RFC3280]
   compliant implementations are not required to populate the AIA
   extension.  However, implementers of path-building and validation
   modules are strongly encouraged to support AIA, especially the HTTP
   transport; this will provide for usability and interoperability with
   many existing PKIs.

6.4.  Subject Information Access

   The subject information access (SIA) extension, defined within
   [RFC3280], indicates how to access information and services for the
   subject of the certificate in which the extension appears.  If a
   certificate with an SIA extension contains an accessMethod defined
   with the id-ad-caRepository OID, the SIA may be used to locate one or
   more certificates (and possibly CRLs) for entities issued
   certificates by the subject.  The SIA will provide a uniform resource
   identifier (URI) [RFC3986] when data can be retrieved via LDAP, HTTP,
   or FTP.  The SIA will provide a directoryName when data can be
   retrieved via directory access protocol (DAP).  The SIA will provide
   an rfc822Name when data can be retrieved via electronic mail.

   If present, the SIA extension may provide reverse path-building
   implementations with the certificates required to continue building
   the path.  Therefore, implementations may wish to provide support for
   decoding the SIA extension and processing the LDAP, HTTP, FTP, DAP,
   or e-mail locators.  Support for SIA is optional; [RFC3280] compliant
   implementations are not required to populate the SIA extension.
   However, implementers of path-building and validation modules are
   strongly encouraged to support SIA, especially the HTTP transport;
   this will provide for usability and interoperability with many
   existing PKIs.

6.5.  CRL Distribution Points

   The CRL distribution points (CRLDP) extension, defined within
   [RFC3280], indicates how to access CRL information.  If a CRLDP
   extension appears within a certificate, the CRL(s) to which the CRLDP
   refer are generally the CRLs that would contain revocation
   information for the certificate.  The CRLDP extension may point to
   multiple distribution points from which the CRL information may be
   obtained; the certificate processing system should process the CRLDP
   extension in accordance with [RFC3280].  The most common distribution
   points contain URIs from which the appropriate CRL may be downloaded,
   and directory names, which can be queried in a directory to retrieve
   the CRL attributes from the corresponding entry.

   If present, CRLDP can provide certificate processing implementations
   with a link to CRL information for a given certificate.  Therefore,
   implementations may wish to provide support for decoding the CRLDP
   extension and using the information to retrieve CRLs.  Support for
   CRLDP is optional and [RFC3280] compliant implementations need not
   populate the CRLDP extension.  However, implementers of path-building
   and validation modules are strongly encouraged to support CRLDPs.  At
   a minimum, developers are encouraged to consider supporting the LDAP
   and HTTP transports; this will provide for interoperability across a
   wide range of existing PKIs.

6.6.  Data Obtained via Application Protocol

   Many application protocols, such as SSL/TLS and S/MIME, allow one
   party to provide certificates and CRLs to another.  Data provided in
   this method is generally very valuable to path-building software
   (will provide direction toward valid paths), and should be stored and
   used accordingly.  Note: self-signed certificates obtained via
   application protocol are not trustworthy; implementations should only
   consider the relying party's trust anchors when building paths.

6.7.  Proprietary Mechanisms

   Some certificate issuing systems and certificate processing systems
   may utilize proprietary retrieval mechanisms, such as network mapped
   drives, databases, or other methods that are not directly referenced
   via the IETF standards.  Certificate processing systems may wish to
   support other proprietary mechanisms, but should only do so in
   addition to supporting standard retrieval mechanisms such as LDAP,
   AIA, and CRLDP (unless functioning in a closed environment).

7.  Improving Retrieval Performance

   Retrieval performance can be improved through a few different
   mechanisms, including the use of caches and setting a specific
   retrieval order.  This section discusses a few methods by which the
   performance of a certificate processing system may be improved during
   the retrieval of PKI objects.  Certificate processing systems that
   are consistently very slow during processing will be disliked by
   users and will be slow to be adopted into organizations.  Certificate
   processing systems are encouraged to do whatever possible to reduce
   the delays associated with requesting and retrieving data from
   external sources.

7.1.  Caching

   Certificate processing systems operating in a non-hierarchical PKI
   will often need to retrieve certificates and certificate revocation
   lists (CRLs) from a source outside the application protocol.
   Typically, these objects are retrieved from an X.500 or LDAP
   repository, an Internet URI [RFC3986], or some other non-local
   source.  Due to the delays associated with establishing connections
   as well as network transfers, certificate processing systems ought to
   be as efficient as possible when retrieving data from external
   sources.  Perhaps the best way to improve retrieval efficiency is by
   using a caching mechanism.  Certificate processing systems can cache
   data retrieved from external sources for some period of time, but not
   to exceed the useful period of the data (i.e., an expired certificate
   need not be cached).  Although this comes at a cost of increased
   memory/disk consumption by the system, the cost and performance
   benefit of reducing network transmissions is great.  Also, CRLs are
   often issued and available in advance of the nextUpdate date in the
   CRL.  Implementations may wish to obtain these "fresher" CRLs before
   the nextUpdate date has passed.

   There are a number of different ways in which caching can be
   implemented; the specifics of these methods can be used as
   distinguishing characteristics between certificate processing
   systems.  However, some things that implementers may wish to consider
   when developing caching systems are as follows:

      - If PKI objects are cached, the certification path-building
        mechanism should be able to examine and retrieve from the cache
        during path building.  This will allow the certificate
        processing system to find or eliminate one or more paths quickly
        without requiring external contact with a directory or other
        retrieval mechanism.

      - Sharing caches between multiple users (via a local area network
        or LAN) may be useful if many users in one organization
        consistently perform PKI operations with another organization.

      - Caching not only PKI objects (such as certificates and CRLs) but
        also relationships between PKI objects (storing a link between a
        certificate and the issuer's certificate) may be useful.  This
        linking may not always lead to the most correct or best
        relationship, but could represent a linking that worked in
        another scenario.

      - Previously built paths and partial paths are quite useful to
        cache, because they will provide information on previous
        successes or failures.  Additionally, if the cache is safe from

        unauthorized modifications, caching validation and signature
        checking status for certificates, CRLs, and paths can also be
        stored.

7.2.  Retrieval Order

   To optimize efficiency, certificate processing systems are encouraged
   to also consider the order in which different PKI objects are
   retrieved, as well as the mechanism from which they are retrieved.
   If caching is utilized, the caches can be consulted for PKI objects
   before attempting other retrieval mechanisms.  If multiple caches are
   present (such as local disk and network), the caches can be consulted
   in the order in which they can be expected to return their result
   from fastest to slowest.  For example, if a certificate processing
   system wishes to retrieve a certificate with a particular subject DN,
   the system might first consult the local cache, then the network
   cache, and then attempt directory retrieval.  The specifics of the
   types of retrieval mechanisms and their relative costs are left to
   the implementer.

   In addition to ordering retrieval mechanisms, the certificate
   processing system ought to order the relative merits of the different
   external sources from which a PKI object can be retrieved.  If the
   AIA is present within a certificate, with a URI [RFC3986] for the
   issuer's certificate, the certificate processing system (if able) may
   wish to attempt to retrieve the certificate first from local cache
   and then by using that URI (because it is expected to point directly
   to the desired certificate) before attempting to retrieve the
   certificates that may exist within a directory.

   If a directory is being consulted, it may be desirable to retrieve
   attributes in a particular order.  A highly cross-certified PKI
   structure will lead to multiple possibilities for certification
   paths, which may mean multiple validation attempts before a
   successful path is retrieved.  Therefore, cACertificate and
   userCertificate (which typically contain certificates from within the
   same 'realm') could be consulted before attempting to retrieve the
   crossCertificatePair values for an entry.  Alternately, all three
   attributes could be retrieved in one query, but cross-certificates
   then tagged as such and used only after exhausting the possibilities
   from the cACertificate attribute.  The best approach will depend on
   the nature of the application and PKI environment.

7.3.  Parallel Fetching and Prefetching

   Much of this document has focused on a path-building algorithm that
   minimizes the performance impact of network retrievals, by preventing
   those retrievals and utilization of caches.  Another way to improve

   performance would be to allow network retrievals to be performed in
   advance (prefetching) or at the same time that other operations are
   performed (parallel fetching).  For example, if an email application
   receives a signed email message, it could download the required
   certificates and CRLs prior to the recipient viewing (or attempting
   to verify) the message.  Implementations that provide the capability
   of parallel fetching and/or prefetching, along with a robust cache,
   can lead to greatly improved performance or user experience.

8.  Security Considerations

8.1.  General Considerations for Building a Certification Path

   Although certification path building deals directly with security
   relevant PKI data, the PKI data itself needs no special handling
   because its integrity is secured with the digital signature applied
   to it.  The only exception to this is the appropriate protection of
   the trust anchor public keys.  These are to be kept safe and obtained
   out of band (e.g., not from an electronic mail message or a
   directory) with respect to the path-building module.

   The greatest security risks associated with this document revolve
   around performing certification path validation while certification
   paths are built.  It is therefore noted here that fully implemented
   certification path validation in accordance with [RFC3280] and
   [X.509] is required in order for certification path building,
   certification path validation, and the certificate using application
   to be properly secured.  All of the Security Considerations listed in
   Section 9 of [RFC3280] apply equally here.

   In addition, as with any application that consumes data from
   potentially untrusted network locations, certification path-building
   components should be carefully implemented so as to reduce or
   eliminate the possibility of network based exploits.  For example, a
   poorly implemented path-building module may not check the length of
   the CRLDP URI [RFC3986] before using the C language strcpy() function
   to place the address in a 1024 byte buffer.  A hacker could use such
   a flaw to create a buffer overflow exploit by encoding malicious
   assembly code into the CRLDP of a certificate and then use the
   certificate to attempt an authentication.  Such an attack could yield
   system level control to the attacker and expose the sensitive data
   the PKI was meant to protect.

   Path building may be used to mount a denial of service (DOS) attack.
   This might occur if multiple simple requests could be performed that
   cause a server to perform a number of path developments, each taking
   time and resources from the server.  Servers can help avoid this by
   limiting the resources they are willing to devote to path building,

   and being able to further limit those resources when the load is
   heavy.  Standard DOS protections such as systems that identify and
   block attackers can also be useful.

   A DOS attack can be also created by presenting spurious CA
   certificates containing very large public keys.  When the system
   attempts to use the large public key to verify the digital signature
   on additional certificates, a long processing delay may occur.  This
   can be mitigated by either of two strategies.  The first strategy is
   to perform signature verifications only after a complete path is
   built, starting from the trust anchor.  This will eliminate the
   spurious CA certificate from consideration before the large public
   key is used.  The second strategy is to recognize and simply reject
   keys longer than a certain size.

   A similar DOS attack can occur with very large public keys in end
   entity certificates.  If a system uses the public key in a
   certificate before building and validating that certificate's
   certification path, long processing delays may occur.  To mitigate
   this threat, the public key in an end entity certificate should not
   be used for any purpose until a complete certification path for that
   certificate is built and validated.

8.2.  Specific Considerations for Building Revocation Signer
      Certification Paths

   If the CRL Signer certificate (and certification path) is not
   identical to the Certification Authority certificate (and
   certification path), special care should be exercised when building
   the CRL Signer certification path.

   If special consideration is not given to building a CRL Signer
   certification path, that path could be constructed such that it
   terminates with a different root or through a different certification
   path to the same root.  If this behavior is not prevented, the
   relying party may end up checking the wrong revocation data, or even
   maliciously substituted data, resulting in denial of service or
   security breach.

   For example, suppose the following certification path is built for E
   and is valid for an example "high assurance" policy.

      A->B->C->E

   When the building/validation routine attempts to verify that E is not
   revoked, C is referred to as the Certification Authority certificate.
   The path builder finds that the CRL for checking the revocation
   status of E is issued by C2; a certificate with the subject name "C",

   but with a different key than the key that was used to sign E.  C2 is
   referred to as the CRL Signer.  An unrestrictive certification path
   builder might then build a path such as the following for the CRL
   Signer C2 certificate:

      X->Y->Z->C2

   If a path such as the one above is permitted, nothing can be
   concluded about the revocation status of E since C2 is a different CA
   from C.

   Fortunately, preventing this security problem is not difficult and
   the solution also makes building CRL Signer certification paths very
   efficient.  In the event the CRL Signer certificate is identical to
   the Certification Authority certificate, the Certification Authority
   certification path should be used to verify the CRL; no additional
   path building is required.  If the CRL Signer certificate is not
   identical to the Certification Authority certificate, a second path
   should be built for the CRL Signer certificate in exactly the same
   fashion as for any certificate, but with the following additional
   guidelines:

   1.  Trust Anchor:  The CRL Signer's certification path should start
       with the same trust anchor as the Certification Authority's
       certification path.  Any trust anchor certificate with a subject
       DN matching that of the Certification Authority's trust anchor
       should be considered acceptable though lower in priority than the
       one with a matching public key and subject DN.  While different
       trust anchor public keys are acceptable at the beginning of the
       CRL signer's certification path and the Certification Authority's
       certification path, both keys must be trusted by the relying
       party per the recommendations in Section 8.1.

   2.  CA Name Matching:  The subject DNs for all CA certificates in the
       two certification paths should match on a one-to-one basis
       (ignoring self-issued certificates) for the entire length of the
       shorter of the two paths.

   3.  CRL Signer Certification Path Length:  The length of the CRL
       Signer certification path (ignoring self-issued certificates)
       should be equal to or less than the length of the Certification
       Authority certification path plus (+) one.  This allows a given
       Certification Authority to issue a certificate to a
       delegated/subordinate CRL Signer.  The latter configuration
       represents the maximum certification path length for a CRL Signer
       certificate.

   The reasoning behind the first guideline is readily apparent.
   Lacking this and the second guideline, any trusted CA could issue
   CRLs for any other CA, even if the PKIs are not related in any
   fashion.  For example, one company could revoke certificates issued
   by another company if the relying party trusted the trust anchors
   from both companies.  The two guidelines also prevent erroneous CRL
   checks since Global uniqueness of names is not guaranteed.

   The second guideline prevents roaming certification paths such as the
   previously described example CRL Signer certification path for
   A->B->C->E.  It is especially important that the "ignoring self-
   issued certificates" is implemented properly.  Self-issued
   certificates are cast out of the one-to-one name comparison in order
   to allow for key rollover.  The path-building algorithm may be
   optimized to only consider certificates with the acceptable subject
   DN for the given point in the CRL Signer certification path while
   building the path.

   The third and final guideline ensures that the CRL used is the
   intended one.  Without a restriction on the length of the CRL Signer
   certification path, the path could roam uncontrolled into another
   domain and still meet the first two guidelines.  For example, again
   using the path A->B->C->E, the Certification Authority C, and a CRL
   Signer C2, a CRL Signer certification path such as the following
   could pass the first two guidelines:

      A->B->C->D->X->Y->RogueCA->C2

   In the preceding example, the trust anchor is identical for both
   paths and the one-to-one name matching test passes for A->B->C.
   However, accepting such a path has obvious security consequences, so
   the third guideline is used to prevent this situation.  Applying the
   second and third guideline to the certification path above, the path
   builder could have immediately detected this path was not acceptable
   (prior to building it) by examining the issuer DN in C2.  Given the
   length and name guidelines, the path builder could detect that
   "RogueCA" is not in the set of possible names by comparing it to the
   set of possible CRL Signer issuer DNs, specifically, A, B, or C.

   Similar consideration should be given when building the path for the
   OCSP Responder certificate when the CA is the OCSP Response Signer or
   the CA has delegated the OCSP Response signing to another entity.

9.  Acknowledgements

   The authors extend their appreciation to David Lemire for his efforts
   coauthoring "Managing Interoperability in Non-Hierarchical Public Key
   Infrastructures" from which material was borrowed heavily for use in
   the introductory sections.

   This document has also greatly benefited from the review and
   additional technical insight provided by Dr. Santosh Chokhani, Carl
   Wallace, Denis Pinkas, Steve Hanna, Alice Sturgeon, Russ Housley, and
   Tim Polk.

10.  Normative References

   [RFC3280]   Housley, R., Polk, W., Ford, W., and D. Solo, "Internet
               X.509 Public Key Infrastructure Certificate and
               Certificate Revocation List (CRL) Profile", RFC 3280,
               April 2002.

11.  Informative References

   [MINHPKIS]  Hesse, P., and D. Lemire, "Managing Interoperability in
               Non-Hierarchical Public Key Infrastructures", 2002
               Conference Proceedings of the Internet Society Network
               and Distributed System Security Symposium, February 2002.

   [RFC1777]   Yeong, W., Howes, T., and S. Kille, "Lightweight
               Directory Access Protocol", RFC 1777, March 1995.

   [RFC2560]   Myers, M., Ankney, R., Malpani, A., Galperin, S., and C.
               Adams, "X.509 Internet Public Key Infrastructure Online
               Certificate Status Protocol - OCSP", RFC 2560, June 1999.

   [RFC2587]   Boeyen, S., Howes, T., and P. Richard, "Internet X.509
               Public Key Infrastructure LDAPv2 Schema", RFC 2587, June
               1999.

   [RFC3377]   Hodges, J. and R. Morgan, "Lightweight Directory Access
               Protocol (v3): Technical Specification", RFC 3377,
               September 2002.

   [RFC3820]   Tuecke, S., Welch, V., Engert, D., Pearlman, L., and M.
               Thompson, "Internet X.509 Public Key Infrastructure (PKI)
               Proxy Certificate Profile", RFC 3820, June 2004.

   [RFC3986]   Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform
               Resource Identifier (URI): Generic Syntax", STD 66, RFC
               3986, January 2005.

   [X.501]     ITU-T Recommendation X.501: Information Technology - Open
               Systems Interconnection - The Directory: Models, 1993.

   [X.509]     ITU-T Recommendation X.509 (2000 E): Information
               Technology - Open Systems Interconnection - The
               Directory: Authentication Framework, March 2000.

   [PKIXALGS]  Bassham, L., Polk, W. and R. Housley, "Algorithms and
               Identifiers for the Internet X.509 Public Key
               Infrastructure Certificate and Certificate Revocation
               Lists (CRL) Profile", RFC 3279, April 2002.

   [CERTSTORE] P. Gutmann, "Internet X.509 Public Key Infrastructure
               Operational Protocols: Certificate Store Access via
               HTTP", Work in Progress, August 2004.

Authors' Addresses

   Matt Cooper
   Orion Security Solutions, Inc.
   1489 Chain Bridge Rd, Ste. 300
   McLean, VA  22101,  USA

   Phone:  +1-703-917-0060
   EMail:  mcooper@orionsec.com


   Yuriy Dzambasow
   A&N Associates, Inc.
   999 Corporate Blvd Ste. 100
   Linthicum, MD  21090,  USA

   Phone:  +1-410-859-5449 x107
   EMail:  yuriy@anassoc.com


   Peter Hesse
   Gemini Security Solutions, Inc.
   4451 Brookfield Corporate Dr. Ste. 200
   Chantilly, VA  20151,  USA

   Phone:  +1-703-378-5808 x105
   EMail:  pmhesse@geminisecurity.com


   Susan Joseph
   Van Dyke Technologies
   6716 Alexander Bell Drive
   Columbia, MD 21046

   EMail:  susan.joseph@vdtg.com


   Richard Nicholas
   BAE Systems Information Technology
   141 National Business Parkway, Ste. 210
   Annapolis Junction, MD  20701,  USA

   Phone:  +1-301-939-2722
   EMail:  richard.nicholas@it.baesystems.com

Full Copyright Statement

   Copyright (C) The Internet Society (2005).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at ietf-
   ipr@ietf.org.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.