5<- index


6 Certification Path Validation

Certification path validation procedures for the Internet PKI are based on the algorithm supplied in [X.509]. Certification path processing verifies the binding between the subject distinguished name and/or subject alternative name and subject public key. The binding is limited by constraints which are specified in the certificates which comprise the path and inputs which are specified by the relying party. The basic constraints and policy constraints extensions allow the certification path processing logic to automate the decision making process.

This section describes an algorithm for validating certification paths. Conforming implementations of this specification are not required to implement this algorithm, but MUST provide functionality equivalent to the external behavior resulting from this procedure. Any algorithm may be used by a particular implementation so long as it derives the correct result.

In section 6.1, the text describes basic path validation. Valid paths begin with certificates issued by a trust anchor. The algorithm requires the public key of the CA, the CA's name, and any constraints upon the set of paths which may be validated using this key.

The selection of a trust anchor is a matter of policy: it could be the top CA in a hierarchical PKI; the CA that issued the verifier's own certificate(s); or any other CA in a network PKI. The path validation procedure is the same regardless of the choice of trust anchor. In addition, different applications may rely on different trust anchor, or may accept paths that begin with any of a set of trust anchor.

Section 6.2 describes methods for using the path validation algorithm in specific implementations. Two specific cases are discussed: the case where paths may begin with one of several trusted CAs; and where compatibility with the PEM architecture is required.

Section 6.3 describes the steps necessary to determine if a certificate is revoked or on hold status when CRLs are the revocation mechanism used by the certificate issuer.

6.1 Basic Path Validation

This text describes an algorithm for X.509 path processing. A conformant implementation MUST include an X.509 path processing procedure that is functionally equivalent to the external behavior of this algorithm. However, support for some of the certificate extensions processed in this algorithm are OPTIONAL for compliant implementations. Clients that do not support these extensions MAY omit the corresponding steps in the path validation algorithm.

For example, clients are NOT REQUIRED to support the policy mapping extension. Clients that do not support this extension MAY omit the path validation steps where policy mappings are processed. Note that clients MUST reject the certificate if it contains an unsupported critical extension.

The algorithm presented in this section validates the certificate with respect to the current date and time. A conformant implementation MAY also support validation with respect to some point in the past. Note that mechanisms are not available for validating a certificate with respect to a time outside the certificate validity period.

The trust anchor is an input to the algorithm. There is no requirement that the same trust anchor be used to validate all certification paths. Different trust anchors MAY be used to validate different paths, as discussed further in Section 6.2.

The primary goal of path validation is to verify the binding between a subject distinguished name or a subject alternative name and subject public key, as represented in the end entity certificate, based on the public key of the trust anchor. This requires obtaining a sequence of certificates that support that binding. The procedure performed to obtain this sequence of certificates is outside the scope of this specification.

To meet this goal, the path validation process verifies, among other things, that a prospective certification path (a sequence of n certificates) satisfies the following conditions:

(a) for all x in {1, ..., n-1}, the subject of certificate x is the issuer of certificate x+1;

(b) certificate 1 is issued by the trust anchor;

(c) certificate n is the certificate to be validated; and

(d) for all x in {1, ..., n}, the certificate was valid at the time in question.

When the trust anchor is provided in the form of a self-signed certificate, this self-signed certificate is not included as part of the prospective certification path. Information about trust anchors are provided as inputs to the certification path validation algorithm (section 6.1.1).

A particular certification path may not, however, be appropriate for all applications. Therefore, an application MAY augment this algorithm to further limit the set of valid paths. The path validation process also determines the set of certificate policies that are valid for this path, based on the certificate policies extension, policy mapping extension, policy constraints extension, and inhibit any-policy extension. To achieve this, the path validation algorithm constructs a valid policy tree. If the set of certificate policies that are valid for this path is not empty, then the result will be a valid policy tree of depth n, otherwise the result will be a null valid policy tree.

A certificate is self-issued if the DNs that appear in the subject and issuer fields are identical and are not empty. In general, the issuer and subject of the certificates that make up a path are different for each certificate. However, a CA may issue a certificate to itself to support key rollover or changes in certificate policies. These self-issued certificates are not counted when evaluating path length or name constraints.

This section presents the algorithm in four basic steps: (1) initialization, (2) basic certificate processing, (3) preparation for the next certificate, and (4) wrap-up. Steps (1) and (4) are performed exactly once. Step (2) is performed for all certificates in the path. Step (3) is performed for all certificates in the path except the final certificate. Figure 2 provides a high-level flowchart of this algorithm.

