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..ad116525a3f2680900b2d0e6539bf0f7492e8d4c
--- /dev/null
+++ b/net/cert/internal/verify_certificate_chain.cc
@@ -0,0 +1,501 @@
+// 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());
+}
+
+// Map from OID to ParsedExtension.
+using ExtensionsMap = std::map<der::Input, ParsedExtension>;
+
+// Describes all parsed properties of a certificate that are relevant for
+// certificate verification.
+struct FullyParsedCert {
+  ParsedCertificate cert;
+  ParsedTbsCertificate tbs;
+
+  scoped_ptr<SignatureAlgorithm> signature_algorithm;
+
+  // Standard extensions that were parsed.
+  bool has_basic_constraints = false;
+  ParsedBasicConstraints basic_constraints;
+
+  bool has_key_usage = false;
+  der::BitString key_usage;
+
+  // The remaining extensions (excludes the standard ones above).
+  ExtensionsMap unconsumed_extensions;
+};
+
+// Removes the extension with OID |oid| from |unconsumed_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,
+                                         ExtensionsMap* unconsumed_extensions,
+                                         ParsedExtension* extension) {
+  auto it = unconsumed_extensions->find(oid);
+  if (it == unconsumed_extensions->end())
+    return false;
+
+  *extension = it->second;
+  unconsumed_extensions->erase(it);
+  return true;
+}
+
+// Returns true if the certificate does not contain any unconsumed _critical_
+// extensions.
+WARN_UNUSED_RESULT bool VerifyNoUnconsumedCriticalExtensions(
+    const FullyParsedCert& cert) {
+  for (const auto& entry : cert.unconsumed_extensions) {
+    if (entry.second.critical)
+      return false;
+  }
+  return true;
+}
+
+// Parses an X.509 Certificate fully (including the TBSCertificate and
+// standard extensions), saving all the properties to |out_|.
+WARN_UNUSED_RESULT bool FullyParseCertificate(const der::Input& cert_tlv,
+                                              FullyParsedCert* out) {
+  // Reset everything.
+  *out = FullyParsedCert();
+
+  // Parse the outer Certificate.
+  if (!ParseCertificate(cert_tlv, &out->cert))
+    return false;
+
+  // Parse the signature algorithm contained in the Certificate (there is
+  // another one in the TBSCertificate, which is checked later by
+  // VerifySignatureAlgorithmsMatch)
+  out->signature_algorithm =
+      SignatureAlgorithm::CreateFromDer(out->cert.signature_algorithm_tlv);
+  if (!out->signature_algorithm)
+    return false;
+
+  // Parse the TBSCertificate.
+  if (!ParseTbsCertificate(out->cert.tbs_certificate_tlv, &out->tbs))
+    return false;
+
+  // Parse the standard X.509 extensions and remove them from
+  // |unconsumed_extensions|.
+  if (out->tbs.has_extensions) {
+    // ParseExtensions() ensures there are no duplicates, and maps the (unique)
+    // OID to the extension value.
+    if (!ParseExtensions(out->tbs.extensions_tlv, &out->unconsumed_extensions))
+      return false;
+
+    ParsedExtension extension;
+
+    // Basic constraints.
+    if (ConsumeExtension(BasicConstraintsOid(), &out->unconsumed_extensions,
+                         &extension)) {
+      out->has_basic_constraints = true;
+      if (!ParseBasicConstraints(extension.value, &out->basic_constraints))
+        return false;
+    }
+
+    // KeyUsage.
+    if (ConsumeExtension(KeyUsageOid(), &out->unconsumed_extensions,
+                         &extension)) {
+      out->has_key_usage = true;
+      if (!ParseKeyUsage(extension.value, &out->key_usage))
+        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 (i.e. call
+  // VerifyNameMatches() instead).
+  return name1.Equals(name2);
+}
+
+// Returns true if |cert| was self-issued. The definition of self-issuance
+// comes from RFC 5280 section 6.1:
+//
+//    A certificate is self-issued if the same DN appears in the subject
+//    and issuer fields (the two DNs are the same if they match according
+//    to the rules specified in Section 7.1).  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.
+WARN_UNUSED_RESULT bool IsSelfIssued(const FullyParsedCert& cert) {
+  return NameMatches(cert.tbs.subject_tlv, cert.tbs.issuer_tlv);
+}
+
+// Finds a trust anchor that matches |name| in |trust_store| or returns
+// nullptr. The returned pointer references data in |trust_store|.
+//
+// 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 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 TrustAnchor* FindTrustAnchorByName(
+    const TrustStore& trust_store,
+    const der::Input& name) {
+  for (const auto& anchor : trust_store.anchors) {
+    if (NameMatches(name, InputFromString(&anchor.name)))
+      return &anchor;
+  }
+  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 VerifyTimeValidity(const FullyParsedCert& cert,
+                                           const der::GeneralizedTime time) {
+  return !(time < cert.tbs.validity_not_before) &&
+         !(cert.tbs.validity_not_after < time);
+}
+
+// Returns true if |signature_algorithm_tlv| is a valid algorithm encoding for
+// RSA with SHA1.
+WARN_UNUSED_RESULT bool IsRsaWithSha1SignatureAlgorithm(
+    const der::Input& signature_algorithm_tlv) {
+  scoped_ptr<SignatureAlgorithm> algorithm =
+      SignatureAlgorithm::CreateFromDer(signature_algorithm_tlv);
+
+  return algorithm &&
+         algorithm->algorithm() == SignatureAlgorithmId::RsaPkcs1 &&
+         algorithm->digest() == DigestAlgorithm::Sha1;
+}
+
+// Returns true if |cert| has internally consistent signature algorithms.
+//
+// X.509 certificates contain two different signature algorithms:
+//  (1) The signatureAlgorithm field of Certificate
+//  (2) The signature field of TBSCertificate
+//
+// According to RFC 5280 section 4.1.1.2 and 4.1.2.3 these two fields must be
+// equal:
+//
+//     This field MUST contain the same algorithm identifier as the
+//     signature field in the sequence tbsCertificate (Section 4.1.2.3).
+//
+// The spec is not explicit about what "the same algorithm identifier" means.
+// Our interpretation is that the two DER-encoded fields must be byte-for-byte
+// identical.
+//
+// In practice however there are certificates which use different encodings for
+// specifying RSA with SHA1 (different OIDs). This is special-cased for
+// compatibility sake.

[davidben, 2015/12/10 23:23:35]

[Incidentally, I have a guess as to what happened. OpenSSL only caches the
TBSCertificate parse (otherwise the signature would break), and re-encodes all
the outer bits. If it, or another implementation which behaves similarly,
converts from one to the other when re-encoding, badness will ensue.

To that end, if we ever felt like it, we could actually drive this out of the
system by providing a tool for people to rewrite their certificates and make the
outer sigalg match the inner one. The outer sigalg isn't signed and can be
freely re-encoded. When we get there, it may be worth gathering UMA on this.]

[eroman, 2015/12/17 19:43:52]

Good to know, thanks

+WARN_UNUSED_RESULT bool VerifySignatureAlgorithmsMatch(
+    const FullyParsedCert& cert) {
+  const der::Input& alg1_tlv = cert.cert.signature_algorithm_tlv;
+  const der::Input& alg2_tlv = cert.tbs.signature_algorithm_tlv;
+
+  // Ensure that the two DER-encoded signature algorithms are byte-for-byte
+  // equal, but make a compatibility concession for RSA with SHA1.
+  return alg1_tlv.Equals(alg2_tlv) ||
+         (IsRsaWithSha1SignatureAlgorithm(alg1_tlv) &&
+          IsRsaWithSha1SignatureAlgorithm(alg2_tlv));
+}
+
+// This function corresponds to RFC 5280 section 6.1.3's "Basic Certificate
+// Processing" procedure.
+WARN_UNUSED_RESULT bool BasicCertificateProcessing(
+    const FullyParsedCert& cert,
+    const SignaturePolicy* signature_policy,
+    const der::GeneralizedTime& time,
+    const der::Input& working_public_key,
+    const der::Input& working_issuer_name) {
+  // Check that the signature algorithms in Certificate vs TBSCertificate
+  // match. This isn't part of RFC section 6.1.3, but is mandated by sections

[davidben, 2015/12/10 23:23:35]

Nit: RFC section -> section or RFC 5280 section?

[eroman, 2015/12/17 19:43:53]

Done.

+  // 4.1.1.2 and 4.1.2.3.
+  if (!VerifySignatureAlgorithmsMatch(cert))
+    return false;
+
+  // Verify the digital signature using the previous certificate's (or trust
+  // anchor's) key (RFC 5280 section 6.1.3 step a.1).
+  if (!VerifySignedData(
+          *cert.signature_algorithm, cert.cert.tbs_certificate_tlv,
+          cert.cert.signature_value, working_public_key, signature_policy)) {
+    return false;
+  }
+
+  // Check the time range for the certificate's validity, ensuring it is valid
+  // at |time|.
+  // (RFC 5280 section 6.1.3 step a.2)
+  if (!VerifyTimeValidity(cert, time))
+    return false;
+
+  // TODO(eroman): Check revocation (RFC 5280 section 6.1.3 step a.3)
+
+  // Verify the certificate's issuer name matches the issuing certificate's (or
+  // trust anchor's) subject name. (RFC 5280 section 6.1.3 step a.4)
+  if (!NameMatches(cert.tbs.issuer_tlv, working_issuer_name))
+    return false;
+
+  return true;
+}
+
+// This function corresponds to RFC 5280 section 6.1.4's "Preparation for
+// Certificate i+1" procedure. |cert| is expected to be an intermediary.
+WARN_UNUSED_RESULT bool PrepareForNextCertificate(
+    const FullyParsedCert& cert,
+    size_t* max_path_length_ptr,
+    der::Input* working_public_key,
+    der::Input* working_issuer_name) {
+  // From RFC 5280 section 6.1.4 step c:
+  //
+  //    Assign the certificate subject name to working_issuer_name.
+  *working_issuer_name = cert.tbs.subject_tlv;
+
+  // From RFC 5280 section 6.1.4 step d:

[davidben, 2015/12/10 23:23:35]

Strictly speaking, this is steps d-f combined, with the crazy parameter
inheritance bit of step e dropped because we don't support key types which
require it.

[eroman, 2015/12/17 19:43:53]

Done. (added comment)

+  //
+  //    Assign the certificate subjectPublicKey to working_public_key.
+  *working_public_key = cert.tbs.spki_tlv;
+
+  // 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 intermediaries, since they
+  // can't contain a BasicConstraints extension.
+  if (!cert.has_basic_constraints || !cert.basic_constraints.is_ca)
+    return false;
+
+  // 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)
+      return false;
+    --(*max_path_length_ptr);
+  }
+
+  // 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.basic_constraints.has_path_len &&
+      cert.basic_constraints.path_len < *max_path_length_ptr) {
+    *max_path_length_ptr = 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)) {
+    return false;
+  }
+
+  // From RFC 5280 section 6.1.4 step o:
+  //
+  //    Recognize and process any other critical extension present in
+  //    the certificate.  Process any other recognized non-critical
+  //    extension present in the certificate that is relevant to path
+  //    processing.
+  if (!VerifyNoUnconsumedCriticalExtensions(cert))
+    return false;
+

[davidben, 2015/12/10 23:23:35]

Nit: Add TODO about policies and name constraints and such where you've skipped
steps? (Or not. Whatever's convenient.)

[mattm, 2015/12/17 02:37:35]

I think it would make sense. It's kind of obvious if you skip from step d to k,
but less obvious like in BasicCertificateProcessing where it's just later steps
that are missing.

[eroman, 2015/12/17 19:43:53]

Done. I have added numerous comments so each step is covered. Either I have a
TODO (policy/name constraints), or I have a note explaining why the step was
omitted

+  return true;
+}
+
+// Checks that if the target certificate has properties that only a CA should
+// have (keyCertSign, CA=true, pathLenConstraint), then its other properties
+// are consistent with being a CA.
+//
+// This follows from some requirements in RFC 5280 section 4.2.1.9. In
+// particular:
+//
+//    CAs MUST NOT include the pathLenConstraint field unless the cA
+//    boolean is asserted and the key usage extension asserts the
+//    keyCertSign bit.
+//
+// And:
+//
+//    If the cA boolean is not asserted, then the keyCertSign bit in the key
+//    usage extension MUST NOT be asserted.
+//
+// TODO(eroman): Strictly speaking the first requirement is on CAs and not the
+// certificate client, so could be skipped.
+//
+// TODO(eroman): I don't believe Firefox enforces the keyCertSign restriction
+// for compatibility reasons. Investigate if we need to similarly relax this
+// constraint.
+WARN_UNUSED_RESULT bool VerifyTargetCertHasConsistentCaBits(
+    const FullyParsedCert& cert) {
+  // Check if the certificate contains any property specific to CAs.
+  bool has_ca_property =
+      (cert.has_basic_constraints &&
+       (cert.basic_constraints.is_ca || cert.basic_constraints.has_path_len)) ||
+      (cert.has_key_usage &&
+       cert.key_usage.AssertsBit(KEY_USAGE_BIT_KEY_CERT_SIGN));
+
+  // If it "looks" like a CA because it has a CA-only property, then check that
+  // it sets ALL the properties expected of a CA.
+  if (has_ca_property) {
+    return cert.has_basic_constraints && cert.basic_constraints.is_ca &&
+           (!cert.has_key_usage ||
+            cert.key_usage.AssertsBit(KEY_USAGE_BIT_KEY_CERT_SIGN));
+  }
+
+  return true;
+}
+
+// This function corresponds with RFC 5280 section 6.1.5's "Wrap-Up Procedure".
+// It does processing for the final certificate (the target cert).
+WARN_UNUSED_RESULT bool WrapUp(const FullyParsedCert& cert) {
+  // 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 with PrepareForNextCertificate() so as to
+  // direclty match the procedures in RFC 5280's section 6.1.

[davidben, 2015/12/10 23:23:35]

directly

[eroman, 2015/12/17 19:43:52]

Done.

+  if (!VerifyNoUnconsumedCriticalExtensions(cert))
+    return false;
+
+  // 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.
+  if (!VerifyTargetCertHasConsistentCaBits(cert))
+    return false;
+
+  return true;
+}
+
+}  // namespace
+
+TrustAnchor::~TrustAnchor() {}
+
+TrustStore::TrustStore() {}
+TrustStore::~TrustStore() {}
+
+// This implementation is structured to mimic the description of certificate
+// path verification given by RFC 5280 section 6.1.
+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 necessarily invalid.
+  if (certs_der.empty())
+    return false;
+
+  // |working_public_key| corresponds with the same named variable in RFC 5280
+  // section 6.1.2:
+  //
+  //    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.
+  der::Input working_public_key;

