| 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 |