Add initial code for verifying a certificate chain.

net/cert/internal/verify_certificate_chain.cc

Index: net/cert/internal/verify_certificate_chain.cc
diff --git a/net/cert/internal/verify_certificate_chain.cc b/net/cert/internal/verify_certificate_chain.cc
new file mode 100644
index 0000000000000000000000000000000000000000..6f452de00de6749921724de5b7e08974aba8d932
--- /dev/null
+++ b/net/cert/internal/verify_certificate_chain.cc
@@ -0,0 +1,438 @@
+// 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 "base/logging.h"
+#include "net/cert/internal/parse_certificate.h"
+#include "net/cert/internal/signature_algorithm.h"
+#include "net/cert/internal/signature_policy.h"
+#include "net/cert/internal/verify_signed_data.h"
+#include "net/der/input.h"
+
+namespace net {
+
+namespace {
+
+// TODO(eroman): Move into net/der (duplicated from test_helpers.cc).
+static der::Input InputFromString(const std::string* s) {
+  return der::Input(reinterpret_cast<const uint8_t*>(s->data()), s->size());
+}
+
+// Describes all parsed properties of a certificate.
+struct FullyParsedCert {
+  CertificateVersion version;
+  scoped_ptr<SignatureAlgorithm> signature_algorithm;
+  scoped_ptr<SignatureAlgorithm> tbs_signature_algorithm;
+  der::BitString signature_value;
+  der::Input tbs_tlv;
+
+  // TODO(eroman): Everywhere this is consumed should also consider
+  // issuerAltName.

[mattm, 2015/11/11 23:55:44]

Did you mean "consider issuerAltName" like "should also check issuerAltName" or
"should consider whether checking issuerAltName is needed"?

(Since 5280 section 4.2.1.7 says "Issuer alternative names are not processed as
part of the certification path validation algorithm in Section 6.  (That is,
issuer alternative names are not used in name chaining and name constraints are
not enforced.)", I guess it's the second?)

[eroman, 2015/11/12 01:58:43]

Thanks, Done.

The TODO was basically to figure out what is needed for issuerAltName. From the
text you pointed me to sounds like no processing is actually needed for it, so I
have removed the TODO.

+  der::Input issuer_tlv;
+  der::GeneralizedTime validity_not_before;
+  der::GeneralizedTime validity_not_after;
+
+  // TODO(eroman): Everywhere this is consumed should also consider
+  // subjectAltName.
+  der::Input subject_tlv;
+  der::Input spki_tlv;
+
+  // Extensions
+  bool has_basic_constraints = false;
+  ParsedBasicConstraints basic_constraints;
+  bool has_key_usage = false;
+  der::BitString key_usage;
+};
+
+// Removes the extension with OID |oid| from |extensions| and fills |extension|
+// with the matching extension value. If there was no extension matching |oid|
+// then returns |false|.
+WARN_UNUSED_RESULT bool ConsumeExtension(
+    const der::Input& oid,
+    std::map<der::Input, ParsedExtension>* extensions,
+    ParsedExtension* extension) {
+  auto it = extensions->find(oid);
+  if (it == extensions->end())
+    return false;
+
+  *extension = it->second;
+
+  // TODO(eroman): Could be faster to just reset the entry instead of
+  //               deleting it, although a bit less clear.
+  extensions->erase(it);
+  return true;
+}
+
+// Parses a Certificate and saves all properties to |out|.
+WARN_UNUSED_RESULT bool FullyParseCertificate(const der::Input& cert_tlv,
+                                              FullyParsedCert* out) {
+  // Parse the Certificate.
+  ParsedCertificate cert;
+  if (!ParseCertificate(cert_tlv, &cert))
+    return false;
+
+  // Extract values of interested from the parsed Certificate.

[mattm, 2015/11/11 23:55:44]

interest

[eroman, 2015/11/12 01:58:43]

Done.

+  out->tbs_tlv = cert.tbs_certificate_tlv;
+  out->signature_value = cert.signature_value;
+
+  // Parse the signature algorithm in the Certificate.
+  out->signature_algorithm =
+      SignatureAlgorithm::CreateFromDer(cert.signature_algorithm_tlv);
+  if (!out->signature_algorithm)
+    return false;
+
+  // Parse the TBSCertificate.
+  ParsedTbsCertificate tbs;
+  if (!ParseTbsCertificate(cert.tbs_certificate_tlv, &tbs))
+    return false;
+
+  // Parse the signature algorithm in the TBSCertificate.
+  out->tbs_signature_algorithm =
+      SignatureAlgorithm::CreateFromDer(tbs.signature_algorithm_tlv);
+  if (!out->tbs_signature_algorithm)
+    return false;
+
+  // Copy fields of interest from the TBSCertificate (just copying pointers to
+  // the data, not the actual DER).
+  out->issuer_tlv = tbs.issuer_tlv;
+  out->version = tbs.version;
+  out->spki_tlv = tbs.spki_tlv;
+  out->subject_tlv = tbs.subject_tlv;
+  out->validity_not_after = tbs.validity_not_after;
+  out->validity_not_before = tbs.validity_not_before;
+
+  // Parse the X.509 extensions.
+  out->has_basic_constraints = false;
+  out->has_key_usage = false;
+
+  if (tbs.has_extensions) {
+    // ParseExtensions() ensures there are no duplicates, and maps the (unique)
+    // OID to the extension value. The verification code must ensure that every
+    // critical extension is understood.
+    std::map<der::Input, ParsedExtension> extensions;
+    if (!ParseExtensions(tbs.extensions_tlv, &extensions))
+      return false;
+
+    ParsedExtension extension;
+
+    // Process each of the recognized extensions. In doing so, the processed
+    // extension is cleared from the |extensions| map.
+    if (ConsumeExtension(BasicConstraintsOid(), &extensions, &extension)) {
+      out->has_basic_constraints = true;
+      if (!ParseBasicConstraints(extension.value, &out->basic_constraints))
+        return false;
+    }
+
+    if (ConsumeExtension(KeyUsageOid(), &extensions, &extension)) {
+      out->has_key_usage = true;
+      if (!ParseKeyUsage(extension.value, &out->key_usage))
+        return false;
+    }
+
+    // Check that there aren't any unconsumed (unprocessed) critical
+    // extensions in |extensions|. It is OK however for there to be
+    // unconsumed non-critical extensions.
+    for (const auto& entry : extensions) {
+      if (entry.second.critical)
+        return false;
+    }
+  }
+
+  return true;
+}
+
+// Returns true if |name1| matches |name2|.
+WARN_UNUSED_RESULT bool NameMatches(const der::Input& name1,
+                                    const der::Input& name2) {
+  // TODO(eroman): Should account for normalization (taht work is part of a
+  // different change).
+  return name1.Equals(name2);
+}
+
+// Returns true if |cert| was self-issued. Note that self-issued is not the
+// same thing as self-signed, see RFC 5280 for the explanation.
+WARN_UNUSED_RESULT bool IsSelfIssued(const FullyParsedCert& cert) {
+  return NameMatches(cert.subject_tlv, cert.issuer_tlv);
+}
+
+// Finds a mapping in the trust store that matches |name|, or returns nullptr.
+//
+// TODO(eroman): This implementation is linear in the size of the trust store,
+// and also presumes that all names are unique. In practice it is possible to
+// have have multiple SPKIs with the same name. Also this mechanism of
+// searching is fairly primitive, and does not take advantage of other
+// properties like the authority key id.
+WARN_UNUSED_RESULT const TrustedRoot* FindTrustedRootByName(
+    const TrustStore& trust_store,
+    const der::Input& name) {
+  for (const auto& root : trust_store.roots) {
+    if (NameMatches(name, InputFromString(&root.name)))
+      return &root;
+  }
+  return nullptr;
+}
+
+// Returns true if |cert| is 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.
+WARN_UNUSED_RESULT bool VerifyValidity(const FullyParsedCert& cert,
+                                       const der::GeneralizedTime time) {
+  return (!(time < cert.validity_not_before) &&
+          !(cert.validity_not_after < time));
+}
+
+// Returns true if |cert| has internally consistent signature algorithms.
+//
+// X.509 certificates contain two signature algorithms:
+//  (1) The signatureAlgorithm field of Certificate
+//  (2) The signature of TBSCertificate
+//
+// According to RFC 5280 section 4.1.1.2 these two fields must be in agreement:
+//
+//     This field MUST contain the same algorithm identifier as the
+//     signature field in the sequence tbsCertificate (Section 4.1.2.3).
+//
+// The  mechanism through which equality is determined is unspecified.
+// The interpretation taken here is that they identify the same algorithm,
+// but the DER-encoded AlgorithmIdentifier needn't be byte-for-byte equal.
+// There are a small number of certificates that require this (having for
+// instance specified a different OID for RSA with SHA-1).
+WARN_UNUSED_RESULT bool VerifySignatureAlgorithsMatch(
+    const FullyParsedCert& cert) {
+  return cert.signature_algorithm->Equals(*cert.tbs_signature_algorithm);
+}
+
+// Returns true if |cert| has a correct key usage for the issuance of other
+// certificates.
+WARN_UNUSED_RESULT bool VerifyKeyUsageForIssuer(const FullyParsedCert& cert) {
+  // If the Key Usage extension is not present, then the key can be used for
+  // any operation.
+  if (!cert.has_key_usage)
+    return true;
+
+  // RFC 5280 section 4.2.1.9:
+  //
+  //       If the keyUsage extension is present, then the subject public key
+  //       MUST NOT be used to verify signatures on certificates or CRLs unless
+  //       the corresponding keyCertSign or cRLSign bit is set.
+  if (!KeyUsageAssertsBit(cert.key_usage, KeyUsageBit::KEY_CERT_SIGN))
+    return false;
+
+  // RFC 5280 section 4.2.1.9:
+  //
+  //       If the keyCertSign bit is asserted, then the cA bit in the basic
+  //       constraints extension (Section 4.2.1.9) MUST also be asserted.
+  //
+  // NOTE: this normative requirement is not enforced by this function, but
+  // rather by VerifyBasicConstraintsForIssuer().
+  return true;
+}
+
+// Returns true if |cert| has a correct BasicConstraints extension for the
+// issuance of other certificates.
+WARN_UNUSED_RESULT bool VerifyBasicConstraintsForIssuer(
+    const FullyParsedCert& cert,
+    size_t current_cert_index,
+    size_t num_prev_self_issued_certs) {
+  DCHECK_GT(current_cert_index, 0u);
+
+  // Only V3 certificates have the concept of extensions.
+  if (cert.version == CertificateVersion::V1 ||
+      cert.version == CertificateVersion::V2) {
+    // RFC 5280:
+    //
+    //     (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.)
+    return false;
+  }
+
+  // RFC 5280 section 4.2.1.9:
+  //
+  //     If the basic constraints extension is not present in a version 3
+  //     certificate, or the extension is present but the cA boolean
+  //     is not asserted, then the certified public key MUST NOT be used to
+  //     verify certificate signatures.
+  if (!cert.has_basic_constraints || !cert.basic_constraints.is_ca)
+    return false;
+
+  // RFC 5280 section 4.2.1.9:
+  //
+  //     Where pathLenConstraint does not appear, no limit is imposed.
+  if (cert.basic_constraints.has_path_len) {
+    // RFC 5280 section 4.2.1.9:
+    //
+    //     ... In this case, it gives the maximum number of non-self-issued
+    //     intermediate certificates that may follow this certificate in a valid
+    //     certification path.  (Note: The last certificate in the certification
+    //     path is not an intermediate certificate, and is not included in this
+    //     limit.  Usually, the last certificate is an end entity certificate,
+    //     but it can be a CA certificate.)
+    size_t current_path_len =
+        current_cert_index - 1 - num_prev_self_issued_certs;
+    if (current_path_len > cert.basic_constraints.path_len)
+      return false;
+  }
+
+  return true;
+}
+
+// Returns true if the subject of |issuing_cert| matches the issuer of
+// |subordinate_cert|.
+WARN_UNUSED_RESULT bool VerifyIssuerMatchesSubject(
+    const FullyParsedCert& issuing_cert,
+    const FullyParsedCert& subordinate_cert) {
+  // TODO(eroman): subjectAltName and issuerAltName ?
+  return NameMatches(issuing_cert.subject_tlv, subordinate_cert.issuer_tlv);
+}
+
+// Returns true if |cert| was signed by a trusted root in |trust_store|.
+WARN_UNUSED_RESULT bool IsSignedByTrustAnchor(
+    const FullyParsedCert& cert,
+    const TrustStore& trust_store,
+    const SignaturePolicy* signature_policy) {
+  const TrustedRoot* trusted_root =
+      FindTrustedRootByName(trust_store, cert.issuer_tlv);
+
+  if (!trusted_root)
+    return false;
+
+  if (!VerifySignedData(
+          *cert.signature_algorithm, cert.tbs_tlv, cert.signature_value,
+          InputFromString(&trusted_root->spki), signature_policy)) {
+    return false;
+  }
+
+  return true;
+}
+
+// Returns true if |cert| has BasicConstraints and KeyUsage consistent with
+// being an end-entity certificate.
+WARN_UNUSED_RESULT bool VerifyTargetCertificateIsEndEntity(
+    const FullyParsedCert& cert) {
+  if (cert.has_basic_constraints) {
+    if (cert.basic_constraints.is_ca)
+      return false;  // Not an end-entity certificate.
+
+    // RFC 5280 section 4.2.1.9:
+    //
+    //    CAs MUST NOT include the pathLenConstraint field unless the cA
+    //    boolean is asserted and the key usage extension asserts the
+    //    keyCertSign bit.
+    if (cert.basic_constraints.has_path_len)
+      return false;
+  }
+
+  // RFC 5280 section 4.2.1.9:
+  //
+  //     If the cA boolean is not asserted, then the keyCertSign bit in the key
+  //     usage extension MUST NOT be asserted.
+  //
+  // TODO(eroman): Should "asserted" in the above apply only when the basic
+  // constraints extension is actually present? (In other words, if Basic
+  // Constraints was omitted, should keyCertSign be allowed even though it
+  // doesn't make sense?)
+  if (cert.has_key_usage &&
+      KeyUsageAssertsBit(cert.key_usage, KeyUsageBit::KEY_CERT_SIGN)) {
+    return false;
+  }
+
+  return true;
+}
+
+}  // namespace
+
+TrustedRoot::~TrustedRoot() {}
+
+TrustStore::TrustStore() {}
+TrustStore::~TrustStore() {}
+
+bool VerifyCertificateChain(const std::vector<der::Input>& certs_der,
+                            const TrustStore& trust_store,
+                            const SignaturePolicy* signature_policy,
+                            const der::GeneralizedTime& time) {
+  // An empty chain is invalid. Fail early since the rest of the code
+  // assumes a non-empty chain.
+  if (certs_der.empty())
+    return false;
+
+  // Fully parse all of the certificates. This is done up-front to simply
+  // access to properties.
+  std::vector<FullyParsedCert> certs(certs_der.size());
+  for (size_t i = 0; i < certs_der.size(); ++i) {
+    if (!FullyParseCertificate(certs_der[i], &certs[i]))
+      return false;
+  }
+
+  // TODO(eroman): Relax this and allow the caller to decide.
+  if (!VerifyTargetCertificateIsEndEntity(certs.front()))
+    return false;
+
+  // The last intermediary must be issued by a trusted root.
+  if (!IsSignedByTrustAnchor(certs.back(), trust_store, signature_policy))
+    return false;
+
+  // Walk the chain in the forward direction (from end entity towards trust
+  // anchor) and check all properties of the certificate, including issuance.
+  size_t num_prev_self_issued_certs = 0;
+  for (size_t i = 0; i < certs_der.size(); ++i) {
+    // |cert| is the current certificate -- either the target or an
+    // intermediary, but never a root.
+    const auto& cert = certs[i];
+
+    if (!VerifyValidity(cert, time))
+      return false;
+
+    if (!VerifySignatureAlgorithsMatch(cert))
+      return false;
+
+    // With the exception of the target (i=0), every other certificate (i) must
+    // be a CA. This section verifies that it is in fact a CA, and that it
+    // issued certificate (i-1).
+    if (i > 0) {
+      // The previous certificate in the chain, that purports to be issued by
+      // |cert|.
+      const auto& subordinate_cert = certs[i - 1];
+
+      if (!VerifyKeyUsageForIssuer(cert))
+        return false;
+
+      if (!VerifyBasicConstraintsForIssuer(cert, i, num_prev_self_issued_certs))
+        return false;
+
+      if (!VerifyIssuerMatchesSubject(cert, subordinate_cert))
+        return false;
+
+      // Verify the digital signature.
+      if (!VerifySignedData(*subordinate_cert.signature_algorithm,
+                            subordinate_cert.tbs_tlv,
+                            subordinate_cert.signature_value, cert.spki_tlv,
+                            signature_policy)) {
+        return false;
+      }
+    }
+
+    // Keep track of how many certificates were self-issued, since some rules
+    // are different for self-issued certificates (notably pathlen for
+    // BasicConstraints).
+    if (IsSelfIssued(cert))
+      num_prev_self_issued_certs++;
+  }
+
+  // TODO(eroman):
+  //  * Name constraints
+  //  * Policy constraints
+  //  * Extended Key Usage
+
+  return true;
+}
+
+}  // namespace net