Allow the TrustStore interface to return matching intermediates, and identify distrusted certs.

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 <set>
 #include <unordered_set>
 
 #include "base/logging.h"
@@ skipping 22 matching lines @@
   if (!ParseName(cert->tbs().subject_tlv, &subject) ||
       !ConvertToRFC2253(subject, &subject_str))
     subject_str = "???";
   if (!ParseName(cert->tbs().issuer_tlv, &issuer) ||
       !ConvertToRFC2253(issuer, &issuer_str))
     issuer_str = "???";
 
   return subject_str + "(" + issuer_str + ")";
 }
 
-// This structure contains either a ParsedCertificate or a TrustAnchor. It is
-// used to describe the result of getting a certificate's issuer, which may
-// either be another certificate, or a trust anchor.
-struct CertificateOrTrustAnchor {
-  CertificateOrTrustAnchor() {}
+// This structure describes a certificate and its trust level. Note that |cert|
+// may be null to indicate an "empty" entry.
+struct IssuerEntry {
+  scoped_refptr<ParsedCertificate> cert;
+  CertificateTrust trust;
+};
 
-  explicit CertificateOrTrustAnchor(scoped_refptr<ParsedCertificate> cert)
-      : cert(std::move(cert)) {}
+// Simple comparator of IssuerEntry that defines the order in which issuers
+// should be explored. It puts trust anchors ahead of unknown or distrusted
+// ones.
+struct IssuerEntryComparator {
+  bool operator()(const IssuerEntry& issuer1, const IssuerEntry& issuer2) {
+    return CertificateTrustToOrder(issuer1.trust) <
+           CertificateTrustToOrder(issuer2.trust);
+  }
 
-  explicit CertificateOrTrustAnchor(scoped_refptr<TrustAnchor> anchor)
-      : anchor(std::move(anchor)) {}
+  static int CertificateTrustToOrder(const CertificateTrust& trust) {
+    switch (trust.type) {
+      case CertificateTrustType::TRUSTED_ANCHOR:
+      case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
+        return 1;
+      case CertificateTrustType::UNSPECIFIED:
+        return 2;
+      case CertificateTrustType::DISTRUSTED:
+        return 4;
+    }
 
-  bool IsTrustAnchor() const { return anchor.get() != nullptr; }
-  bool IsCertificate() const { return cert.get() != nullptr; }
-  bool IsEmpty() const { return !IsTrustAnchor() && !IsCertificate(); }
-
-  scoped_refptr<ParsedCertificate> cert;
-  scoped_refptr<TrustAnchor> anchor;
+    NOTREACHED();
+    return 5;
+  }
 };
 
 // CertIssuersIter iterates through the intermediates from |cert_issuer_sources|
 // which may be issuers of |cert|.
 class CertIssuersIter {
  public:
   // Constructs the CertIssuersIter. |*cert_issuer_sources| and |*trust_store|
   // must be valid for the lifetime of the CertIssuersIter.
   CertIssuersIter(scoped_refptr<ParsedCertificate> cert,
                   CertIssuerSources* cert_issuer_sources,
                   const TrustStore* trust_store);
 
   // Gets the next candidate issuer, or clears |*out| when all issuers have been
   // exhausted.
-  void GetNextIssuer(CertificateOrTrustAnchor* out);
+  void GetNextIssuer(IssuerEntry* out);
 
   // Returns the |cert| for which issuers are being retrieved.
   const ParsedCertificate* cert() const { return cert_.get(); }
   scoped_refptr<ParsedCertificate> reference_cert() const { return cert_; }
 
  private:
   void AddIssuers(ParsedCertificateList issuers);
   void DoAsyncIssuerQuery();
 
   // Returns true if |issuers_| contains unconsumed certificates.
   bool HasCurrentIssuer() const { return cur_issuer_ < issuers_.size(); }
 
+  // Sorts the remaining entries in |issuers_| in the preferred order to
+  // explore. Does not change the ordering for indices before cur_issuer_.
+  void SortRemainingIssuers();
+
   scoped_refptr<ParsedCertificate> cert_;
   CertIssuerSources* cert_issuer_sources_;
   const TrustStore* trust_store_;
 
-  // The list of trust anchors that match the issuer name for |cert_|.
-  TrustAnchors anchors_;
-  // The index of the next trust anchor in |anchors_| to return.
-  size_t cur_anchor_ = 0;
-
   // 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.
   // Elements should not be removed from |issuers_| once added, since
   // |present_issuers_| will point to data owned by the certs.
-  ParsedCertificateList issuers_;
+  std::vector<IssuerEntry> issuers_;
   // The index of the next cert in |issuers_| to return.
   size_t cur_issuer_ = 0;
+  // Set to true whenever new issuers are appended at the end, to indicate the
+  // ordering needs to be checked.
+  bool issuers_needs_sort_ = false;
 
   // Set of DER-encoded values for the certs in |issuers_|. Used to prevent
   // duplicates. This is based on the full DER of the cert to allow different
   // versions of the same certificate to be tried in different candidate paths.
   // This points to data owned by |issuers_|.
   std::unordered_set<base::StringPiece, base::StringPieceHash> present_issuers_;
 
   // Tracks which requests have been made yet.
   bool did_initial_query_ = false;
   bool did_async_issuer_query_ = false;
   // Index into pending_async_requests_ that is the next one to process.
   size_t cur_async_request_ = 0;
   // Owns the Request objects for any asynchronous requests so that they will be
   // cancelled if CertIssuersIter is destroyed.
   std::vector<std::unique_ptr<CertIssuerSource::Request>>
       pending_async_requests_;
 
   DISALLOW_COPY_AND_ASSIGN(CertIssuersIter);
 };
 
 CertIssuersIter::CertIssuersIter(scoped_refptr<ParsedCertificate> in_cert,
                                  CertIssuerSources* cert_issuer_sources,
                                  const TrustStore* trust_store)
     : cert_(in_cert),
       cert_issuer_sources_(cert_issuer_sources),
       trust_store_(trust_store) {
   DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert()) << ") created";
 }
 
