Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.cc

Index: components/certificate_transparency/single_tree_tracker.cc
diff --git a/components/certificate_transparency/single_tree_tracker.cc b/components/certificate_transparency/single_tree_tracker.cc
index 7946208ca753303a7589260e7a60fd34a58bb5e0..bd43e836fc8f629779213553865a3e7db136ccac 100644
--- a/components/certificate_transparency/single_tree_tracker.cc
+++ b/components/certificate_transparency/single_tree_tracker.cc
@@ -4,16 +4,61 @@
 
 #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)) {}
@@ -25,26 +70,32 @@ void SingleTreeTracker::OnSCTVerified(
     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) {
@@ -74,27 +125,58 @@ void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& 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);
+
+  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);
+}
 
-  return it == entries_status_.end() ? SCT_NOT_OBSERVED : it->second;
+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