1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "net/cert/internal/path_builder.h"
6
7 #include <memory>
8 #include <set>
9 #include <unordered_set>
10
11 #include "base/logging.h"
12 #include "base/metrics/histogram_functions.h"
13 #include "base/notreached.h"
14 #include "base/strings/string_number_conversions.h"
15 #include "crypto/sha2.h"
16 #include "net/base/net_errors.h"
17 #include "net/cert/internal/cert_issuer_source.h"
18 #include "net/cert/internal/certificate_policies.h"
19 #include "net/cert/internal/parse_certificate.h"
20 #include "net/cert/internal/parse_name.h" // For CertDebugString.
21 #include "net/cert/internal/trust_store.h"
22 #include "net/cert/internal/verify_certificate_chain.h"
23 #include "net/cert/internal/verify_name_match.h"
24 #include "net/der/parser.h"
25 #include "net/der/tag.h"
26
27 namespace net {
28
29 namespace {
30
31 using CertIssuerSources = std::vector<CertIssuerSource*>;
32
33 // Returns a hex-encoded sha256 of the DER-encoding of |cert|.
FingerPrintParsedCertificate(const net::ParsedCertificate * cert)34 std::string FingerPrintParsedCertificate(const net::ParsedCertificate* cert) {
35 std::string hash = crypto::SHA256HashString(cert->der_cert().AsStringPiece());
36 return base::HexEncode(hash.data(), hash.size());
37 }
38
39 // TODO(mattm): decide how much debug logging to keep.
CertDebugString(const ParsedCertificate * cert)40 std::string CertDebugString(const ParsedCertificate* cert) {
41 RDNSequence subject;
42 std::string subject_str;
43 if (!ParseName(cert->tbs().subject_tlv, &subject) ||
44 !ConvertToRFC2253(subject, &subject_str))
45 subject_str = "???";
46
47 return FingerPrintParsedCertificate(cert) + " " + subject_str;
48 }
49
PathDebugString(const ParsedCertificateList & certs)50 std::string PathDebugString(const ParsedCertificateList& certs) {
51 std::string s;
52 for (const auto& cert : certs) {
53 if (!s.empty())
54 s += "\n";
55 s += " " + CertDebugString(cert.get());
56 }
57 return s;
58 }
59
RecordIterationCountHistogram(uint32_t iteration_count)60 void RecordIterationCountHistogram(uint32_t iteration_count) {
61 base::UmaHistogramCounts10000("Net.CertVerifier.PathBuilderIterationCount",
62 iteration_count);
63 }
64
65 // This structure describes a certificate and its trust level. Note that |cert|
66 // may be null to indicate an "empty" entry.
67 struct IssuerEntry {
68 scoped_refptr<ParsedCertificate> cert;
69 CertificateTrust trust;
70 int trust_and_key_id_match_ordering;
71 };
72
73 enum KeyIdentifierMatch {
74 // |target| has a keyIdentifier and it matches |issuer|'s
75 // subjectKeyIdentifier.
76 kMatch = 0,
77 // |target| does not have authorityKeyIdentifier or |issuer| does not have
78 // subjectKeyIdentifier.
79 kNoData = 1,
80 // |target|'s authorityKeyIdentifier does not match |issuer|.
81 kMismatch = 2,
82 };
83
84 // Returns an integer that represents the relative ordering of |issuer| for
85 // prioritizing certificates in path building based on |issuer|'s
86 // subjectKeyIdentifier and |target|'s authorityKeyIdentifier. Lower return
87 // values indicate higer priority.
CalculateKeyIdentifierMatch(const ParsedCertificate * target,const ParsedCertificate * issuer)88 KeyIdentifierMatch CalculateKeyIdentifierMatch(
89 const ParsedCertificate* target,
90 const ParsedCertificate* issuer) {
91 if (!target->authority_key_identifier())
92 return kNoData;
93
94 // TODO(crbug.com/635205): If issuer does not have a subjectKeyIdentifier,
95 // could try synthesizing one using the standard SHA-1 method. Ideally in a
96 // way where any issuers that do have a matching subjectKeyIdentifier could
97 // be tried first before doing the extra work.
98 if (target->authority_key_identifier()->key_identifier &&
99 issuer->subject_key_identifier()) {
100 if (target->authority_key_identifier()->key_identifier !=
101 issuer->subject_key_identifier().value()) {
102 return kMismatch;
103 }
104 return kMatch;
105 }
106
107 return kNoData;
108 }
109
110 // Returns an integer that represents the relative ordering of |issuer| based
111 // on |issuer_trust| and authorityKeyIdentifier matching for prioritizing
112 // certificates in path building. Lower return values indicate higer priority.
TrustAndKeyIdentifierMatchToOrder(const ParsedCertificate * target,const ParsedCertificate * issuer,const CertificateTrust & issuer_trust)113 int TrustAndKeyIdentifierMatchToOrder(const ParsedCertificate* target,
114 const ParsedCertificate* issuer,
115 const CertificateTrust& issuer_trust) {
116 enum {
117 kTrustedAndKeyIdMatch = 0,
118 kTrustedAndKeyIdNoData = 1,
119 kKeyIdMatch = 2,
120 kKeyIdNoData = 3,
121 kTrustedAndKeyIdMismatch = 4,
122 kKeyIdMismatch = 5,
123 kDistrustedAndKeyIdMatch = 6,
124 kDistrustedAndKeyIdNoData = 7,
125 kDistrustedAndKeyIdMismatch = 8,
126 };
127
128 KeyIdentifierMatch key_id_match = CalculateKeyIdentifierMatch(target, issuer);
129 switch (issuer_trust.type) {
130 case CertificateTrustType::TRUSTED_ANCHOR:
131 case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
132 switch (key_id_match) {
133 case kMatch:
134 return kTrustedAndKeyIdMatch;
135 case kNoData:
136 return kTrustedAndKeyIdNoData;
137 case kMismatch:
138 return kTrustedAndKeyIdMismatch;
139 }
140 case CertificateTrustType::UNSPECIFIED:
141 switch (key_id_match) {
142 case kMatch:
143 return kKeyIdMatch;
144 case kNoData:
145 return kKeyIdNoData;
146 case kMismatch:
147 return kKeyIdMismatch;
148 }
149 case CertificateTrustType::DISTRUSTED:
150 switch (key_id_match) {
151 case kMatch:
152 return kDistrustedAndKeyIdMatch;
153 case kNoData:
154 return kDistrustedAndKeyIdNoData;
155 case kMismatch:
156 return kDistrustedAndKeyIdMismatch;
157 }
158 }
159 }
160
161 // CertIssuersIter iterates through the intermediates from |cert_issuer_sources|
162 // which may be issuers of |cert|.
163 class CertIssuersIter {
164 public:
165 // Constructs the CertIssuersIter. |*cert_issuer_sources|, |*trust_store|,
166 // and |*debug_data| must be valid for the lifetime of the CertIssuersIter.
167 CertIssuersIter(scoped_refptr<ParsedCertificate> cert,
168 CertIssuerSources* cert_issuer_sources,
169 const TrustStore* trust_store,
170 base::SupportsUserData* debug_data);
171
172 // Gets the next candidate issuer, or clears |*out| when all issuers have been
173 // exhausted.
174 void GetNextIssuer(IssuerEntry* out);
175
176 // Returns the |cert| for which issuers are being retrieved.
cert() const177 const ParsedCertificate* cert() const { return cert_.get(); }
reference_cert() const178 scoped_refptr<ParsedCertificate> reference_cert() const { return cert_; }
179
180 private:
181 void AddIssuers(ParsedCertificateList issuers);
182 void DoAsyncIssuerQuery();
183
184 // Returns true if |issuers_| contains unconsumed certificates.
HasCurrentIssuer() const185 bool HasCurrentIssuer() const { return cur_issuer_ < issuers_.size(); }
186
187 // Sorts the remaining entries in |issuers_| in the preferred order to
188 // explore. Does not change the ordering for indices before cur_issuer_.
189 void SortRemainingIssuers();
190
191 scoped_refptr<ParsedCertificate> cert_;
192 CertIssuerSources* cert_issuer_sources_;
193 const TrustStore* trust_store_;
194
195 // The list of issuers for |cert_|. This is added to incrementally (first
196 // synchronous results, then possibly multiple times as asynchronous results
197 // arrive.) The issuers may be re-sorted each time new issuers are added, but
198 // only the results from |cur_| onwards should be sorted, since the earlier
199 // results were already returned.
200 // Elements should not be removed from |issuers_| once added, since
201 // |present_issuers_| will point to data owned by the certs.
202 std::vector<IssuerEntry> issuers_;
203 // The index of the next cert in |issuers_| to return.
204 size_t cur_issuer_ = 0;
205 // Set to true whenever new issuers are appended at the end, to indicate the
206 // ordering needs to be checked.
207 bool issuers_needs_sort_ = false;
208
209 // Set of DER-encoded values for the certs in |issuers_|. Used to prevent
210 // duplicates. This is based on the full DER of the cert to allow different
211 // versions of the same certificate to be tried in different candidate paths.
212 // This points to data owned by |issuers_|.
213 std::unordered_set<base::StringPiece, base::StringPieceHash> present_issuers_;
214
215 // Tracks which requests have been made yet.
216 bool did_initial_query_ = false;
217 bool did_async_issuer_query_ = false;
218 // Index into pending_async_requests_ that is the next one to process.
219 size_t cur_async_request_ = 0;
220 // Owns the Request objects for any asynchronous requests so that they will be
221 // cancelled if CertIssuersIter is destroyed.
222 std::vector<std::unique_ptr<CertIssuerSource::Request>>
223 pending_async_requests_;
224
225 base::SupportsUserData* debug_data_;
226
227 DISALLOW_COPY_AND_ASSIGN(CertIssuersIter);
228 };
229
CertIssuersIter(scoped_refptr<ParsedCertificate> in_cert,CertIssuerSources * cert_issuer_sources,const TrustStore * trust_store,base::SupportsUserData * debug_data)230 CertIssuersIter::CertIssuersIter(scoped_refptr<ParsedCertificate> in_cert,
231 CertIssuerSources* cert_issuer_sources,
232 const TrustStore* trust_store,
233 base::SupportsUserData* debug_data)
234 : cert_(in_cert),
235 cert_issuer_sources_(cert_issuer_sources),
236 trust_store_(trust_store),
237 debug_data_(debug_data) {
238 DVLOG(2) << "CertIssuersIter created for " << CertDebugString(cert());
239 }
240
GetNextIssuer(IssuerEntry * out)241 void CertIssuersIter::GetNextIssuer(IssuerEntry* out) {
242 if (!did_initial_query_) {
243 did_initial_query_ = true;
244 for (auto* cert_issuer_source : *cert_issuer_sources_) {
245 ParsedCertificateList new_issuers;
246 cert_issuer_source->SyncGetIssuersOf(cert(), &new_issuers);
247 AddIssuers(std::move(new_issuers));
248 }
249 }
250
251 // If there aren't any issuers, block until async results are ready.
252 if (!HasCurrentIssuer()) {
253 if (!did_async_issuer_query_) {
254 // Now issue request(s) for async ones (AIA, etc).
255 DoAsyncIssuerQuery();
256 }
257
258 // TODO(eroman): Rather than blocking on the async requests in FIFO order,
259 // consume in the order they become ready.
260 while (!HasCurrentIssuer() &&
261 cur_async_request_ < pending_async_requests_.size()) {
262 ParsedCertificateList new_issuers;
263 pending_async_requests_[cur_async_request_]->GetNext(&new_issuers);
264 if (new_issuers.empty()) {
265 // Request is exhausted, no more results pending from that
266 // CertIssuerSource.
267 pending_async_requests_[cur_async_request_++].reset();
268 } else {
269 AddIssuers(std::move(new_issuers));
270 }
271 }
272 }
273
274 if (HasCurrentIssuer()) {
275 SortRemainingIssuers();
276
277 DVLOG(2) << "CertIssuersIter returning issuer " << cur_issuer_ << " of "
278 << issuers_.size() << " for " << CertDebugString(cert());
279 // Still have issuers that haven't been returned yet, return the highest
280 // priority one (head of remaining list). A reference to the returned issuer
281 // is retained, since |present_issuers_| points to data owned by it.
282 *out = issuers_[cur_issuer_++];
283 return;
284 }
285
286 DVLOG(2) << "CertIssuersIter reached the end of all available issuers for "
287 << CertDebugString(cert());
288 // Reached the end of all available issuers.
289 *out = IssuerEntry();
290 }
291
AddIssuers(ParsedCertificateList new_issuers)292 void CertIssuersIter::AddIssuers(ParsedCertificateList new_issuers) {
293 for (scoped_refptr<ParsedCertificate>& issuer : new_issuers) {
294 if (present_issuers_.find(issuer->der_cert().AsStringPiece()) !=
295 present_issuers_.end())
296 continue;
297 present_issuers_.insert(issuer->der_cert().AsStringPiece());
298
299 // Look up the trust for this issuer.
300 IssuerEntry entry;
301 entry.cert = std::move(issuer);
302 trust_store_->GetTrust(entry.cert, &entry.trust, debug_data_);
303 entry.trust_and_key_id_match_ordering = TrustAndKeyIdentifierMatchToOrder(
304 cert(), entry.cert.get(), entry.trust);
305
306 issuers_.push_back(std::move(entry));
307 issuers_needs_sort_ = true;
308 }
309 }
310
DoAsyncIssuerQuery()311 void CertIssuersIter::DoAsyncIssuerQuery() {
312 DCHECK(!did_async_issuer_query_);
313 did_async_issuer_query_ = true;
314 cur_async_request_ = 0;
315 for (auto* cert_issuer_source : *cert_issuer_sources_) {
316 std::unique_ptr<CertIssuerSource::Request> request;
317 cert_issuer_source->AsyncGetIssuersOf(cert(), &request);
318 if (request) {
319 DVLOG(1) << "AsyncGetIssuersOf pending for " << CertDebugString(cert());
320 pending_async_requests_.push_back(std::move(request));
321 }
322 }
323 }
324
SortRemainingIssuers()325 void CertIssuersIter::SortRemainingIssuers() {
326 if (!issuers_needs_sort_)
327 return;
328
329 std::stable_sort(
330 issuers_.begin() + cur_issuer_, issuers_.end(),
331 [](const IssuerEntry& issuer1, const IssuerEntry& issuer2) {
332 // TODO(crbug.com/635205): Add other prioritization hints. (See big list
333 // of possible sorting hints in RFC 4158.)
334 return std::tie(issuer1.trust_and_key_id_match_ordering,
335 // Newer(larger) notBefore & notAfter dates are
336 // preferred, hence |issuer2| is on the LHS of
337 // the comparison and |issuer1| on the RHS.
338 issuer2.cert->tbs().validity_not_before,
339 issuer2.cert->tbs().validity_not_after) <
340 std::tie(issuer2.trust_and_key_id_match_ordering,
341 issuer1.cert->tbs().validity_not_before,
342 issuer1.cert->tbs().validity_not_after);
343 });
344
345 issuers_needs_sort_ = false;
346 }
347
348 // CertIssuerIterPath tracks which certs are present in the path and prevents
349 // paths from being built which repeat any certs (including different versions
350 // of the same cert, based on Subject+SubjectAltName+SPKI).
351 // (RFC 5280 forbids duplicate certificates per section 6.1, and RFC 4158
352 // further recommends disallowing the same Subject+SubjectAltName+SPKI in
353 // section 2.4.2.)
354 class CertIssuerIterPath {
355 public:
356 // Returns true if |cert| is already present in the path.
IsPresent(const ParsedCertificate * cert) const357 bool IsPresent(const ParsedCertificate* cert) const {
358 return present_certs_.find(GetKey(cert)) != present_certs_.end();
359 }
360
361 // Appends |cert_issuers_iter| to the path. The cert referred to by
362 // |cert_issuers_iter| must not be present in the path already.
Append(std::unique_ptr<CertIssuersIter> cert_issuers_iter)363 void Append(std::unique_ptr<CertIssuersIter> cert_issuers_iter) {
364 bool added =
365 present_certs_.insert(GetKey(cert_issuers_iter->cert())).second;
366 DCHECK(added);
367 cur_path_.push_back(std::move(cert_issuers_iter));
368 }
369
370 // Pops the last CertIssuersIter off the path.
Pop()371 void Pop() {
372 size_t num_erased = present_certs_.erase(GetKey(cur_path_.back()->cert()));
373 DCHECK_EQ(num_erased, 1U);
374 cur_path_.pop_back();
375 }
376
377 // Copies the ParsedCertificate elements of the current path to |*out_path|.
CopyPath(ParsedCertificateList * out_path)378 void CopyPath(ParsedCertificateList* out_path) {
379 out_path->clear();
380 for (const auto& node : cur_path_)
381 out_path->push_back(node->reference_cert());
382 }
383
384 // Returns true if the path is empty.
Empty() const385 bool Empty() const { return cur_path_.empty(); }
386
387 // Returns the last CertIssuersIter in the path.
back()388 CertIssuersIter* back() { return cur_path_.back().get(); }
389
PathDebugString()390 std::string PathDebugString() {
391 std::string s;
392 for (const auto& node : cur_path_) {
393 if (!s.empty())
394 s += "\n";
395 s += " " + CertDebugString(node->cert());
396 }
397 return s;
398 }
399
400 private:
401 using Key =
402 std::tuple<base::StringPiece, base::StringPiece, base::StringPiece>;
403
GetKey(const ParsedCertificate * cert)404 static Key GetKey(const ParsedCertificate* cert) {
405 // TODO(mattm): ideally this would use a normalized version of
406 // SubjectAltName, but it's not that important just for LoopChecker.
407 //
408 // Note that subject_alt_names_extension().value will be empty if the cert
409 // had no SubjectAltName extension, so there is no need for a condition on
410 // has_subject_alt_names().
411 return Key(cert->normalized_subject().AsStringPiece(),
412 cert->subject_alt_names_extension().value.AsStringPiece(),
413 cert->tbs().spki_tlv.AsStringPiece());
414 }
415
416 std::vector<std::unique_ptr<CertIssuersIter>> cur_path_;
417
418 // This refers to data owned by |cur_path_|.
419 // TODO(mattm): use unordered_set. Requires making a hash function for Key.
420 std::set<Key> present_certs_;
421 };
422
423 } // namespace
424
GetTrustedCert() const425 const ParsedCertificate* CertPathBuilderResultPath::GetTrustedCert() const {
426 if (certs.empty())
427 return nullptr;
428
429 switch (last_cert_trust.type) {
430 case CertificateTrustType::TRUSTED_ANCHOR:
431 case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
432 return certs.back().get();
433 case CertificateTrustType::UNSPECIFIED:
434 case CertificateTrustType::DISTRUSTED:
435 return nullptr;
436 }
437
438 NOTREACHED();
439 return nullptr;
440 }
441
442 // CertPathIter generates possible paths from |cert| to a trust anchor in
443 // |trust_store|, using intermediates from the |cert_issuer_source| objects if
444 // necessary.
445 class CertPathIter {
446 public:
447 CertPathIter(scoped_refptr<ParsedCertificate> cert,
448 const TrustStore* trust_store,
449 base::SupportsUserData* debug_data);
450
451 // Adds a CertIssuerSource to provide intermediates for use in path building.
452 // The |*cert_issuer_source| must remain valid for the lifetime of the
453 // CertPathIter.
454 void AddCertIssuerSource(CertIssuerSource* cert_issuer_source);
455
456 // Gets the next candidate path, and fills it into |out_certs| and
457 // |out_last_cert_trust|. Note that the returned path is unverified and must
458 // still be run through a chain validator. Once all paths have been exhausted
459 // returns false.
460 bool GetNextPath(ParsedCertificateList* out_certs,
461 CertificateTrust* out_last_cert_trust,
462 const base::TimeTicks deadline,
463 uint32_t* iteration_count,
464 const uint32_t max_iteration_count);
465
466 private:
467 // Stores the next candidate issuer, until it is used during the
468 // STATE_GET_NEXT_ISSUER_COMPLETE step.
469 IssuerEntry next_issuer_;
470 // The current path being explored, made up of CertIssuerIters. Each node
471 // keeps track of the state of searching for issuers of that cert, so that
472 // when backtracking it can resume the search where it left off.
473 CertIssuerIterPath cur_path_;
474 // The CertIssuerSources for retrieving candidate issuers.
475 CertIssuerSources cert_issuer_sources_;
476 // The TrustStore for checking if a path ends in a trust anchor.
477 const TrustStore* trust_store_;
478
479 base::SupportsUserData* debug_data_;
480
481 DISALLOW_COPY_AND_ASSIGN(CertPathIter);
482 };
483
CertPathIter(scoped_refptr<ParsedCertificate> cert,const TrustStore * trust_store,base::SupportsUserData * debug_data)484 CertPathIter::CertPathIter(scoped_refptr<ParsedCertificate> cert,
485 const TrustStore* trust_store,
486 base::SupportsUserData* debug_data)
487 : trust_store_(trust_store), debug_data_(debug_data) {
488 // Initialize |next_issuer_| to the target certificate.
489 next_issuer_.cert = std::move(cert);
490 trust_store_->GetTrust(next_issuer_.cert, &next_issuer_.trust, debug_data_);
491 }
492
AddCertIssuerSource(CertIssuerSource * cert_issuer_source)493 void CertPathIter::AddCertIssuerSource(CertIssuerSource* cert_issuer_source) {
494 cert_issuer_sources_.push_back(cert_issuer_source);
495 }
496
GetNextPath(ParsedCertificateList * out_certs,CertificateTrust * out_last_cert_trust,const base::TimeTicks deadline,uint32_t * iteration_count,const uint32_t max_iteration_count)497 bool CertPathIter::GetNextPath(ParsedCertificateList* out_certs,
498 CertificateTrust* out_last_cert_trust,
499 const base::TimeTicks deadline,
500 uint32_t* iteration_count,
501 const uint32_t max_iteration_count) {
502 while (true) {
503 if (!deadline.is_null() && base::TimeTicks::Now() > deadline)
504 return false;
505
506 if (!next_issuer_.cert) {
507 if (cur_path_.Empty()) {
508 DVLOG(1) << "CertPathIter exhausted all paths...";
509 return false;
510 }
511
512 (*iteration_count)++;
513 if (max_iteration_count > 0 && *iteration_count > max_iteration_count) {
514 return false;
515 }
516
517 cur_path_.back()->GetNextIssuer(&next_issuer_);
518 if (!next_issuer_.cert) {
519 // TODO(mattm): should also include such paths in
520 // CertPathBuilder::Result, maybe with a flag to enable it. Or use a
521 // visitor pattern so the caller can decide what to do with any failed
522 // paths. No more issuers for current chain, go back up and see if there
523 // are any more for the previous cert.
524 DVLOG(1) << "CertPathIter backtracking...";
525 cur_path_.Pop();
526 // Continue exploring issuers of the previous path...
527 continue;
528 }
529 }
530
531 // If the cert is trusted but is the leaf, treat it as having unspecified
532 // trust. This may allow a successful path to be built to a different root
533 // (or to the same cert if it's self-signed).
534 switch (next_issuer_.trust.type) {
535 case CertificateTrustType::TRUSTED_ANCHOR:
536 case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
537 if (cur_path_.Empty()) {
538 DVLOG(1) << "Leaf is a trust anchor, considering as UNSPECIFIED";
539 next_issuer_.trust = CertificateTrust::ForUnspecified();
540 }
541 break;
542 case CertificateTrustType::DISTRUSTED:
543 case CertificateTrustType::UNSPECIFIED:
544 // No override necessary.
545 break;
546 }
547
548 switch (next_issuer_.trust.type) {
549 // If the trust for this issuer is "known" (either becuase it is
550 // distrusted, or because it is trusted) then stop building and return the
551 // path.
552 case CertificateTrustType::DISTRUSTED:
553 case CertificateTrustType::TRUSTED_ANCHOR:
554 case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS: {
555 // If the issuer has a known trust level, can stop building the path.
556 DVLOG(2) << "CertPathIter got anchor: "
557 << CertDebugString(next_issuer_.cert.get());
558 cur_path_.CopyPath(out_certs);
559 out_certs->push_back(std::move(next_issuer_.cert));
560 DVLOG(1) << "CertPathIter returning path:\n"
561 << PathDebugString(*out_certs);
562 *out_last_cert_trust = next_issuer_.trust;
563 next_issuer_ = IssuerEntry();
564 return true;
565 }
566 case CertificateTrustType::UNSPECIFIED: {
567 // Skip this cert if it is already in the chain.
568 if (cur_path_.IsPresent(next_issuer_.cert.get())) {
569 DVLOG(1) << "CertPathIter skipping dupe cert: "
570 << CertDebugString(next_issuer_.cert.get());
571 next_issuer_ = IssuerEntry();
572 continue;
573 }
574
575 cur_path_.Append(std::make_unique<CertIssuersIter>(
576 std::move(next_issuer_.cert), &cert_issuer_sources_, trust_store_,
577 debug_data_));
578 next_issuer_ = IssuerEntry();
579 DVLOG(1) << "CertPathIter cur_path_ =\n" << cur_path_.PathDebugString();
580 // Continue descending the tree.
581 continue;
582 }
583 }
584 }
585 }
586
587 CertPathBuilderResultPath::CertPathBuilderResultPath() = default;
588 CertPathBuilderResultPath::~CertPathBuilderResultPath() = default;
589
IsValid() const590 bool CertPathBuilderResultPath::IsValid() const {
591 return GetTrustedCert() && !errors.ContainsHighSeverityErrors();
592 }
593
594 CertPathBuilder::Result::Result() = default;
595 CertPathBuilder::Result::Result(Result&&) = default;
596 CertPathBuilder::Result::~Result() = default;
597 CertPathBuilder::Result& CertPathBuilder::Result::operator=(Result&&) = default;
598
HasValidPath() const599 bool CertPathBuilder::Result::HasValidPath() const {
600 return GetBestValidPath() != nullptr;
601 }
602
AnyPathContainsError(CertErrorId error_id) const603 bool CertPathBuilder::Result::AnyPathContainsError(CertErrorId error_id) const {
604 for (const auto& path : paths) {
605 if (path->errors.ContainsError(error_id))
606 return true;
607 }
608
609 return false;
610 }
611
GetBestValidPath() const612 const CertPathBuilderResultPath* CertPathBuilder::Result::GetBestValidPath()
613 const {
614 const CertPathBuilderResultPath* result_path = GetBestPathPossiblyInvalid();
615
616 if (result_path && result_path->IsValid())
617 return result_path;
618
619 return nullptr;
620 }
621
622 const CertPathBuilderResultPath*
GetBestPathPossiblyInvalid() const623 CertPathBuilder::Result::GetBestPathPossiblyInvalid() const {
624 DCHECK((paths.empty() && best_result_index == 0) ||
625 best_result_index < paths.size());
626
627 if (best_result_index >= paths.size())
628 return nullptr;
629
630 return paths[best_result_index].get();
631 }
632
CertPathBuilder(scoped_refptr<ParsedCertificate> cert,TrustStore * trust_store,CertPathBuilderDelegate * delegate,const der::GeneralizedTime & time,KeyPurpose key_purpose,InitialExplicitPolicy initial_explicit_policy,const std::set<der::Input> & user_initial_policy_set,InitialPolicyMappingInhibit initial_policy_mapping_inhibit,InitialAnyPolicyInhibit initial_any_policy_inhibit)633 CertPathBuilder::CertPathBuilder(
634 scoped_refptr<ParsedCertificate> cert,
635 TrustStore* trust_store,
636 CertPathBuilderDelegate* delegate,
637 const der::GeneralizedTime& time,
638 KeyPurpose key_purpose,
639 InitialExplicitPolicy initial_explicit_policy,
640 const std::set<der::Input>& user_initial_policy_set,
641 InitialPolicyMappingInhibit initial_policy_mapping_inhibit,
642 InitialAnyPolicyInhibit initial_any_policy_inhibit)
643 : cert_path_iter_(new CertPathIter(std::move(cert),
644 trust_store,
645 /*debug_data=*/&out_result_)),
646 delegate_(delegate),
647 time_(time),
648 key_purpose_(key_purpose),
649 initial_explicit_policy_(initial_explicit_policy),
650 user_initial_policy_set_(user_initial_policy_set),
651 initial_policy_mapping_inhibit_(initial_policy_mapping_inhibit),
652 initial_any_policy_inhibit_(initial_any_policy_inhibit) {
653 DCHECK(delegate);
654 // The TrustStore also implements the CertIssuerSource interface.
655 AddCertIssuerSource(trust_store);
656 }
657
658 CertPathBuilder::~CertPathBuilder() = default;
659
AddCertIssuerSource(CertIssuerSource * cert_issuer_source)660 void CertPathBuilder::AddCertIssuerSource(
661 CertIssuerSource* cert_issuer_source) {
662 cert_path_iter_->AddCertIssuerSource(cert_issuer_source);
663 }
664
SetIterationLimit(uint32_t limit)665 void CertPathBuilder::SetIterationLimit(uint32_t limit) {
666 max_iteration_count_ = limit;
667 }
668
SetDeadline(base::TimeTicks deadline)669 void CertPathBuilder::SetDeadline(base::TimeTicks deadline) {
670 deadline_ = deadline;
671 }
672
SetExploreAllPaths(bool explore_all_paths)673 void CertPathBuilder::SetExploreAllPaths(bool explore_all_paths) {
674 explore_all_paths_ = explore_all_paths;
675 }
676
Run()677 CertPathBuilder::Result CertPathBuilder::Run() {
678 uint32_t iteration_count = 0;
679
680 while (true) {
681 std::unique_ptr<CertPathBuilderResultPath> result_path =
682 std::make_unique<CertPathBuilderResultPath>();
683
684 if (!cert_path_iter_->GetNextPath(&result_path->certs,
685 &result_path->last_cert_trust, deadline_,
686 &iteration_count, max_iteration_count_)) {
687 // No more paths to check.
688 if (max_iteration_count_ > 0 && iteration_count > max_iteration_count_) {
689 out_result_.exceeded_iteration_limit = true;
690 }
691 if (!deadline_.is_null() && base::TimeTicks::Now() > deadline_) {
692 out_result_.exceeded_deadline = true;
693 }
694 RecordIterationCountHistogram(iteration_count);
695 return std::move(out_result_);
696 }
697
698 // Verify the entire certificate chain.
699 VerifyCertificateChain(
700 result_path->certs, result_path->last_cert_trust, delegate_, time_,
701 key_purpose_, initial_explicit_policy_, user_initial_policy_set_,
702 initial_policy_mapping_inhibit_, initial_any_policy_inhibit_,
703 &result_path->user_constrained_policy_set, &result_path->errors);
704
705 DVLOG(1) << "CertPathBuilder VerifyCertificateChain errors:\n"
706 << result_path->errors.ToDebugString(result_path->certs);
707
708 // Give the delegate a chance to add errors to the path.
709 delegate_->CheckPathAfterVerification(*this, result_path.get());
710
711 bool path_is_good = result_path->IsValid();
712
713 AddResultPath(std::move(result_path));
714
715 if (path_is_good && !explore_all_paths_) {
716 RecordIterationCountHistogram(iteration_count);
717 // Found a valid path, return immediately.
718 return std::move(out_result_);
719 }
720 // Path did not verify. Try more paths.
721 }
722 }
723
AddResultPath(std::unique_ptr<CertPathBuilderResultPath> result_path)724 void CertPathBuilder::AddResultPath(
725 std::unique_ptr<CertPathBuilderResultPath> result_path) {
726 // TODO(mattm): If there are no valid paths, set best_result_index based on
727 // number or severity of errors. If there are multiple valid paths, could set
728 // best_result_index based on prioritization (since due to AIA and such, the
729 // actual order results were discovered may not match the ideal).
730 if (result_path->IsValid() && !out_result_.HasValidPath())
731 out_result_.best_result_index = out_result_.paths.size();
732 out_result_.paths.push_back(std::move(result_path));
733 }
734
735 } // namespace net
736