-void CertIssuersIter::GetNextIssuer(CertificateOrTrustAnchor* out) {
+void CertIssuersIter::GetNextIssuer(IssuerEntry* out) {
   if (!did_initial_query_) {
     did_initial_query_ = true;
-    trust_store_->FindTrustAnchorsForCert(cert_, &anchors_);
-
     for (auto* cert_issuer_source : *cert_issuer_sources_) {
       ParsedCertificateList new_issuers;
       cert_issuer_source->SyncGetIssuersOf(cert(), &new_issuers);
       AddIssuers(std::move(new_issuers));
     }
-    DVLOG(1) << anchors_.size() << " sync anchors, " << issuers_.size()
-             << " sync issuers";
-    // TODO(mattm): 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)
   }
 
-  // Return possible trust anchors first.
-  if (cur_anchor_ < anchors_.size()) {
-    DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
-             << "): returning anchor " << cur_anchor_ << " of "
-             << anchors_.size();
-    // Still have anchors that haven't been returned yet, return one of them.
-    *out = CertificateOrTrustAnchor(anchors_[cur_anchor_++]);
-    return;
-  }
-
-  // If there aren't any issuers left, block until async results are ready.
+  // If there aren't any issuers, block until async results are ready.
   if (!HasCurrentIssuer()) {
     if (!did_async_issuer_query_) {
       // Now issue request(s) for async ones (AIA, etc).
       DoAsyncIssuerQuery();
     }
 
     // TODO(eroman): Rather than blocking on the async requests in FIFO order,
     // consume in the order they become ready.
     while (!HasCurrentIssuer() &&
            cur_async_request_ < pending_async_requests_.size()) {
       ParsedCertificateList new_issuers;
       pending_async_requests_[cur_async_request_]->GetNext(&new_issuers);
       if (new_issuers.empty()) {
         // Request is exhausted, no more results pending from that
         // CertIssuerSource.
         pending_async_requests_[cur_async_request_++].reset();
       } else {
         AddIssuers(std::move(new_issuers));
       }
     }
   }
 
   if (HasCurrentIssuer()) {
+    SortRemainingIssuers();
+
     DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
              << "): returning issuer " << cur_issuer_ << " of "
              << issuers_.size();
-    // Still have issuers that haven't been returned yet, return one of them.
-    // A reference to the returned issuer is retained, since |present_issuers_|
-    // points to data owned by it.
-    *out = CertificateOrTrustAnchor(issuers_[cur_issuer_++]);
+    // Still have issuers that haven't been returned yet, return the highest
+    // priority one (head of remaining list). A reference to the returned issuer
+    // is retained, since |present_issuers_| points to data owned by it.
+    *out = issuers_[cur_issuer_++];
     return;
   }
 
   DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
            << ") Reached the end of all available issuers.";
   // Reached the end of all available issuers.
-  *out = CertificateOrTrustAnchor();
+  *out = IssuerEntry();
 }
 
 void CertIssuersIter::AddIssuers(ParsedCertificateList new_issuers) {
   for (scoped_refptr<ParsedCertificate>& issuer : new_issuers) {
     if (present_issuers_.find(issuer->der_cert().AsStringPiece()) !=
         present_issuers_.end())
       continue;
     present_issuers_.insert(issuer->der_cert().AsStringPiece());
-    issuers_.push_back(std::move(issuer));
+
+    // Look up the trust for this issuer.
+    IssuerEntry entry;
+    entry.cert = std::move(issuer);
+    trust_store_->GetTrust(entry.cert, &entry.trust);
+
+    issuers_.push_back(std::move(entry));
+    issuers_needs_sort_ = true;
   }
 }
 
 void CertIssuersIter::DoAsyncIssuerQuery() {
   DCHECK(!did_async_issuer_query_);
   did_async_issuer_query_ = true;
   cur_async_request_ = 0;
   for (auto* cert_issuer_source : *cert_issuer_sources_) {
     std::unique_ptr<CertIssuerSource::Request> request;
     cert_issuer_source->AsyncGetIssuersOf(cert(), &request);
     if (request) {
       DVLOG(1) << "AsyncGetIssuersOf(" << CertDebugString(cert())
                << ") pending...";
       pending_async_requests_.push_back(std::move(request));
     }
   }
 }
 
+void CertIssuersIter::SortRemainingIssuers() {
+  // TODO(mattm): 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)
+  if (!issuers_needs_sort_)
+    return;
+
+  std::stable_sort(issuers_.begin() + cur_issuer_, issuers_.end(),
+                   IssuerEntryComparator());
+
+  issuers_needs_sort_ = false;
+}
+
 // CertIssuerIterPath tracks which certs are present in the path and prevents
 // paths from being built which repeat any certs (including different versions
 // of the same cert, based on Subject+SubjectAltName+SPKI).
 class CertIssuerIterPath {
  public:
   // Returns true if |cert| is already present in the path.
   bool IsPresent(const ParsedCertificate* cert) const {
     return present_certs_.find(GetKey(cert)) != present_certs_.end();
   }
 
@@ skipping 58 matching lines @@
   // TODO(mattm): use unordered_set. Requires making a hash function for Key.
   std::set<Key> present_certs_;
 };
 
 }  // namespace
 
 CertPath::CertPath() = default;
 CertPath::~CertPath() = default;
 
 void CertPath::Clear() {
-  trust_anchor = nullptr;
+  last_cert_trust = CertificateTrust::ForUnspecified();
   certs.clear();
 }
 
 bool CertPath::IsEmpty() const {
   return certs.empty();
 }
 
