ct_log_verifier_unittest.cc 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757
  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
  3. // found in the LICENSE file.
  4. #include "net/cert/ct_log_verifier.h"
  5. #include <stdint.h>
  6. #include <memory>
  7. #include <string>
  8. #include <vector>
  9. #include "base/strings/string_number_conversions.h"
  10. #include "base/time/time.h"
  11. #include "crypto/secure_hash.h"
  12. #include "net/base/hash_value.h"
  13. #include "net/cert/ct_log_verifier_util.h"
  14. #include "net/cert/merkle_audit_proof.h"
  15. #include "net/cert/merkle_consistency_proof.h"
  16. #include "net/cert/signed_certificate_timestamp.h"
  17. #include "net/cert/signed_tree_head.h"
  18. #include "net/test/ct_test_util.h"
  19. #include "testing/gtest/include/gtest/gtest.h"
  20. namespace net {
  21. namespace {
  22. // Calculate the power of two nearest to, but less than, |n|.
  23. // |n| must be at least 2.
  24. size_t CalculateNearestPowerOfTwo(size_t n) {
  25. DCHECK_GT(n, 1u);
  26. size_t ret = size_t(1) << (sizeof(size_t) * 8 - 1);
  27. while (ret >= n)
  28. ret >>= 1;
  29. return ret;
  30. }
  31. // All test data replicated from
  32. // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc
  33. // The SHA-256 hash of an empty Merkle tree.
  34. const uint8_t kEmptyTreeHash[32] = {
  35. 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4,
  36. 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b,
  37. 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55};
  38. std::string GetEmptyTreeHash() {
  39. return std::string(std::begin(kEmptyTreeHash), std::end(kEmptyTreeHash));
  40. }
  41. // SHA-256 Merkle leaf hashes for the sample tree that all of the other test
  42. // data relates to (8 leaves).
  43. const char* const kLeafHashes[8] = {
  44. "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
  45. "96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
  46. "0298d122906dcfc10892cb53a73992fc5b9f493ea4c9badb27b791b4127a7fe7",
  47. "07506a85fd9dd2f120eb694f86011e5bb4662e5c415a62917033d4a9624487e7",
  48. "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
  49. "4271a26be0d8a84f0bd54c8c302e7cb3a3b5d1fa6780a40bcce2873477dab658",
  50. "b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f",
  51. "46f6ffadd3d06a09ff3c5860d2755c8b9819db7df44251788c7d8e3180de8eb1"};
  52. // SHA-256 Merkle root hashes from building the sample tree leaf-by-leaf.
  53. // The first entry is the root when the tree contains 1 leaf, and the last is
  54. // the root when the tree contains all 8 leaves.
  55. const char* const kRootHashes[8] = {
  56. "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
  57. "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125",
  58. "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77",
  59. "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
  60. "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4",
  61. "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef",
  62. "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c",
  63. "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"};
  64. // A single consistency proof. Contains at most 3 proof nodes (all test proofs
  65. // will be for a tree of size 8).
  66. struct ConsistencyProofTestVector {
  67. size_t old_tree_size;
  68. size_t new_tree_size;
  69. size_t proof_length;
  70. const char* const proof[3];
  71. };
  72. // A collection of consistency proofs between various sub-trees of the sample
  73. // tree.
  74. const ConsistencyProofTestVector kConsistencyProofs[] = {
  75. // Empty consistency proof between trees of the same size (1).
  76. {1, 1, 0, {"", "", ""}},
  77. // Consistency proof between tree of size 1 and tree of size 8, with 3
  78. // nodes in the proof.
  79. {1,
  80. 8,
  81. 3,
  82. {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
  83. "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
  84. "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}},
  85. // Consistency proof between tree of size 6 and tree of size 8, with 3
  86. // nodes in the proof.
  87. {6,
  88. 8,
  89. 3,
  90. {"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a",
  91. "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
  92. "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}},
  93. // Consistency proof between tree of size 2 and tree of size 5, with 2
  94. // nodes in the proof.
  95. {2,
  96. 5,
  97. 2,
  98. {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
  99. "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", ""}}};
  100. // A single audit proof. Contains at most 3 proof nodes (all test proofs will be
  101. // for a tree of size 8).
  102. struct AuditProofTestVector {
  103. size_t leaf;
  104. size_t tree_size;
  105. size_t proof_length;
  106. const char* const proof[3];
  107. };
  108. // A collection of audit proofs for various leaves and sub-trees of the tree
  109. // defined by |kRootHashes|.
  110. const AuditProofTestVector kAuditProofs[] = {
  111. {0, 1, 0, {"", "", ""}},
  112. {0,
  113. 8,
  114. 3,
  115. {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
  116. "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
  117. "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}},
  118. {5,
  119. 8,
  120. 3,
  121. {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
  122. "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
  123. "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}},
  124. {2,
  125. 3,
  126. 1,
  127. {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", "",
  128. ""}},
  129. {1,
  130. 5,
  131. 3,
  132. {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
  133. "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
  134. "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"}}};
  135. // Decodes a hexadecimal string into the binary data it represents.
  136. std::string HexToBytes(const std::string& hex_data) {
  137. std::string result;
  138. if (!base::HexStringToString(hex_data, &result))
  139. result.clear();
  140. return result;
  141. }
  142. // Constructs a consistency/audit proof from a test vector.
  143. // This is templated so that it can be used with both ConsistencyProofTestVector
  144. // and AuditProofTestVector.
  145. template <typename TestVectorType>
  146. std::vector<std::string> GetProof(const TestVectorType& test_vector) {
  147. std::vector<std::string> proof(test_vector.proof_length);
  148. std::transform(test_vector.proof,
  149. test_vector.proof + test_vector.proof_length, proof.begin(),
  150. &HexToBytes);
  151. return proof;
  152. }
  153. // Creates a ct::MerkleConsistencyProof from its arguments and returns the
  154. // result of passing this to log.VerifyConsistencyProof().
  155. bool VerifyConsistencyProof(const CTLogVerifier& log,
  156. size_t old_tree_size,
  157. const std::string& old_tree_root,
  158. size_t new_tree_size,
  159. const std::string& new_tree_root,
  160. const std::vector<std::string>& proof) {
  161. return log.VerifyConsistencyProof(
  162. ct::MerkleConsistencyProof(log.key_id(), proof, old_tree_size,
  163. new_tree_size),
  164. old_tree_root, new_tree_root);
  165. }
  166. // Creates a ct::MerkleAuditProof from its arguments and returns the result of
  167. // passing this to log.VerifyAuditProof().
  168. bool VerifyAuditProof(const CTLogVerifier& log,
  169. size_t leaf,
  170. size_t tree_size,
  171. const std::vector<std::string>& proof,
  172. const std::string& tree_root,
  173. const std::string& leaf_hash) {
  174. return log.VerifyAuditProof(ct::MerkleAuditProof(leaf, tree_size, proof),
  175. tree_root, leaf_hash);
  176. }
  177. class CTLogVerifierTest : public ::testing::Test {
  178. public:
  179. void SetUp() override {
  180. log_ = CTLogVerifier::Create(ct::GetTestPublicKey(), "testlog");
  181. ASSERT_TRUE(log_);
  182. EXPECT_EQ(ct::GetTestPublicKeyId(), log_->key_id());
  183. }
  184. protected:
  185. scoped_refptr<const CTLogVerifier> log_;
  186. };
  187. // Given an audit proof for a leaf in a Merkle tree, asserts that it verifies
  188. // and no other combination of leaves, tree sizes and proof nodes verifies.
  189. void CheckVerifyAuditProof(const CTLogVerifier& log,
  190. size_t leaf,
  191. size_t tree_size,
  192. const std::vector<std::string>& proof,
  193. const std::string& root_hash,
  194. const std::string& leaf_hash) {
  195. EXPECT_TRUE(
  196. VerifyAuditProof(log, leaf, tree_size, proof, root_hash, leaf_hash))
  197. << "proof for leaf " << leaf << " did not pass verification";
  198. EXPECT_FALSE(
  199. VerifyAuditProof(log, leaf - 1, tree_size, proof, root_hash, leaf_hash))
  200. << "proof passed verification with wrong leaf index";
  201. EXPECT_FALSE(
  202. VerifyAuditProof(log, leaf + 1, tree_size, proof, root_hash, leaf_hash))
  203. << "proof passed verification with wrong leaf index";
  204. EXPECT_FALSE(
  205. VerifyAuditProof(log, leaf ^ 2, tree_size, proof, root_hash, leaf_hash))
  206. << "proof passed verification with wrong leaf index";
  207. EXPECT_FALSE(
  208. VerifyAuditProof(log, leaf, tree_size * 2, proof, root_hash, leaf_hash))
  209. << "proof passed verification with wrong tree height";
  210. EXPECT_FALSE(VerifyAuditProof(log, leaf / 2, tree_size / 2, proof, root_hash,
  211. leaf_hash))
  212. << "proof passed verification with wrong leaf index and tree height";
  213. EXPECT_FALSE(
  214. VerifyAuditProof(log, leaf, tree_size / 2, proof, root_hash, leaf_hash))
  215. << "proof passed verification with wrong tree height";
  216. EXPECT_FALSE(VerifyAuditProof(log, leaf, tree_size, proof, GetEmptyTreeHash(),
  217. leaf_hash))
  218. << "proof passed verification with wrong root hash";
  219. std::vector<std::string> wrong_proof;
  220. // Modify a single element on the proof.
  221. for (size_t j = 0; j < proof.size(); ++j) {
  222. wrong_proof = proof;
  223. wrong_proof[j] = GetEmptyTreeHash();
  224. EXPECT_FALSE(VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash,
  225. leaf_hash))
  226. << "proof passed verification with one wrong node (node " << j << ")";
  227. }
  228. wrong_proof = proof;
  229. wrong_proof.emplace_back();
  230. EXPECT_FALSE(
  231. VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
  232. << "proof passed verification with an empty node appended";
  233. wrong_proof.back() = root_hash;
  234. EXPECT_FALSE(
  235. VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
  236. << "proof passed verification with an incorrect node appended";
  237. wrong_proof.pop_back();
  238. if (!wrong_proof.empty()) {
  239. wrong_proof.pop_back();
  240. EXPECT_FALSE(VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash,
  241. leaf_hash))
  242. << "proof passed verification with the last node missing";
  243. }
  244. wrong_proof.clear();
  245. wrong_proof.emplace_back();
  246. wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
  247. EXPECT_FALSE(
  248. VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
  249. << "proof passed verification with an empty node prepended";
  250. wrong_proof[0] = root_hash;
  251. EXPECT_FALSE(
  252. VerifyAuditProof(log, leaf, tree_size, wrong_proof, root_hash, leaf_hash))
  253. << "proof passed verification with an incorrect node prepended";
  254. }
  255. // Given a consistency proof between two snapshots of the tree, asserts that it
  256. // verifies and no other combination of tree sizes and proof nodes verifies.
  257. void CheckVerifyConsistencyProof(const CTLogVerifier& log,
  258. int old_tree_size,
  259. int new_tree_size,
  260. const std::string& old_root,
  261. const std::string& new_root,
  262. const std::vector<std::string>& proof) {
  263. // Verify the original consistency proof.
  264. EXPECT_TRUE(VerifyConsistencyProof(log, old_tree_size, old_root,
  265. new_tree_size, new_root, proof))
  266. << "proof between trees of size " << old_tree_size << " and "
  267. << new_tree_size << " did not pass verification";
  268. if (proof.empty()) {
  269. // For simplicity test only non-trivial proofs that have old_root !=
  270. // new_root
  271. // old_tree_size != 0 and old_tree_size != new_tree_size.
  272. return;
  273. }
  274. // Wrong tree size: The proof checking code should not accept as a valid proof
  275. // a proof for a tree size different than the original size it was produced
  276. // for. Test that this is not the case for off-by-one changes.
  277. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size - 1, old_root,
  278. new_tree_size, new_root, proof))
  279. << "proof passed verification with old tree size - 1";
  280. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size + 1, old_root,
  281. new_tree_size, new_root, proof))
  282. << "proof passed verification with old tree size + 1";
  283. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size ^ 2, old_root,
  284. new_tree_size, new_root, proof))
  285. << "proof passed verification with old tree size ^ 2";
  286. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  287. new_tree_size * 2, new_root, proof))
  288. << "proof passed verification with new tree height + 1";
  289. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  290. new_tree_size / 2, new_root, proof))
  291. << "proof passed verification with new tree height - 1";
  292. const std::string wrong_root("WrongRoot");
  293. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  294. new_tree_size, wrong_root, proof))
  295. << "proof passed verification with wrong old root";
  296. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, wrong_root,
  297. new_tree_size, new_root, proof))
  298. << "proof passed verification with wrong new root";
  299. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, new_root,
  300. new_tree_size, old_root, proof))
  301. << "proof passed verification with old and new root swapped";
  302. // Variations of wrong proofs, all of which should be rejected.
  303. std::vector<std::string> wrong_proof;
  304. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  305. new_tree_size, new_root, wrong_proof))
  306. << "empty proof passed verification";
  307. // Modify a single element in the proof.
  308. for (size_t j = 0; j < proof.size(); ++j) {
  309. wrong_proof = proof;
  310. wrong_proof[j] = GetEmptyTreeHash();
  311. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  312. new_tree_size, new_root, wrong_proof))
  313. << "proof passed verification with incorrect node (node " << j << ")";
  314. }
  315. wrong_proof = proof;
  316. wrong_proof.emplace_back();
  317. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  318. new_tree_size, new_root, wrong_proof))
  319. << "proof passed verification with empty node appended";
  320. wrong_proof.back() = proof.back();
  321. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  322. new_tree_size, new_root, wrong_proof))
  323. << "proof passed verification with last node duplicated";
  324. wrong_proof.pop_back();
  325. wrong_proof.pop_back();
  326. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  327. new_tree_size, new_root, wrong_proof))
  328. << "proof passed verification with last node missing";
  329. wrong_proof.clear();
  330. wrong_proof.emplace_back();
  331. wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
  332. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  333. new_tree_size, new_root, wrong_proof))
  334. << "proof passed verification with empty node prepended";
  335. wrong_proof[0] = proof[0];
  336. EXPECT_FALSE(VerifyConsistencyProof(log, old_tree_size, old_root,
  337. new_tree_size, new_root, wrong_proof))
  338. << "proof passed verification with first node duplicated";
  339. }
  340. TEST_F(CTLogVerifierTest, VerifiesCertSCT) {
  341. ct::SignedEntryData cert_entry;
  342. ct::GetX509CertSignedEntry(&cert_entry);
  343. scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
  344. ct::GetX509CertSCT(&cert_sct);
  345. EXPECT_TRUE(log_->Verify(cert_entry, *cert_sct.get()));
  346. }
  347. TEST_F(CTLogVerifierTest, VerifiesPrecertSCT) {
  348. ct::SignedEntryData precert_entry;
  349. ct::GetPrecertSignedEntry(&precert_entry);
  350. scoped_refptr<ct::SignedCertificateTimestamp> precert_sct;
  351. ct::GetPrecertSCT(&precert_sct);
  352. EXPECT_TRUE(log_->Verify(precert_entry, *precert_sct.get()));
  353. }
  354. TEST_F(CTLogVerifierTest, FailsInvalidTimestamp) {
  355. ct::SignedEntryData cert_entry;
  356. ct::GetX509CertSignedEntry(&cert_entry);
  357. scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
  358. ct::GetX509CertSCT(&cert_sct);
  359. // Mangle the timestamp, so that it should fail signature validation.
  360. cert_sct->timestamp = base::Time::Now();
  361. EXPECT_FALSE(log_->Verify(cert_entry, *cert_sct.get()));
  362. }
  363. TEST_F(CTLogVerifierTest, FailsInvalidLogID) {
  364. ct::SignedEntryData cert_entry;
  365. ct::GetX509CertSignedEntry(&cert_entry);
  366. scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
  367. ct::GetX509CertSCT(&cert_sct);
  368. // Mangle the log ID, which should cause it to match a different log before
  369. // attempting signature validation.
  370. cert_sct->log_id.assign(cert_sct->log_id.size(), '\0');
  371. EXPECT_FALSE(log_->Verify(cert_entry, *cert_sct.get()));
  372. }
  373. TEST_F(CTLogVerifierTest, VerifiesValidSTH) {
  374. ct::SignedTreeHead sth;
  375. ASSERT_TRUE(ct::GetSampleSignedTreeHead(&sth));
  376. EXPECT_TRUE(log_->VerifySignedTreeHead(sth));
  377. }
  378. TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidSTH) {
  379. ct::SignedTreeHead sth;
  380. ASSERT_TRUE(ct::GetSampleSignedTreeHead(&sth));
  381. sth.sha256_root_hash[0] = '\x0';
  382. EXPECT_FALSE(log_->VerifySignedTreeHead(sth));
  383. }
  384. TEST_F(CTLogVerifierTest, VerifiesValidEmptySTH) {
  385. ct::SignedTreeHead sth;
  386. ASSERT_TRUE(ct::GetSampleEmptySignedTreeHead(&sth));
  387. EXPECT_TRUE(log_->VerifySignedTreeHead(sth));
  388. }
  389. TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidEmptySTH) {
  390. ct::SignedTreeHead sth;
  391. ASSERT_TRUE(ct::GetBadEmptySignedTreeHead(&sth));
  392. EXPECT_FALSE(log_->VerifySignedTreeHead(sth));
  393. }
  394. // Test that excess data after the public key is rejected.
  395. TEST_F(CTLogVerifierTest, ExcessDataInPublicKey) {
  396. std::string key = ct::GetTestPublicKey();
  397. key += "extra";
  398. scoped_refptr<const CTLogVerifier> log =
  399. CTLogVerifier::Create(key, "testlog");
  400. EXPECT_FALSE(log);
  401. }
  402. TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_EmptyProof) {
  403. std::vector<std::string> empty_proof;
  404. std::string old_root(GetEmptyTreeHash()), new_root(GetEmptyTreeHash());
  405. // Tree snapshots that are always consistent, because the proofs are either
  406. // from an empty tree to a non-empty one or for trees of the same size.
  407. EXPECT_TRUE(
  408. VerifyConsistencyProof(*log_, 0, old_root, 0, new_root, empty_proof));
  409. EXPECT_TRUE(
  410. VerifyConsistencyProof(*log_, 0, old_root, 1, new_root, empty_proof));
  411. EXPECT_TRUE(
  412. VerifyConsistencyProof(*log_, 1, old_root, 1, new_root, empty_proof));
  413. // Invalid consistency proofs.
  414. // Time travel to the past.
  415. EXPECT_FALSE(
  416. VerifyConsistencyProof(*log_, 1, old_root, 0, new_root, empty_proof));
  417. EXPECT_FALSE(
  418. VerifyConsistencyProof(*log_, 2, old_root, 1, new_root, empty_proof));
  419. // Proof between two trees of different size can never be empty.
  420. EXPECT_FALSE(
  421. VerifyConsistencyProof(*log_, 1, old_root, 2, new_root, empty_proof));
  422. }
  423. TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_MismatchingRoots) {
  424. const std::string old_root(GetEmptyTreeHash());
  425. std::string new_root;
  426. std::vector<std::string> empty_proof;
  427. // Roots don't match.
  428. EXPECT_FALSE(
  429. VerifyConsistencyProof(*log_, 0, old_root, 0, new_root, empty_proof));
  430. EXPECT_FALSE(
  431. VerifyConsistencyProof(*log_, 1, old_root, 1, new_root, empty_proof));
  432. }
  433. TEST_F(CTLogVerifierTest,
  434. VerifiesConsistencyProofEdgeCases_MatchingRootsNonEmptyProof) {
  435. const std::string empty_tree_hash(GetEmptyTreeHash());
  436. std::vector<std::string> proof;
  437. proof.push_back(empty_tree_hash);
  438. // Roots match and the tree size is either the same or the old tree size is 0,
  439. // but the proof is not empty (the verification code should not accept
  440. // proofs with redundant nodes in this case).
  441. proof.push_back(empty_tree_hash);
  442. EXPECT_FALSE(VerifyConsistencyProof(*log_, 0, empty_tree_hash, 0,
  443. empty_tree_hash, proof));
  444. EXPECT_FALSE(VerifyConsistencyProof(*log_, 0, empty_tree_hash, 1,
  445. empty_tree_hash, proof));
  446. EXPECT_FALSE(VerifyConsistencyProof(*log_, 1, empty_tree_hash, 1,
  447. empty_tree_hash, proof));
  448. }
  449. class CTLogVerifierConsistencyProofTest
  450. : public CTLogVerifierTest,
  451. public ::testing::WithParamInterface<size_t /* proof index */> {};
  452. // Checks that a sample set of valid consistency proofs verify successfully.
  453. TEST_P(CTLogVerifierConsistencyProofTest, VerifiesValidConsistencyProof) {
  454. const ConsistencyProofTestVector& test_vector =
  455. kConsistencyProofs[GetParam()];
  456. const std::vector<std::string> proof = GetProof(test_vector);
  457. const char* const old_root = kRootHashes[test_vector.old_tree_size - 1];
  458. const char* const new_root = kRootHashes[test_vector.new_tree_size - 1];
  459. CheckVerifyConsistencyProof(*log_, test_vector.old_tree_size,
  460. test_vector.new_tree_size, HexToBytes(old_root),
  461. HexToBytes(new_root), proof);
  462. }
  463. INSTANTIATE_TEST_SUITE_P(KnownGoodProofs,
  464. CTLogVerifierConsistencyProofTest,
  465. ::testing::Range(size_t(0),
  466. std::size(kConsistencyProofs)));
  467. class CTLogVerifierAuditProofTest
  468. : public CTLogVerifierTest,
  469. public ::testing::WithParamInterface<size_t /* proof index */> {};
  470. // Checks that a sample set of valid audit proofs verify successfully.
  471. TEST_P(CTLogVerifierAuditProofTest, VerifiesValidAuditProofs) {
  472. const AuditProofTestVector& test_vector = kAuditProofs[GetParam()];
  473. const std::vector<std::string> proof = GetProof(test_vector);
  474. const char* const root_hash = kRootHashes[test_vector.tree_size - 1];
  475. CheckVerifyAuditProof(*log_, test_vector.leaf, test_vector.tree_size, proof,
  476. HexToBytes(root_hash),
  477. HexToBytes(kLeafHashes[test_vector.leaf]));
  478. }
  479. INSTANTIATE_TEST_SUITE_P(KnownGoodProofs,
  480. CTLogVerifierAuditProofTest,
  481. ::testing::Range(size_t(0), std::size(kAuditProofs)));
  482. TEST_F(CTLogVerifierTest, VerifiesAuditProofEdgeCases_InvalidLeafIndex) {
  483. std::vector<std::string> proof;
  484. EXPECT_FALSE(
  485. VerifyAuditProof(*log_, 1, 0, proof, std::string(), std::string()));
  486. EXPECT_FALSE(
  487. VerifyAuditProof(*log_, 2, 1, proof, std::string(), std::string()));
  488. const std::string empty_hash = GetEmptyTreeHash();
  489. EXPECT_FALSE(VerifyAuditProof(*log_, 1, 0, proof, empty_hash, std::string()));
  490. EXPECT_FALSE(VerifyAuditProof(*log_, 2, 1, proof, empty_hash, std::string()));
  491. }
  492. // Functions that implement algorithms from RFC6962 necessary for constructing
  493. // Merkle trees and proofs. This allows tests to generate a variety of trees
  494. // for exhaustive testing.
  495. namespace rfc6962 {
  496. // Calculates the hash of a leaf in a Merkle tree, given its content.
  497. // See RFC6962, section 2.1.
  498. std::string HashLeaf(const std::string& leaf) {
  499. const char kLeafPrefix[] = {'\x00'};
  500. SHA256HashValue sha256;
  501. memset(sha256.data, 0, sizeof(sha256.data));
  502. std::unique_ptr<crypto::SecureHash> hash(
  503. crypto::SecureHash::Create(crypto::SecureHash::SHA256));
  504. hash->Update(kLeafPrefix, 1);
  505. hash->Update(leaf.data(), leaf.size());
  506. hash->Finish(sha256.data, sizeof(sha256.data));
  507. return std::string(reinterpret_cast<const char*>(sha256.data),
  508. sizeof(sha256.data));
  509. }
  510. // Calculates the root hash of a Merkle tree, given its leaf data and size.
  511. // See RFC6962, section 2.1.
  512. std::string HashTree(std::string leaves[], size_t tree_size) {
  513. if (tree_size == 0)
  514. return GetEmptyTreeHash();
  515. if (tree_size == 1)
  516. return HashLeaf(leaves[0]);
  517. // Find the index of the last leaf in the left sub-tree.
  518. const size_t split = CalculateNearestPowerOfTwo(tree_size);
  519. // Hash the left and right sub-trees, then hash the results.
  520. return ct::internal::HashNodes(HashTree(leaves, split),
  521. HashTree(&leaves[split], tree_size - split));
  522. }
  523. // Returns a Merkle audit proof for the leaf with index |leaf_index|.
  524. // The tree consists of |leaves[0]| to |leaves[tree_size-1]|.
  525. // If |leaf_index| is >= |tree_size|, an empty proof will be returned.
  526. // See RFC6962, section 2.1.1, for more details.
  527. std::vector<std::string> CreateAuditProof(std::string leaves[],
  528. size_t tree_size,
  529. size_t leaf_index) {
  530. std::vector<std::string> proof;
  531. if (leaf_index >= tree_size)
  532. return proof;
  533. if (tree_size == 1)
  534. return proof;
  535. // Find the index of the first leaf in the right sub-tree.
  536. const size_t split = CalculateNearestPowerOfTwo(tree_size);
  537. // Recurse down the correct branch of the tree (left or right) to reach the
  538. // leaf with |leaf_index|. Add the hash of the branch not taken at each step
  539. // on the way up to build the proof.
  540. if (leaf_index < split) {
  541. proof = CreateAuditProof(leaves, split, leaf_index);
  542. proof.push_back(HashTree(&leaves[split], tree_size - split));
  543. } else {
  544. proof =
  545. CreateAuditProof(&leaves[split], tree_size - split, leaf_index - split);
  546. proof.push_back(HashTree(leaves, split));
  547. }
  548. return proof;
  549. }
  550. // Returns a Merkle consistency proof between two Merkle trees.
  551. // The old tree contains |leaves[0]| to |leaves[old_tree_size-1]|.
  552. // The new tree contains |leaves[0]| to |leaves[new_tree_size-1]|.
  553. // Call with |contains_old_tree| = true.
  554. // See RFC6962, section 2.1.2, for more details.
  555. std::vector<std::string> CreateConsistencyProof(std::string leaves[],
  556. size_t new_tree_size,
  557. size_t old_tree_size,
  558. bool contains_old_tree = true) {
  559. std::vector<std::string> proof;
  560. if (old_tree_size == 0 || old_tree_size > new_tree_size)
  561. return proof;
  562. if (old_tree_size == new_tree_size) {
  563. // Consistency proof for two equal subtrees is empty.
  564. if (!contains_old_tree) {
  565. // Record the hash of this subtree unless it's the root for which
  566. // the proof was originally requested. (This happens when the old tree is
  567. // balanced).
  568. proof.push_back(HashTree(leaves, old_tree_size));
  569. }
  570. return proof;
  571. }
  572. // Find the index of the last leaf in the left sub-tree.
  573. const size_t split = CalculateNearestPowerOfTwo(new_tree_size);
  574. if (old_tree_size <= split) {
  575. // Root of the old tree is in the left subtree of the new tree.
  576. // Prove that the left subtrees are consistent.
  577. proof =
  578. CreateConsistencyProof(leaves, split, old_tree_size, contains_old_tree);
  579. // Record the hash of the right subtree (only present in the new tree).
  580. proof.push_back(HashTree(&leaves[split], new_tree_size - split));
  581. } else {
  582. // The old tree root is at the same level as the new tree root.
  583. // Prove that the right subtrees are consistent. The right subtree
  584. // doesn't contain the root of the old tree, so set contains_old_tree =
  585. // false.
  586. proof = CreateConsistencyProof(&leaves[split], new_tree_size - split,
  587. old_tree_size - split,
  588. /* contains_old_tree = */ false);
  589. // Record the hash of the left subtree (equal in both trees).
  590. proof.push_back(HashTree(leaves, split));
  591. }
  592. return proof;
  593. }
  594. } // namespace rfc6962
  595. class CTLogVerifierTestUsingGenerator
  596. : public CTLogVerifierTest,
  597. public ::testing::WithParamInterface<size_t /* tree_size */> {};
  598. // Checks that valid consistency proofs for a range of generated Merkle trees
  599. // verify successfully.
  600. TEST_P(CTLogVerifierTestUsingGenerator, VerifiesValidConsistencyProof) {
  601. const size_t tree_size = GetParam();
  602. std::vector<std::string> tree_leaves(tree_size);
  603. for (size_t i = 0; i < tree_size; ++i)
  604. tree_leaves[i].push_back(static_cast<char>(i));
  605. const std::string tree_root =
  606. rfc6962::HashTree(tree_leaves.data(), tree_size);
  607. // Check consistency proofs for every sub-tree.
  608. for (size_t old_tree_size = 0; old_tree_size <= tree_size; ++old_tree_size) {
  609. SCOPED_TRACE(old_tree_size);
  610. const std::string old_tree_root =
  611. rfc6962::HashTree(tree_leaves.data(), old_tree_size);
  612. const std::vector<std::string> proof = rfc6962::CreateConsistencyProof(
  613. tree_leaves.data(), tree_size, old_tree_size);
  614. // Checks that the consistency proof verifies only with the correct tree
  615. // sizes and root hashes.
  616. CheckVerifyConsistencyProof(*log_, old_tree_size, tree_size, old_tree_root,
  617. tree_root, proof);
  618. }
  619. }
  620. // Checks that valid audit proofs for a range of generated Merkle trees verify
  621. // successfully.
  622. TEST_P(CTLogVerifierTestUsingGenerator, VerifiesValidAuditProofs) {
  623. const size_t tree_size = GetParam();
  624. std::vector<std::string> tree_leaves(tree_size);
  625. for (size_t i = 0; i < tree_size; ++i)
  626. tree_leaves[i].push_back(static_cast<char>(i));
  627. const std::string root = rfc6962::HashTree(tree_leaves.data(), tree_size);
  628. // Check audit proofs for every leaf in the tree.
  629. for (size_t leaf = 0; leaf < tree_size; ++leaf) {
  630. SCOPED_TRACE(leaf);
  631. std::vector<std::string> proof =
  632. rfc6962::CreateAuditProof(tree_leaves.data(), tree_size, leaf);
  633. // Checks that the audit proof verifies only for this leaf data, index,
  634. // hash, tree size and root hash.
  635. CheckVerifyAuditProof(*log_, leaf, tree_size, proof, root,
  636. rfc6962::HashLeaf(tree_leaves[leaf]));
  637. }
  638. }
  639. // Test verification of consistency proofs and audit proofs for all tree sizes
  640. // from 0 to 128.
  641. INSTANTIATE_TEST_SUITE_P(RangeOfTreeSizes,
  642. CTLogVerifierTestUsingGenerator,
  643. testing::Range(size_t(0), size_t(129)));
  644. } // namespace
  645. } // namespace net