Certificate path builder for new certificate verification library

net/cert/internal/path_builder.cc

Index: net/cert/internal/path_builder.cc
diff --git a/net/cert/internal/path_builder.cc b/net/cert/internal/path_builder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..92749262cb1dd0c709ae71c3a35f48656f271a99
--- /dev/null
+++ b/net/cert/internal/path_builder.cc
@@ -0,0 +1,576 @@
+// Copyright 2016 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/path_builder.h"
+
+//#include <unordered_set>
+#include <set>
+
+#include "base/callback_helpers.h"
+#include "base/memory/ptr_util.h"
+#include "net/base/net_errors.h"
+#include "net/cert/internal/parse_certificate.h"
+#include "net/cert/internal/parse_name.h"  // XXX for DumpPath. Remove.
+#include "net/cert/internal/verify_name_match.h"
+#include "net/der/parser.h"
+#include "net/der/tag.h"
+
+namespace net {
+
+namespace {
+
+// LoopChecker tracks which certs are present in the path and prevents paths
+// from being built which repeat any certs.
+class LoopChecker {
+ public:
+  using Key =
+      std::tuple<base::StringPiece, base::StringPiece, base::StringPiece>;
+  // Attempts to add |cert| to the list of certs to check. If it has not already
+  // been added, true is returned and |cert| is added, such that any future
+  // attempts will return false.
+  // The |cert| data is not copied, Remove must be called before the |cert| data
+  // is destroyed.
+  bool Insert(const CertThing* cert) {
+    Key key = GetKey(cert);
+    if (present_certs_.find(key) != present_certs_.end())
+      return false;
+    present_certs_.insert(key);
+    return true;
+  }
+  // Removes a cert from being disallowed.
+  void Remove(const CertThing* cert) { present_certs_.erase(GetKey(cert)); }
+
+ private:
+  static Key GetKey(const CertThing* cert) {
+    // TODO(mattm): ideally this would use a normalized version of
+    // SubjectAltName, but it's not that important just for LoopChecker.
+    //
+    // Note that subject_alt_names_extension().value will be empty if the cert
+    // had no SubjectAltName extension, so there is no need for a condition on
+    // has_subject_alt_names().
+    return std::make_tuple(
+        cert->normalized_subject(),
+        cert->subject_alt_names_extension().value.AsStringPiece(),
+        cert->parsed_tbs().spki_tlv.AsStringPiece());
+  }
+
+  // TODO: use unordered_set. Requires making a hash function for Key.
+  std::set<Key> present_certs_;
+};
+
+// CertIssuersIter iterates through the intermediates from |cert_sources| which
+// may be issuers of |cert|.
+// TODO: It should return the issuers in order most likely to succeed.
+// TODO: deduping of certs in case multiple certsources return the same cert
+class CertIssuersIter {
+ public:
+  // Constructs the CertIssuersIter. Takes ownership of |cert|. |*cert_sources|
+  // must be valid for the lifetime of the CertIssuersIter.
+  CertIssuersIter(scoped_refptr<CertThing> cert,
+                  CertPathBuilder::CertSources* cert_sources,
+                  const TrustStore& trust_store);
+
+  // Gets the next candidate issuer for |cert_|. If one is not ready
+  // synchronously, the return value ERR_IO_PENDING is returned and |callback|
+  // will be called once an issuer is ready.
+  // In either case, the next issuer will be set in |*out_cert|, or if there are
+  // no
+  // more issuers available, |*out_cert| will be cleared.
+  // and it will have been stored in |*out_cert|
+  // it. If an issuer is ready, OK is returned and the cert is stored in
+  // |*out_cert|.
+  // If all issuers have been exhausted, OK is returned and |*out_cert| is
+  // cleared.
+  int GetNextIssuer(scoped_refptr<CertThing>* out_cert,
+                    const base::Closure& callback);
+
+  // Returns the |cert| for which issuers are being retrieved.
+  const CertThing* cert() const { return cert_.get(); }
+  scoped_refptr<CertThing> reference_cert() const { return cert_; }
+
+ private:
+  void GotAsyncCerts(CertVector certs);
+
+  scoped_refptr<CertThing> cert_;
+  CertPathBuilder::CertSources* cert_sources_;
+
+  // The list of issuers for |cert_|. This is added to incrementally (first
+  // synchronous, results, then possibly multiple times as asynchronous results
+  // arrive.) The issuers may be re-sorted each time new issuers are added, but
+  // only the results from |cur_| onwards should be sorted, since the earlier
+  // results were already returned.
+  CertVector issuers_;
+  // The index of the next cert in |issuers_| to return.
+  size_t cur_ = 0;
+
+  // Tracks whether asynchronous requests have been made yet.
+  bool did_async_query_ = false;
+  // If asynchronous requests were made, how many of them are still outstanding?
+  int pending_async_results_;
+  // Owns the Request objects for any asynchronous requests so that they will be
+  // cancelled if CertIssuersIter is destroyed.
+  std::vector<std::unique_ptr<CertSource::Request>> pending_async_requests_;
+
+  // When GetNextIssuer was called and returned asynchronously, |out_cert_| is
+  // where the result will be stored, and |callback_| will be run when the
+  // result is ready.
+  scoped_refptr<CertThing>* out_cert_;
+  base::Closure callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertIssuersIter);
+};
+
+CertIssuersIter::CertIssuersIter(scoped_refptr<CertThing> in_cert,
+                                 CertPathBuilder::CertSources* cert_sources,
+                                 const TrustStore& trust_store)
+    : cert_(in_cert), cert_sources_(cert_sources) {
+  trust_store.FindTrustAnchorsByNormalizedName(in_cert->normalized_issuer(),
+                                               &issuers_);
+  for (auto* cert_source : *cert_sources_)
+    cert_source->SyncGetIssuersOf(cert(), &issuers_);
+  // TODO: sort by notbefore, etc (eg if cert issuer matches a trust anchor
+  // subject (or is a trust anchor), that should be sorted higher too. See big
+  // list of possible sorting hints in RFC 4158.)
+  // (Update PathBuilderKeyRolloverTest.TestRolloverBothRootsTrusted once that
+  // is done)
+}
+
+int CertIssuersIter::GetNextIssuer(scoped_refptr<CertThing>* out_cert,
+                                   const base::Closure& callback) {
+  // Should not be called again while already waiting for an async result.
+  DCHECK(callback_.is_null());
+
+  if (cur_ < issuers_.size()) {
+    DVLOG(1) << "CertIssuersIter: returning item " << cur_ << " of "
+             << issuers_.size();
+    // Still have issuers that haven't been returned yet, return one of them.
+    *out_cert = std::move(issuers_[cur_++]);
+    return OK;
+  }
+  if (did_async_query_) {
+    if (pending_async_results_ == 0) {
+      DVLOG(1) << "CertIssuersIter Reached the end of all available issuers.";
+      // Reached the end of all available issuers.
+      *out_cert = nullptr;
+      return OK;
+    }
+
+    DVLOG(1) << "CertIssuersIter Still waiting for async results from other "
+                "CertSources.";
+    // Still waiting for async results from other CertSources.
+    out_cert_ = out_cert;
+    callback_ = callback;
+    return ERR_IO_PENDING;
+  }
+
+  // Reached the end of synchronously gathered issuers, now issue request(s) for
+  // async ones (AIA, etc).
+
+  did_async_query_ = true;
+  pending_async_results_ = 0;
+  for (auto* cert_source : *cert_sources_) {
+    std::unique_ptr<CertSource::Request> request;
+    int rv = cert_source->AsyncGetIssuersOf(
+        cert(),
+        base::Bind(&CertIssuersIter::GotAsyncCerts, base::Unretained(this)),
+        &request);
+    DVLOG(1) << "AsyncGetIssuersOf v=" << rv;
+    // XXX any other error handling here?
+    if (rv == ERR_IO_PENDING)
+      pending_async_results_++;
+    if (request)
+      pending_async_requests_.push_back(std::move(request));
+  }
+
+  if (pending_async_results_ == 0) {
+    DVLOG(1) << "CertIssuersIter No cert sources have async results.";
+    // No cert sources have async results.
+    *out_cert = nullptr;
+    return OK;
+  }
+
+  DVLOG(1) << "CertIssuersIter issued AsyncGetIssuersOf call(s) (n="
+           << pending_async_results_ << ")";
+  out_cert_ = out_cert;
+  callback_ = callback;
+  return ERR_IO_PENDING;
+}
+
+void CertIssuersIter::GotAsyncCerts(CertVector certs) {
+  DVLOG(1) << "CertIssuersIter::GotAsyncCerts n=" << certs.size();
+  pending_async_results_--;
+  for (auto& c : certs)
+    issuers_.push_back(std::move(c));
+
+  // TODO: re-sort remaining elements of issuers_ (remaining elements may be
+  // more than the ones just inserted, depending on |cur_| value).
+
+  // Notify that more results are available, if necessary.
+  if (!callback_.is_null()) {
+    if (cur_ < issuers_.size()) {
+      DVLOG(1) << "CertIssuersIter: async returning item " << cur_ << " of "
+               << issuers_.size();
+      *out_cert_ = std::move(issuers_[cur_++]);
+      base::ResetAndReturn(&callback_).Run();
+    } else if (pending_async_results_ == 0) {
+      DVLOG(1) << "CertIssuersIter: async returning empty result";
+      *out_cert_ = nullptr;
+      base::ResetAndReturn(&callback_).Run();
+    } else {
+      DVLOG(1) << "CertIssuersIter: empty result, but other async results "
+                  "pending, waiting..";
+    }
+  }
+}
+
+}  // namespace
+
+StaticCertSource::StaticCertSource(const CertVector& certs) {
+  for (const auto& cert : certs) {
+    intermediates_.insert(
+        std::make_pair(cert->normalized_subject(), std::move(cert)));
+  }
+}
+StaticCertSource::~StaticCertSource() {}
+
+void StaticCertSource::SyncGetIssuersOf(const CertThing* cert,
+                                        CertVector* issuers) {
+  auto range = intermediates_.equal_range(cert->normalized_issuer());
+  for (auto it = range.first; it != range.second; ++it)
+    issuers->push_back(it->second);
+}
+
+int StaticCertSource::AsyncGetIssuersOf(const CertThing* cert,
+                                        const IssuerCallback& issuers_callback,
+                                        std::unique_ptr<Request>* out_req) {
+  // StaticCertSource never returns asynchronous results.
+  return OK;
+}
+
+// CertPathIter generates possible paths from |cert| to a trust anchor in
+// |trust_store|, using intermediates from |cert_sources| if necessary.
+class CertPathIter {
+ public:
+  CertPathIter(scoped_refptr<CertThing> cert,
+               const CertPathBuilder::CertSources& cert_sources,
+               const TrustStore& trust_store);
+
+  // Gets the next candidate path. If a path is ready synchronously, OK is
+  // returned and the path is stored in |*path|.  If a path is not ready,
+  // ERR_IO_PENDING is returned and |async_ready_callback| will be called once
+  // |*path| has been set.
+  // In either case, if all paths have been exhausted, OK result is returned and
+  // |*path| is cleared.
+  // The cert data referred to in |*path| is only valid until the next
+  // GetNextPath call or until the CertPathIter is destroyed.
+  int GetNextPath(CertVector* path, const CompletionCallback& callback);
+
+ private:
+  enum State {
+    STATE_NONE,
+    STATE_GET_NEXT_ISSUER,
+    STATE_GET_NEXT_ISSUER_COMPLETE,
+    STATE_RETURN_A_PATH,
+    STATE_BACKTRACK,
+  };
+
+  int DoLoop();
+
+  int DoGetNextIssuer();
+  int DoGetNextIssuerComplete();
+  int DoBackTrack();
+
+  void HandleGotNextIssuer(void);
+
+  LoopChecker loop_checker_;
+  scoped_refptr<CertThing> next_cert_;
+  std::vector<std::unique_ptr<CertIssuersIter>> cur_path_;
+  CertPathBuilder::CertSources cert_sources_;
+  const TrustStore& trust_store_;
+  CertVector* out_path_;
+  CompletionCallback callback_;
+  State next_state_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertPathIter);
+};
+
+CertPathIter::CertPathIter(scoped_refptr<CertThing> cert,
+                           const CertPathBuilder::CertSources& cert_sources,
+                           const TrustStore& trust_store)
+    : next_cert_(std::move(cert)),
+      cert_sources_(cert_sources),
+      trust_store_(trust_store),
+      next_state_(STATE_GET_NEXT_ISSUER_COMPLETE) {}
+
+int CertPathIter::GetNextPath(CertVector* path,
+                              const CompletionCallback& callback) {
+  out_path_ = path;
+  out_path_->clear();
+  int rv = DoLoop();
+  if (rv == ERR_IO_PENDING)
+    callback_ = callback;
+  return rv;
+}
+
+int CertPathIter::DoLoop() {
+  int result;
+  do {
+    State state = next_state_;
+    next_state_ = STATE_NONE;
+    switch (state) {
+      case STATE_NONE:
+        NOTREACHED();
+        break;
+      case STATE_GET_NEXT_ISSUER:
+        result = DoGetNextIssuer();
+        break;
+      case STATE_GET_NEXT_ISSUER_COMPLETE:
+        result = DoGetNextIssuerComplete();
+        break;
+      case STATE_RETURN_A_PATH:
+        // If the returned path did not verify, then backtrack and keep
+        // looking.
+        next_state_ = STATE_BACKTRACK;
+        break;
+      case STATE_BACKTRACK:
+        result = DoBackTrack();
+        break;
+    }
+  } while (result != ERR_IO_PENDING && next_state_ != STATE_NONE &&
+           next_state_ != STATE_RETURN_A_PATH);
+
+  return result;
+}
+
+int CertPathIter::DoGetNextIssuer() {
+  next_state_ = STATE_GET_NEXT_ISSUER_COMPLETE;
+  int rv = cur_path_.back()->GetNextIssuer(
+      &next_cert_,
+      base::Bind(&CertPathIter::HandleGotNextIssuer, base::Unretained(this)));
+  return rv;
+}
+
+std::string DumpPath(
+    const std::vector<std::unique_ptr<CertIssuersIter>>& cur_path) {
+  std::string s;
+  for (const auto& node : cur_path) {
+    const CertThing* cert = node->cert();
+
+    RDNSequence subject, issuer;
+    if (!ParseName(cert->parsed_tbs().subject_tlv, &subject))
+      return std::string();
+    if (!ParseName(cert->parsed_tbs().issuer_tlv, &issuer))
+      return std::string();
+
+    std::string subject_str, issuer_str;
+
+    if (!ConvertToRFC2253(subject, &subject_str))
+      return std::string();
+    if (!ConvertToRFC2253(issuer, &issuer_str))
+      return std::string();
+    if (!s.empty())
+      s += " -> ";
+    s += subject_str + "(" + issuer_str + ")";
+  }
+  return s;
+}
+
+// Should we include trust anchors as a CertSource, or handle them separately?
+//
+// Pros/cons for handling them as a CertSource:
+// + CertPathIter will automatically try each one as a separate path
+// ? Could this cause LoopChecker issues? (preventing finding a trust anchor if
+// it has same Name+SAN+SPKI as the last cert in chain. Or would there always be
+// a better path by just removing that last cert and going directly to the trust
+// anchor?)
+// - Need special logic to not try to descend past a trust anchor (No reason
+// to).
+// - CertIssuersIter would need prioritization logic to put trust anchors first.
+// + Automatically handles the case where the trust anchor is the end-entity.
+// (Do we care about that?)
+//
+// Not as a Certsource, but Loop through trust anchors separately in
+// CertPathIter:
+// - requires another layer of logic to return the sequence of paths. bleh.
+//
+// Loop through trust anchors separately in CertPathBuilder:
+// + pretty straightforward
+// + doesn't require any special cases in CertPathIter for handling anchors.
+// ? maybe requires little extra work to make a separate path/result for each?
+// ? may want to sort/prioritize the anchors before trying them - but could
+// probably re-use whatever sort function CertIssuersIter uses.
+// - need to check TrustStore twice, unless CertPathIter returns the list of
+// matching anchors.
+// - means we can't just return a const-reference to the cur_path_, instead have
+// to clone all the entries a new CertVector, since the CertPathBuilder will
+// need to append the trust anchor to it.
+//
+// Old Conclusion: Loop through trust anchors separately in CertPathBuilder
+// looks nice, except for having to clone the entries..
+// New Conclusion: Handle them similar to a CertSource.
+
+int CertPathIter::DoGetNextIssuerComplete() {
+  if (next_cert_) {
+    // Skip this cert if it is already in the chain.
+    if (!loop_checker_.Insert(next_cert_.get())) {
+      next_state_ = STATE_GET_NEXT_ISSUER;
+      return OK;
+    }
+    // Note that loop_checker_.Insert does not make a copy of the cert data.
+    // Must call loop_checker_.Remove before destroying the cert data.
+
+    cur_path_.push_back(base::WrapUnique(new CertIssuersIter(
+        std::move(next_cert_), &cert_sources_, trust_store_)));
+    next_cert_ = nullptr;
+    DVLOG(1) << "CertPathIter cur_path_ = " << DumpPath(cur_path_);
+    // If the cert matches a trust root, this is a (possible) complete path.
+    // Signal readiness.
+    if (trust_store_.IsTrustedCertificate(cur_path_.back()->cert())) {
+      DVLOG(1) << "CertPathIter IsTrustedCertificate = true";
+      next_state_ = STATE_RETURN_A_PATH;
+      for (const auto& node : cur_path_)
+        out_path_->push_back(node->reference_cert());
+      return OK;
+    }
+    // Continue descending the tree.
+    next_state_ = STATE_GET_NEXT_ISSUER;
+  } else {
+    // XXX should also include such paths in CertPathBuilder::Result?
+    // No more issuers for current chain, go back up and see if there are any
+    // more for the previous cert.
+    next_state_ = STATE_BACKTRACK;
+  }
+  return OK;
+}
+
+int CertPathIter::DoBackTrack() {
+  DVLOG(1) << "CertPathIter backtracking...";
+  loop_checker_.Remove(cur_path_.back()->cert());
+  cur_path_.pop_back();
+  if (cur_path_.empty()) {
+    // Exhausted all paths.
+    next_state_ = STATE_NONE;
+  } else {
+    next_state_ = STATE_GET_NEXT_ISSUER;
+  }
+  return OK;
+}
+
+void CertPathIter::HandleGotNextIssuer(void) {
+  DCHECK(!callback_.is_null());
+  int rv = DoLoop();
+  if (rv != ERR_IO_PENDING)
+    base::ResetAndReturn(&callback_).Run(rv);
+}
+
+CertPathBuilder::ResultPath::ResultPath() {}
+CertPathBuilder::ResultPath::~ResultPath() {}
+CertPathBuilder::Result::Result() {}
+CertPathBuilder::Result::~Result() {}
+
+CertPathBuilder::CertPathBuilder(scoped_refptr<CertThing> cert,
+                                 const CertSources& cert_sources,
+                                 const TrustStore& trust_store,
+                                 const SignaturePolicy* signature_policy,
+                                 const der::GeneralizedTime& time,
+                                 Result* result)
+    : cert_path_iter_(
+          new CertPathIter(std::move(cert), cert_sources, trust_store)),
+      trust_store_(trust_store),
+      signature_policy_(signature_policy),
+      time_(time),
+      next_state_(STATE_NONE),
+      out_result_(result) {}
+
+CertPathBuilder::~CertPathBuilder() {}
+
+int CertPathBuilder::Run(const CompletionCallback& callback) {
+  DCHECK_EQ(STATE_NONE, next_state_);
+  next_state_ = STATE_GET_NEXT_PATH;
+  int rv = DoLoop(OK);
+
+  if (rv == ERR_IO_PENDING)
+    callback_ = callback;
+
+  return rv;
+}
+
+int CertPathBuilder::DoLoop(int result) {
+  do {
+    State state = next_state_;
+    next_state_ = STATE_NONE;
+    switch (state) {
+      case STATE_NONE:
+        NOTREACHED();
+        break;
+      case STATE_GET_NEXT_PATH:
+        DCHECK_EQ(OK, result);
+        result = DoGetNextPath();
+        break;
+      case STATE_GET_NEXT_PATH_COMPLETE:
+        result = DoGetNextPathComplete(result);
+        break;
+    }
+  } while (result != ERR_IO_PENDING && next_state_ != STATE_NONE);
+
+  return result;
+}
+
+int CertPathBuilder::DoGetNextPath() {
+  next_state_ = STATE_GET_NEXT_PATH_COMPLETE;
+  int rv = cert_path_iter_->GetNextPath(
+      &next_path_,
+      base::Bind(&CertPathBuilder::HandleGotNextPath, base::Unretained(this)));
+  return rv;
+}
+
+void CertPathBuilder::HandleGotNextPath(int result) {
+  DCHECK(!callback_.is_null());
+  int rv = DoLoop(result);
+  if (rv != ERR_IO_PENDING)
+    base::ResetAndReturn(&callback_).Run(rv);
+}
+
+int CertPathBuilder::DoGetNextPathComplete(int result) {
+  if (next_path_.empty()) {
+    // No more paths to check, cert failed to verify. Return the result code for
+    // the best path that was found.
+    next_state_ = STATE_NONE;
+    return out_result_->result();
+  }
+
+  bool verify_result = VerifyCertificateChainAssumingTrustedRoot(
+      next_path_, trust_store_, signature_policy_, time_);
+  DVLOG(1) << "CertPathBuilder VerifyCertificateChain result = "
+           << verify_result;
+  AddResultPath(next_path_, verify_result);
+
+  if (verify_result) {
+    // Found a valid path, return immediately.
+    // XXX add debug/test mode that tries all possible paths.
+    next_state_ = STATE_NONE;
+    return out_result_->result();
+  }
+
+  // Path did not verify. Try more paths. If there are no more paths, the result
+  // will be returned next time DoGetNextPathComplete is called with next_path_
+  // empty.
+  next_state_ = STATE_GET_NEXT_PATH;
+  return OK;
+}
+
+void CertPathBuilder::AddResultPath(const CertVector& path, bool result) {
+  std::unique_ptr<ResultPath> rp(new ResultPath());
+  // XXX do better error mapping from VerifyCertificateChain results
+  rp->rv = result ? OK : ERR_CERT_AUTHORITY_INVALID;
+  // XXX set best_path_ if #errors(this) < #errors(best):
+  if (rp->rv == OK)
+    out_result_->best_result_index = out_result_->paths.size();
+  // XXX only return a single path except in debug/test mode.
+  for (const auto& cert : path)
+    rp->path.push_back(cert);
+  out_result_->paths.push_back(std::move(rp));
+}
+
+}  // namespace net