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> |
(...skipping 19 matching lines...) Expand all Loading... |
30 uint64_t CalculateNearestPowerOfTwo(uint64_t n) { | 30 uint64_t CalculateNearestPowerOfTwo(uint64_t n) { |
31 DCHECK_GT(n, 1u); | 31 DCHECK_GT(n, 1u); |
32 | 32 |
33 uint64_t ret = UINT64_C(1) << 63; | 33 uint64_t ret = UINT64_C(1) << 63; |
34 while (ret >= n) | 34 while (ret >= n) |
35 ret >>= 1; | 35 ret >>= 1; |
36 | 36 |
37 return ret; | 37 return ret; |
38 } | 38 } |
39 | 39 |
40 // The following structures, TestVector and ProofTestVector are used for | |
41 // definining test proofs later on. | |
42 | |
43 // A single hash node. | |
44 struct TestVector { | |
45 const char* const str; | |
46 size_t length_bytes; | |
47 }; | |
48 | |
49 // A single consistency proof. Contains the old and new tree sizes | 40 // A single consistency proof. Contains the old and new tree sizes |
50 // (snapshot1 and snapshot2), the length of the proof (proof_length) and | 41 // (snapshot1 and snapshot2), the length of the proof (proof_length) and |
51 // at most 3 proof nodes (all test proofs will be for a tree of size 8). | 42 // at most 3 proof nodes (all test proofs will be for a tree of size 8). |
52 struct ProofTestVector { | 43 struct ProofTestVector { |
53 uint64_t snapshot1; | 44 uint64_t snapshot1; |
54 uint64_t snapshot2; | 45 uint64_t snapshot2; |
55 size_t proof_length; | 46 size_t proof_length; |
56 TestVector proof[3]; | 47 const char* const proof[3]; |
57 }; | 48 }; |
58 | 49 |
59 // All test data replicated from | 50 // All test data replicated from |
60 // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531
dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc | 51 // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531
dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc |
61 // A hash of the empty string. | 52 // A hash of the empty string. |
62 const TestVector kSHA256EmptyTreeHash = { | 53 const uint8_t kSHA256EmptyTreeHash[32] = { |
63 "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32}; | 54 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, |
| 55 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, |
| 56 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55}; |
64 | 57 |
65 // Node hashes for a sample tree of size 8 (each element in this array is | 58 // Node hashes for a sample tree of size 8 (each element in this array is |
66 // a node hash, not leaf data; order represents order of the nodes in the tree). | 59 // a node hash, not leaf data; order represents order of the nodes in the tree). |
67 const TestVector kSHA256Roots[8] = { | 60 const char* const kSHA256Roots[8] = { |
68 {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32}, | 61 "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", |
69 {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32}, | 62 "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", |
70 {"aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 32}, | 63 "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", |
71 {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32}, | 64 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", |
72 {"4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 32}, | 65 "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", |
73 {"76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 32}, | 66 "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", |
74 {"ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32}, | 67 "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", |
75 {"5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32}}; | 68 "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"}; |
76 | 69 |
77 // A collection of consistency proofs between various sub-trees of the tree | 70 // A collection of consistency proofs between various sub-trees of the tree |
78 // defined by |kSHA256Roots|. | 71 // defined by |kSHA256Roots|. |
79 const ProofTestVector kSHA256Proofs[4] = { | 72 const ProofTestVector kSHA256Proofs[4] = { |
80 // Empty consistency proof between trees of the same size (1). | 73 // Empty consistency proof between trees of the same size (1). |
81 {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}}, | 74 {1, 1, 0, {"", "", ""}}, |
82 // Consistency proof between tree of size 1 and tree of size 8, with 3 | 75 // Consistency proof between tree of size 1 and tree of size 8, with 3 |
83 // nodes in the proof. | 76 // nodes in the proof. |
84 {1, | 77 {1, |
85 8, | 78 8, |
86 3, | 79 3, |
87 {{"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32}, | 80 {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", |
88 {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32}, | 81 "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", |
89 {"6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4", | 82 "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}}, |
90 32}}}, | |
91 // Consistency proof between tree of size 6 and tree of size 8, with 3 | 83 // Consistency proof between tree of size 6 and tree of size 8, with 3 |
92 // nodes in the proof. | 84 // nodes in the proof. |
93 {6, | 85 {6, |
94 8, | 86 8, |
95 3, | 87 3, |
96 {{"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", 32}, | 88 {"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", |
97 {"ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32}, | 89 "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", |
98 {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", | 90 "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}}, |
99 32}}}, | |
100 // Consistency proof between tree of size 2 and tree of size 5, with 2 | 91 // Consistency proof between tree of size 2 and tree of size 5, with 2 |
101 // nodes in the proof. | 92 // nodes in the proof. |
102 {2, | 93 {2, |
103 5, | 94 5, |
104 2, | 95 2, |
105 {{"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32}, | 96 {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", |
106 {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32}, | 97 "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", ""}}}; |
107 {"", 0}}}}; | |
108 | 98 |
109 // Decodes a hexadecimal string into the binary data it represents. | 99 // Decodes a hexadecimal string into the binary data it represents. |
110 std::string HexToBytes(const char* hex_data, size_t hex_data_length) { | 100 std::string HexToBytes(const std::string& hex_data) { |
111 std::vector<uint8_t> output; | 101 std::vector<uint8_t> output; |
112 std::string result; | 102 std::string result; |
113 std::string hex_data_input(hex_data, hex_data_length); | |
114 if (base::HexStringToBytes(hex_data, &output)) | 103 if (base::HexStringToBytes(hex_data, &output)) |
115 result.assign(reinterpret_cast<const char*>(&output[0]), output.size()); | 104 result.assign(output.begin(), output.end()); |
116 return result; | 105 return result; |
117 } | 106 } |
118 | 107 |
119 std::string GetEmptyTreeHash() { | 108 std::string GetEmptyTreeHash() { |
120 return HexToBytes(kSHA256EmptyTreeHash.str, | 109 return std::string(std::begin(kSHA256EmptyTreeHash), |
121 kSHA256EmptyTreeHash.length_bytes); | 110 std::end(kSHA256EmptyTreeHash)); |
122 } | 111 } |
123 | 112 |
124 // Creates a ct::MerkleConsistencyProof and returns the result of | 113 // Creates a ct::MerkleConsistencyProof and returns the result of |
125 // calling log->VerifyConsistencyProof with that proof and snapshots. | 114 // calling log->VerifyConsistencyProof with that proof and snapshots. |
126 bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log, | 115 bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log, |
127 uint64_t old_tree_size, | 116 uint64_t old_tree_size, |
128 const std::string& old_tree_root, | 117 const std::string& old_tree_root, |
129 uint64_t new_tree_size, | 118 uint64_t new_tree_size, |
130 const std::string& new_tree_root, | 119 const std::string& new_tree_root, |
131 const std::vector<std::string>& proof) { | 120 const std::vector<std::string>& proof) { |
(...skipping 243 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
375 } | 364 } |
376 | 365 |
377 TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) { | 366 TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) { |
378 std::vector<std::string> proof; | 367 std::vector<std::string> proof; |
379 std::string root1, root2; | 368 std::string root1, root2; |
380 | 369 |
381 // Known good proofs. | 370 // Known good proofs. |
382 for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) { | 371 for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) { |
383 proof.clear(); | 372 proof.clear(); |
384 for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) { | 373 for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) { |
385 const TestVector& v = kSHA256Proofs[i].proof[j]; | 374 const char* const v = kSHA256Proofs[i].proof[j]; |
386 proof.push_back(HexToBytes(v.str, v.length_bytes)); | 375 proof.push_back(HexToBytes(v)); |
387 } | 376 } |
388 const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1; | 377 const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1; |
389 const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2; | 378 const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2; |
390 const TestVector& old_root = kSHA256Roots[snapshot1 - 1]; | 379 const char* const old_root = kSHA256Roots[snapshot1 - 1]; |
391 const TestVector& new_root = kSHA256Roots[snapshot2 - 1]; | 380 const char* const new_root = kSHA256Roots[snapshot2 - 1]; |
392 VerifierConsistencyCheck( | 381 VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root), |
393 snapshot1, snapshot2, HexToBytes(old_root.str, old_root.length_bytes), | 382 HexToBytes(new_root), proof); |
394 HexToBytes(new_root.str, new_root.length_bytes), proof); | |
395 } | 383 } |
396 } | 384 } |
397 | 385 |
398 const char kLeafPrefix[] = {'\x00'}; | 386 const char kLeafPrefix[] = {'\x00'}; |
399 | 387 |
400 // Reference implementation of RFC6962. | 388 // Reference implementation of RFC6962. |
401 // This allows generation of arbitrary-sized Merkle trees and consistency | 389 // This allows generation of arbitrary-sized Merkle trees and consistency |
402 // proofs between them for testing the consistency proof validation | 390 // proofs between them for testing the consistency proof validation |
403 // code. | 391 // code. |
404 class TreeHasher { | 392 class TreeHasher { |
405 public: | 393 public: |
406 static std::string HashEmpty() { | |
407 return HexToBytes(kSHA256EmptyTreeHash.str, | |
408 kSHA256EmptyTreeHash.length_bytes); | |
409 } | |
410 | |
411 static std::string HashLeaf(const std::string& leaf) { | 394 static std::string HashLeaf(const std::string& leaf) { |
412 SHA256HashValue sha256; | 395 SHA256HashValue sha256; |
413 memset(sha256.data, 0, sizeof(sha256.data)); | 396 memset(sha256.data, 0, sizeof(sha256.data)); |
414 | 397 |
415 std::unique_ptr<crypto::SecureHash> hash( | 398 std::unique_ptr<crypto::SecureHash> hash( |
416 crypto::SecureHash::Create(crypto::SecureHash::SHA256)); | 399 crypto::SecureHash::Create(crypto::SecureHash::SHA256)); |
417 hash->Update(kLeafPrefix, 1); | 400 hash->Update(kLeafPrefix, 1); |
418 hash->Update(leaf.data(), leaf.size()); | 401 hash->Update(leaf.data(), leaf.size()); |
419 hash->Finish(sha256.data, sizeof(sha256.data)); | 402 hash->Finish(sha256.data, sizeof(sha256.data)); |
420 | 403 |
421 return std::string(reinterpret_cast<const char*>(sha256.data), | 404 return std::string(reinterpret_cast<const char*>(sha256.data), |
422 sizeof(sha256.data)); | 405 sizeof(sha256.data)); |
423 } | 406 } |
424 }; | 407 }; |
425 | 408 |
426 // Reference implementation of Merkle hash, for cross-checking. | 409 // Reference implementation of Merkle hash, for cross-checking. |
427 // Recursively calculates the hash of the root given the leaf data | 410 // Recursively calculates the hash of the root given the leaf data |
428 // specified in |inputs|. | 411 // specified in |inputs|. |
429 std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) { | 412 std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) { |
430 if (!input_size) | 413 if (!input_size) |
431 return TreeHasher::HashEmpty(); | 414 return GetEmptyTreeHash(); |
432 if (input_size == 1) | 415 if (input_size == 1) |
433 return TreeHasher::HashLeaf(inputs[0]); | 416 return TreeHasher::HashLeaf(inputs[0]); |
434 | 417 |
435 const uint64_t split = CalculateNearestPowerOfTwo(input_size); | 418 const uint64_t split = CalculateNearestPowerOfTwo(input_size); |
436 | 419 |
437 return ct::internal::HashNodes( | 420 return ct::internal::HashNodes( |
438 ReferenceMerkleTreeHash(&inputs[0], split), | 421 ReferenceMerkleTreeHash(&inputs[0], split), |
439 ReferenceMerkleTreeHash(&inputs[split], input_size - split)); | 422 ReferenceMerkleTreeHash(&inputs[split], input_size - split)); |
440 } | 423 } |
441 | 424 |
(...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
514 | 497 |
515 // Test verification of consistency proofs between all tree sizes from 1 to 128. | 498 // Test verification of consistency proofs between all tree sizes from 1 to 128. |
516 INSTANTIATE_TEST_CASE_P(RangeOfTreeSizesAndSnapshots, | 499 INSTANTIATE_TEST_CASE_P(RangeOfTreeSizesAndSnapshots, |
517 CTLogVerifierTestUsingReferenceGenerator, | 500 CTLogVerifierTestUsingReferenceGenerator, |
518 testing::Range(UINT64_C(1), | 501 testing::Range(UINT64_C(1), |
519 (kReferenceTreeSize / 2) + 1)); | 502 (kReferenceTreeSize / 2) + 1)); |
520 | 503 |
521 } // namespace | 504 } // namespace |
522 | 505 |
523 } // namespace net | 506 } // namespace net |
OLD | NEW |