+const ParsedCertificate* CertPath::GetTrustedCert() const {
+  if (certs.empty())
+    return nullptr;
+
+  switch (last_cert_trust.type) {
+    case CertificateTrustType::TRUSTED_ANCHOR:
+    case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
+      return certs.back().get();
+    case CertificateTrustType::UNSPECIFIED:
+    case CertificateTrustType::DISTRUSTED:
+      return nullptr;
+  }
+
+  NOTREACHED();
+  return nullptr;
+}
+
 // CertPathIter generates possible paths from |cert| to a trust anchor in
 // |trust_store|, using intermediates from the |cert_issuer_source| objects if
 // necessary.
 class CertPathIter {
  public:
   CertPathIter(scoped_refptr<ParsedCertificate> cert,
                const TrustStore* trust_store);
 
   // Adds a CertIssuerSource to provide intermediates for use in path building.
   // The |*cert_issuer_source| must remain valid for the lifetime of the
@@ skipping 12 matching lines @@
     STATE_RETURN_A_PATH,
     STATE_BACKTRACK,
   };
 
   void DoGetNextIssuer();
   void DoGetNextIssuerComplete();
   void DoBackTrack();
 
   // Stores the next candidate issuer, until it is used during the
   // STATE_GET_NEXT_ISSUER_COMPLETE step.
-  CertificateOrTrustAnchor next_issuer_;
+  IssuerEntry next_issuer_;
   // The current path being explored, made up of CertIssuerIters. Each node
   // keeps track of the state of searching for issuers of that cert, so that
   // when backtracking it can resume the search where it left off.
   CertIssuerIterPath cur_path_;
   // The CertIssuerSources for retrieving candidate issuers.
   CertIssuerSources cert_issuer_sources_;
   // The TrustStore for checking if a path ends in a trust anchor.
   const TrustStore* trust_store_;
   // The output variable for storing the next candidate path, which the client
   // passes in to GetNextPath. Only used for a single path output.
   CertPath* out_path_;
   // Current state of the state machine.
   State next_state_;
 
   DISALLOW_COPY_AND_ASSIGN(CertPathIter);
 };
 
 CertPathIter::CertPathIter(scoped_refptr<ParsedCertificate> cert,
                            const TrustStore* trust_store)
