Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(175)

Side by Side Diff: net/cert/ct_log_verifier_unittest.cc

Issue 2182533002: Adds a VerifyAuditProof method to CTLogVerifier (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Rebase Created 4 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « net/cert/ct_log_verifier.cc ('k') | net/cert/merkle_audit_proof.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2013 The Chromium Authors. All rights reserved. 1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "net/cert/ct_log_verifier.h" 5 #include "net/cert/ct_log_verifier.h"
6 6
7 #include <stdint.h> 7 #include <stdint.h>
8 8
9 #include <memory> 9 #include <memory>
10 #include <string> 10 #include <string>
11 #include <vector> 11 #include <vector>
12 12
13 #include "base/macros.h"
13 #include "base/strings/string_number_conversions.h" 14 #include "base/strings/string_number_conversions.h"
14 #include "base/time/time.h" 15 #include "base/time/time.h"
15 #include "crypto/secure_hash.h" 16 #include "crypto/secure_hash.h"
16 #include "net/base/hash_value.h" 17 #include "net/base/hash_value.h"
17 #include "net/cert/ct_log_verifier_util.h" 18 #include "net/cert/ct_log_verifier_util.h"
19 #include "net/cert/merkle_audit_proof.h"
18 #include "net/cert/merkle_consistency_proof.h" 20 #include "net/cert/merkle_consistency_proof.h"
19 #include "net/cert/signed_certificate_timestamp.h" 21 #include "net/cert/signed_certificate_timestamp.h"
20 #include "net/cert/signed_tree_head.h" 22 #include "net/cert/signed_tree_head.h"
21 #include "net/test/ct_test_util.h" 23 #include "net/test/ct_test_util.h"
22 #include "testing/gtest/include/gtest/gtest.h" 24 #include "testing/gtest/include/gtest/gtest.h"
23 25
24 namespace net { 26 namespace net {
25 27
26 namespace { 28 namespace {
27 29
28 // Calculate the power of two nearest to, but less than, |n|. 30 // Calculate the power of two nearest to, but less than, |n|.
29 // |n| must be at least 2. 31 // |n| must be at least 2.
30 uint64_t CalculateNearestPowerOfTwo(uint64_t n) { 32 size_t CalculateNearestPowerOfTwo(size_t n) {
31 DCHECK_GT(n, 1u); 33 DCHECK_GT(n, 1u);
32 34
33 uint64_t ret = UINT64_C(1) << 63; 35 size_t ret = size_t(1) << (sizeof(size_t) * 8 - 1);
34 while (ret >= n) 36 while (ret >= n)
35 ret >>= 1; 37 ret >>= 1;
36 38
37 return ret; 39 return ret;
38 } 40 }
39 41
40 // A single consistency proof. Contains the old and new tree sizes
41 // (snapshot1 and snapshot2), the length of the proof (proof_length) and
42 // at most 3 proof nodes (all test proofs will be for a tree of size 8).
43 struct ProofTestVector {
44 uint64_t snapshot1;
45 uint64_t snapshot2;
46 size_t proof_length;
47 const char* const proof[3];
48 };
49
50 // All test data replicated from 42 // All test data replicated from
51 // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531 dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc 43 // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531 dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc
52 // A hash of the empty string. 44
53 const uint8_t kSHA256EmptyTreeHash[32] = { 45 // The SHA-256 hash of an empty Merkle tree.
46 const uint8_t kEmptyTreeHash[32] = {
54 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 47 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4,
55 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 48 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b,
56 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55}; 49 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55};
57 50
58 // Root hashes from building the sample tree of size 8 leaf-by-leaf. 51 std::string GetEmptyTreeHash() {
59 // The first entry is the root at size 0, the last is the root at size 8. 52 return std::string(std::begin(kEmptyTreeHash), std::end(kEmptyTreeHash));
60 const char* const kSHA256Roots[8] = { 53 }
54
55 // SHA-256 Merkle leaf hashes for the sample tree that all of the other test
56 // data relates to (8 leaves).
57 const char* const kLeafHashes[8] = {
58 "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
59 "96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
60 "0298d122906dcfc10892cb53a73992fc5b9f493ea4c9badb27b791b4127a7fe7",
61 "07506a85fd9dd2f120eb694f86011e5bb4662e5c415a62917033d4a9624487e7",
62 "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
63 "4271a26be0d8a84f0bd54c8c302e7cb3a3b5d1fa6780a40bcce2873477dab658",
64 "b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f",
65 "46f6ffadd3d06a09ff3c5860d2755c8b9819db7df44251788c7d8e3180de8eb1"};
66
67 // SHA-256 Merkle root hashes from building the sample tree leaf-by-leaf.
68 // The first entry is the root when the tree contains 1 leaf, and the last is
69 // the root when the tree contains all 8 leaves.
70 const char* const kRootHashes[8] = {
61 "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 71 "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
62 "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 72 "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125",
63 "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 73 "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77",
64 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 74 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
65 "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 75 "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4",
66 "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 76 "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef",
67 "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 77 "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c",
68 "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"}; 78 "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"};
69 79
70 // A collection of consistency proofs between various sub-trees of the tree 80 // A single consistency proof. Contains at most 3 proof nodes (all test proofs
71 // defined by |kSHA256Roots|. 81 // will be for a tree of size 8).
72 const ProofTestVector kSHA256Proofs[4] = { 82 struct ConsistencyProofTestVector {
83 size_t old_tree_size;
84 size_t new_tree_size;
85 size_t proof_length;
86 const char* const proof[3];
87 };
88
89 // A collection of consistency proofs between various sub-trees of the sample
90 // tree.
91 const ConsistencyProofTestVector kConsistencyProofs[] = {
73 // Empty consistency proof between trees of the same size (1). 92 // Empty consistency proof between trees of the same size (1).
74 {1, 1, 0, {"", "", ""}}, 93 {1, 1, 0, {"", "", ""}},
75 // Consistency proof between tree of size 1 and tree of size 8, with 3 94 // Consistency proof between tree of size 1 and tree of size 8, with 3
76 // nodes in the proof. 95 // nodes in the proof.
77 {1, 96 {1,
78 8, 97 8,
79 3, 98 3,
80 {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 99 {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
81 "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 100 "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
82 "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}}, 101 "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}},
83 // Consistency proof between tree of size 6 and tree of size 8, with 3 102 // Consistency proof between tree of size 6 and tree of size 8, with 3
84 // nodes in the proof. 103 // nodes in the proof.
85 {6, 104 {6,
86 8, 105 8,
87 3, 106 3,
88 {"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", 107 {"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a",
89 "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 108 "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
90 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}}, 109 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}},
91 // Consistency proof between tree of size 2 and tree of size 5, with 2 110 // Consistency proof between tree of size 2 and tree of size 5, with 2
92 // nodes in the proof. 111 // nodes in the proof.
93 {2, 112 {2,
94 5, 113 5,
95 2, 114 2,
96 {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 115 {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
97 "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", ""}}}; 116 "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", ""}}};
98 117
118 // A single audit proof. Contains at most 3 proof nodes (all test proofs will be
119 // for a tree of size 8).
120 struct AuditProofTestVector {
121 size_t leaf;
122 size_t tree_size;
123 size_t proof_length;
124 const char* const proof[3];
125 };
126
127 // A collection of audit proofs for various leaves and sub-trees of the tree
128 // defined by |kRootHashes|.
129 const AuditProofTestVector kAuditProofs[] = {
130 {0, 1, 0, {"", "", ""}},
131 {0,
132 8,
133 3,
134 {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
135 "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
136 "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}},
137 {5,
138 8,
139 3,
140 {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
141 "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
142 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}},
143 {2,
144 3,
145 1,
146 {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", "",
147 ""}},
148 {1,
149 5,
150 3,
151 {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
152 "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
153 "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"}}};
154
99 // Decodes a hexadecimal string into the binary data it represents. 155 // Decodes a hexadecimal string into the binary data it represents.
100 std::string HexToBytes(const std::string& hex_data) { 156 std::string HexToBytes(const std::string& hex_data) {
101 std::vector<uint8_t> output; 157 std::vector<uint8_t> output;
102 std::string result; 158 std::string result;
103 if (base::HexStringToBytes(hex_data, &output)) 159 if (base::HexStringToBytes(hex_data, &output))
104 result.assign(output.begin(), output.end()); 160 result.assign(output.begin(), output.end());
105 return result; 161 return result;
106 } 162 }
107 163
108 std::string GetEmptyTreeHash() { 164 // Constructs a consistency/audit proof from a test vector.
109 return std::string(std::begin(kSHA256EmptyTreeHash), 165 // This is templated so that it can be used with both ConsistencyProofTestVector
110 std::end(kSHA256EmptyTreeHash)); 166 // and AuditProofTestVector.
111 } 167 template <typename TestVectorType>
112 168 std::vector<std::string> GetProof(const TestVectorType& test_vector) {
113 // Creates a ct::MerkleConsistencyProof and returns the result of 169 std::vector<std::string> proof(test_vector.proof_length);
114 // calling log->VerifyConsistencyProof with that proof and snapshots. 170 std::transform(test_vector.proof,
115 bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log, 171 test_vector.proof + test_vector.proof_length, proof.begin(),
116 uint64_t old_tree_size, 172 &HexToBytes);
173
174 return proof;
175 }
176
177 // Creates a ct::MerkleConsistencyProof from its arguments and returns the
178 // result of passing this to log.VerifyConsistencyProof().
179 bool VerifyConsistencyProof(const CTLogVerifier& log,
180 size_t old_tree_size,
117 const std::string& old_tree_root, 181 const std::string& old_tree_root,
118 uint64_t new_tree_size, 182 size_t new_tree_size,
119 const std::string& new_tree_root, 183 const std::string& new_tree_root,
120 const std::vector<std::string>& proof) { 184 const std::vector<std::string>& proof) {
121 return log->VerifyConsistencyProof( 185 return log.VerifyConsistencyProof(
122 ct::MerkleConsistencyProof(log->key_id(), proof, old_tree_size, 186 ct::MerkleConsistencyProof(log.key_id(), proof, old_tree_size,
123 new_tree_size), 187 new_tree_size),
124 old_tree_root, new_tree_root); 188 old_tree_root, new_tree_root);
125 } 189 }
126 190
191 // Creates a ct::MerkleAuditProof from its arguments and returns the result of
192 // passing this to log.VerifyAuditProof().
193 bool VerifyAuditProof(const CTLogVerifier& log,
194 size_t leaf,
195 size_t tree_size,
196 const std::vector<std::string>& proof,
197 const std::string& tree_root,
198 const std::string& leaf_hash) {
199 return log.VerifyAuditProof(ct::MerkleAuditProof(leaf, tree_size, proof),
200 tree_root, leaf_hash);
201 }
202
127 class CTLogVerifierTest : public ::testing::Test { 203 class CTLogVerifierTest : public ::testing::Test {
128 public: 204 public:
129 CTLogVerifierTest() {}
130
131 void SetUp() override { 205 void SetUp() override {
132 log_ = CTLogVerifier::Create(ct::GetTestPublicKey(), "testlog", 206 log_ = CTLogVerifier::Create(ct::GetTestPublicKey(), "testlog",
133 "https://ct.example.com", "ct.example.com"); 207 "https://ct.example.com", "ct.example.com");
134 208
135 ASSERT_TRUE(log_); 209 ASSERT_TRUE(log_);
136 ASSERT_EQ(ct::GetTestPublicKeyId(), log_->key_id()); 210 EXPECT_EQ(ct::GetTestPublicKeyId(), log_->key_id());
137 ASSERT_EQ("ct.example.com", log_->dns_domain()); 211 EXPECT_EQ("ct.example.com", log_->dns_domain());
138 }
139
140 // Given a consistency proof between two snapshots of the tree, asserts that
141 // it verifies and no other combination of snapshots and proof nodes verifies.
142 void VerifierConsistencyCheck(int snapshot1,
143 int snapshot2,
144 const std::string& root1,
145 const std::string& root2,
146 const std::vector<std::string>& proof) {
147 // Verify the original consistency proof.
148 EXPECT_TRUE(
149 VerifyConsistencyProof(log_, snapshot1, root1, snapshot2, root2, proof))
150 << " " << snapshot1 << " " << snapshot2;
151
152 if (proof.empty()) {
153 // For simplicity test only non-trivial proofs that have root1 != root2
154 // snapshot1 != 0 and snapshot1 != snapshot2.
155 return;
156 }
157
158 // Wrong snapshot index: The proof checking code should not accept
159 // as a valid proof a proof for a tree size different than the original
160 // size it was produced for.
161 // Test that this is not the case for off-by-one changes.
162 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 - 1, root1, snapshot2,
163 root2, proof));
164 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 + 1, root1, snapshot2,
165 root2, proof));
166 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 ^ 2, root1, snapshot2,
167 root2, proof));
168
169 // Test that the proof is not accepted for trees with wrong tree height.
170 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2 * 2,
171 root2, proof));
172 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2 / 2,
173 root2, proof));
174
175 // Test that providing the wrong input root fails checking an
176 // otherwise-valid proof.
177 const std::string wrong_root("WrongRoot");
178 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
179 wrong_root, proof));
180 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, wrong_root, snapshot2,
181 root2, proof));
182 // Test that swapping roots fails checking an otherwise-valid proof (that
183 // the right root is used for each calculation).
184 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root2, snapshot2,
185 root1, proof));
186
187 // Variations of wrong proofs, all of which should be rejected.
188 std::vector<std::string> wrong_proof;
189 // Empty proof.
190 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
191 root2, wrong_proof));
192
193 // Modify a single element in the proof.
194 for (size_t j = 0; j < proof.size(); ++j) {
195 wrong_proof = proof;
196 wrong_proof[j] = GetEmptyTreeHash();
197 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
198 root2, wrong_proof));
199 }
200
201 // Add garbage at the end of the proof.
202 wrong_proof = proof;
203 wrong_proof.push_back(std::string());
204 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
205 root2, wrong_proof));
206 wrong_proof.pop_back();
207
208 wrong_proof.push_back(proof.back());
209 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
210 root2, wrong_proof));
211 wrong_proof.pop_back();
212
213 // Remove a node from the end.
214 wrong_proof.pop_back();
215 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
216 root2, wrong_proof));
217
218 // Add garbage in the beginning of the proof.
219 wrong_proof.clear();
220 wrong_proof.push_back(std::string());
221 wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
222 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
223 root2, wrong_proof));
224
225 wrong_proof[0] = proof[0];
226 EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
227 root2, wrong_proof));
228 } 212 }
229 213
230 protected: 214 protected:
231 scoped_refptr<const CTLogVerifier> log_; 215 scoped_refptr<const CTLogVerifier> log_;
232 }; 216 };
233 217
218 // Given an audit proof for a leaf in a Merkle tree, asserts that it verifies
219 // and no other combination of leaves, tree sizes and proof nodes verifies.
220 void CheckVerifyAuditProof(const CTLogVerifier& log,
221 size_t leaf,
222 size_t tree_size,
223 const std::vector<std::string>& proof,
224 const std::string& root_hash,
225 const std::string& leaf_hash) {
226 EXPECT_TRUE(
227 VerifyAuditProof(log, leaf, tree_size, proof, root_hash, leaf_hash))
228 << "proof for leaf " << leaf << " did not pass verification";
229 EXPECT_FALSE(
230 VerifyAuditProof(log, leaf - 1, tree_size, proof, root_hash, leaf_hash))
231 << "proof passed verification with wrong leaf index";
232 EXPECT_FALSE(
233 VerifyAuditProof(log, leaf + 1, tree_size, proof, root_hash, leaf_hash))
234 << "proof passed verification with wrong leaf index";
235 EXPECT_FALSE(
236 VerifyAuditProof(log, leaf ^ 2, tree_size, proof, root_hash, leaf_hash))
237 << "proof passed verification with wrong leaf index";
238 EXPECT_FALSE(
239 VerifyAuditProof(log, leaf, tree_size * 2, proof, root_hash, leaf_hash))
240 << "proof passed verification with wrong tree height";
241 EXPECT_FALSE(VerifyAuditProof(log, leaf / 2, tree_size / 2, proof, root_hash,
242 leaf_hash))
243 << "proof passed verification with wrong leaf index and tree height";
244 EXPECT_FALSE(
245 VerifyAuditProof(log, leaf, tree_size / 2, proof, root_hash, leaf_hash))
246 << "proof passed verification with wrong tree height";
247 EXPECT_FALSE(VerifyAuditProof(log, leaf, tree_size, proof, GetEmptyTreeHash(),
248 leaf_hash))
249 << "proof passed verification with wrong root hash";
250
251 std::vector<std::string> wrong_proof;
252
253 // Modify a single element on the proof.
254 for (size_t j = 0; j < proof.size(); ++j) {
255 wrong_proof = proof;
256 wrong_proof[j] = GetEmptyTreeHash();
257 EXPECT_FALSE(VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash,
258 leaf_hash))
259 << "proof passed verification with one wrong node (node " << j << ")";
260 }
261
262 wrong_proof = proof;
263 wrong_proof.push_back(std::string());
264 EXPECT_FALSE(
265 VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
266 << "proof passed verification with an empty node appended";
267
268 wrong_proof.back() = root_hash;
269 EXPECT_FALSE(
270 VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
271 << "proof passed verification with an incorrect node appended";
272 wrong_proof.pop_back();
273
274 if (!wrong_proof.empty()) {
275 wrong_proof.pop_back();
276 EXPECT_FALSE(VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash,
277 leaf_hash))
278 << "proof passed verification with the last node missing";
279 }
280
281 wrong_proof.clear();
282 wrong_proof.push_back(std::string());
283 wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
284 EXPECT_FALSE(
285 VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
286 << "proof passed verification with an empty node prepended";
287
288 wrong_proof[0] = root_hash;
289 EXPECT_FALSE(
290 VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
291 << "proof passed verification with an incorrect node prepended";
292 }
293
294 // Given a consistency proof between two snapshots of the tree, asserts that it
295 // verifies and no other combination of tree sizes and proof nodes verifies.
296 void CheckVerifyConsistencyProof(const CTLogVerifier& log,
297 int old_tree_size,
298 int new_tree_size,
299 const std::string& old_root,
300 const std::string& new_root,
301 const std::vector<std::string>& proof) {
302 // Verify the original consistency proof.
303 EXPECT_TRUE(VerifyConsistencyProof(log, old_tree_size, old_root,
304 new_tree_size, new_root, proof))
305 << "proof between trees of size " << old_tree_size << " and "
306 << new_tree_size << " did not pass verification";
307
308 if (proof.empty()) {
309 // For simplicity test only non-trivial proofs that have old_root !=
310 // new_root
311 // old_tree_size != 0 and old_tree_size != new_tree_size.
312 return;
313 }
314
315 // Wrong tree size: The proof checking code should not accept as a valid proof
316 // a proof for a tree size different than the original size it was produced
317 // for. Test that this is not the case for off-by-one changes.
318 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size - 1, old_root,
319 new_tree_size, new_root, proof))
320 << "proof passed verification with old tree size - 1";
321 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size + 1, old_root,
322 new_tree_size, new_root, proof))
323 << "proof passed verification with old tree size + 1";
324 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size ^ 2, old_root,
325 new_tree_size, new_root, proof))
326 << "proof passed verification with old tree size ^ 2";
327
328 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
329 new_tree_size * 2, new_root, proof))
330 << "proof passed verification with new tree height + 1";
331 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
332 new_tree_size / 2, new_root, proof))
333 << "proof passed verification with new tree height - 1";
334
335 const std::string wrong_root("WrongRoot");
336 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
337 new_tree_size, wrong_root, proof))
338 << "proof passed verification with wrong old root";
339 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, wrong_root,
340 new_tree_size, new_root, proof))
341 << "proof passed verification with wrong new root";
342 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, new_root,
343 new_tree_size, old_root, proof))
344 << "proof passed verification with old and new root swapped";
345
346 // Variations of wrong proofs, all of which should be rejected.
347 std::vector<std::string> wrong_proof;
348 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
349 new_tree_size, new_root, wrong_proof))
350 << "empty proof passed verification";
351
352 // Modify a single element in the proof.
353 for (size_t j = 0; j < proof.size(); ++j) {
354 wrong_proof = proof;
355 wrong_proof[j] = GetEmptyTreeHash();
356 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
357 new_tree_size, new_root, wrong_proof))
358 << "proof passed verification with incorrect node (node " << j << ")";
359 }
360
361 wrong_proof = proof;
362 wrong_proof.push_back(std::string());
363 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
364 new_tree_size, new_root, wrong_proof))
365 << "proof passed verification with empty node appended";
366
367 wrong_proof.back() = proof.back();
368 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
369 new_tree_size, new_root, wrong_proof))
370 << "proof passed verification with last node duplicated";
371 wrong_proof.pop_back();
372
373 wrong_proof.pop_back();
374 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
375 new_tree_size, new_root, wrong_proof))
376 << "proof passed verification with last node missing";
377
378 wrong_proof.clear();
379 wrong_proof.push_back(std::string());
380 wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
381 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
382 new_tree_size, new_root, wrong_proof))
383 << "proof passed verification with empty node prepended";
384
385 wrong_proof[0] = proof[0];
386 EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
387 new_tree_size, new_root, wrong_proof))
388 << "proof passed verification with first node duplicated";
389 }
390
234 TEST_F(CTLogVerifierTest, VerifiesCertSCT) { 391 TEST_F(CTLogVerifierTest, VerifiesCertSCT) {
235 ct::LogEntry cert_entry; 392 ct::LogEntry cert_entry;
236 ct::GetX509CertLogEntry(&cert_entry); 393 ct::GetX509CertLogEntry(&cert_entry);
237 394
238 scoped_refptr<ct::SignedCertificateTimestamp> cert_sct; 395 scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
239 ct::GetX509CertSCT(&cert_sct); 396 ct::GetX509CertSCT(&cert_sct);
240 397
241 EXPECT_TRUE(log_->Verify(cert_entry, *cert_sct.get())); 398 EXPECT_TRUE(log_->Verify(cert_entry, *cert_sct.get()));
242 } 399 }
243 400
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after
308 std::string key = ct::GetTestPublicKey(); 465 std::string key = ct::GetTestPublicKey();
309 key += "extra"; 466 key += "extra";
310 467
311 scoped_refptr<const CTLogVerifier> log = CTLogVerifier::Create( 468 scoped_refptr<const CTLogVerifier> log = CTLogVerifier::Create(
312 key, "testlog", "https://ct.example.com", "ct.example.com"); 469 key, "testlog", "https://ct.example.com", "ct.example.com");
313 EXPECT_FALSE(log); 470 EXPECT_FALSE(log);
314 } 471 }
315 472
316 TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_EmptyProof) { 473 TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_EmptyProof) {
317 std::vector<std::string> empty_proof; 474 std::vector<std::string> empty_proof;
318 std::string root1(GetEmptyTreeHash()), root2(GetEmptyTreeHash()); 475 std::string old_root(GetEmptyTreeHash()), new_root(GetEmptyTreeHash());
319 476
320 // Snapshots that are always consistent, because they are either 477 // Tree snapshots that are always consistent, because the proofs are either
321 // from an empty tree to a non-empty one or for trees of the same 478 // from an empty tree to a non-empty one or for trees of the same size.
322 // size. 479 EXPECT_TRUE(
323 EXPECT_TRUE(VerifyConsistencyProof(log_, 0, root1, 0, root2, empty_proof)); 480 VerifyConsistencyProof(*log_, 0, old_root, 0, new_root, empty_proof));
324 EXPECT_TRUE(VerifyConsistencyProof(log_, 0, root1, 1, root2, empty_proof)); 481 EXPECT_TRUE(
325 EXPECT_TRUE(VerifyConsistencyProof(log_, 1, root1, 1, root2, empty_proof)); 482 VerifyConsistencyProof(*log_, 0, old_root, 1, new_root, empty_proof));
483 EXPECT_TRUE(
484 VerifyConsistencyProof(*log_, 1, old_root, 1, new_root, empty_proof));
326 485
327 // Invalid consistency proofs. 486 // Invalid consistency proofs.
328 // Time travel to the past. 487 // Time travel to the past.
329 EXPECT_FALSE(VerifyConsistencyProof(log_, 1, root1, 0, root2, empty_proof)); 488 EXPECT_FALSE(
330 EXPECT_FALSE(VerifyConsistencyProof(log_, 2, root1, 1, root2, empty_proof)); 489 VerifyConsistencyProof(*log_, 1, old_root, 0, new_root, empty_proof));
490 EXPECT_FALSE(
491 VerifyConsistencyProof(*log_, 2, old_root, 1, new_root, empty_proof));
331 // Proof between two trees of different size can never be empty. 492 // Proof between two trees of different size can never be empty.
332 EXPECT_FALSE(VerifyConsistencyProof(log_, 1, root1, 2, root2, empty_proof)); 493 EXPECT_FALSE(
494 VerifyConsistencyProof(*log_, 1, old_root, 2, new_root, empty_proof));
333 } 495 }
334 496
335 TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_MismatchingRoots) { 497 TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_MismatchingRoots) {
498 const std::string old_root(GetEmptyTreeHash());
499 std::string new_root;
336 std::vector<std::string> empty_proof; 500 std::vector<std::string> empty_proof;
337 std::string root2;
338 const std::string empty_tree_hash(GetEmptyTreeHash());
339 501
340 // Roots don't match. 502 // Roots don't match.
341 EXPECT_FALSE( 503 EXPECT_FALSE(
342 VerifyConsistencyProof(log_, 0, empty_tree_hash, 0, root2, empty_proof)); 504 VerifyConsistencyProof(*log_, 0, old_root, 0, new_root, empty_proof));
343 EXPECT_FALSE( 505 EXPECT_FALSE(
344 VerifyConsistencyProof(log_, 1, empty_tree_hash, 1, root2, empty_proof)); 506 VerifyConsistencyProof(*log_, 1, old_root, 1, new_root, empty_proof));
345 } 507 }
346 508
347 TEST_F(CTLogVerifierTest, 509 TEST_F(CTLogVerifierTest,
348 VerifiesConsistencyProofEdgeCases_MatchingRootsNonEmptyProof) { 510 VerifiesConsistencyProofEdgeCases_MatchingRootsNonEmptyProof) {
349 const std::string empty_tree_hash(GetEmptyTreeHash()); 511 const std::string empty_tree_hash(GetEmptyTreeHash());
350 512
351 std::vector<std::string> proof; 513 std::vector<std::string> proof;
352 proof.push_back(empty_tree_hash); 514 proof.push_back(empty_tree_hash);
353 515
354 // Roots match and the tree size is either the same or the old tree size is 0, 516 // Roots match and the tree size is either the same or the old tree size is 0,
355 // but the proof is not empty (the verification code should not accept 517 // but the proof is not empty (the verification code should not accept
356 // proofs with redundant nodes in this case). 518 // proofs with redundant nodes in this case).
357 proof.push_back(empty_tree_hash); 519 proof.push_back(empty_tree_hash);
358 EXPECT_FALSE(VerifyConsistencyProof(log_, 0, empty_tree_hash, 0, 520 EXPECT_FALSE(VerifyConsistencyProof(*log_, 0, empty_tree_hash, 0,
359 empty_tree_hash, proof)); 521 empty_tree_hash, proof));
360 EXPECT_FALSE(VerifyConsistencyProof(log_, 0, empty_tree_hash, 1, 522 EXPECT_FALSE(VerifyConsistencyProof(*log_, 0, empty_tree_hash, 1,
361 empty_tree_hash, proof)); 523 empty_tree_hash, proof));
362 EXPECT_FALSE(VerifyConsistencyProof(log_, 1, empty_tree_hash, 1, 524 EXPECT_FALSE(VerifyConsistencyProof(*log_, 1, empty_tree_hash, 1,
363 empty_tree_hash, proof)); 525 empty_tree_hash, proof));
364 } 526 }
365 527
366 TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) { 528 class CTLogVerifierConsistencyProofTest
529 : public CTLogVerifierTest,
530 public ::testing::WithParamInterface<size_t /* proof index */> {};
531
532 // Checks that a sample set of valid consistency proofs verify successfully.
533 TEST_P(CTLogVerifierConsistencyProofTest, VerifiesValidConsistencyProof) {
534 const ConsistencyProofTestVector& test_vector =
535 kConsistencyProofs[GetParam()];
536 const std::vector<std::string> proof = GetProof(test_vector);
537
538 const char* const old_root = kRootHashes[test_vector.old_tree_size - 1];
539 const char* const new_root = kRootHashes[test_vector.new_tree_size - 1];
540 CheckVerifyConsistencyProof(*log_, test_vector.old_tree_size,
541 test_vector.new_tree_size, HexToBytes(old_root),
542 HexToBytes(new_root), proof);
543 }
544
545 INSTANTIATE_TEST_CASE_P(KnownGoodProofs,
546 CTLogVerifierConsistencyProofTest,
547 ::testing::Range(size_t(0),
548 arraysize(kConsistencyProofs)));
549
550 class CTLogVerifierAuditProofTest
551 : public CTLogVerifierTest,
552 public ::testing::WithParamInterface<size_t /* proof index */> {};
553
554 // Checks that a sample set of valid audit proofs verify successfully.
555 TEST_P(CTLogVerifierAuditProofTest, VerifiesValidAuditProofs) {
556 const AuditProofTestVector& test_vector = kAuditProofs[GetParam()];
557 const std::vector<std::string> proof = GetProof(test_vector);
558
559 const char* const root_hash = kRootHashes[test_vector.tree_size - 1];
560 CheckVerifyAuditProof(*log_, test_vector.leaf, test_vector.tree_size, proof,
561 HexToBytes(root_hash),
562 HexToBytes(kLeafHashes[test_vector.leaf]));
563 }
564
565 INSTANTIATE_TEST_CASE_P(KnownGoodProofs,
566 CTLogVerifierAuditProofTest,
567 ::testing::Range(size_t(0), arraysize(kAuditProofs)));
568
569 TEST_F(CTLogVerifierTest, VerifiesAuditProofEdgeCases_InvalidLeafIndex) {
367 std::vector<std::string> proof; 570 std::vector<std::string> proof;
368 std::string root1, root2; 571 EXPECT_FALSE(
369 572 VerifyAuditProof(*log_, 1, 0, proof, std::string(), std::string()));
370 // Known good proofs. 573 EXPECT_FALSE(
371 for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) { 574 VerifyAuditProof(*log_, 2, 1, proof, std::string(), std::string()));
372 SCOPED_TRACE(i); 575
373 proof.clear(); 576 const std::string empty_hash = GetEmptyTreeHash();
374 for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) { 577 EXPECT_FALSE(VerifyAuditProof(*log_, 1, 0, proof, empty_hash, std::string()));
375 const char* const v = kSHA256Proofs[i].proof[j]; 578 EXPECT_FALSE(VerifyAuditProof(*log_, 2, 1, proof, empty_hash, std::string()));
376 proof.push_back(HexToBytes(v)); 579 }
580
581 // Functions that implement algorithms from RFC6962 necessary for constructing
582 // Merkle trees and proofs. This allows tests to generate a variety of trees
583 // for exhaustive testing.
584 namespace rfc6962 {
585
586 // Calculates the hash of a leaf in a Merkle tree, given its content.
587 // See RFC6962, section 2.1.
588 std::string HashLeaf(const std::string& leaf) {
589 const char kLeafPrefix[] = {'\x00'};
590
591 SHA256HashValue sha256;
592 memset(sha256.data, 0, sizeof(sha256.data));
593
594 std::unique_ptr<crypto::SecureHash> hash(
595 crypto::SecureHash::Create(crypto::SecureHash::SHA256));
596 hash->Update(kLeafPrefix, 1);
597 hash->Update(leaf.data(), leaf.size());
598 hash->Finish(sha256.data, sizeof(sha256.data));
599
600 return std::string(reinterpret_cast<const char*>(sha256.data),
601 sizeof(sha256.data));
602 }
603
604 // Calculates the root hash of a Merkle tree, given its leaf data and size.
605 // See RFC6962, section 2.1.
606 std::string HashTree(std::string leaves[], size_t tree_size) {
607 if (tree_size == 0)
608 return GetEmptyTreeHash();
609 if (tree_size == 1)
610 return HashLeaf(leaves[0]);
611
612 // Find the index of the last leaf in the left sub-tree.
613 const size_t split = CalculateNearestPowerOfTwo(tree_size);
614
615 // Hash the left and right sub-trees, then hash the results.
616 return ct::internal::HashNodes(HashTree(leaves, split),
617 HashTree(&leaves[split], tree_size - split));
618 }
619
620 // Returns a Merkle audit proof for the leaf with index |leaf_index|.
621 // The tree consists of |leaves[0]| to |leaves[tree_size-1]|.
622 // If |leaf_index| is >= |tree_size|, an empty proof will be returned.
623 // See RFC6962, section 2.1.1, for more details.
624 std::vector<std::string> CreateAuditProof(std::string leaves[],
625 size_t tree_size,
626 size_t leaf_index) {
627 std::vector<std::string> proof;
628 if (leaf_index >= tree_size)
629 return proof;
630 if (tree_size == 1)
631 return proof;
632
633 // Find the index of the first leaf in the right sub-tree.
634 const size_t split = CalculateNearestPowerOfTwo(tree_size);
635
636 // Recurse down the correct branch of the tree (left or right) to reach the
637 // leaf with |leaf_index|. Add the hash of the branch not taken at each step
638 // on the way up to build the proof.
639 if (leaf_index < split) {
640 proof = CreateAuditProof(leaves, split, leaf_index);
641 proof.push_back(HashTree(&leaves[split], tree_size - split));
642 } else {
643 proof =
644 CreateAuditProof(&leaves[split], tree_size - split, leaf_index - split);
645 proof.push_back(HashTree(leaves, split));
646 }
647
648 return proof;
649 }
650
651 // Returns a Merkle consistency proof between two Merkle trees.
652 // The old tree contains |leaves[0]| to |leaves[old_tree_size-1]|.
653 // The new tree contains |leaves[0]| to |leaves[new_tree_size-1]|.
654 // Call with |contains_old_tree| = true.
655 // See RFC6962, section 2.1.2, for more details.
656 std::vector<std::string> CreateConsistencyProof(std::string leaves[],
657 size_t new_tree_size,
658 size_t old_tree_size,
659 bool contains_old_tree = true) {
660 std::vector<std::string> proof;
661 if (old_tree_size == 0 || old_tree_size > new_tree_size)
662 return proof;
663 if (old_tree_size == new_tree_size) {
664 // Consistency proof for two equal subtrees is empty.
665 if (!contains_old_tree) {
666 // Record the hash of this subtree unless it's the root for which
667 // the proof was originally requested. (This happens when the old tree is
668 // balanced).
669 proof.push_back(HashTree(leaves, old_tree_size));
377 } 670 }
378 const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1; 671 return proof;
379 const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2; 672 }
380 const char* const old_root = kSHA256Roots[snapshot1 - 1]; 673
381 const char* const new_root = kSHA256Roots[snapshot2 - 1]; 674 // Find the index of the last leaf in the left sub-tree.
382 VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root), 675 const size_t split = CalculateNearestPowerOfTwo(new_tree_size);
383 HexToBytes(new_root), proof); 676
384 } 677 if (old_tree_size <= split) {
385 } 678 // Root of the old tree is in the left subtree of the new tree.
386
387 const char kLeafPrefix[] = {'\x00'};
388
389 // Reference implementation of RFC6962.
390 // This allows generation of arbitrary-sized Merkle trees and consistency
391 // proofs between them for testing the consistency proof validation
392 // code.
393 class TreeHasher {
394 public:
395 static std::string HashLeaf(const std::string& leaf) {
396 SHA256HashValue sha256;
397 memset(sha256.data, 0, sizeof(sha256.data));
398
399 std::unique_ptr<crypto::SecureHash> hash(
400 crypto::SecureHash::Create(crypto::SecureHash::SHA256));
401 hash->Update(kLeafPrefix, 1);
402 hash->Update(leaf.data(), leaf.size());
403 hash->Finish(sha256.data, sizeof(sha256.data));
404
405 return std::string(reinterpret_cast<const char*>(sha256.data),
406 sizeof(sha256.data));
407 }
408 };
409
410 // Reference implementation of Merkle hash, for cross-checking.
411 // Recursively calculates the hash of the root given the leaf data
412 // specified in |inputs|.
413 std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) {
414 if (!input_size)
415 return GetEmptyTreeHash();
416 if (input_size == 1)
417 return TreeHasher::HashLeaf(inputs[0]);
418
419 const uint64_t split = CalculateNearestPowerOfTwo(input_size);
420
421 return ct::internal::HashNodes(
422 ReferenceMerkleTreeHash(&inputs[0], split),
423 ReferenceMerkleTreeHash(&inputs[split], input_size - split));
424 }
425
426 // Reference implementation of snapshot consistency. Returns a
427 // consistency proof between two snapshots of the tree designated
428 // by |inputs|.
429 // Call with have_root1 = true.
430 std::vector<std::string> ReferenceSnapshotConsistency(std::string* inputs,
431 uint64_t snapshot2,
432 uint64_t snapshot1,
433 bool have_root1) {
434 std::vector<std::string> proof;
435 if (snapshot1 == 0 || snapshot1 > snapshot2)
436 return proof;
437 if (snapshot1 == snapshot2) {
438 // Consistency proof for two equal subtrees is empty.
439 if (!have_root1) {
440 // Record the hash of this subtree unless it's the root for which
441 // the proof was originally requested. (This happens when the snapshot1
442 // tree is balanced.)
443 proof.push_back(ReferenceMerkleTreeHash(inputs, snapshot1));
444 }
445 return proof;
446 }
447
448 // 0 < snapshot1 < snapshot2
449 const uint64_t split = CalculateNearestPowerOfTwo(snapshot2);
450
451 std::vector<std::string> subproof;
452 if (snapshot1 <= split) {
453 // Root of snapshot1 is in the left subtree of snapshot2.
454 // Prove that the left subtrees are consistent. 679 // Prove that the left subtrees are consistent.
455 subproof = 680 proof =
456 ReferenceSnapshotConsistency(inputs, split, snapshot1, have_root1); 681 CreateConsistencyProof(leaves, split, old_tree_size, contains_old_tree);
457 proof.insert(proof.end(), subproof.begin(), subproof.end()); 682 // Record the hash of the right subtree (only present in the new tree).
458 // Record the hash of the right subtree (only present in snapshot2). 683 proof.push_back(HashTree(&leaves[split], new_tree_size - split));
459 proof.push_back(ReferenceMerkleTreeHash(&inputs[split], snapshot2 - split));
460 } else { 684 } else {
461 // Snapshot1 root is at the same level as snapshot2 root. 685 // The old tree root is at the same level as the new tree root.
462 // Prove that the right subtrees are consistent. The right subtree 686 // Prove that the right subtrees are consistent. The right subtree
463 // doesn't contain the root of snapshot1, so set have_root1 = false. 687 // doesn't contain the root of the old tree, so set contains_old_tree =
464 subproof = ReferenceSnapshotConsistency(&inputs[split], snapshot2 - split, 688 // false.
465 snapshot1 - split, false); 689 proof = CreateConsistencyProof(&leaves[split], new_tree_size - split,
466 proof.insert(proof.end(), subproof.begin(), subproof.end()); 690 old_tree_size - split,
691 /* contains_old_tree = */ false);
467 // Record the hash of the left subtree (equal in both trees). 692 // Record the hash of the left subtree (equal in both trees).
468 proof.push_back(ReferenceMerkleTreeHash(&inputs[0], split)); 693 proof.push_back(HashTree(leaves, split));
469 } 694 }
470 return proof; 695 return proof;
471 } 696 }
472 697
473 class CTLogVerifierTestUsingReferenceGenerator 698 } // namespace rfc6962
699
700 class CTLogVerifierTestUsingGenerator
474 : public CTLogVerifierTest, 701 : public CTLogVerifierTest,
475 public ::testing::WithParamInterface<uint64_t> {}; 702 public ::testing::WithParamInterface<size_t /* tree_size */> {};
476 703
477 const uint64_t kReferenceTreeSize = 256; 704 // Checks that valid consistency proofs for a range of generated Merkle trees
478 705 // verify successfully.
479 // Tests that every possible valid consistency proof for a tree of a given size 706 TEST_P(CTLogVerifierTestUsingGenerator, VerifiesValidConsistencyProof) {
480 // verifies correctly. Also checks that invalid variations of each proof fail to 707 const size_t tree_size = GetParam();
481 // verify (see VerifierConsistencyCheck). 708
482 TEST_P(CTLogVerifierTestUsingReferenceGenerator, 709 std::vector<std::string> tree_leaves(tree_size);
483 VerifiesValidConsistencyProof) { 710 for (size_t i = 0; i < tree_size; ++i)
484 std::vector<std::string> data; 711 tree_leaves[i].push_back(static_cast<char>(i));
485 for (uint64_t i = 0; i < kReferenceTreeSize; ++i) 712
486 data.push_back(std::string(1, static_cast<char>(i))); 713 const std::string tree_root =
487 714 rfc6962::HashTree(tree_leaves.data(), tree_size);
488 const uint64_t tree_size = GetParam(); 715
489 const std::string tree_root = ReferenceMerkleTreeHash(data.data(), tree_size); 716 // Check consistency proofs for every sub-tree.
490 717 for (size_t old_tree_size = 0; old_tree_size <= tree_size; ++old_tree_size) {
491 for (uint64_t snapshot = 1; snapshot <= tree_size; ++snapshot) { 718 SCOPED_TRACE(old_tree_size);
492 SCOPED_TRACE(snapshot); 719 const std::string old_tree_root =
493 const std::string snapshot_root = 720 rfc6962::HashTree(tree_leaves.data(), old_tree_size);
494 ReferenceMerkleTreeHash(data.data(), snapshot); 721 const std::vector<std::string> proof = rfc6962::CreateConsistencyProof(
495 const std::vector<std::string> proof = 722 tree_leaves.data(), tree_size, old_tree_size);
496 ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true); 723 // Checks that the consistency proof verifies only with the correct tree
497 VerifierConsistencyCheck(snapshot, tree_size, snapshot_root, tree_root, 724 // sizes and root hashes.
498 proof); 725 CheckVerifyConsistencyProof(*log_, old_tree_size, tree_size, old_tree_root,
499 } 726 tree_root, proof);
500 } 727 }
501 728 }
502 // Test verification of consistency proofs between all tree sizes from 1 to 128. 729
503 INSTANTIATE_TEST_CASE_P(RangeOfTreeSizesAndSnapshots, 730 // Checks that valid audit proofs for a range of generated Merkle trees verify
504 CTLogVerifierTestUsingReferenceGenerator, 731 // successfully.
505 testing::Range(UINT64_C(1), 732 TEST_P(CTLogVerifierTestUsingGenerator, VerifiesValidAuditProofs) {
506 (kReferenceTreeSize / 2) + 1)); 733 const size_t tree_size = GetParam();
734
735 std::vector<std::string> tree_leaves(tree_size);
736 for (size_t i = 0; i < tree_size; ++i)
737 tree_leaves[i].push_back(static_cast<char>(i));
738
739 const std::string root = rfc6962::HashTree(tree_leaves.data(), tree_size);
740
741 // Check audit proofs for every leaf in the tree.
742 for (size_t leaf = 0; leaf < tree_size; ++leaf) {
743 SCOPED_TRACE(leaf);
744 std::vector<std::string> proof =
745 rfc6962::CreateAuditProof(tree_leaves.data(), tree_size, leaf);
746 // Checks that the audit proof verifies only for this leaf data, index,
747 // hash, tree size and root hash.
748 CheckVerifyAuditProof(*log_, leaf, tree_size, proof, root,
749 rfc6962::HashLeaf(tree_leaves[leaf]));
750 }
751 }
752
753 // Test verification of consistency proofs and audit proofs for all tree sizes
754 // from 0 to 128.
755 INSTANTIATE_TEST_CASE_P(RangeOfTreeSizes,
756 CTLogVerifierTestUsingGenerator,
757 testing::Range(size_t(0), size_t(129)));
507 758
508 } // namespace 759 } // namespace
509 760
510 } // namespace net 761 } // namespace net
OLDNEW
« no previous file with comments | « net/cert/ct_log_verifier.cc ('k') | net/cert/merkle_audit_proof.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698