@

                           +-------+
                           | START |
                           +-------+
                               |
                               V
                       +----------------+
                       | Initialization |
                       +----------------+
                               |
                               +<--------------------+
                               |                     |
                               V                     |
                       +----------------+            |
                       |  Process Cert  |            |
                       +----------------+            |
                               |                     |
                               V                     |
                       +================+            |
                       |  IF Last Cert  |            |
                       |    in Path     |            |
                       +================+            |
                         |            |              |
                    THEN |            | ELSE         |
                         V            V              |
              +----------------+ +----------------+  |
              |    Wrap up     | |  Prepare for   |  |
              +----------------+ |   Next Cert    |  |
                      |          +----------------+  |
                      V               |              |
                  +-------+           +--------------+
                  | STOP  |
                  +-------+

Figure 2. Certification Path Processing Flowchart

6.1.1 Inputs

This algorithm assumes the following seven inputs are provided to the path processing logic:

(a) a prospective certification path of length n.

(b) the current date/time.

(c) user-initial-policy-set: A set of certificate policy identifiers naming the policies that are acceptable to the certificate user. The user-initial-policy-set contains the special value any-policy if the user is not concerned about certificate policy.

(d) trust anchor information, describing a CA that serves as a trust anchor for the certification path. The trust anchor information includes:

(1) the trusted issuer name,

(2) the trusted public key algorithm,

(3) the trusted public key, and

(4) optionally, the trusted public key parameters associated with the public key.

The trust anchor information may be provided to the path processing procedure in the form of a self-signed certificate. The trusted anchor information is trusted because it was delivered to the path processing procedure by some trustworthy out-of-band procedure. If the trusted public key algorithm requires parameters, then the parameters are provided along with the trusted public key.

(e) initial-policy-mapping-inhibit, which indicates if policy mapping is allowed in the certification path.

(f) initial-explicit-policy, which indicates if the path must be valid for at least one of the certificate policies in the user- initial-policy-set.

(g) initial-any-policy-inhibit, which indicates whether the anyPolicy OID should be processed if it is included in a certificate.

6.1.2 Initialization

This initialization phase establishes eleven state variables based upon the seven inputs:

(a) valid_policy_tree: A tree of certificate policies with their optional qualifiers; each of the leaves of the tree represents a valid policy at this stage in the certification path validation. If valid policies exist at this stage in the certification path validation, the depth of the tree is equal to the number of certificates in the chain that have been processed. If valid policies do not exist at this stage in the certification path validation, the tree is set to NULL. Once the tree is set to NULL, policy processing ceases.

Each node in the valid_policy_tree includes four data objects: the valid policy, a set of associated policy qualifiers, a set of one or more expected policy values, and a criticality indicator. If the node is at depth x, the components of the node have the following semantics:

(1) The valid_policy is a single policy OID representing a valid policy for the path of length x.

(2) The qualifier_set is a set of policy qualifiers associated with the valid policy in certificate x.

(3) The criticality_indicator indicates whether the certificate policy extension in certificate x was marked as critical.

(4) The expected_policy_set contains one or more policy OIDs that would satisfy this policy in the certificate x+1.

The initial value of the valid_policy_tree is a single node with valid_policy anyPolicy, an empty qualifier_set, an expected_policy_set with the single value anyPolicy, and a criticality_indicator of FALSE. This node is considered to be at depth zero.

Figure 3 is a graphic representation of the initial state of the valid_policy_tree. Additional figures will use this format to describe changes in the valid_policy_tree during path processing.

@

              +----------------+
              |   anyPolicy    |   <---- valid_policy
              +----------------+
              |       {}       |   <---- qualifier_set
              +----------------+
              |     FALSE      |   <---- criticality_indicator
              +----------------+
              |  {anyPolicy}   |   <---- expected_policy_set
              +----------------+

@

Figure 3. Initial value of the valid_policy_tree state variable

(b) permitted_subtrees: A set of root names for each name type (e.g., X.500 distinguished names, email addresses, or ip addresses) defining a set of subtrees within which all subject names in subsequent certificates in the certification path MUST fall. This variable includes a set for each name type: the initial value for the set for Distinguished Names is the set of all Distinguished names; the initial value for the set of RFC822 names is the set of all RFC822 names, etc.

(c) excluded_subtrees: A set of root names for each name type (e.g., X.500 distinguished names, email addresses, or ip addresses) defining a set of subtrees within which no subject name in subsequent certificates in the certification path may fall. This variable includes a set for each name type, and the initial value for each set is empty.

