Certificate path builder for new certificate verification library

net/cert/internal/path_builder.cc

+// 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 "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:
+  // 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) {
+    if (present_certs_.find(cert.der_cert().AsStringPiece()) !=
+        present_certs_.end())
+      return false;
+    present_certs_.insert(cert.der_cert().AsStringPiece());
+    return true;
+  }
+  // Removes a cert from being disallowed.
+  void Remove(const CertThing& cert) {
+    present_certs_.erase(cert.der_cert().AsStringPiece());
+  }
+
+ private:
+  // TODO: this should be keyed on Name+SAN+SPKI.  (Update
+  // PathBuilderKeyRolloverTest.TestRolloverLongChain once that is done)
+  std::unordered_set<base::StringPiece, base::StringPieceHash> 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.
+class CertIssuersIter {
+ public:
+  // Constructs the CertIssuersIter. Takes ownership of |cert|. |*cert_sources|
+  // must be valid for the lifetime of the CertIssuersIter.
+  CertIssuersIter(std::unique_ptr<CertThing> cert,
+                  CertPathBuilder::CertSources* cert_sources);
+
+  // 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(std::unique_ptr<CertThing>* out_cert,
+                    const base::Closure& callback);
+
+  // Returns the |cert| for which issuers are being retrieved.
+  const CertThing& cert() const { return *cert_; }
+
+ private:
+  void GotAsyncCerts(CertVector certs);
+
+  std::unique_ptr<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.
+  std::unique_ptr<CertThing>* out_cert_;
+  base::Closure callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertIssuersIter);
+};
+
+CertIssuersIter::CertIssuersIter(std::unique_ptr<CertThing> in_cert,
+                                 CertPathBuilder::CertSources* cert_sources)
+    : cert_(std::move(in_cert)), cert_sources_(cert_sources) {
+  for (auto* cert_source : *cert_sources_) {
+    if (!cert_source->SyncGetIssuersOf(cert(), &issuers_))
+      LOG(ERROR) << "SyncGetIssuersOf error";  // XXX what to do with errors
+                                               // here? Change SyncGetIssuersOf
+                                               // to never fail now that it
+                                               // doesn't do parsing?
+  }
+  // TODO: sort by notbefore, etc (eg if cert issuer matches a trust anchor
+  // subject, 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(std::unique_ptr<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->reset();
+      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->reset();
+    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_->reset();
+      base::ResetAndReturn(&callback_).Run();
+    } else {
+      DVLOG(1) << "CertIssuersIter: empty result, but other async results "
+                  "pending, waiting..";
+    }
+  }
+}
+
+}  // namespace
+
+StaticCertsSource::StaticCertsSource() {}
+StaticCertsSource::~StaticCertsSource() {}
+
+bool StaticCertsSource::Init(std::vector<der::Input> certs) {
+  for (auto cert_der : certs) {
+    std::unique_ptr<CertThing> cert(CertThing::CreateFromCertificateData(
+        cert_der.UnsafeData(), cert_der.Length(),
+        CertThing::DataSource::EXTERNAL_REFERENCE));
+    if (!cert)
+      return false;
+    intermediates_.insert(
+        std::make_pair(cert->normalized_subject(), std::move(cert)));
+  }
+  return true;
+}
+
+bool StaticCertsSource::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->Clone());
+  return true;
+}
+
+int StaticCertsSource::AsyncGetIssuersOf(const CertThing& cert,
+                                         const IssuerCallback& issuers_callback,
+                                         std::unique_ptr<Request>* out_req) {
+  // StaticCertsSource 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(std::unique_ptr<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,
+  };
+
+  bool IsIssuerTrusted(const CertThing& cert) const;
+
+  int DoLoop();
+
+  int DoGetNextIssuer();
+  int DoGetNextIssuerComplete();
+
+  void HandleGotNextIssuer(void);
+
+  LoopChecker loop_checker_;
+  std::unique_ptr<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(std::unique_ptr<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;
+}
+
+bool CertPathIter::IsIssuerTrusted(const CertThing& cert) const {
+  // XXX make trust store do pre-normalization for searching
+  return !trust_store_
+              .FindTrustAnchorsByNormalizedName(cert.normalized_issuer())
+              .empty();
+}
+
+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:
+        next_state_ = STATE_GET_NEXT_ISSUER;
+        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.
+//
+// Conclusion: Loop through trust anchors separately in CertPathBuilder looks
+// nice, except for having to clone the entries..
+
+int CertPathIter::DoGetNextIssuerComplete() {
+  if (next_cert_) {
+    // Skip this cert if it is already in the chain.
+    if (!loop_checker_.Insert(*next_cert_)) {
+      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_)));
+    next_cert_.reset();
+    DVLOG(1) << "CertPathIter cur_path_ = " << DumpPath(cur_path_);
+    // If the issuer of the cert matches a trust root, this is a (possible)
+    // // complete path. Signal readiness.
+    // Note that if this path does not verify, further subpaths will still
+    // be checked.  This is needed to handle cases like key rollover.
+    if (IsIssuerTrusted(cur_path_.back()->cert())) {
+      DVLOG(1) << "CertPathIter IsIssuerTrusted = true";
+      next_state_ = STATE_RETURN_A_PATH;
+      for (const auto& node : cur_path_)
+        out_path_->push_back(node->cert().Clone());  // XXX see if we can clone
+                                                     // without copying? Or just
+                                                     // return a ref/pointer to
+                                                     // the out_path_?
+      return OK;
+    }
+    // Continue descending the tree.
+    next_state_ = STATE_GET_NEXT_ISSUER;
+  } else {
+    DVLOG(1) << "CertPathIter backtracking...";
+    // 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.
+    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(std::unique_ptr<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();
+  }
+
+  std::vector<const CertThing*> matching_anchors(
+      trust_store_.FindTrustAnchorsByNormalizedName(
+          next_path_.back()->normalized_issuer()));
+  // TODO: sort/prioritize matching_anchors
+
+  for (auto& trust_anchor : matching_anchors) {

[eroman, 2016/04/26 22:10:10]

How does this work when the target cert being verified is a trust anchor itself?

I could envision handling the trust anchors more generally as part of building
out the path (you also mention something like this higher up).

  (1) Lookup the trustedness of current certificate in trust store -- it may be
{trusted, distrusted, unknown}. If it is actively trusted/untrusted then can
stop looking for issuers.

  (2) Otherwise try to find an issuer. Look for an issuer in all the cert
sources, _including_ the trust store.

  (3) go to (1)


In the case where the issuer came from trust store in step (2) you basically
already know its trustedness. But conceptually I think that loop works.

[mattm, 2016/04/26 22:54:16]

Yeah, that would be an issue with this approach.
yeah, that is one of the alternate approaches I was considering. The one issue I
thought might occur is with LoopChecker preventing the trust anchor from being
added to the chain (eg if the target cert had same Name+SAN+SPKI as a trust
anchor, but was a different cert which wasn't in the trust store). (This would
be once LoopChecker is updated to use Name+SAN+SPKI instead of the full cert
DER.)

+    // CertVector full_path(next_path_);
+    // full_path.push_back(trust_anchor->cert());
+
+    next_path_.push_back(trust_anchor->Clone());
+    bool verify_result = VerifyCertificateChainAssumingTrustedRoot(
+        next_path_, trust_store_, signature_policy_, time_);
+    DVLOG(1) << "CertPathBuilder VerifyCertificateChain result = "
+             << verify_result;
+    AddResultPath(next_path_, verify_result);
+    next_path_.pop_back();

[eroman, 2016/04/26 22:10:10]

Here it looks to be popping the trust anchor out of the path -- why?

 definitely believe we want to keep the trust anchor as part of the path.

Both internally in the code (so any hooks can operate on the root like any other
cert), but especially so for the public API, since callers may want to see what
trust anchor the path chained up to.

Since we are requiring trust anchors be certificates, we can do this, and don't
need some other separate representation for the resulting trust anchor.

[mattm, 2016/04/26 22:54:16]

AddResultPath makes a copy of the path which is what actually gets returned, the
popping here is just to prepare the next_path_ for the next iteration of the
loop.

+
+    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->Clone());
+  out_result_->paths.push_back(std::move(rp));
+}
+
+}  // namespace net