Add initial code for verifying a certificate chain.

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 "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;
+
+  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 interest from the parsed Certificate.
+  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 (that work is part of a
+  // different change).

[davidben, 2015/11/19 22:24:02]

Link to a bug or something? "that work is part of a different change" is an odd
thing to see in the source code after a change has landed.

[eroman, 2015/12/03 04:45:12]

I re-worded the TODO, and will address as follow-up.

VerifyNameMatches has since landed and I should be able to use that, but it has
a different API - expects the sequence tag already stripped - so will need to
resolve some stuff first.

+  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.

[davidben, 2015/11/19 22:24:02]

It's an ASN.1 structure, so I think the natural interpretation is ASN.1's notion
of equality, which should be the same as byte-for-byte equality in DER.

Rather than have to route through an Equals, perhaps we should do byte-for-byte
equality and, if they fail, just check for sha1WithRSAEncryption and
sha1WithRSASignature? (If you want to be super-lazy, we could even just write
out their DER serializations somewhere and memcmp the two.)

That we we don't need to have code for comparing funny kinds of parameters or
implement it for future ones. If we end up having to grow a looseness in
SignatureAlgorithm parsing later or they have two ways to express the same
thing, we can keep this line in the sand and prevent it from getting worse.

[eroman, 2015/12/03 04:45:12]

Done.

That sounds like a very sensible approach. I have sent out a separate CL to
remove the existing code for doing SignatureAlgorithm::Equals().

+// 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 (!cert.key_usage.AssertsBit(KEY_USAGE_BIT_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.

[davidben, 2015/11/19 22:24:02]

Might be worth a comment that |current_cert_index| is counting from the
end-entity, starting from zero. |cert| must be an issuer, so
|current_cert_index| may not be zero. Or something like that.

[eroman, 2015/12/03 04:45:12]

I went ahead and changed the ordering so it matches RFC 5280.

+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);

[davidben, 2015/11/19 22:24:02]

DCHECK_LT(num_prev_self_issued_certs, current_cert_index);

[eroman, 2015/12/03 04:45:12]

This line is no longer applicable.

+
+  // 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 ?

[davidben, 2015/11/19 22:24:02]

This TODO should also be removed, right?

+  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?)

[davidben, 2015/11/19 22:24:02]

My interpretation is {cA boolean is asserted} means {has key usage AND key usage
has cA bit}, so {cA boolean is not asserted} should include the missing key
usage xtn case.

[eroman, 2015/12/03 04:45:12]

Removed TODO and am enforcing this along that interpretation

+  if (cert.has_key_usage &&
+      cert.key_usage.AssertsBit(KEY_USAGE_BIT_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) {

[davidben, 2015/11/19 22:24:02]

It seems RFC 5280 6.1 actually specifies a different algorithm which walks in
the other order. It then has a somewhat inverted algorithm for checking
max_path_len. Initialize to n, decrement on non-self-issued cert (fail if you
can't), take minimum every time you see a path length constraint.

I'm wondering why you choose to do it in this direction. I haven't thought about
this very hard so I don't know which order is cleaner for the more complex
checks. The RFC's algorithm does have to intersect sets of permitted subtrees
for name constraints (or do some O(N^2) thing), which is rather a bother. But I
don't if the other direction makes it any easier to avoid that.

[eroman, 2015/12/03 04:45:12]

I have switched it to the other direction.

(Doesn't make much difference until adding policy and name constraints anyway).

+    // |cert| is the current certificate -- either the target or an
+    // intermediary, but never a root.
+    const auto& cert = certs[i];
+
+    if (!VerifyValidity(cert, time))

[davidben, 2015/11/19 22:24:02]

At no point do we verify that the the certificate isn't valid on February 31s or
some such. Not worth bothering? (Probably not.)

[eroman, 2015/12/03 04:45:12]

I think we are already good here, but worth adding a test tomorrow.

Day ranges for months are currently enforced during parsing of
UTCTime/GeneralizedTime:

https://code.google.com/p/chromium/codesearch#chromium/src/net/der/parse_valu...

+      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