(d) explicit_policy: an integer which indicates if a non-NULL valid_policy_tree is required. The integer indicates the number of non-self-issued certificates to be processed before this requirement is imposed. Once set, this variable may be decreased, but may not be increased. That is, if a certificate in the path requires a non-NULL valid_policy_tree, a later certificate can not remove this requirement. If initial-explicit-policy is set, then the initial value is 0, otherwise the initial value is n+1.

(e) inhibit_any-policy: an integer which indicates whether the anyPolicy policy identifier is considered a match. The integer indicates the number of non-self-issued certificates to be processed before the anyPolicy OID, if asserted in a certificate, is ignored. Once set, this variable may be decreased, but may not be increased. That is, if a certificate in the path inhibits processing of anyPolicy, a later certificate can not permit it. If initial-any-policy-inhibit is set, then the initial value is 0, otherwise the initial value is n+1.

(f) policy_mapping: an integer which indicates if policy mapping is permitted. The integer indicates the number of non-self-issued certificates to be processed before policy mapping is inhibited. Once set, this variable may be decreased, but may not be increased. That is, if a certificate in the path specifies policy mapping is not permitted, it can not be overridden by a later certificate. If initial-policy-mapping-inhibit is set, then the initial value is 0, otherwise the initial value is n+1.

(g) working_public_key_algorithm: the digital signature algorithm used to verify the signature of a certificate. The working_public_key_algorithm is initialized from the trusted public key algorithm provided in the trust anchor information.

(h) working_public_key: the public key used to verify the signature of a certificate. The working_public_key is initialized from the trusted public key provided in the trust anchor information.

(i) working_public_key_parameters: parameters associated with the current public key, that may be required to verify a signature (depending upon the algorithm). The working_public_key_parameters variable is initialized from the trusted public key parameters provided in the trust anchor information.

(j) working_issuer_name: the issuer distinguished name expected in the next certificate in the chain. The working_issuer_name is initialized to the trusted issuer provided in the trust anchor information.

(k) max_path_length: this integer is initialized to n, is decremented for each non-self-issued certificate in the path, and may be reduced to the value in the path length constraint field within the basic constraints extension of a CA certificate.

Upon completion of the initialization steps, perform the basic certificate processing steps specified in 6.1.3.

6.1.3 Basic Certificate Processing

The basic path processing actions to be performed for certificate i (for all i in [1..n]) are listed below.

(a) Verify the basic certificate information. The certificate MUST satisfy each of the following:

(1) The certificate was signed with the working_public_key_algorithm using the working_public_key and the working_public_key_parameters.

(2) The certificate validity period includes the current time.

(3) At the current time, the certificate is not revoked and is not on hold status. This may be determined by obtaining the appropriate CRL (section 6.3), status information, or by out- of-band mechanisms.

(4) The certificate issuer name is the working_issuer_name.

(b) If certificate i is self-issued and it is not the final certificate in the path, skip this step for certificate i. Otherwise, verify that the subject name is within one of the permitted_subtrees for X.500 distinguished names, and verify that each of the alternative names in the subjectAltName extension (critical or non-critical) is within one of the permitted_subtrees for that name type.

(c) If certificate i is self-issued and it is not the final certificate in the path, skip this step for certificate i. Otherwise, verify that the subject name is not within one of the excluded_subtrees for X.500 distinguished names, and verify that each of the alternative names in the subjectAltName extension (critical or non-critical) is not within one of the excluded_subtrees for that name type.

(d) If the certificate policies extension is present in the certificate and the valid_policy_tree is not NULL, process the policy information by performing the following steps in order:

(1) For each policy P not equal to anyPolicy in the certificate policies extension, let P-OID denote the OID in policy P and P-Q denote the qualifier set for policy P. Perform the following steps in order:

(i) If the valid_policy_tree includes a node of depth i-1 where P-OID is in the expected_policy_set, create a child node as follows: set the valid_policy to OID-P; set the qualifier_set to P-Q, and set the expected_policy_set to {P-OID}.

For example, consider a valid_policy_tree with a node of depth i-1 where the expected_policy_set is {Gold, White}. Assume the certificate policies Gold and Silver appear in the certificate policies extension of certificate i. The Gold policy is matched but the Silver policy is not. This rule will generate a child node of depth i for the Gold policy. The result is shown as Figure 4.

                             +-----------------+
                             |       Red       |
                             +-----------------+
                             |       {}        |
                             +-----------------+   node of depth i-1
                             |      FALSE      |
                             +-----------------+
                             |  {Gold, White}  |
                             +-----------------+
                                      |
                                      |
                                      |
                                      V
                             +-----------------+
                             |      Gold       |
                             +-----------------+
                             |       {}        |
                             +-----------------+ node of depth i
                             |  uninitialized  |
                             +-----------------+
                             |     {Gold}      |
                             +-----------------+

