Add policies support to VerifyCertificateChain().

net/cert/internal/verify_certificate_chain.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/cert/internal/verify_certificate_chain.h"
 
+#include <algorithm>
 #include <memory>
 
 #include "base/logging.h"
 #include "base/memory/ptr_util.h"
 #include "net/cert/internal/cert_error_params.h"
 #include "net/cert/internal/cert_errors.h"
 #include "net/cert/internal/extended_key_usage.h"
 #include "net/cert/internal/name_constraints.h"
 #include "net/cert/internal/parse_certificate.h"
 #include "net/cert/internal/signature_algorithm.h"
@@ skipping 39 matching lines @@
 DEFINE_CERT_ERROR_ID(kVerifySignedDataFailed, "VerifySignedData failed");
 DEFINE_CERT_ERROR_ID(kSignatureAlgorithmsDifferentEncoding,
                      "Certificate.signatureAlgorithm is encoded differently "
                      "than TBSCertificate.signature");
 DEFINE_CERT_ERROR_ID(kEkuLacksServerAuth,
                      "The extended key usage does not include server auth");
 DEFINE_CERT_ERROR_ID(kEkuLacksClientAuth,
                      "The extended key usage does not include client auth");
 DEFINE_CERT_ERROR_ID(kCertIsNotTrustAnchor,
                      "Certificate is not a trust anchor");
+DEFINE_CERT_ERROR_ID(kNoValidPolicy, "No valid policy");
+DEFINE_CERT_ERROR_ID(kPolicyMappingAnyPolicy,
+                     "PolicyMappings must not map anyPolicy");
 
 bool IsHandledCriticalExtensionOid(const der::Input& oid) {
   if (oid == BasicConstraintsOid())
     return true;
   // Key Usage is NOT processed for end-entity certificates (this is the
   // responsibility of callers), however it is considered "handled" here in
   // order to allow being marked as critical.
   if (oid == KeyUsageOid())
     return true;
   if (oid == ExtKeyUsageOid())
     return true;
   if (oid == NameConstraintsOid())
     return true;
   if (oid == SubjectAltNameOid())
     return true;
+  if (oid == CertificatePoliciesOid())
+    return true;
+  if (oid == PolicyMappingsOid())
+    return true;
+  if (oid == PolicyConstraintsOid())
+    return true;
+  if (oid == InhibitAnyPolicyOid())
+    return true;
 
-  // TODO(eroman): Make this more complete.
   return false;
 }
 
 // Adds errors to |errors| if the certificate contains unconsumed _critical_
 // extensions.
 void VerifyNoUnconsumedCriticalExtensions(const ParsedCertificate& cert,
                                           CertErrors* errors) {
   for (const auto& it : cert.extensions()) {
     const ParsedExtension& extension = it.second;
     if (extension.critical && !IsHandledCriticalExtensionOid(extension.oid)) {
@@ skipping 20 matching lines @@
 }
 
 // Adds errors to |errors| if |cert| is not valid at time |time|.
 //
 // The certificate's validity requirements are described by RFC 5280 section
 // 4.1.2.5:
 //
 //    The validity period for a certificate is the period of time from
 //    notBefore through notAfter, inclusive.
 void VerifyTimeValidity(const ParsedCertificate& cert,
-                        const der::GeneralizedTime time,
+                        const der::GeneralizedTime& time,
                         CertErrors* errors) {
   if (time < cert.tbs().validity_not_before)
     errors->AddError(kValidityFailedNotBefore);
 
   if (cert.tbs().validity_not_after < time)
     errors->AddError(kValidityFailedNotAfter);
 }
 
 // Adds errors to |errors| if |cert| has internally inconsistent signature
 // algorithms.
@@ skipping 75 matching lines @@
         if (key_purpose_oid == ClientAuth())
           return;
       }
 
       errors->AddError(kEkuLacksClientAuth);
       break;
     }
   }
 }
 
