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/merkle_tree_leaf.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::SignedCertificateTimestamp;
 using net::ct::SignedTreeHead;
 
+namespace {
+
+// TODO(eranm): HACK HACK HACK!
+// GetMerkleTreeLeaf has the logic for constructing the LogEntry so I'm
+// reusing it here, but the right approach is to have a GetLogEntry
+// function declared in signed_certificate_timestamp.h which will
+// fill in a LogEntry given the cert and the SCT origin.
+bool GetLogEntry(const net::X509Certificate* cert,
+                 const SignedCertificateTimestamp* sct,
+                 LogEntry* entry) {
+  MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
+    return false;
+
+  *entry = leaf.log_entry;
+  return true;
+}
+
+// TODO(eranm): HACK HACK HACK!
+// Need to change the CTVerifier interface to pass the scoped_refptr
+// to the SignedCertificateTimestamp so we can avoid copying it.

[Ryan Sleevi, 2016/07/18 23:38:01]

I don't understand why this hack is necessary?

Because our refcounting is implemented intrusively, rather than externally (e.g.
like shared_ptr is), you can always turn a raw pointer back into it's
scoped_refptr<>

I don't disagree that the API, if we're going to be holding references, should
be passing the scoped_refptr<> to make that clearer, but you can always do

entry.sct = sct

and It Just Works

[Eran Messeri, 2016/09/21 21:10:43]

This is now obsolete.

+void ManuallyCopySignedCertificateTimestamp(
+    const SignedCertificateTimestamp* sct,
+    scoped_refptr<SignedCertificateTimestamp> out) {
+  out->version = sct->version;
+  out->log_id = sct->log_id;
+  out->timestamp = sct->timestamp;
+  out->extensions = sct->extensions;
+  out->signature = sct->signature;
+  out->origin = sct->origin;
+  out->log_description = sct->log_description;
+}
+}
+
 namespace certificate_transparency {
 
+struct SingleTreeTracker::EntryToAudit {

[Ryan Sleevi, 2016/07/18 23:38:01]

Documentation :)

[Eran Messeri, 2016/09/21 21:10:43]

Done.

+  scoped_refptr<SignedCertificateTimestamp> sct;
+  LogEntry log_entry;
+};
+
 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);
 
+  EntryToAudit entry;
+  if (!GetLogEntry(cert, sct, &entry.log_entry))
+    return;
+  entry.sct = new SignedCertificateTimestamp();
+  ManuallyCopySignedCertificateTimestamp(sct, entry.sct);
+
   // SCT was previously observed, so its status should not be changed.
-  if (entries_status_.find(sct->timestamp) != entries_status_.end())
+  if (EntryAlreadyEncountered(entry))
     return;
 
+  SCTInclusionStatus state = SCT_NOT_OBSERVED;
+  const base::TimeDelta kMaximumMergeDelay = base::TimeDelta::FromHours(24);

[Ryan Sleevi, 2016/07/18 23:38:01]

you can make this static const (TimeDelta is constexpr and thus doesn't add
static initializers)

[Eran Messeri, 2016/09/21 21:10:43]

Done.

   // 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.

[Ryan Sleevi, 2016/07/18 23:38:01]

Why? Is this just a proxy metric for something else? What would this data be
used to inform?

If you're going to keep this TODO, at least explain more of the context for why
this data might be useful, otherwise this feels a bit like Fermat's Last Theorem
:)

[Eran Messeri, 2016/09/21 21:10:43]

Obsolete - I've simply added the UMA logging.
This will inform us:
* How often can SCTs be checked immediately (i.e. how often SCTs are so fresh
that clients see them before they see an STH covering them. If that is very rare
we could make a case for requiring an inclusion proof together with the SCT when
we implement 6962-bis, which supports that).
* How many clients don't have valid STHs at all.
* If the queue size we choose for the pending entries is enough (i.e. how often
SCTs are dropped because the pending entries queue is full).

+    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(entry), state));
 }
 
 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(

[Ryan Sleevi, 2016/07/18 23:38:01]

if |observed_entries_| is sorted on timestamp, shouldn't this be
std::lower_bound() ? 

[Eran Messeri, 2016/09/21 21:10:43]

What I'd like to do is process entries whose timestamp + MMD > sth.timestamp.
Since |pending_entries_| is sorted on timestamp, I have to find the first entry
that's in PENDING_NEWER_STH state and the last entry whose timestamp + MMD <
sth.timestamp.

So I should use find_if to find the first entry that's in a pending state and
lower_bound to find the entry I should stop at.

+      observed_entries_.begin(), observed_entries_.end(),
+      [&sth](const std::pair<const EntryToAudit&, const SCTInclusionStatus&>
+                 entry) { return entry.first.sct->timestamp > sth.timestamp; });
+  for (auto it = observed_entries_.begin(); it != first_entry_not_included;
+       ++it) {
+    it->second = 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);
+  EntryToAudit entry;
+  if (!GetLogEntry(cert, sct, &entry.log_entry))
+    return SCT_NOT_OBSERVED;
+  entry.sct = new SignedCertificateTimestamp();
+  ManuallyCopySignedCertificateTimestamp(sct, entry.sct);
 
-  return it == entries_status_.end() ? SCT_NOT_OBSERVED : it->second;
+  auto entry_iterator = observed_entries_.find(entry);

[Ryan Sleevi, 2016/07/18 23:38:01]

Do you actually need to reconstitute the LogEntry from the SCT? Couldn't you
just find for an equality check on the SCT?

[Eran Messeri, 2016/09/21 21:10:43]

Obsolete - The SCT is no longer stored, only the hash.

+  if (entry_iterator == observed_entries_.end())
+    return SCT_NOT_OBSERVED;
+
+  return entry_iterator->second;
+}
+
+bool SingleTreeTracker::OrderByTimestamp::operator()(
+    const EntryToAudit& lhs,
+    const EntryToAudit& rhs) const {
+  if (lhs.sct->timestamp != rhs.sct->timestamp)
+    return lhs.sct->timestamp < rhs.sct->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::EntryAlreadyEncountered(const EntryToAudit& entry) {
+  return observed_entries_.find(entry) != observed_entries_.end();

[Ryan Sleevi, 2016/07/18 23:38:01]

This doesn't seem like it should be a member function (especially since you're
forcing public exposure of it)

[Eran Messeri, 2016/09/21 21:10:43]

Obsolete - removed.

 }
 
 }  // namespace certificate_transparency