Figure 4. Processing an exact match

(ii) If there was no match in step (i) and the valid_policy_tree includes a node of depth i-1 with the valid policy anyPolicy, generate a child node with the following values: set the valid_policy to P-OID; set the qualifier_set to P-Q, and set the expected_policy_set to {P-OID}.

For example, consider a valid_policy_tree with a node of depth i-1 where the valid_policy is anyPolicy. Assume the certificate policies Gold and Silver appear in the certificate policies extension of certificate i. The Gold policy does not have a qualifier, but the Silver policy has the qualifier Q-Silver. If Gold and Silver were not matched in (i) above, this rule will generate two child nodes of depth i, one for each policy. The result is shown as Figure 5.

                             +-----------------+
                             |    anyPolicy    |
                             +-----------------+
                             |       {}        |
                             +-----------------+ node of depth i-1
                             |      FALSE      |
                             +-----------------+
                             |   {anyPolicy}   |
                             +-----------------+
                                /           \
                               /             \
                              /               \
                             /                 \
               +-----------------+          +-----------------+
               |      Gold       |          |     Silver      |
               +-----------------+          +-----------------+
               |       {}        |          |   {Q-Silver}    |
               +-----------------+ nodes of +-----------------+
               | uninitialized   | depth i  | uninitialized   |
               +-----------------+          +-----------------+
               |     {Gold}      |          |    {Silver}     |
               +-----------------+          +-----------------+

Figure 5. Processing unmatched policies when a leaf node specifies anyPolicy

(2) If the certificate policies extension includes the policy anyPolicy with the qualifier set AP-Q and either (a) inhibit_any-policy is greater than 0 or (b) i<n and the certificate is self-issued, then:

For each node in the valid_policy_tree of depth i-1, for each value in the expected_policy_set (including anyPolicy) that does not appear in a child node, create a child node with the following values: set the valid_policy to the value from the expected_policy_set in the parent node; set the qualifier_set to AP-Q, and set the expected_policy_set to the value in the valid_policy from this node.

For example, consider a valid_policy_tree with a node of depth i-1 where the expected_policy_set is {Gold, Silver}. Assume anyPolicy appears in the certificate policies extension of certificate i, but Gold and Silver do not. This rule will generate two child nodes of depth i, one for each policy. The result is shown below as Figure 6.

                          +-----------------+
                          |      Red        |
                          +-----------------+
                          |       {}        |
                          +-----------------+ node of depth i-1
                          |      FALSE      |
                          +-----------------+
                          |  {Gold, Silver} |
                          +-----------------+
                             /           \
                            /             \
                           /               \
                          /                 \
            +-----------------+          +-----------------+
            |      Gold       |          |     Silver      |
            +-----------------+          +-----------------+
            |       {}        |          |       {}        |
            +-----------------+ nodes of +-----------------+
            |  uninitialized  | depth i  |  uninitialized  |
            +-----------------+          +-----------------+
            |     {Gold}      |          |    {Silver}     |
            +-----------------+          +-----------------+

Figure 6. Processing unmatched policies when the certificate policies extension specifies anyPolicy

(3) If there is a node in the valid_policy_tree of depth i-1 or less without any child nodes, delete that node. Repeat this step until there are no nodes of depth i-1 or less without children.

For example, consider the valid_policy_tree shown in Figure 7 below. The two nodes at depth i-1 that are marked with an 'X' have no children, and are deleted. Applying this rule to the resulting tree will cause the node at depth i-2 that is marked with an 'Y' to be deleted. The following application of the rule does not cause any nodes to be deleted, and this step is complete.

@

                              +-----------+
                              |           | node of depth i-3
                              +-----------+
                              /     |     \
                             /      |      \
                            /       |       \
                +-----------+ +-----------+ +-----------+
                |           | |           | |     Y     | nodes of
                +-----------+ +-----------+ +-----------+ depth i-2
                /   \               |             |
               /     \              |             |
              /       \             |             |
   +-----------+ +-----------+ +-----------+ +-----------+ nodes of
   |           | |     X     | |           | |    X      |  depth
   +-----------+ +-----------+ +-----------+ +-----------+   i-1
         |                      /    |    \
         |                     /     |     \
         |                    /      |      \
   +-----------+ +-----------+ +-----------+ +-----------+ nodes of
   |           | |           | |           | |           |  depth
   +-----------+ +-----------+ +-----------+ +-----------+   i

