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 |