[davidben, 2015/12/10 23:23:35]

It's actually a combination of working_public_key, working_public_key_algorithm,
and working_public_key_parameters. The three are split in the RFC to allow for
implementing the parameter inheritance thing.

(I'd call this working_spki or working_public_key_info or something to
distinguish from those names.)

[eroman, 2015/12/17 19:43:53]

Good idea, done (also added a comment block trying to explain the why).

+
+  // |working_public_key| corresponds with the same named variable in RFC 5280

[davidben, 2015/12/10 23:23:35]

working_issuer_name

[eroman, 2015/12/17 19:43:53]

Done.

+  // section 6.1.2:
+  //
+  //    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 name
+  //    provided in the trust anchor information.
+  der::Input working_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_der.size();
+
+  // Iterate over all the certificates in the reverse direction: starting from
+  // the trust anchor and progressing towards the target certificate.
+  for (size_t i = 1; i <= certs_der.size(); ++i) {
+    // Note that |i| is a 1-based index as per RFC 5280, where the target
+    // certificate is i=N and the certificate signed by trust anchor is i=N.

[davidben, 2015/12/10 23:23:35]

(I probably wouldn't have bothered, but whatever. :-) I suppose
teeeeecccchhhhnnniiiicccaaaallllyyyy a 1-indexed might overflow and a 0-indexed
can't. But sizeof(der::Input) > 1, so not actually.)

[eroman, 2015/12/17 19:43:52]

Changed to 0-based indexing. Agreed, perhaps this was overkill with matching RFC
5280.

+    const size_t index_into_certs_der = certs_der.size() - i;
+    const bool is_target_cert = index_into_certs_der == 0;
+
+    // Parse the current certificate into |cert|.
+    FullyParsedCert cert;
+    const der::Input& cert_der = certs_der[index_into_certs_der];
+    if (!FullyParseCertificate(cert_der, &cert))
+      return false;
+
+    // When processing the first certificate, initialize |working_public_key|
+    // and |working_issuer_name| to the trust anchor per RFC 5280 section 6.1.2.
+    // This is done inside the loop in order to have access to the parsed
+    // certificate.
+    if (i == 1) {
+      const TrustAnchor* trust_anchor =
+          FindTrustAnchorByName(trust_store, cert.tbs.issuer_tlv);
+      if (!trust_anchor)
+        return false;
+      working_public_key = InputFromString(&trust_anchor->spki);
+      working_issuer_name = InputFromString(&trust_anchor->name);
+    }
+
+    // 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"
+    if (!BasicCertificateProcessing(cert, signature_policy, time,
+                                    working_public_key, working_issuer_name)) {
+      return false;
+    }
+    if (!is_target_cert) {
+      if (!PrepareForNextCertificate(cert, &max_path_length,
+                                     &working_public_key,
+                                     &working_issuer_name)) {
+        return false;
+      }
+    } else {
+      if (!WrapUp(cert))
+        return false;
+    }
+  }
+
+  // TODO(eroman): Are duplicates possible? RFC 5280 forbids them per section
+  // 6.1:
+  //
+  //    A certificate MUST NOT appear more than once in a prospective
+  //    certification path.

[davidben, 2015/12/10 23:23:35]

It's certainly possible in so far as I could construct such a thing easily and
pass it into this function. Although I dunno what you'd check here. You could do
byte-for-byte equality, but then there's the two ways to encode the sig-alg. Or
maybe I sign two sliiiight variants on the same certificate. I suppose you could
go by serial number??

I dunno, this seems more of a concern for the path builder avoiding infinite
loop than anything else.

[eroman, 2015/12/17 19:43:52]

Perhaps not worth handling this at the verification layer. Are there any
security problems you can think of by allowing duplicates, other than being
crappy paths?

[davidben, 2015/12/17 20:02:26]

None that I can think of.

+
+  return true;
+}
+
+}  // namespace net