Figure 7. Pruning the valid_policy_tree

(4) If the certificate policies extension was marked as critical, set the criticality_indicator in all nodes of depth i to TRUE. If the certificate policies extension was not marked critical, set the criticality_indicator in all nodes of depth i to FALSE.

(e) If the certificate policies extension is not present, set the valid_policy_tree to NULL.

(f) Verify that either explicit_policy is greater than 0 or the valid_policy_tree is not equal to NULL;

If any of steps (a), (b), (c), or (f) fails, the procedure terminates, returning a failure indication and an appropriate reason.

If i is not equal to n, continue by performing the preparatory steps listed in 6.1.4. If i is equal to n, perform the wrap-up steps listed in 6.1.5.

6.1.4 Preparation for Certificate i+1

To prepare for processing of certificate i+1, perform the following steps for certificate i:

(a) If a policy mapping extension is present, verify that the special value anyPolicy does not appear as an issuerDomainPolicy or a subjectDomainPolicy.

(b) If a policy mapping extension is present, then for each issuerDomainPolicy ID-P in the policy mapping extension:

(1) If the policy_mapping variable is greater than 0, for each node in the valid_policy_tree of depth i where ID-P is the valid_policy, set expected_policy_set to the set of subjectDomainPolicy values that are specified as equivalent to ID-P by the policy mapping extension.

If no node of depth i in the valid_policy_tree has a valid_policy of ID-P but there is a node of depth i with a valid_policy of anyPolicy, then generate a child node of the node of depth i-1 that has a valid_policy of anyPolicy as follows:

(i) set the valid_policy to ID-P;

(ii) set the qualifier_set to the qualifier set of the policy anyPolicy in the certificate policies extension of certificate i;

(iii) set the criticality_indicator to the criticality of the certificate policies extension of certificate i;

(iv) and set the expected_policy_set to the set of subjectDomainPolicy values that are specified as equivalent to ID-P by the policy mappings extension.

(2) If the policy_mapping variable is equal to 0:

(i) delete each node of depth i in the valid_policy_tree where ID-P is the valid_policy.

(ii) If there is a node in the valid_policy_tree of depth i-1 or less without any child nodes, delete that node. Repeat this step until there are no nodes of depth i-1 or less without children.

(c) Assign the certificate subject name to working_issuer_name.

(d) Assign the certificate subjectPublicKey to working_public_key.

(e) If the subjectPublicKeyInfo field of the certificate contains an algorithm field with non-null parameters, assign the parameters to the working_public_key_parameters variable.

If the subjectPublicKeyInfo field of the certificate contains an algorithm field with null parameters or parameters are omitted, compare the certificate subjectPublicKey algorithm to the working_public_key_algorithm. If the certificate subjectPublicKey algorithm and the working_public_key_algorithm are different, set the working_public_key_parameters to null.

(f) Assign the certificate subjectPublicKey algorithm to the working_public_key_algorithm variable.

(g) If a name constraints extension is included in the certificate, modify the permitted_subtrees and excluded_subtrees state variables as follows:

(1) If permittedSubtrees is present in the certificate, set the permitted_subtrees state variable to the intersection of its previous value and the value indicated in the extension field. If permittedSubtrees does not include a particular name type, the permitted_subtrees state variable is unchanged for that name type. For example, the intersection of nist.gov and csrc.nist.gov is csrc.nist.gov. And, the intersection of nist.gov and rsasecurity.com is the empty set.

(2) If excludedSubtrees is present in the certificate, set the excluded_subtrees state variable to the union of its previous value and the value indicated in the extension field. If excludedSubtrees does not include a particular name type, the excluded_subtrees state variable is unchanged for that name type. For example, the union of the name spaces nist.gov and csrc.nist.gov is nist.gov. And, the union of nist.gov and rsasecurity.com is both name spaces.

(h) If the issuer and subject names are not identical:

(1) If explicit_policy is not 0, decrement explicit_policy by 1.

(2) If policy_mapping is not 0, decrement policy_mapping by 1.

(3) If inhibit_any-policy is not 0, decrement inhibit_any- policy by 1.

(i) If a policy constraints extension is included in the certificate, modify the explicit_policy and policy_mapping state variables as follows:

(1) If requireExplicitPolicy is present and is less than explicit_policy, set explicit_policy to the value of requireExplicitPolicy.

