Adds a VerifyAuditProof method to CTLogVerifier

net/cert/ct_log_verifier_unittest.cc

 // Copyright 2013 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_log_verifier.h"
 
 #include <stdint.h>
 
+#include <map>
 #include <memory>
 #include <string>
+#include <utility>
+#include <vector>
 
+#include "base/macros.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/time/time.h"
 #include "crypto/secure_hash.h"
 #include "net/base/hash_value.h"
 #include "net/cert/ct_log_verifier_util.h"
+#include "net/cert/merkle_audit_proof.h"
 #include "net/cert/merkle_consistency_proof.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/signed_tree_head.h"
 #include "net/test/ct_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace net {
 
 namespace {
 
+// Enables the node hash cache used to accelerate some of the tests.
+// The cache reduces the duration of some tests by at least 50%, in exchange for
+// significantly higher memory usage.
+const bool kIsHashCacheEnabled = true;
+
 // Calculate the power of two nearest to, but less than, |n|.
 // |n| must be at least 2.
 uint64_t CalculateNearestPowerOfTwo(uint64_t n) {
   DCHECK_GT(n, 1u);
 
   uint64_t ret = UINT64_C(1) << 63;
   while (ret >= n)
     ret >>= 1;
 
   return ret;
 }
 
 // The following structures, TestVector and ProofTestVector are used for
 // definining test proofs later on.
 
 // A single hash node.
 struct TestVector {
-  const char* const str;
-  size_t length_bytes;
+  const char* const str;  // hex string
+  size_t length_bytes;    // number of bytes represented by |str|
 };
 
 // A single consistency proof. Contains the old and new tree sizes
 // (snapshot1 and snapshot2), the length of the proof (proof_length) and
 // at most 3 proof nodes (all test proofs will be for a tree of size 8).
 struct ProofTestVector {
   uint64_t snapshot1;
   uint64_t snapshot2;
   size_t proof_length;
   TestVector proof[3];
 };
 
 // All test data replicated from
 // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc
 // A hash of the empty string.
 const TestVector kSHA256EmptyTreeHash = {
     "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32};
 
-// Node hashes for a sample tree of size 8 (each element in this array is
-// a node hash, not leaf data; order represents order of the nodes in the tree).
+// Hashes of the leaf data for the sample tree (8 leaves).
+const TestVector kSHA256LeafHashes[8] = {
+    {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
+    {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
+    {"0298d122906dcfc10892cb53a73992fc5b9f493ea4c9badb27b791b4127a7fe7", 32},
+    {"07506a85fd9dd2f120eb694f86011e5bb4662e5c415a62917033d4a9624487e7", 32},
+    {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
+    {"4271a26be0d8a84f0bd54c8c302e7cb3a3b5d1fa6780a40bcce2873477dab658", 32},
+    {"b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f", 32},
+    {"46f6ffadd3d06a09ff3c5860d2755c8b9819db7df44251788c7d8e3180de8eb1", 32},
+};
+
+// Incremental roots from building the sample tree of size 8 leaf-by-leaf.
+// The first entry is the root at size 0, the last is the root at size 8.
 const TestVector kSHA256Roots[8] = {
     {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
     {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32},
     {"aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 32},
     {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32},
     {"4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 32},
     {"76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 32},
     {"ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32},
     {"5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32}};
 
-// A collection of consistency proofs between various sub-trees of the tree
-// defined by |kSHA256Roots|.
+// A collection of consistency proofs between various nodes of the sample tree.
 const ProofTestVector kSHA256Proofs[4] = {
     // Empty consistency proof between trees of the same size (1).
     {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}},
     // Consistency proof between tree of size 1 and tree of size 8, with 3
     // nodes in the proof.
     {1,
      8,
      3,
      {{"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
       {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
@@ skipping 10 matching lines @@
        32}}},
     // Consistency proof between tree of size 2 and tree of size 5, with 2
     // nodes in the proof.
     {2,
      5,
      2,
      {{"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
       {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
       {"", 0}}}};
 
+// A single audit proof. Contains the leaf index (leaf), tree size (snapshot),
+// the length of the proof (proof_length) and at most 3 proof nodes (all test
+// proofs will be for a tree of size 8).
+struct PathTestVector {
+  int leaf;
+  int snapshot;
+  int path_length;
+  TestVector path[3];
+};
+
+// A collection of audit proofs for various leaves and sub-trees of the tree
+// defined by |kSHA256Roots|.
+const PathTestVector kSHA256Paths[6] = {
+    {0, 0, 0, {{"", 0}, {"", 0}, {"", 0}}},
+    {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}},
+    {1,
+     8,
+     3,
+     {{"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
+      {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
+      {"6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4",
+       32}}},
+    {6,
+     8,
+     3,
+     {{"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
+      {"ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32},
+      {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
+       32}}},
+    {3,
+     3,
+     1,
+     {{"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32},
+      {"", 0},
+      {"", 0}}},
+    {2,
+     5,
+     3,
+     {{"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
+      {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
+      {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
+       32}}}};
+
 // Decodes a hexadecimal string into the binary data it represents.
 std::string HexToBytes(const char* hex_data, size_t hex_data_length) {
   std::vector<uint8_t> output;
   std::string result;
   std::string hex_data_input(hex_data, hex_data_length);
   if (base::HexStringToBytes(hex_data, &output))
     result.assign(reinterpret_cast<const char*>(&output[0]), output.size());
   return result;
 }
 
+std::string HexToBytes(const TestVector& x) {
+  std::string bytes = HexToBytes(x.str, x.length_bytes * 2);
+  CHECK_EQ(x.length_bytes, bytes.size());
+  return bytes;
+}
+
 std::string GetEmptyTreeHash() {
-  return HexToBytes(kSHA256EmptyTreeHash.str,
-                    kSHA256EmptyTreeHash.length_bytes);
+  return HexToBytes(kSHA256EmptyTreeHash);
 }
 
 // Creates a ct::MerkleConsistencyProof and returns the result of
 // calling log->VerifyConsistencyProof with that proof and snapshots.
 bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log,
                             uint64_t old_tree_size,
                             const std::string& old_tree_root,
                             uint64_t new_tree_size,
                             const std::string& new_tree_root,
                             const std::vector<std::string>& proof) {
   return log->VerifyConsistencyProof(
       ct::MerkleConsistencyProof(log->key_id(), proof, old_tree_size,
                                  new_tree_size),
       old_tree_root, new_tree_root);
 }
 
+bool VerifyAuditProof(scoped_refptr<const CTLogVerifier> log,
+                      uint64_t leaf,
+                      uint64_t tree_size,
+                      const std::vector<std::string>& proof,
+                      const std::string& tree_root,
+                      const std::string& leaf_hash) {
+  // Test vectors use a 1-based leaf index, but our code uses a 0-based index.
+  if (leaf == 0)
+    return false;
+  return log->VerifyAuditProof(ct::MerkleAuditProof(leaf - 1, tree_size, proof),
+                               tree_root, leaf_hash);
+}
+
 class CTLogVerifierTest : public ::testing::Test {
  public:
   CTLogVerifierTest() {}
 
   void SetUp() override {
     log_ = CTLogVerifier::Create(ct::GetTestPublicKey(), "testlog",
                                  "https://ct.example.com", "ct.example.com");
 
     ASSERT_TRUE(log_);
     ASSERT_EQ(ct::GetTestPublicKeyId(), log_->key_id());
     ASSERT_EQ("ct.example.com", log_->dns_domain());
   }
 
+  // Given an audit proof for a leaf in the tree, asserts that it verifies and
+  // no other combination of leaves, snapshots and proof nodes verifies.
+  void VerifierCheck(int leaf,
+                     int tree_size,
+                     const std::vector<std::string>& path,
+                     const std::string& root,
+                     const std::string& leaf_hash) {
+    // Verify the original path.
+    EXPECT_TRUE(VerifyAuditProof(log_, leaf, tree_size, path, root, leaf_hash));
+
+    // Wrong leaf index.
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf - 1, tree_size, path, root, leaf_hash));
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf + 1, tree_size, path, root, leaf_hash));
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf ^ 2, tree_size, path, root, leaf_hash));
+
+    // Wrong tree height.
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size * 2, path, root, leaf_hash));
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size / 2, path, root, leaf_hash));
+
+    // Wrong root.
+    EXPECT_FALSE(VerifyAuditProof(log_, leaf, tree_size, path,
+                                  HexToBytes(kSHA256EmptyTreeHash), leaf_hash));
+
+    // Wrong paths.
+    std::vector<std::string> wrong_path;
+
+    // Modify a single element on the path.
+    for (size_t j = 0; j < path.size(); ++j) {
+      wrong_path = path;
+      wrong_path[j] = HexToBytes(kSHA256EmptyTreeHash);
+      EXPECT_FALSE(
+          VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    }
+
+    // Add garbage at the end of the path.
+    wrong_path = path;
+    wrong_path.push_back(std::string());
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    wrong_path.pop_back();
+
+    wrong_path.push_back(root);
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    wrong_path.pop_back();
+
+    // Remove a node from the end.
+    if (!wrong_path.empty()) {
+      wrong_path.pop_back();
+      EXPECT_FALSE(
+          VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    }
+
+    // Add garbage in the beginning of the path.
+    wrong_path.clear();
+    wrong_path.push_back(std::string());
+    wrong_path.insert(wrong_path.end(), path.begin(), path.end());
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+
+    wrong_path[0] = root;
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+  }
+
   // Given a consistency proof between two snapshots of the tree, asserts that
   // it verifies and no other combination of snapshots and proof nodes verifies.
   void VerifierConsistencyCheck(int snapshot1,
                                 int snapshot2,
                                 const std::string& root1,
                                 const std::string& root2,
                                 const std::vector<std::string>& proof) {
     // Verify the original consistency proof.
     EXPECT_TRUE(
         VerifyConsistencyProof(log_, snapshot1, root1, snapshot2, root2, proof))
@@ skipping 212 matching lines @@
   EXPECT_FALSE(VerifyConsistencyProof(log_, 1, empty_tree_hash, 1,
                                       empty_tree_hash, proof));
 }
 
 TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) {
   std::vector<std::string> proof;
   std::string root1, root2;
 
   // Known good proofs.
   for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) {
+    SCOPED_TRACE(i);
     proof.clear();
     for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) {
       const TestVector& v = kSHA256Proofs[i].proof[j];
-      proof.push_back(HexToBytes(v.str, v.length_bytes));
+      proof.push_back(HexToBytes(v));
     }
     const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
     const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
     const TestVector& old_root = kSHA256Roots[snapshot1 - 1];
     const TestVector& new_root = kSHA256Roots[snapshot2 - 1];
-    VerifierConsistencyCheck(
-        snapshot1, snapshot2, HexToBytes(old_root.str, old_root.length_bytes),
-        HexToBytes(new_root.str, new_root.length_bytes), proof);
+    VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root),
+                             HexToBytes(new_root), proof);
   }
 }
 
 const char kLeafPrefix[] = {'\x00'};
 
 // Reference implementation of RFC6962.
 // This allows generation of arbitrary-sized Merkle trees and consistency
 // proofs between them for testing the consistency proof validation
 // code.
 class TreeHasher {
  public:
-  static std::string HashEmpty() {
-    return HexToBytes(kSHA256EmptyTreeHash.str,
-                      kSHA256EmptyTreeHash.length_bytes);
-  }
+  static std::string HashEmpty() { return HexToBytes(kSHA256EmptyTreeHash); }
 
   static std::string HashLeaf(const std::string& leaf) {
     SHA256HashValue sha256;
     memset(sha256.data, 0, sizeof(sha256.data));
 
     std::unique_ptr<crypto::SecureHash> hash(
         crypto::SecureHash::Create(crypto::SecureHash::SHA256));
     hash->Update(kLeafPrefix, 1);
     hash->Update(leaf.data(), leaf.size());
     hash->Finish(sha256.data, sizeof(sha256.data));
 
     return std::string(reinterpret_cast<const char*>(sha256.data),
                        sizeof(sha256.data));
   }
 };
 
 // Reference implementation of Merkle hash, for cross-checking.
 // Recursively calculates the hash of the root given the leaf data
 // specified in |inputs|.
 std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) {
-  if (!input_size)
-    return TreeHasher::HashEmpty();
+  // Memoize function - this requires 34 bytes of memory per unique pair of
+  // |inputs| and |input_size|, plus std::map and std::string overhead.
+  // This results in a ~50% reduction in time required to run the
+  // *FromReferenceGenerator tests.
+  static std::map<std::pair<std::string*, uint64_t>, std::string> cache;
+  if (kIsHashCacheEnabled) {
+    auto iter = cache.find(std::make_pair(inputs, input_size));
+    if (iter != cache.end())
+      return iter->second;
+  }
+
+  std::string hash;
+  if (!input_size) {
+    hash = TreeHasher::HashEmpty();
+  } else if (input_size == 1) {
+    hash = TreeHasher::HashLeaf(inputs[0]);
+  } else {
+    const uint64_t split = CalculateNearestPowerOfTwo(input_size);
+
+    hash = ct::internal::HashNodes(
+        ReferenceMerkleTreeHash(&inputs[0], split),
+        ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  }
+
+  if (kIsHashCacheEnabled)
+    cache[std::make_pair(inputs, input_size)] = hash;
+
+  return hash;
+}
+
+// Reference implementation of Merkle paths. Path from leaf to root,
+// excluding the leaf and root themselves. Returns an audit proof for the tree
+// leaf with index |leaf| (1-based). The tree is designated by |inputs|.
+std::vector<std::string> ReferenceMerklePath(std::string* inputs,
+                                             uint64_t input_size,
+                                             uint64_t leaf) {
+  std::vector<std::string> path;
+  if (leaf > input_size || leaf == 0)
+    return path;
+
   if (input_size == 1)
-    return TreeHasher::HashLeaf(inputs[0]);
+    return path;
 
   const uint64_t split = CalculateNearestPowerOfTwo(input_size);
 
-  return ct::internal::HashNodes(
-      ReferenceMerkleTreeHash(&inputs[0], split),
-      ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  std::vector<std::string> subpath;
+  if (leaf <= split) {
+    subpath = ReferenceMerklePath(&inputs[0], split, leaf);
+    path.insert(path.end(), subpath.begin(), subpath.end());
+    path.push_back(ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  } else {
+    subpath =
+        ReferenceMerklePath(&inputs[split], input_size - split, leaf - split);
+    path.insert(path.end(), subpath.begin(), subpath.end());
+    path.push_back(ReferenceMerkleTreeHash(&inputs[0], split));
+  }
+
+  return path;
 }
 
 // Reference implementation of snapshot consistency. Returns a
 // consistency proof between two snapshots of the tree designated
 // by |inputs|.
 // Call with have_root1 = true.
 std::vector<std::string> ReferenceSnapshotConsistency(std::string* inputs,
                                                       uint64_t snapshot2,
                                                       uint64_t snapshot1,
                                                       bool have_root1) {
@@ skipping 47 matching lines @@
 TEST_F(CTLogVerifierTest,
        MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator) {
   std::vector<std::string> data;
   for (int i = 0; i < 256; ++i)
     data.push_back(std::string(1, i));
 
   std::vector<std::string> proof;
   std::string root1, root2;
   // More tests with reference proof generator.
   for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
+    SCOPED_TRACE(tree_size);
     root2 = ReferenceMerkleTreeHash(data.data(), tree_size);
     // Repeat for each snapshot in range.
     for (size_t snapshot = 1; snapshot <= tree_size; ++snapshot) {
+      SCOPED_TRACE(snapshot);
       proof =
           ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
       root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
       VerifierConsistencyCheck(snapshot, tree_size, root1, root2, proof);
     }
   }
 }
 
+TEST_F(CTLogVerifierTest, VerifiesAuditProofEdgeCases_EmptyProof) {
+  std::vector<std::string> path;
+  // Various invalid paths.
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 0, 0, path, std::string(), std::string()));
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 0, 1, path, std::string(), std::string()));
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 1, 0, path, std::string(), std::string()));
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 2, 1, path, std::string(), std::string()));
+
+  const std::string empty_hash = HexToBytes(kSHA256EmptyTreeHash);
+  EXPECT_FALSE(VerifyAuditProof(log_, 0, 0, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 0, 1, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 1, 0, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 2, 1, path, empty_hash, std::string()));
+}
+
+TEST_F(CTLogVerifierTest, VerifiesValidAuditProofs) {
+  std::vector<std::string> path;
+  // Known good paths.
+  // i = 0 is an invalid path.
+  for (int i = 1; i < 6; ++i) {
+    SCOPED_TRACE(i);
+    // Construct the path.
+    path.clear();
+    for (int j = 0; j < kSHA256Paths[i].path_length; ++j)
+      path.push_back(HexToBytes(kSHA256Paths[i].path[j]));
+    const TestVector& root_hash = kSHA256Roots[kSHA256Paths[i].snapshot - 1];
+    VerifierCheck(kSHA256Paths[i].leaf, kSHA256Paths[i].snapshot, path,
+                  HexToBytes(root_hash),
+                  HexToBytes(kSHA256LeafHashes[kSHA256Paths[i].leaf - 1]));
+  }
+}
+
+TEST_F(CTLogVerifierTest, VerifiesValidAuditProofsFromReferenceGenerator) {
+  std::vector<std::string> data;
+  for (size_t i = 0; i < 256; ++i)
+    data.emplace_back(1, i);
+
+  // More tests with reference path generator.
+  std::string root;
+  std::vector<std::string> path;
+  for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
+    SCOPED_TRACE(tree_size);
+    // Repeat for each leaf in range.
+    for (size_t leaf = 1; leaf <= tree_size; ++leaf) {
+      SCOPED_TRACE(leaf);
+      path = ReferenceMerklePath(data.data(), tree_size, leaf);
+      root = ReferenceMerkleTreeHash(data.data(), tree_size);
+      VerifierCheck(leaf, tree_size, path, root,
+                    TreeHasher::HashLeaf(data[leaf - 1]));
+    }
+  }
+}
+
 }  // namespace
 
 }  // namespace net