-// This function corresponds to RFC 5280 section 6.1.3's "Basic Certificate
-// Processing" procedure.
-void BasicCertificateProcessing(
+// Returns |true| if |policies| contains the OID |search_oid|.
+bool ContainsPolicy(const std::set<der::Input>& policies,
+                    const der::Input& search_oid) {
+  return policies.count(search_oid) > 0;
+}
+
+// Class that encapsulates the state variables used by certificate path
+// validation.
+class PathVerifier {
+ public:
+  // Same parameters and meaning as VerifyCertificateChain().
+  void Run(const ParsedCertificateList& certs,
+           const CertificateTrust& last_cert_trust,
+           const SignaturePolicy* signature_policy,
+           const der::GeneralizedTime& time,
+           KeyPurpose required_key_purpose,
+           bool initial_explicit_policy,
+           const std::set<der::Input>& user_initial_policy_set,
+           bool initial_policy_mapping_inhibit,
+           bool initial_any_policy_inhibit,
+           CertPathErrors* errors);
+
+ private:
+  // Verifies and updates the valid policies. This corresponds with RFC 5280
+  // section 6.1.3 steps d-f.
+  void VerifyPolicies(const ParsedCertificate& cert,
+                      bool is_target_cert,
+                      CertErrors* errors);
+
+  // Applies the policy mappings. This corresponds with RFC 5280 section 6.1.4
+  // steps a-b.
+  void VerifyPolicyMappings(const ParsedCertificate& cert, CertErrors* errors);
+
+  // This function corresponds to RFC 5280 section 6.1.3's "Basic Certificate
+  // Processing" procedure.
+  void BasicCertificateProcessing(const ParsedCertificate& cert,
+                                  bool is_target_cert,
+                                  const SignaturePolicy* signature_policy,
+                                  const der::GeneralizedTime& time,
+                                  KeyPurpose required_key_purpose,
+                                  CertErrors* errors);
+
+  // This function corresponds to RFC 5280 section 6.1.4's "Preparation for
+  // Certificate i+1" procedure. |cert| is expected to be an intermediate.
+  void PrepareForNextCertificate(const ParsedCertificate& cert,
+                                 CertErrors* errors);
+
+  // This function corresponds with RFC 5280 section 6.1.5's "Wrap-Up
+  // Procedure". It does processing for the final certificate (the target cert).
+  void WrapUp(const ParsedCertificate& cert, CertErrors* errors);
+
+  // Enforces trust anchor constraints compatibile with RFC 5937.
+  //
+  // Note that the anchor constraints are encoded via the attached certificate
+  // itself.
+  void ApplyTrustAnchorConstraints(const ParsedCertificate& cert,
+                                   KeyPurpose required_key_purpose,
+                                   CertErrors* errors);
+
+  // Initializes the path validation algorithm given anchor constraints. This
+  // follows the description in RFC 5937
+  void ProcessRootCertificate(const ParsedCertificate& cert,
+                              const CertificateTrust& trust,
+                              KeyPurpose required_key_purpose,
+                              CertErrors* errors);
+
+  // The set of certificate policy OIDs that are valid at the current depth in
+  // the path. These OIDs are in the domain of the current issuer (relevant in
+  // case policy mapping were used). This variable is a simplification of RFC
+  // 5280's "valid_policy_tree" variable.
+  std::set<der::Input> valid_policies_;
+
+  // Will contain a NameConstraints for each previous cert in the chain which
+  // had nameConstraints. This corresponds to the permitted_subtrees and
+  // excluded_subtrees state variables from RFC 5280.
+  std::vector<const NameConstraints*> name_constraints_list_;
+
+  // |explicit_policy_| corresponds with the same named variable from RFC 5280
+  // section 6.1.2:
+  //
+  //   explicit_policy:  an integer that 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 cannot
+  //   remove this requirement.  If initial-explicit-policy is set, then the
+  //   initial value is 0, otherwise the initial value is n+1.
+  size_t explicit_policy_;
+
+  // |inhibit_any_policy_| corresponds with the same named variable from RFC
+  // 5280 section 6.1.2:
+  //
+  //   inhibit_anyPolicy:  an integer that 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 other than an intermediate self-issued
+  //   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 cannot permit it.  If initial-any-policy-
+  //   inhibit is set, then the initial value is 0, otherwise the
+  //   initial value is n+1.
+  size_t inhibit_any_policy_;
+
+  // |policy_mapping_| corresponds with the same named variable from RFC 5280
+  // section 6.1.2:
+  //
+  //   policy_mapping:  an integer that 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 that policy mapping is not permitted, it cannot 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.
+  size_t policy_mapping_;
+
+  // |working_spki_| is an amalgamation of 3 separate variables from RFC 5280:
+  //    * working_public_key
+  //    * working_public_key_algorithm
+  //    * working_public_key_parameters
+  //
+  // They are combined for simplicity since the signature verification takes an
+  // SPKI, and the parameter inheritence is not applicable for the supported
+  // key types.
+  //
+  // An approximate explanation of |working_spki| is this description from RFC
+  // 5280 section 6.1.2:
+  //
+  //    working_public_key:  the public key used to verify the
+  //    signature of a certificate.
+  der::Input working_spki_;
+
+  // |working_normalized_issuer_name_| is the normalized value of the
+  // working_issuer_name variable in RFC 5280 section 6.1.2:
+  //
+  //    working_issuer_name:  the issuer distinguished name expected
+  //    in the next certificate in the chain.
+  der::Input working_normalized_issuer_name_;
+
+  // |max_path_length_| corresponds with the same named variable in RFC 5280
+  // section 6.1.2.
+  //
+  //    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.
+  size_t max_path_length_;
+};
+
+void PathVerifier::VerifyPolicies(const ParsedCertificate& cert,
+                                  bool is_target_cert,
+                                  CertErrors* errors) {
+  // RFC 5280 section 6.1.3:
+  //
+  //       (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:
+  if (cert.has_policy_oids() && !valid_policies_.empty()) {
+    std::set<der::Input> new_valid_policies;
+
+    bool valid_policies_contains_any_policy =
+        ContainsPolicy(valid_policies_, AnyPolicy());
+
+    bool cert_policies_contains_any_policy = false;
+
+    //  (1)  For each policy P not equal to anyPolicy in the
+    //       certificate policies extension, let P-OID denote the OID
+    //       for policy P and P-Q denote the qualifier set for policy
+    //       P.  Perform the following steps in order:
+    for (const der::Input& p_oid : cert.policy_oids()) {
+      if (p_oid == AnyPolicy()) {
+        cert_policies_contains_any_policy = true;
+        continue;
+      }
+
+      //  (i)   For each node of depth i-1 in the valid_policy_tree
+      //        where P-OID is in the expected_policy_set,
+      if (ContainsPolicy(valid_policies_, p_oid)) {
+        new_valid_policies.insert(p_oid);
+      } else {
+        // (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}.
+        if (valid_policies_contains_any_policy) {
+          new_valid_policies.insert(p_oid);
+        }
+      }
+    }
+
+    // (2)  If the certificate policies extension includes the policy
+    //      anyPolicy with the qualifier set AP-Q and either (a)
+    //      inhibit_anyPolicy is greater than 0 or (b) i<n and the
+    //      certificate is self-issued, then:

[mattm, 2017/05/25 23:21:48]

paste more RFC instead of leaving the cliffhanger "then: ..."?

+    if (cert_policies_contains_any_policy &&
+        ((inhibit_any_policy_ > 0) ||
+         (!is_target_cert && IsSelfIssued(cert)))) {
+      for (const der::Input& valid_oid : valid_policies_) {
+        new_valid_policies.insert(valid_oid);
+      }
+    }
+
+    valid_policies_ = std::move(new_valid_policies);

[mattm, 2017/05/25 23:21:49]

so is step (3) unnecessary because we replace valid_policies_ with
new_valid_policies instead of keeping the whole policy tree and updating in
place? Maybe add a comment about that?

+  }
+
+  //   (e)  If the certificate policies extension is not present, set the
+  //        valid_policy_tree to NULL.
+  if (!cert.has_policy_oids()) {
+    valid_policies_.clear();
+  }
+
+  //  (f)  Verify that either explicit_policy is greater than 0 or the
+  //       valid_policy_tree is not equal to NULL;
+  if (explicit_policy_ == 0 && valid_policies_.empty()) {
+    errors->AddError(kNoValidPolicy);
+  }
+}
+
+void PathVerifier::VerifyPolicyMappings(const ParsedCertificate& cert,
+                                        CertErrors* errors) {
+  if (!cert.has_policy_mappings())
+    return;
+
+  //      (a)  If a policy mappings extension is present, verify that the

[mattm, 2017/05/25 23:21:48]

Preceed this with what RFC section you're referencing now

+  //           special value anyPolicy does not appear as an
+  //           issuerDomainPolicy or a subjectDomainPolicy.
+  for (const ParsedPolicyMapping& mapping : cert.policy_mappings()) {
+    if (mapping.issuer_domain_policy == AnyPolicy() ||
+        mapping.subject_domain_policy == AnyPolicy()) {
+      errors->AddError(kPolicyMappingAnyPolicy);

[mattm, 2017/05/25 23:21:48]

Is it intentionally not returning here for the "try to accumulate all errors"
thing?
(As the rfc says it should terminate if this fails)

+    }
+  }
+
+  //      (b)  If a policy mappings extension is present, then for each
+  //           issuerDomainPolicy ID-P in the policy mappings 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 mappings 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; and
+  //
+  //            (iii)  set the expected_policy_set to the set of
+  //                   subjectDomainPolicy values that are specified as
+  //                   equivalent to ID-P by the policy mappings extension.

[mattm, 2017/05/25 23:21:48]

Man the policy mapping stuff is impossible to comprehend. It doesn't seem like
this is done though?

+  //
+  //            (ii)   If there is a node in the valid_policy_tree of depth

[mattm, 2017/05/25 23:21:48]

comment out of place? (this is b.2.ii?)

+  //                   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.
+  if (policy_mapping_ > 0) {
+    std::set<der::Input> new_valid_policies;
+
+    for (const der::Input& orig_policy : valid_policies_) {
+      bool is_remapped = false;
+
+      // Find everything it is got remapped to.
+      for (const ParsedPolicyMapping& mapping : cert.policy_mappings()) {
+        if (mapping.issuer_domain_policy == orig_policy ||
+            mapping.issuer_domain_policy == AnyPolicy()) {

[mattm, 2017/05/25 23:21:48]

so this is an extrapolation for what to do when continuing through the error
case of having AnyPolicy as an issuerDomainPolicy?
or was that supposed to be orig_policy == AnyPolicy()?

+          new_valid_policies.insert(mapping.subject_domain_policy);
+          is_remapped = true;
+        }
+      }
+
+      // If it wasn't remapped, carry it over as usual.
+      if (!is_remapped)
+        new_valid_policies.insert(orig_policy);
+    }
+
+    valid_policies_ = std::move(new_valid_policies);
+  } else {
+    //  (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.
+    for (const ParsedPolicyMapping& mapping : cert.policy_mappings()) {
+      valid_policies_.erase(mapping.issuer_domain_policy);
+    }
+  }
+}
+
+void PathVerifier::BasicCertificateProcessing(
     const ParsedCertificate& cert,
     bool is_target_cert,
     const SignaturePolicy* signature_policy,
     const der::GeneralizedTime& time,
-    const der::Input& working_spki,
-    const der::Input& working_normalized_issuer_name,
-    const std::vector<const NameConstraints*>& name_constraints_list,
+    KeyPurpose required_key_purpose,
     CertErrors* errors) {
   // Check that the signature algorithms in Certificate vs TBSCertificate
   // match. This isn't part of RFC 5280 section 6.1.3, but is mandated by
   // sections 4.1.1.2 and 4.1.2.3.
   VerifySignatureAlgorithmsMatch(cert, errors);
 
   // Verify the digital signature using the previous certificate's key (RFC
   // 5280 section 6.1.3 step a.1).
   if (!VerifySignedData(cert.signature_algorithm(), cert.tbs_certificate_tlv(),
-                        cert.signature_value(), working_spki, signature_policy,
+                        cert.signature_value(), working_spki_, signature_policy,
                         errors)) {
     errors->AddError(kVerifySignedDataFailed);
   }
 
   // Check the time range for the certificate's validity, ensuring it is valid
   // at |time|.
   // (RFC 5280 section 6.1.3 step a.2)
   VerifyTimeValidity(cert, time, errors);
 
   // TODO(eroman): Check revocation (RFC 5280 section 6.1.3 step a.3)
 
   // Verify the certificate's issuer name matches the issuing certificate's
   // subject name. (RFC 5280 section 6.1.3 step a.4)
-  if (cert.normalized_issuer() != working_normalized_issuer_name)
+  if (cert.normalized_issuer() != working_normalized_issuer_name_)
     errors->AddError(kSubjectDoesNotMatchIssuer);
 
   // Name constraints (RFC 5280 section 6.1.3 step b & c)
   // If certificate i is self-issued and it is not the final certificate in the
   // path, skip this step for certificate i.
-  if (!name_constraints_list.empty() &&
+  if (!name_constraints_list_.empty() &&
       (!IsSelfIssued(cert) || is_target_cert)) {
-    for (const NameConstraints* nc : name_constraints_list) {
+    for (const NameConstraints* nc : name_constraints_list_) {
       if (!nc->IsPermittedCert(cert.normalized_subject(),
                                cert.subject_alt_names())) {
         errors->AddError(kNotPermittedByNameConstraints);
       }
     }
   }
 
-  // TODO(eroman): Steps d-f are omitted, as policy constraints are not yet
-  // implemented.
+  // RFC 5280 section 6.1.3 step d - f.
+  VerifyPolicies(cert, is_target_cert, errors);
+
+  // The key purpose is checked not just for the end-entity certificate, but
+  // also interpreted as a constraint when it appears in intermediates. This
+  // goes beyond what RFC 5280 describes, but is the de-facto standard. See
+  // https://wiki.mozilla.org/CA:CertificatePolicyV2.1#Frequently_Asked_Questions
+  VerifyExtendedKeyUsage(cert, required_key_purpose, errors);
 }
 
-// This function corresponds to RFC 5280 section 6.1.4's "Preparation for
-// Certificate i+1" procedure. |cert| is expected to be an intermediate.
-void PrepareForNextCertificate(
-    const ParsedCertificate& cert,
-    size_t* max_path_length_ptr,
-    der::Input* working_spki,
-    der::Input* working_normalized_issuer_name,
-    std::vector<const NameConstraints*>* name_constraints_list,
-    CertErrors* errors) {
-  // TODO(crbug.com/634456): Steps a-b are omitted, as policy mappings are not
-  // yet implemented.
+void PathVerifier::PrepareForNextCertificate(const ParsedCertificate& cert,
+                                             CertErrors* errors) {
+  // RFC 5280 section 6.1.4 step a-b
+  VerifyPolicyMappings(cert, errors);
 
   // From RFC 5280 section 6.1.4 step c:
   //
   //    Assign the certificate subject name to working_normalized_issuer_name.
-  *working_normalized_issuer_name = cert.normalized_subject();
+  working_normalized_issuer_name_ = cert.normalized_subject();
 
   // From RFC 5280 section 6.1.4 step d:
   //
   //    Assign the certificate subjectPublicKey to working_public_key.
-  *working_spki = cert.tbs().spki_tlv;
+  working_spki_ = cert.tbs().spki_tlv;
 
   // Note that steps e and f are omitted as they are handled by
   // the assignment to |working_spki| above. See the definition
   // of |working_spki|.
 
   // From RFC 5280 section 6.1.4 step g:
   if (cert.has_name_constraints())
-    name_constraints_list->push_back(&cert.name_constraints());
+    name_constraints_list_.push_back(&cert.name_constraints());
 
-  // TODO(eroman): Steps h-j are omitted as policy
-  // constraints/mappings/inhibitAnyPolicy are not yet implemented.
+  //     (h)  If certificate i is not self-issued:
+  if (!IsSelfIssued(cert)) {
+    //         (1)  If explicit_policy is not 0, decrement explicit_policy by
+    //              1.
+    if (explicit_policy_ > 0)
+      explicit_policy_ -= 1;
+
+    //         (2)  If policy_mapping is not 0, decrement policy_mapping by 1.
+    if (policy_mapping_ > 0)
+      policy_mapping_ -= 1;
+
+    //         (3)  If inhibit_anyPolicy is not 0, decrement inhibit_anyPolicy
+    //              by 1.
+    if (inhibit_any_policy_ > 0)
+      inhibit_any_policy_ -= 1;
+  }
+
+  //      (i)  If a policy constraints extension is included in the
+  //           certificate, modify the explicit_policy and policy_mapping
+  //           state variables as follows:
+  if (cert.has_policy_constraints()) {
+    //         (1)  If requireExplicitPolicy is present and is less than
+    //              explicit_policy, set explicit_policy to the value of
+    //              requireExplicitPolicy.
+    if (cert.policy_constraints().has_require_explicit_policy &&
+        cert.policy_constraints().require_explicit_policy < explicit_policy_) {
+      explicit_policy_ = cert.policy_constraints().require_explicit_policy;
+    }
+
+    //         (2)  If inhibitPolicyMapping is present and is less than
+    //              policy_mapping, set policy_mapping to the value of
+    //              inhibitPolicyMapping.
+    if (cert.policy_constraints().has_inhibit_policy_mapping &&
+        cert.policy_constraints().inhibit_policy_mapping < policy_mapping_) {
+      policy_mapping_ = cert.policy_constraints().inhibit_policy_mapping;
+    }
+  }
+
+  //      (j)  If the inhibitAnyPolicy extension is included in the
+  //           certificate and is less than inhibit_anyPolicy, set
+  //           inhibit_anyPolicy to the value of inhibitAnyPolicy.
+  if (cert.has_inhibit_any_policy() &&
+      cert.inhibit_any_policy() < inhibit_any_policy_) {
+    inhibit_any_policy_ = cert.inhibit_any_policy();
+  }
 
   // From RFC 5280 section 6.1.4 step k:
   //
   //    If certificate i is a version 3 certificate, verify that the
   //    basicConstraints extension is present and that cA is set to
   //    TRUE.  (If certificate i is a version 1 or version 2
   //    certificate, then the application MUST either verify that
   //    certificate i is a CA certificate through out-of-band means
   //    or reject the certificate.  Conforming implementations may
   //    choose to reject all version 1 and version 2 intermediate
   //    certificates.)
   //
   // This code implicitly rejects non version 3 intermediates, since they
   // can't contain a BasicConstraints extension.
   if (!cert.has_basic_constraints()) {
     errors->AddError(kMissingBasicConstraints);
   } else if (!cert.basic_constraints().is_ca) {
     errors->AddError(kBasicConstraintsIndicatesNotCa);
   }
 
   // From RFC 5280 section 6.1.4 step l:
   //
   //    If the certificate was not self-issued, verify that
   //    max_path_length is greater than zero and decrement
   //    max_path_length by 1.
   if (!IsSelfIssued(cert)) {
-    if (*max_path_length_ptr == 0) {
+    if (max_path_length_ == 0) {
       errors->AddError(kMaxPathLengthViolated);
     } else {
-      --(*max_path_length_ptr);
+      --max_path_length_;
     }
   }
 
   // From RFC 5280 section 6.1.4 step m:
   //
   //    If pathLenConstraint is present in the certificate and is
   //    less than max_path_length, set max_path_length to the value
   //    of pathLenConstraint.
   if (cert.has_basic_constraints() && cert.basic_constraints().has_path_len &&
-      cert.basic_constraints().path_len < *max_path_length_ptr) {
-    *max_path_length_ptr = cert.basic_constraints().path_len;
+      cert.basic_constraints().path_len < max_path_length_) {
+    max_path_length_ = cert.basic_constraints().path_len;
   }
 
   // From RFC 5280 section 6.1.4 step n:
   //
   //    If a key usage extension is present, verify that the
   //    keyCertSign bit is set.
   if (cert.has_key_usage() &&
       !cert.key_usage().AssertsBit(KEY_USAGE_BIT_KEY_CERT_SIGN)) {
     errors->AddError(kKeyCertSignBitNotSet);
   }
@@ skipping 46 matching lines @@
                    cert.basic_constraints().is_ca &&
                    (!cert.has_key_usage() ||
                     cert.key_usage().AssertsBit(KEY_USAGE_BIT_KEY_CERT_SIGN));
     if (!success) {
       // TODO(eroman): Add DER for basic constraints and key usage.
       errors->AddError(kTargetCertInconsistentCaBits);
     }
   }
 }
 
-// This function corresponds with RFC 5280 section 6.1.5's "Wrap-Up Procedure".
-// It does processing for the final certificate (the target cert).
-void WrapUp(const ParsedCertificate& cert, CertErrors* errors) {
-  // TODO(crbug.com/634452): Steps a-b are omitted as policy constraints are not
-  // yet implemented.
+void PathVerifier::WrapUp(const ParsedCertificate& cert, CertErrors* errors) {
+  // From RFC 5280 section 6.1.5:
+  //      (a)  If explicit_policy is not 0, decrement explicit_policy by 1.
+  if (explicit_policy_ > 0)
+    explicit_policy_ -= 1;
 
-  // Note step c-e are omitted the verification function does
+  //      (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.
+  if (cert.has_policy_constraints() &&
+      cert.policy_constraints().has_require_explicit_policy &&
+      cert.policy_constraints().require_explicit_policy == 0) {
+    explicit_policy_ = 0;
+  }
+
+  // Note step c-e are omitted as the verification function does
   // not output the working public key.
 
   // From RFC 5280 section 6.1.5 step f:
   //
   //    Recognize and process any other critical extension present in
   //    the certificate n.  Process any other recognized non-critical
   //    extension present in certificate n that is relevant to path
   //    processing.
   //
   // Note that this is duplicated by PrepareForNextCertificate() so as to
   // directly match the procedures in RFC 5280's section 6.1.
   VerifyNoUnconsumedCriticalExtensions(cert, errors);
 
-  // TODO(eroman): Step g is omitted, as policy constraints are not yet
-  // implemented.
+  // RFC 5280 section 6.1.5 step g is skipped, as the intersection of valid
+  // policies was computed during previous steps.
+  //
+  //    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.
+  if (explicit_policy_ == 0 && valid_policies_.empty()) {
+    errors->AddError(kNoValidPolicy);
+  }
 
   // The following check is NOT part of RFC 5280 6.1.5's "Wrap-Up Procedure",
   // however is implied by RFC 5280 section 4.2.1.9.
   VerifyTargetCertHasConsistentCaBits(cert, errors);
 }
 
-// Enforces trust anchor constraints compatibile with RFC 5937.
-//
-// Note that the anchor constraints are encoded via the attached certificate
-// itself.
-void ApplyTrustAnchorConstraints(
-    const ParsedCertificate& cert,
-    KeyPurpose required_key_purpose,
-    size_t* max_path_length_ptr,
-    std::vector<const NameConstraints*>* name_constraints_list,
-    CertErrors* errors) {
+void PathVerifier::ApplyTrustAnchorConstraints(const ParsedCertificate& cert,
+                                               KeyPurpose required_key_purpose,
+                                               CertErrors* errors) {
   // This is not part of RFC 5937 nor RFC 5280, but matches the EKU handling
   // done for intermediates (described in Web PKI's Baseline Requirements).
   VerifyExtendedKeyUsage(cert, required_key_purpose, errors);
 
   // The following enforcements follow from RFC 5937 (primarily section 3.2):
 
   // Initialize name constraints initial-permitted/excluded-subtrees.
   if (cert.has_name_constraints())
-    name_constraints_list->push_back(&cert.name_constraints());
+    name_constraints_list_.push_back(&cert.name_constraints());
 
   // TODO(eroman): Initialize user-initial-policy-set based on anchor
   // constraints.
 
   // TODO(eroman): Initialize inhibit any policy based on anchor constraints.
 
   // TODO(eroman): Initialize require explicit policy based on anchor
   // constraints.
 
   // TODO(eroman): Initialize inhibit policy mapping based on anchor
   // constraints.

[mattm, 2017/05/25 23:21:48]

should these todos be done?

 
   // From RFC 5937 section 3.2:
   //
   //    If a basic constraints extension is associated with the trust
   //    anchor and contains a pathLenConstraint value, set the
   //    max_path_length state variable equal to the pathLenConstraint
   //    value from the basic constraints extension.
   //
   // NOTE: RFC 5937 does not say to enforce the CA=true part of basic
   // constraints.
   if (cert.has_basic_constraints() && cert.basic_constraints().has_path_len)
-    *max_path_length_ptr = cert.basic_constraints().path_len;
+    max_path_length_ = cert.basic_constraints().path_len;
 
   // From RFC 5937 section 2:
   //
   //    Extensions may be marked critical or not critical.  When trust anchor
   //    constraints are enforced, clients MUST reject certification paths
   //    containing a trust anchor with unrecognized critical extensions.
   VerifyNoUnconsumedCriticalExtensions(cert, errors);
 }
 
-// Initializes the path validation algorithm given anchor constraints. This
-// follows the description in RFC 5937
-void ProcessRootCertificate(
-    const ParsedCertificate& cert,
-    const CertificateTrust& trust,
-    KeyPurpose required_key_purpose,
-    size_t* max_path_length_ptr,
-    std::vector<const NameConstraints*>* name_constraints_list,
-    der::Input* working_spki,
-    der::Input* working_normalized_issuer_name,
-    CertErrors* errors) {
+void PathVerifier::ProcessRootCertificate(const ParsedCertificate& cert,
+                                          const CertificateTrust& trust,
+                                          KeyPurpose required_key_purpose,
+                                          CertErrors* errors) {
   // Use the certificate's SPKI and subject when verifying the next certificate.
   // Note this is initialized even in the case of untrusted roots (they already
   // emit an error for the distrust).
-  *working_spki = cert.tbs().spki_tlv;
-  *working_normalized_issuer_name = cert.normalized_subject();
+  working_spki_ = cert.tbs().spki_tlv;
+  working_normalized_issuer_name_ = cert.normalized_subject();
 
   switch (trust.type) {
     case CertificateTrustType::UNSPECIFIED:
       // Doesn't chain to a trust anchor - implicitly distrusted
       errors->AddError(kCertIsNotTrustAnchor);
       break;
     case CertificateTrustType::DISTRUSTED:
       // Chains to an actively distrusted certificate.
       errors->AddError(kCertIsDistrusted);
       break;
     case CertificateTrustType::TRUSTED_ANCHOR:
     case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
       // If the trust anchor has constraints, enforce them.
       if (trust.type == CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS) {
-        ApplyTrustAnchorConstraints(cert, required_key_purpose,
-                                    max_path_length_ptr, name_constraints_list,
-                                    errors);
+        ApplyTrustAnchorConstraints(cert, required_key_purpose, errors);
       }
       break;
   }
 }
 
-}  // namespace
-
-// This implementation is structured to mimic the description of certificate
-// path verification given by RFC 5280 section 6.1.
-void VerifyCertificateChain(const ParsedCertificateList& certs,
-                            const CertificateTrust& last_cert_trust,
-                            const SignaturePolicy* signature_policy,
-                            const der::GeneralizedTime& time,
-                            KeyPurpose required_key_purpose,
-                            CertPathErrors* errors) {
+void PathVerifier::Run(const ParsedCertificateList& certs,
+                       const CertificateTrust& last_cert_trust,
+                       const SignaturePolicy* signature_policy,
+                       const der::GeneralizedTime& time,
+                       KeyPurpose required_key_purpose,
+                       bool initial_explicit_policy,
+                       const std::set<der::Input>& user_initial_policy_set,
+                       bool initial_policy_mapping_inhibit,
+                       bool initial_any_policy_inhibit,
+                       CertPathErrors* errors) {
+  // This implementation is structured to mimic the description of certificate
+  // path verification given by RFC 5280 section 6.1.
   DCHECK(signature_policy);
   DCHECK(errors);
 
   // An empty chain is necessarily invalid.
   if (certs.empty()) {
     errors->GetOtherErrors()->AddError(kChainIsEmpty);
     return;
   }
 
   // TODO(eroman): Verifying a trusted leaf certificate is not currently
   // permitted.
   if (certs.size() == 1) {
     errors->GetOtherErrors()->AddError(kChainIsLength1);
     return;
   }
 
-  // Will contain a NameConstraints for each previous cert in the chain which
-  // had nameConstraints. This corresponds to the permitted_subtrees and
-  // excluded_subtrees state variables from RFC 5280.
-  std::vector<const NameConstraints*> name_constraints_list;
+  // RFC 5280's "n" variable is the length of the path, which does not count
+  // the trust anchor. (Although in practice it doesn't really change behaviors
+  // if n is used in place of n+1).
+  const size_t n = certs.size() - 1;
 
-  // |working_spki| is an amalgamation of 3 separate variables from RFC 5280:
-  //    * working_public_key
-  //    * working_public_key_algorithm
-  //    * working_public_key_parameters
-  //
-  // They are combined for simplicity since the signature verification takes an
-  // SPKI, and the parameter inheritence is not applicable for the supported
-  // key types.
-  //
-  // An approximate explanation of |working_spki| is this description from RFC
-  // 5280 section 6.1.2:
-  //
-  //    working_public_key:  the public key used to verify the
-  //    signature of a certificate.
-  der::Input working_spki;
-
-  // |working_normalized_issuer_name| is the normalized value of the
-  // working_issuer_name variable in RFC 5280 section 6.1.2:
-  //
-  //    working_issuer_name:  the issuer distinguished name expected
-  //    in the next certificate in the chain.
-  der::Input working_normalized_issuer_name;
-
-  // |max_path_length| corresponds with the same named variable in RFC 5280
-  // section 6.1.2:
-  //
-  //    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.
-  size_t max_path_length = certs.size();
+  valid_policies_ = user_initial_policy_set;
+  explicit_policy_ = initial_explicit_policy ? 0 : n + 1;
+  inhibit_any_policy_ = initial_any_policy_inhibit ? 0 : n + 1;
+  policy_mapping_ = initial_policy_mapping_inhibit ? 0 : n + 1;
+  max_path_length_ = n;
 
   // Iterate over all the certificates in the reverse direction: starting from
   // the root certificate and progressing towards the target certificate.
   //
-  //   * i=0               :  Root certificate (i.e. trust anchor)
-  //   * i=1               :  Certificated signed by the root certificate
-  //   * i=certs.size()-1  :  Target certificate.
+  //   * i=0  :  Root certificate (i.e. trust anchor)
+  //   * i=1  :  Certificate issued by root
+  //   * i=x  :  Certificate i=x is issued by certificate i=x-1
+  //   * i=n  :  Target certificate.
   for (size_t i = 0; i < certs.size(); ++i) {
     const size_t index_into_certs = certs.size() - i - 1;
 
     // |is_target_cert| is true if the current certificate is the target
     // certificate being verified. The target certificate isn't necessarily an
     // end-entity certificate.
     const bool is_target_cert = index_into_certs == 0;
     const bool is_root_cert = i == 0;
 
     const ParsedCertificate& cert = *certs[index_into_certs];
 
     // Output errors for the current certificate into an error bucket that is
     // associated with that certificate.
     CertErrors* cert_errors = errors->GetErrorsForCert(index_into_certs);
 
     if (is_root_cert) {
       ProcessRootCertificate(cert, last_cert_trust, required_key_purpose,
-                             &max_path_length, &name_constraints_list,
-                             &working_spki, &working_normalized_issuer_name,
                              cert_errors);
 
       // Don't do any other checks for root certificates.
       continue;
     }
 
     // Per RFC 5280 section 6.1:
     //  * Do basic processing for each certificate
     //  * If it is the last certificate in the path (target certificate)
     //     - Then run "Wrap up"
     //     - Otherwise run "Prepare for Next cert"
     BasicCertificateProcessing(cert, is_target_cert, signature_policy, time,
-                               working_spki, working_normalized_issuer_name,
-                               name_constraints_list, cert_errors);
-
-    // The key purpose is checked not just for the end-entity certificate, but
-    // also interpreted as a constraint when it appears in intermediates. This
-    // goes beyond what RFC 5280 describes, but is the de-facto standard. See
-    // https://wiki.mozilla.org/CA:CertificatePolicyV2.1#Frequently_Asked_Questions
-    VerifyExtendedKeyUsage(cert, required_key_purpose, cert_errors);
-
+                               required_key_purpose, cert_errors);
     if (!is_target_cert) {
-      PrepareForNextCertificate(cert, &max_path_length, &working_spki,
-                                &working_normalized_issuer_name,
-                                &name_constraints_list, cert_errors);
+      PrepareForNextCertificate(cert, cert_errors);
     } else {
       WrapUp(cert, cert_errors);
     }
   }
 
   // TODO(eroman): RFC 5280 forbids duplicate certificates per section 6.1:
   //
   //    A certificate MUST NOT appear more than once in a prospective
   //    certification path.
 }
 
+}  // namespace
+
+void VerifyCertificateChain(const ParsedCertificateList& certs,
+                            const CertificateTrust& last_cert_trust,
+                            const SignaturePolicy* signature_policy,
+                            const der::GeneralizedTime& time,
+                            KeyPurpose required_key_purpose,
+                            bool initial_explicit_policy,
+                            const std::set<der::Input>& user_initial_policy_set,
+                            bool initial_policy_mapping_inhibit,
+                            bool initial_any_policy_inhibit,
+                            CertPathErrors* errors) {
+  PathVerifier verifier;
+  verifier.Run(certs, last_cert_trust, signature_policy, time,
+               required_key_purpose, initial_explicit_policy,
+               user_initial_policy_set, initial_policy_mapping_inhibit,
+               initial_any_policy_inhibit, errors);
+}
+
 }  // namespace net