(2) If inhibitPolicyMapping is present and is less than policy_mapping, set policy_mapping to the value of inhibitPolicyMapping.

(j) If the inhibitAnyPolicy extension is included in the certificate and is less than inhibit_any-policy, set inhibit_any- policy to the value of inhibitAnyPolicy.

(k) Verify that the certificate is a CA certificate (as specified in a basicConstraints extension or as verified out-of-band).

(l) If the certificate was not self-issued, verify that max_path_length is greater than zero and decrement max_path_length by 1.

(m) If pathLengthConstraint is present in the certificate and is less than max_path_length, set max_path_length to the value of pathLengthConstraint.

(n) If a key usage extension is present, verify that the keyCertSign bit is set.

(o) Recognize and process any other critical extension present in the certificate. Process any other recognized non-critical extension present in the certificate.

If check (a), (k), (l), (n) or (o) fails, the procedure terminates, returning a failure indication and an appropriate reason.

If (a), (k), (l), (n) and (o) have completed successfully, increment i and perform the basic certificate processing specified in 6.1.3.

6.1.5 Wrap-up procedure

To complete the processing of the end entity certificate, perform the following steps for certificate n:

(a) If certificate n was not self-issued and explicit_policy is not 0, decrement explicit_policy by 1.

(b) If a policy constraints extension is included in the certificate and requireExplicitPolicy is present and has a value of 0, set the explicit_policy state variable to 0.

(c) Assign the certificate subjectPublicKey to working_public_key.

(d) If the subjectPublicKeyInfo field of the certificate contains an algorithm field with non-null parameters, assign the parameters to the working_public_key_parameters variable.

If the subjectPublicKeyInfo field of the certificate contains an algorithm field with null parameters or parameters are omitted, compare the certificate subjectPublicKey algorithm to the working_public_key_algorithm. If the certificate subjectPublicKey algorithm and the working_public_key_algorithm are different, set the working_public_key_parameters to null.

(e) Assign the certificate subjectPublicKey algorithm to the working_public_key_algorithm variable.

(f) Recognize and process any other critical extension present in the certificate n. Process any other recognized non-critical extension present in certificate n.

(g) Calculate the intersection of the valid_policy_tree and the user-initial-policy-set, as follows:

(i) If the valid_policy_tree is NULL, the intersection is NULL.

(ii) If the valid_policy_tree is not NULL and the user- initial-policy-set is any-policy, the intersection is the entire valid_policy_tree.

(iii) If the valid_policy_tree is not NULL and the user- initial-policy-set is not any-policy, calculate the intersection of the valid_policy_tree and the user-initial- policy-set as follows:

1. Determine the set of policy nodes whose parent nodes have a valid_policy of anyPolicy. This is the valid_policy_node_set.

2. If the valid_policy of any node in the valid_policy_node_set is not in the user-initial-policy-set and is not anyPolicy, delete this node and all its children.

3. If the valid_policy_tree includes a node of depth n with the valid_policy anyPolicy and the user-initial-policy-set is not any-policy perform the following steps:

a. Set P-Q to the qualifier_set in the node of depth n with valid_policy anyPolicy.

b. For each P-OID in the user-initial-policy-set that is not the valid_policy of a node in the valid_policy_node_set, create a child node whose parent is the node of depth n-1 with the valid_policy anyPolicy. Set the values in the child node as follows: set the valid_policy to P-OID; set the qualifier_set to P-Q; copy the criticality_indicator from the node of depth n with the valid_policy anyPolicy; and set the expected_policy_set to {P-OID}.

c. Delete the node of depth n with the valid_policy anyPolicy.

4. If there is a node in the valid_policy_tree of depth n-1 or less without any child nodes, delete that node. Repeat this step until there are no nodes of depth n-1 or less without children.

If either (1) the value of explicit_policy variable is greater than zero, or (2) the valid_policy_tree is not NULL, then path processing has succeeded.

6.1.6 Outputs

If path processing succeeds, the procedure terminates, returning a success indication together with final value of the valid_policy_tree, the working_public_key, the working_public_key_algorithm, and the working_public_key_parameters.

6.2 Using the Path Validation Algorithm

The path validation algorithm describes the process of validating a single certification path. While each certification path begins with a specific trust anchor, there is no requirement that all certification paths validated by a particular system share a single trust anchor. An implementation that supports multiple trust anchors MAY augment the algorithm presented in section 6.1 to further limit the set of valid certification paths which begin with a particular trust anchor. For example, an implementation MAY modify the algorithm to apply name constraints to a specific trust anchor during the initialization phase, or the application MAY require the presence of a particular alternative name form in the end entity certificate, or the application MAY impose requirements on application-specific extensions. Thus, the path validation algorithm presented in section 6.1 defines the minimum conditions for a path to be considered valid.

