Certificate Transparency: Code for unpacking EV cert hashes whitelist

net/cert/ct_ev_whitelist.cc

Index: net/cert/ct_ev_whitelist.cc
diff --git a/net/cert/ct_ev_whitelist.cc b/net/cert/ct_ev_whitelist.cc
new file mode 100644
index 0000000000000000000000000000000000000000..7264549452f7090dc05e73885c60d895b82aa3b7
--- /dev/null
+++ b/net/cert/ct_ev_whitelist.cc
@@ -0,0 +1,214 @@
+// Copyright 2014 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/ct_ev_whitelist.h"
+
+#include <set>
+
+#include "base/big_endian.h"
+#include "base/file_util.h"
+#include "base/lazy_instance.h"

[Ryan Sleevi, 2014/09/11 23:44:38]

Unused?

[Eran Messeri, 2014/10/01 16:08:35]

Done.

+#include "base/logging.h"
+#include "net/ssl/ssl_config_service.h"

[Ryan Sleevi, 2014/09/11 23:44:38]

Layering violation to depend on net/ssl from net/cert

(//net/cert should only pickup //net/base, //crypto, and //base)

[Eran Messeri, 2014/10/01 16:08:35]

Done.

+
+namespace net {
+
+namespace ct {
+
+namespace {
+const uint8_t kCertHashLengthBits = 64;     // 8 bytes
+const uint64_t kGolombMParameterBits = 47;  // 2^47
+}  // namespace
+
+namespace internal {
+
+BitStreamReader::BitStreamReader(const base::StringPiece& source)
+    : source_(source), current_byte_(0), current_bit_(7) {
+}
+
+bool BitStreamReader::ReadUnaryEncoding(uint64_t* out) {
+  uint64_t res = 0;
+  if (BitsLeft() == 0)
+    return false;
+
+  while ((BitsLeft() > 0) && ReadBit())
+    res++;
+
+  *out = res;
+  return true;
+}
+
+bool BitStreamReader::ReadBits(uint8_t num_bits, uint64_t* out) {
+  if (num_bits > 64)
+    return false;
+
+  if (BitsLeft() < num_bits)
+    return false;
+
+  uint64_t res = 0;
+  for (uint8_t i = 0; i < num_bits; ++i)
+    res |= (static_cast<uint64_t>(ReadBit()) << (num_bits - (i + 1)));
+
+  *out = res;
+  return true;
+}
+
+uint64_t BitStreamReader::BitsLeft() const {
+  if (current_byte_ == source_.length())
+    return 0;
+  return (source_.length() - (current_byte_ + 1)) * 8 + current_bit_ + 1;
+}
+
+uint8_t BitStreamReader::ReadBit() {
+  DCHECK_GT(BitsLeft(), 0u);
+  DCHECK(current_bit_ < 8 && current_bit_ >= 0);
+  uint8_t res =
+      (source_.data()[current_byte_] & (1 << current_bit_)) >> current_bit_;
+  current_bit_--;
+  if (current_bit_ < 0) {
+    current_byte_++;
+    current_bit_ = 7;
+  }
+
+  return res;
+}
+
+}  // namespace internal
+
+/*
+void SetEVWhitelistFromFile(const base::FilePath& compressed_whitelist_file) {
+  VLOG(1) << "Setting EV whitelist from file: "
+          << compressed_whitelist_file.value();
+  std::string compressed_list;
+  if (!base::ReadFileToString(compressed_whitelist_file, &compressed_list)) {
+    VLOG(1) << "Failed reading from " << compressed_whitelist_file.value();
+    return;
+  }
+
+  std::set<std::string> uncompressed_list;
+  if (!internal::UncompressEVWhitelist(compressed_list, &uncompressed_list)) {
+    VLOG(1) << "Failed uncompressing.";
+    return;
+  }
+  VLOG(1) << "Uncompressing succeeded, hashes: " << uncompressed_list.size();
+
+  internal::SetEVWhitelistData(uncompressed_list);
+}
+
+bool ContainsCertificateHash(const std::string& certificate_hash) {
+  const std::set<std::string>& current_ev_whitelist =
+      g_current_ev_whitelist.Get();
+  return current_ev_whitelist.find(certificate_hash) !=
+         current_ev_whitelist.end();
+}
+
+bool IsValid() {
+  return !g_current_ev_whitelist.Get().empty();
+}
+*/
+
+bool EVCertsWhitelist::UncompressEVWhitelist(
+    const std::string& compressed_whitelist,
+    std::set<std::string>* uncompressed_list) {
+  internal::BitStreamReader reader(base::StringPiece(
+      compressed_whitelist.data(), compressed_whitelist.size()));
+  std::set<std::string> result;
+
+  VLOG(1) << "Uncompressing EV whitelist of size "
+          << compressed_whitelist.size();
+  uint64_t curr_hash(0);
+  if (!reader.ReadBits(kCertHashLengthBits, &curr_hash)) {
+    VLOG(1) << "Failed reading first hash.";
+    return false;
+  }
+  char hash_bytes[8];
+  base::WriteBigEndian(hash_bytes, curr_hash);
+  result.insert(std::string(hash_bytes, 8));
+  static const uint64_t M = static_cast<uint64_t>(1) << kGolombMParameterBits;
+
+  while (reader.BitsLeft() > kGolombMParameterBits) {
+    uint64_t read_prefix = 0;
+    if (!reader.ReadUnaryEncoding(&read_prefix)) {
+      VLOG(1) << "Failed reading unary-encoded prefix.";
+      return false;
+    }
+
+    uint64_t r = 0;
+    if (!reader.ReadBits(kGolombMParameterBits, &r)) {
+      VLOG(1) << "Failed reading " << kGolombMParameterBits << " bits.";
+      return false;
+    }
+
+    uint64_t curr_diff = read_prefix * M + r;
+    curr_hash += curr_diff;
+
+    base::WriteBigEndian(hash_bytes, curr_hash);
+    result.insert(std::string(hash_bytes, 8));
+  }
+
+  uncompressed_list->swap(result);
+  return true;
+}
+
+class SetBackedEVCertsWhitelist : public EVCertsWhitelist {
+ public:
+  SetBackedEVCertsWhitelist() : is_whitelist_valid_(false) {}
+
+  virtual bool ContainsCertificateHash(
+      const std::string& certificate_hash) const OVERRIDE {
+    return whitelist_.find(certificate_hash) != whitelist_.end();
+  }
+
+  virtual bool IsValid() const OVERRIDE { return is_whitelist_valid_; }
+
+  // Sets the EV whitelist from a compressed string, if it is valid.
+  virtual bool Update(const std::string& compressed_whitelist) OVERRIDE {
+    std::set<std::string> new_whitelist;
+    if (!UncompressEVWhitelist(compressed_whitelist, &new_whitelist))
+      return false;
+
+    whitelist_.swap(new_whitelist);
+    is_whitelist_valid_ = true;
+    return true;
+  }
+
+ private:
+  virtual ~SetBackedEVCertsWhitelist() {}
+
+  bool is_whitelist_valid_;
+  std::set<std::string> whitelist_;

[Ryan Sleevi, 2014/09/11 23:44:38]

This is a lot of overhead for a large number of entries.

Are there data structures we can use to optimize this? For example, could the
uncompressed whitelist be a sorted continuous buffer that you then used bsearch
over?

[Eran Messeri, 2014/10/01 16:08:35]

There'll be ~600K entries in this set. I will benchmark memory overhead vs.
added runtime of bsearching over an array so we'll have data to justify one over
the other.

+};
+
+void SetEVWhitelistFromFile(const base::FilePath& compressed_whitelist_file) {
+  VLOG(1) << "Setting EV whitelist from file: "
+          << compressed_whitelist_file.value();
+  std::string compressed_list;
+  if (!base::ReadFileToString(compressed_whitelist_file, &compressed_list)) {

[Ryan Sleevi, 2014/09/11 23:44:38]

So, this method is bad because it does disk IO on whatever thread it's called
in, and then calls the SSLConfigService method (which should only ever be on the
IO thread)

So, the way I read it, you're blocking the IO thread. That's Very Very Bad.

Structurally, like I mentioned in the header, I think the "Parse a file and
build a concrete whitelist" is something that lives outside of //net in your
higher layer. There, you use the BrowserThread aspects, as needed, to
deserialize the file (on a worker thread), parse it (worker thread?), then send
the parsed result back to the IO thread to update this global. All of that lives
outside of //net.

[Eran Messeri, 2014/10/01 16:08:35]

Done: This method is called on a blocking pool task (see
chrome/browser/component_updater/ev_whitelist_component_installer.cc), so IIUC
it is not blocking anything.
I've added another task dispatching that does the actual setting on the
SSLConfigService on the IO thread.

+    VLOG(1) << "Failed reading from " << compressed_whitelist_file.value();
+    return;
+  }
+
+  scoped_refptr<EVCertsWhitelist> new_whitelist(
+      new SetBackedEVCertsWhitelist());
+  if (!new_whitelist->Update(compressed_list)) {
+    VLOG(1) << "Failed uncompressing.";
+    return;
+  }
+  VLOG(1) << "Uncompressing succeeded.";
+
+  SSLConfigService::SetEVCertsWhitelist(new_whitelist);
+}
+
+namespace internal {
+
+// For testing purposes
+EVCertsWhitelist* GetEmptyEVCertsWhitelist() {
+  return new SetBackedEVCertsWhitelist();
+}
+
+}  // namespace
+
+}  // namespace ct
+
+}  // namespace net