OLD | NEW |
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 Loading... |
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 |
OLD | NEW |