The selection of one or more trusted CAs is a local decision. A system may provide any one of its trusted CAs as the trust anchor for a particular path. The inputs to the path validation algorithm may be different for each path. The inputs used to process a path may reflect application-specific requirements or limitations in the trust accorded a particular trust anchor. For example, a trusted CA may only be trusted for a particular certificate policy. This restriction can be expressed through the inputs to the path validation procedure.

It is also possible to specify an extended version of the above certification path processing procedure which results in default behavior identical to the rules of PEM [RFC 1422]. In this extended version, additional inputs to the procedure are a list of one or more Policy Certification Authority (PCA) names and an indicator of the position in the certification path where the PCA is expected. At the nominated PCA position, the CA name is compared against this list. If a recognized PCA name is found, then a constraint of SubordinateToCA is implicitly assumed for the remainder of the certification path and processing continues. If no valid PCA name is found, and if the certification path cannot be validated on the basis of identified policies, then the certification path is considered invalid.

6.3 CRL Validation

This section describes the steps necessary to determine if a certificate is revoked or on hold status when CRLs are the revocation mechanism used by the certificate issuer. Conforming implementations that support CRLs are not required to implement this algorithm, but they MUST be functionally equivalent to the external behavior resulting from this procedure. Any algorithm may be used by a particular implementation so long as it derives the correct result.

This algorithm assumes that all of the needed CRLs are available in a local cache. Further, if the next update time of a CRL has passed, the algorithm assumes a mechanism to fetch a current CRL and place it in the local CRL cache.

This algorithm defines a set of inputs, a set of state variables, and processing steps that are performed for each certificate in the path. The algorithm output is the revocation status of the certificate.

6.3.1 Revocation Inputs

To support revocation processing, the algorithm requires two inputs:

(a) certificate: The algorithm requires the certificate serial number and issuer name to determine whether a certificate is on a particular CRL. The basicConstraints extension is used to determine whether the supplied certificate is associated with a CA or an end entity. If present, the algorithm uses the cRLDistributionsPoint and freshestCRL extensions to determine revocation status.

(b) use-deltas: This boolean input determines whether delta CRLs are applied to CRLs.

Note that implementations supporting legacy PKIs, such as RFC 1422 and X.509 version 1, will need an additional input indicating whether the supplied certificate is associated with a CA or an end entity.

6.3.2 Initialization and Revocation State Variables

To support CRL processing, the algorithm requires the following state variables:

(a) reasons_mask: This variable contains the set of revocation reasons supported by the CRLs and delta CRLs processed so far. The legal members of the set are the possible revocation reason values: unspecified, keyCompromise, caCompromise, affiliationChanged, superseded, cessationOfOperation, certificateHold, privilegeWithdrawn, and aACompromise. The special value all-reasons is used to denote the set of all legal members. This variable is initialized to the empty set.

(b) cert_status: This variable contains the status of the certificate. This variable may be assigned one of the following values: unspecified, keyCompromise, caCompromise, affiliationChanged, superseded, cessationOfOperation, certificateHold, removeFromCRL, privilegeWithdrawn, aACompromise, the special value UNREVOKED, or the special value UNDETERMINED. This variable is initialized to the special value UNREVOKED.

(c) interim_reasons_mask: This contains the set of revocation reasons supported by the CRL or delta CRL currently being processed.

Note: In some environments, it is not necessary to check all reason codes. For example, some environments are only concerned with caCompromise and keyCompromise for CA certificates. This algorithm checks all reason codes. Additional processing and state variables may be necessary to limit the checking to a subset of the reason codes.

6.3.3 CRL Processing

This algorithm begins by assuming the certificate is not revoked. The algorithm checks one or more CRLs until either the certificate status is determined to be revoked or sufficient CRLs have been checked to cover all reason codes.

For each distribution point (DP) in the certificate CRL distribution points extension, for each corresponding CRL in the local CRL cache, while ((reasons_mask is not all-reasons) and (cert_status is UNREVOKED)) perform the following:

(a) Update the local CRL cache by obtaining a complete CRL, a delta CRL, or both, as required:

(1) If the current time is after the value of the CRL next update field, then do one of the following:

(i) If use-deltas is set and either the certificate or the CRL contains the freshest CRL extension, obtain a delta CRL with the a next update value that is after the current time and can be used to update the locally cached CRL as specified in section 5.2.4.