-    : next_issuer_(std::move(cert)),
-      trust_store_(trust_store),
-      next_state_(STATE_GET_NEXT_ISSUER_COMPLETE) {}
+    : trust_store_(trust_store), next_state_(STATE_GET_NEXT_ISSUER_COMPLETE) {
+  // Initialize |next_issuer_| to the target certificate.
+  next_issuer_.cert = std::move(cert);
+  trust_store_->GetTrust(next_issuer_.cert, &next_issuer_.trust);
+}
 
 void CertPathIter::AddCertIssuerSource(CertIssuerSource* cert_issuer_source) {
   cert_issuer_sources_.push_back(cert_issuer_source);
 }
 
 // TODO(eroman): Simplify (doesn't need to use the "DoLoop" pattern).
 void CertPathIter::GetNextPath(CertPath* path) {
   out_path_ = path;
   out_path_->Clear();
   do {
@@ skipping 18 matching lines @@
       case STATE_BACKTRACK:
         DoBackTrack();
         break;
     }
   } while (next_state_ != STATE_NONE && next_state_ != STATE_RETURN_A_PATH);
 
   out_path_ = nullptr;
 }
 
 void CertPathIter::DoGetNextIssuer() {
-  next_state_ = STATE_GET_NEXT_ISSUER_COMPLETE;
-  cur_path_.back()->GetNextIssuer(&next_issuer_);
+  if (cur_path_.Empty()) {
+    // Exhausted all paths.
+    next_state_ = STATE_NONE;
+  } else {
+    next_state_ = STATE_GET_NEXT_ISSUER_COMPLETE;
+    cur_path_.back()->GetNextIssuer(&next_issuer_);
+  }
 }
 
 void CertPathIter::DoGetNextIssuerComplete() {
-  // If the issuer is a trust anchor signal readiness.
-  if (next_issuer_.IsTrustAnchor()) {
-    DVLOG(1) << "CertPathIter got anchor("
-             << CertDebugString(next_issuer_.anchor->cert().get());
-    next_state_ = STATE_RETURN_A_PATH;
-    cur_path_.CopyPath(&out_path_->certs);
-    out_path_->trust_anchor = std::move(next_issuer_.anchor);
-    next_issuer_ = CertificateOrTrustAnchor();
-    return;
-  }
-
-  if (next_issuer_.IsCertificate()) {
-    // Skip this cert if it is already in the chain.
-    if (cur_path_.IsPresent(next_issuer_.cert.get())) {
-      next_state_ = STATE_GET_NEXT_ISSUER;
-      return;
-    }
-
-    cur_path_.Append(base::MakeUnique<CertIssuersIter>(
-        std::move(next_issuer_.cert), &cert_issuer_sources_, trust_store_));
-    next_issuer_ = CertificateOrTrustAnchor();
-    DVLOG(1) << "CertPathIter cur_path_ = " << cur_path_.PathDebugString();
-    // Continue descending the tree.
-    next_state_ = STATE_GET_NEXT_ISSUER;
-  } else {
+  if (!next_issuer_.cert) {
     // TODO(mattm): should also include such paths in CertPathBuilder::Result,
     // maybe with a flag to enable it. Or use a visitor pattern so the caller
     // can decide what to do with any failed paths.
     // 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;
+  }
+
+  switch (next_issuer_.trust.type) {
+    // If the trust for this issuer is "known" (either becuase it is distrusted,
+    // or because it is trusted) then stop building and return the path.
+    case CertificateTrustType::DISTRUSTED:
+    case CertificateTrustType::TRUSTED_ANCHOR:
+    case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS: {
+      // If the issuer has a known trust level, can stop building the path.
+      DVLOG(1) << "CertPathIter got anchor: "
+               << CertDebugString(next_issuer_.cert.get());
+      next_state_ = STATE_RETURN_A_PATH;
+      cur_path_.CopyPath(&out_path_->certs);
+      out_path_->certs.push_back(std::move(next_issuer_.cert));
+      out_path_->last_cert_trust = next_issuer_.trust;
+      next_issuer_ = IssuerEntry();
+      break;
+    }
+    case CertificateTrustType::UNSPECIFIED: {
+      // Skip this cert if it is already in the chain.
+      if (cur_path_.IsPresent(next_issuer_.cert.get())) {
+        next_state_ = STATE_GET_NEXT_ISSUER;
+        break;
+      }
+
+      cur_path_.Append(base::MakeUnique<CertIssuersIter>(
+          std::move(next_issuer_.cert), &cert_issuer_sources_, trust_store_));
+      next_issuer_ = IssuerEntry();
+      DVLOG(1) << "CertPathIter cur_path_ = " << cur_path_.PathDebugString();
+      // Continue descending the tree.
+      next_state_ = STATE_GET_NEXT_ISSUER;
+      break;
+    }
   }
 }
 
 void CertPathIter::DoBackTrack() {
   DVLOG(1) << "CertPathIter backtracking...";
   cur_path_.Pop();
   if (cur_path_.Empty()) {
     // Exhausted all paths.
     next_state_ = STATE_NONE;
   } else {
     // Continue exploring issuers of the previous path.
     next_state_ = STATE_GET_NEXT_ISSUER;
   }
 }
 
 CertPathBuilder::ResultPath::ResultPath() = default;
 CertPathBuilder::ResultPath::~ResultPath() = default;
 
 bool CertPathBuilder::ResultPath::IsValid() const {
-  return !path.certs.empty() && path.trust_anchor &&
-         !errors.ContainsHighSeverityErrors();
+  return path.GetTrustedCert() && !errors.ContainsHighSeverityErrors();
 }
 
 CertPathBuilder::Result::Result() = default;
 CertPathBuilder::Result::~Result() = default;
 
 const CertPathBuilder::ResultPath* CertPathBuilder::Result::GetBestValidPath()
     const {
   DCHECK((paths.empty() && best_result_index == 0) ||
          best_result_index < paths.size());
 
   if (best_result_index >= paths.size())
     return nullptr;
 
   const ResultPath* result_path = paths[best_result_index].get();
   if (result_path->IsValid())
     return result_path;
 
   return nullptr;
 }
 
 bool CertPathBuilder::Result::HasValidPath() const {
   return GetBestValidPath() != nullptr;
 }
 
 CertPathBuilder::CertPathBuilder(scoped_refptr<ParsedCertificate> cert,
-                                 const TrustStore* trust_store,
+                                 TrustStore* trust_store,
                                  const SignaturePolicy* signature_policy,
                                  const der::GeneralizedTime& time,
                                  KeyPurpose key_purpose,
                                  Result* result)
     : cert_path_iter_(new CertPathIter(std::move(cert), trust_store)),
       signature_policy_(signature_policy),
       time_(time),
       key_purpose_(key_purpose),
       next_state_(STATE_NONE),
-      out_result_(result) {}
+      out_result_(result) {
+  // The TrustStore also implements the CertIssuerSource interface.
+  AddCertIssuerSource(trust_store);
+}
 
 CertPathBuilder::~CertPathBuilder() {}
 
 void CertPathBuilder::AddCertIssuerSource(
     CertIssuerSource* cert_issuer_source) {
   cert_path_iter_->AddCertIssuerSource(cert_issuer_source);
 }
 
 // TODO(eroman): Simplify (doesn't need to use the "DoLoop" pattern).
 void CertPathBuilder::Run() {
@@ skipping 24 matching lines @@
 
 void CertPathBuilder::DoGetNextPathComplete() {
   if (next_path_.IsEmpty()) {
     // No more paths to check, signal completion.
     next_state_ = STATE_NONE;
     return;
   }
 
   // Verify the entire certificate chain.
   auto result_path = base::MakeUnique<ResultPath>();
-  bool verify_result = VerifyCertificateChain(
-      next_path_.certs, next_path_.trust_anchor.get(), signature_policy_, time_,
-      key_purpose_, &result_path->errors);
+  VerifyCertificateChain(next_path_.certs, next_path_.last_cert_trust,
+                         signature_policy_, time_, key_purpose_,
+                         &result_path->errors);
+  bool verify_result = !result_path->errors.ContainsHighSeverityErrors();
+
   DVLOG(1) << "CertPathBuilder VerifyCertificateChain result = "
-           << verify_result;
+           << verify_result << "\n"
+           << result_path->errors.ToDebugString(next_path_.certs);
   result_path->path = next_path_;
-  DCHECK_EQ(verify_result, !result_path->errors.ContainsHighSeverityErrors());
   AddResultPath(std::move(result_path));
 
   if (verify_result) {
     // Found a valid path, return immediately.
     // TODO(mattm): add debug/test mode that tries all possible paths.
     next_state_ = STATE_NONE;
     return;
   }
 
   // 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;
 }
 
 void CertPathBuilder::AddResultPath(std::unique_ptr<ResultPath> result_path) {
   // TODO(mattm): set best_result_index based on number or severity of errors.
   if (result_path->IsValid())
     out_result_->best_result_index = out_result_->paths.size();
   // TODO(mattm): add flag to only return a single path or all attempted paths?
   out_result_->paths.push_back(std::move(result_path));
 }
 
 }  // namespace net