Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.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 "components/certificate_transparency/single_tree_tracker.h"
 
+#include <algorithm>
+#include <iterator>
 #include <utility>
 
 #include "net/cert/ct_log_verifier.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/x509_certificate.h"
 
+using net::ct::LogEntry;
+using net::ct::MerkleTreeLeaf;
 using net::ct::SignedTreeHead;
 
 namespace certificate_transparency {
 
 SingleTreeTracker::SingleTreeTracker(
     scoped_refptr<const net::CTLogVerifier> ct_log)
     : ct_log_(std::move(ct_log)) {}
 
 SingleTreeTracker::~SingleTreeTracker() {}
 
 void SingleTreeTracker::OnSCTVerified(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
   DCHECK_EQ(ct_log_->key_id(), sct->log_id);
 
-  // SCT was previously observed, so its status should not be changed.
-  if (entries_status_.find(sct->timestamp) != entries_status_.end())
+  MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
     return;
 
+  // SCT was previously observed, so its status should not be changed.
+  if (LeafAlreadyEncountered(leaf))
+    return;
+
+  SCTInclusionStatus state = SCT_NOT_OBSERVED;
+  const base::TimeDelta kMaximumMergeDelay = base::TimeDelta::FromHours(24);
   // If there isn't a valid STH or the STH is not fresh enough to check
   // inclusion against, store the SCT for future checking and return.
   if (verified_sth_.timestamp.is_null() ||
-      (verified_sth_.timestamp <
-       (sct->timestamp + base::TimeDelta::FromHours(24)))) {
+      (verified_sth_.timestamp < (sct->timestamp + kMaximumMergeDelay))) {
     // TODO(eranm): UMA - how often SCTs have to wait for a newer STH for
     // inclusion check.
-    entries_status_.insert(
-        std::make_pair(sct->timestamp, SCT_PENDING_NEWER_STH));
-    return;
+    state = SCT_PENDING_NEWER_STH;
+  } else {
+    // TODO(eranm): UMA - how often inclusion can be checked immediately.
+    state = SCT_PENDING_INCLUSION_CHECK;
   }
 
-  // TODO(eranm): Check inclusion here.
-  // TODO(eranm): UMA - how often inclusion can be checked immediately.
-  entries_status_.insert(
-      std::make_pair(sct->timestamp, SCT_PENDING_INCLUSION_CHECK));
+  // TODO(eranm): Check inclusion here, see https://crbug.com/624894
+  observed_entries_.insert(
+      std::make_pair(std::move(leaf), LeafState(state, base::Time::Now())));
 }
 
 void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& sth) {
   DCHECK_EQ(ct_log_->key_id(), sth.log_id);
 
   if (!ct_log_->VerifySignedTreeHead(sth)) {
     // Sanity check the STH; the caller should have done this
     // already, but being paranoid here.
     // NOTE(eranm): Right now there's no way to get rid of this check here
     // as this is the first object in the chain that has an instance of
     // a CTLogVerifier to verify the STH.
     return;
   }
 
   // In order to avoid updating |verified_sth_| to an older STH in case
   // an older STH is observed, check that either the observed STH is for
   // a larger tree size or that it is for the same tree size but has
   // a newer timestamp.
   const bool sths_for_same_tree = verified_sth_.tree_size == sth.tree_size;
   const bool received_sth_is_for_larger_tree =
       (verified_sth_.tree_size > sth.tree_size);
   const bool received_sth_is_newer = (sth.timestamp > verified_sth_.timestamp);
 
   if (verified_sth_.timestamp.is_null() || received_sth_is_for_larger_tree ||
       (sths_for_same_tree && received_sth_is_newer)) {
     verified_sth_ = sth;
   }
 
   // Find out which SCTs can now be checked for inclusion.
-  // TODO(eranm): Keep two maps of MerkleTreeLeaf instances, one for leaves
-  // pending inclusion checks and one for leaves pending a new STH.
-  // The comparison function between MerkleTreeLeaf instances should use the
-  // timestamp to determine sorting order, so that bulk moving from one
-  // map to the other can happen.
-  auto entry = entries_status_.begin();
-  while (entry != entries_status_.end() &&
-         entry->first < verified_sth_.timestamp) {
-    entry->second = SCT_PENDING_INCLUSION_CHECK;
-    ++entry;
-    // TODO(eranm): Check inclusion here.
+  auto first_entry_not_included = std::find_if(
+      observed_entries_.begin(), observed_entries_.end(),
+      [&sth](const std::pair<const MerkleTreeLeaf&, const LeafState&> entry) {
+        return entry.first.timestamp > sth.timestamp;
+      });
+  for (auto it = observed_entries_.begin(); it != first_entry_not_included;
+       ++it) {
+    it->second.SetState(SCT_PENDING_INCLUSION_CHECK);
   }
+
+  // TODO(eranm): Check inclusion here of entries that can now be checked.
+  // See https://crbug.com/624894
 }
 
 SingleTreeTracker::SCTInclusionStatus
 SingleTreeTracker::GetLogEntryInclusionStatus(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
-  auto it = entries_status_.find(sct->timestamp);
+  MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
+    return SCT_NOT_OBSERVED;
 
-  return it == entries_status_.end() ? SCT_NOT_OBSERVED : it->second;
+  auto entry_iterator = observed_entries_.find(leaf);
+  if (entry_iterator == observed_entries_.end())
+    return SCT_NOT_OBSERVED;
+
+  return entry_iterator->second.State();
+}
+
+SingleTreeTracker::LeafState::LeafState(SCTInclusionStatus status,
+                                        const base::Time& observed_at)
+    : observed_at_(observed_at), state_(status) {}
+
+SingleTreeTracker::LeafState::LeafState(const LeafState& other) = default;
+
+SingleTreeTracker::LeafState::LeafState(LeafState&&) = default;
+
+SingleTreeTracker::LeafState::~LeafState() = default;
+
+void SingleTreeTracker::LeafState::SetLeafIndex(uint64_t index) {
+  // The leaf index may be set only once. Doing so more than once indicates
+  // a programming error where the index is fetched more than once for a given
+  // leaf.
+  DCHECK(!leaf_index_);
+  leaf_index_ = index;
+}
+
+bool SingleTreeTracker::LeafState::HasLeafIndex() const {
+  return bool(leaf_index_);
+}
+
+uint64_t SingleTreeTracker::LeafState::GetLeafIndex() const {
+  DCHECK(leaf_index_);
+  return leaf_index_.value();
+}
+
+const base::Time& SingleTreeTracker::LeafState::ObservedAt() const {
+  return observed_at_;
+}
+
+SingleTreeTracker::SCTInclusionStatus SingleTreeTracker::LeafState::State()
+    const {
+  return state_;
+}
+
+void SingleTreeTracker::LeafState::SetState(
+    SingleTreeTracker::SCTInclusionStatus state) {
+  DCHECK_NE(state, SCT_NOT_OBSERVED);
+  DCHECK_NE(state, state_);
+  state_ = state;
+}
+
+bool SingleTreeTracker::OrderByTimestamp::operator()(
+    const MerkleTreeLeaf& lhs,
+    const MerkleTreeLeaf& rhs) const {
+  // This comparator should only used for containers where leaves from
+  // different logs are not mixed.
+  DCHECK_EQ(lhs.log_id, rhs.log_id);
+
+  if (lhs.timestamp != rhs.timestamp)
+    return lhs.timestamp < rhs.timestamp;
+
+  const LogEntry& lhs_entry = lhs.log_entry;
+  const LogEntry& rhs_entry = rhs.log_entry;
+  if (lhs_entry.type != rhs_entry.type)
+    return lhs_entry.type < rhs_entry.type;
+
+  if (lhs_entry.type == LogEntry::LOG_ENTRY_TYPE_X509)
+    return lhs_entry.leaf_certificate < rhs_entry.leaf_certificate;
+
+  // lhs_entry.type == LOG_ENTRY_TYPE_PRECERT
+  return lhs_entry.tbs_certificate < rhs_entry.tbs_certificate &&
+         net::SHA256HashValueLessThan()(lhs_entry.issuer_key_hash,
+                                        rhs_entry.issuer_key_hash);
+}
+
+bool SingleTreeTracker::LeafAlreadyEncountered(const MerkleTreeLeaf& leaf) {
+  return observed_entries_.find(leaf) != observed_entries_.end();
 }
 
 }  // namespace certificate_transparency