(ii) Update the local CRL cache with a current complete CRL, verify that the current time is before the next update value in the new CRL, and continue processing with the new CRL. If use-deltas is set, then obtain the current delta CRL that can be used to update the new locally cached complete CRL as specified in section 5.2.4.

(2) If the current time is before the value of the next update field and use-deltas is set, then obtain the current delta CRL that can be used to update the locally cached complete CRL as specified in section 5.2.4.

(b) Verify the issuer and scope of the complete CRL as follows:

(1) If the DP includes cRLIssuer, then verify that the issuer field in the complete CRL matches cRLIssuer in the DP and that the complete CRL contains an issuing distribution point extension with the indrectCRL boolean asserted. Otherwise, verify that the CRL issuer matches the certificate issuer.

(2) If the complete CRL includes an issuing distribution point (IDP) CRL extension check the following:

(i) If the distribution point name is present in the IDP CRL extension and the distribution field is present in the DP, then verify that one of the names in the IDP matches one of the names in the DP. If the distribution point name is present in the IDP CRL extension and the distribution field is omitted from the DP, then verify that one of the names in the IDP matches one of the names in the cRLIssuer field of the DP.

(ii) If the onlyContainsUserCerts boolean is asserted in the IDP CRL extension, verify that the certificate does not include the basic constraints extension with the cA boolean asserted.

(iii) If the onlyContainsCACerts boolean is asserted in the IDP CRL extension, verify that the certificate includes the basic constraints extension with the cA boolean asserted.

(iv) Verify that the onlyContainsAttributeCerts boolean is not asserted.

(c) If use-deltas is set, verify the issuer and scope of the delta CRL as follows:

(1) Verify that the delta CRL issuer matches complete CRL issuer.

(2) If the complete CRL includes an issuing distribution point (IDP) CRL extension, verify that the delta CRL contains a matching IDP CRL extension. If the complete CRL omits an IDP CRL extension, verify that the delta CRL also omits an IDP CRL extension.

(3) Verify that the delta CRL authority key identifier extension matches complete CRL authority key identifier extension.

(d) Compute the interim_reasons_mask for this CRL as follows:

(1) If the issuing distribution point (IDP) CRL extension is present and includes onlySomeReasons and the DP includes reasons, then set interim_reasons_mask to the intersection of reasons in the DP and onlySomeReasons in IDP CRL extension.

(2) If the IDP CRL extension includes onlySomeReasons but the DP omits reasons, then set interim_reasons_mask to the value of onlySomeReasons in IDP CRL extension.

(3) If the IDP CRL extension is not present or omits onlySomeReasons but the DP includes reasons, then set interim_reasons_mask to the value of DP reasons.

(4) If the IDP CRL extension is not present or omits onlySomeReasons and the DP omits reasons, then set interim_reasons_mask to the special value all-reasons.

(e) Verify that interim_reasons_mask includes one or more reasons that is not included in the reasons_mask.

(f) Obtain and validate the certification path for the complete CRL issuer. If a key usage extension is present in the CRL issuer's certificate, verify that the cRLSign bit is set.

(g) Validate the signature on the complete CRL using the public key validated in step (f).

(h) If use-deltas is set, then validate the signature on the delta CRL using the public key validated in step (f).

(i) If use-deltas is set, then search for the certificate on the delta CRL. If an entry is found that matches the certificate issuer and serial number as described in section 5.3.4, then set the cert_status variable to the indicated reason as follows:

(1) If the reason code CRL entry extension is present, set the cert_status variable to the value of the reason code CRL entry extension.

(2) If the reason code CRL entry extension is not present, set the cert_status variable to the value unspecified.

(j) If (cert_status is UNREVOKED), then search for the certificate on the complete CRL. If an entry is found that matches the certificate issuer and serial number as described in section 5.3.4, then set the cert_status variable to the indicated reason as described in step (i).

(k) If (cert_status is removeFromCRL), then set cert_status to UNREVOKED.

If ((reasons_mask is all-reasons) OR (cert_status is not UNREVOKED)), then the revocation status has been determined, so return cert_status.

If the revocation status has not been determined, repeat the process above with any available CRLs not specified in a distribution point but issued by the certificate issuer. For the processing of such a CRL, assume a DP with both the reasons and the cRLIssuer fields omitted and a distribution point name of the certificate issuer. That is, the sequence of names in fullName is generated from the certificate issuer field as well as the certificate issuerAltName extension. If the revocation status remains undetermined, then return the cert_status UNDETERMINED.


->7