pki: Allow Merkle subtrees of size 0 draft-ietf-plants-merkle-tree-certs-05 now allows subtrees with size 0 to be considered valid. This required tweaking the API for consistency proofs. The previously exposed "evaluate subtree consistency proof" function is unexported, because this operation is not well defined for an empty subtree, and that functionality is instead exposed as "verify subtree consistency proof", which now matches section 4.4.3 of the draft. Bug: 452986180 Change-Id: I735bdcaba357816d6102d258b72662666a6a6964 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/102227 Commit-Queue: Lily Chen <chlily@google.com> Reviewed-by: David Benjamin <davidben@google.com> Auto-Submit: Lily Chen <chlily@google.com>
diff --git a/pki/merkle_tree.cc b/pki/merkle_tree.cc index 2308a60..0e0d0b5 100644 --- a/pki/merkle_tree.cc +++ b/pki/merkle_tree.cc
@@ -47,6 +47,13 @@ } // namespace +// This value is equal to SHA256(""). +const TreeHash MerkleTree::kEmptySubtreeHash = { + 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, + 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, + 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55, +}; + // Computes HASH(0x01 || left || right) and saves the result to `out`. void HashNode(TreeHashConstSpan left, TreeHashConstSpan right, TreeHashSpan out) { @@ -68,12 +75,35 @@ SHA256_Final(out.data(), &ctx); } +namespace { + +// Performs the procedure defined in section 4.4.3 of +// draft-davidben-tls-merkle-tree-certs-08, Verifying a Subtree Consistency +// Proof: +// +// Given a Merkle Tree over `n` elements, a subtree defined by `[start, end)`, +// a consistency proof `proof`, a subtree hash `node_hash`, and a root hash +// `root_hash` +// +// The one difference between this function and the routine described in +// draft-davidben-tls-merkle-tree-certs-08 is that instead of taking `root_hash` +// as an input, this function returns the computed root hash and it is the +// caller's responsibility to verify that the computed root hash matches the +// expected root hash. This function returns std::nullopt if other steps of +// proof verification failed. +// +// This function does not accept empty subtrees, which are otherwise valid. For +// an empty subtree, the procedure to compute a root hash isn't coherent. If the +// subtree is empty, a consistency proof can only be verified, not evaluated. std::optional<TreeHash> EvaluateMerkleSubtreeConsistencyProof( uint64_t n, const Subtree &subtree, Span<const uint8_t> proof, TreeHashConstSpan node_hash) { // For more detail on how subtree consistency proofs work, see appendix B // of draft-davidben-tls-merkle-tree-certs-08. + // This function does not accept empty subtrees, which are otherwise valid. + assert(subtree.start < subtree.end); + // Check that inputs are valid. (Step 1) if (!subtree.IsValid() || n < subtree.end) { return std::nullopt; @@ -223,10 +253,29 @@ return computed_root_hash; } +} // namespace + +OPENSSL_EXPORT bool VerifyMerkleSubtreeConsistencyProof( + uint64_t n, const Subtree &subtree, Span<const uint8_t> proof, + TreeHashConstSpan node_hash, TreeHashConstSpan root_hash) { + // Special case for empty subtrees. + if (subtree.start == subtree.end) { + return proof.empty() && node_hash == MerkleTree::kEmptySubtreeHash; + } + + // Computation for non-empty subtrees. + std::optional<TreeHash> computed_root_hash = + EvaluateMerkleSubtreeConsistencyProof(n, subtree, proof, node_hash); + return computed_root_hash.has_value() && *computed_root_hash == root_hash; +} + std::optional<TreeHash> EvaluateMerkleSubtreeInclusionProof( Span<const uint8_t> inclusion_proof, uint64_t index, TreeHashConstSpan entry_hash, const Subtree &subtree) { - if (!subtree.IsValid() || !subtree.Contains(index)) { + if (!subtree.IsValid() || !subtree.Contains(index) || + // Empty subtrees, which are otherwise valid, must fail inclusion proof + // evaluation. + subtree.start == subtree.end) { return std::nullopt; } // Re-root `index` inside of `subtree`. @@ -239,6 +288,10 @@ BSSL_CHECK(subtree.IsValid()); BSSL_CHECK(subtree.end <= Size()); + if (subtree.Size() == 0) { + return kEmptySubtreeHash; + } + // Start at the largest complete subtree on the right edge. uint64_t start = subtree.start, last = subtree.end - 1; size_t level = TrailingOnes(last - start);
diff --git a/pki/merkle_tree.h b/pki/merkle_tree.h index 5c86db6..f049e6e 100644 --- a/pki/merkle_tree.h +++ b/pki/merkle_tree.h
@@ -72,9 +72,7 @@ // Returns whether [start, end) specifies a valid Subtree. constexpr bool IsValid() const { - // A Subtree must be a valid, non-empty interval. - // TODO(crbug.com/452986180): Empty subtrees are now considered valid. - if (start >= end) { + if (start > end) { return false; } uint64_t n = Size(); @@ -137,22 +135,17 @@ using TreeHashConstSpan = Span<const uint8_t, SHA256_DIGEST_LENGTH>; // Performs the procedure defined in section 4.4.3 of -// draft-davidben-tls-merkle-tree-certs-08, Verifying a Subtree Consistency +// draft-ietf-plants-merkle-tree-certs, Verifying a Subtree Consistency // Proof: // // Given a Merkle Tree over `n` elements, a subtree defined by `[start, end)`, // a consistency proof `proof`, a subtree hash `node_hash`, and a root hash // `root_hash` // -// The one difference between this function and the routine described in -// draft-davidben-tls-merkle-tree-certs-08 is that instead of taking `root_hash` -// as an input, this function returns the computed root hash and it is the -// caller's responsibility to verify that the computed root hash matches the -// expected root hash. This function returns std::nullopt if other steps of -// proof verification failed. -OPENSSL_EXPORT std::optional<TreeHash> EvaluateMerkleSubtreeConsistencyProof( +// Returns whether the consistency proof was accepted. +OPENSSL_EXPORT bool VerifyMerkleSubtreeConsistencyProof( uint64_t n, const Subtree &subtree, Span<const uint8_t> proof, - TreeHashConstSpan node_hash); + TreeHashConstSpan node_hash, TreeHashConstSpan root_hash); // Performs the procedure defined in section 4.3.2 of // draft-davidben-tls-merkle-tree-certs-08, Evaluating a Subtree Inclusion @@ -183,6 +176,9 @@ // full subtrees, but partial subtrees are computed dynamically. class OPENSSL_EXPORT MerkleTree { public: + // The subtree hash for any empty subtree. + static const TreeHash kEmptySubtreeHash; + virtual ~MerkleTree() = default; // Returns the number of leaves in the Merkle Tree.
diff --git a/pki/merkle_tree_unittest.cc b/pki/merkle_tree_unittest.cc index 8a3927d..39cb1a7 100644 --- a/pki/merkle_tree_unittest.cc +++ b/pki/merkle_tree_unittest.cc
@@ -92,8 +92,8 @@ } TEST(MerkleTreeTest, SubtreeIsValid) { - // An empty subtree is invalid. - EXPECT_FALSE((Subtree{0, 0}.IsValid())); + // An empty subtree is valid. + EXPECT_TRUE((Subtree{0, 0}.IsValid())); // But if the end is before start, it's invalid. EXPECT_FALSE((Subtree{1, 0}.IsValid())); // A subtree of the maximum expressible size is valid. @@ -137,12 +137,11 @@ auto node_hash = tree.SubtreeHash({index, index + 1}); Subtree subtree{0, 16}; auto proof = tree.SubtreeInclusionProof(index, subtree); - auto root_hash = EvaluateMerkleSubtreeConsistencyProof( - subtree.end, {index, index + 1}, proof, node_hash); - ASSERT_TRUE(root_hash.has_value()); - EXPECT_EQ(root_hash, tree.SubtreeHash(subtree)); + EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof( + subtree.end, {index, index + 1}, proof, node_hash, + tree.SubtreeHash(subtree))); // Check again with EvaluateMerkleSubtreeInclusionProof - root_hash = + auto root_hash = EvaluateMerkleSubtreeInclusionProof(proof, index, node_hash, subtree); ASSERT_TRUE(root_hash.has_value()); EXPECT_EQ(root_hash, tree.SubtreeHash(subtree)); @@ -152,11 +151,9 @@ node_hash = tree.SubtreeHash({index, index + 1}); subtree = {840, 847}; proof = tree.SubtreeInclusionProof(index, subtree); - root_hash = EvaluateMerkleSubtreeConsistencyProof( + EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof( subtree.Size(), {index - subtree.start, index - subtree.start + 1}, proof, - node_hash); - ASSERT_TRUE(root_hash.has_value()); - EXPECT_EQ(root_hash, tree.SubtreeHash(subtree)); + node_hash, tree.SubtreeHash(subtree))); // Check again with EvaluateMerkleSubtreeInclusionProof root_hash = EvaluateMerkleSubtreeInclusionProof(proof, index, node_hash, subtree); @@ -265,9 +262,8 @@ auto subtree_hash = tree.SubtreeHash(subtree); auto proof = SubtreeConsistencyProof(tree, subtree, full_tree); - auto computed_hash = - EvaluateMerkleSubtreeConsistencyProof(n, subtree, proof, subtree_hash); - EXPECT_EQ(computed_hash, tree_hash); + EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(n, subtree, proof, + subtree_hash, tree_hash)); } TEST(MerkleTreeTest, ValidProofs) { @@ -290,7 +286,7 @@ } // Exhaustively test subtree consistency proofs. - for (uint64_t n = 1; n < limit; n++) { + for (uint64_t n = 0; n < limit; n++) { Subtree full_tree{0, n}; auto tree_hash = tree.SubtreeHash(full_tree); for (uint64_t end = 0; end <= n; end++) { @@ -303,9 +299,8 @@ << start << ", end: " << end); auto subtree_hash = tree.SubtreeHash(subtree); auto proof = SubtreeConsistencyProof(tree, subtree, full_tree); - auto computed_hash = EvaluateMerkleSubtreeConsistencyProof( - n, subtree, proof, subtree_hash); - EXPECT_EQ(computed_hash, tree_hash); + EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof( + n, subtree, proof, subtree_hash, tree_hash)); } } } @@ -379,9 +374,9 @@ << ", end: " << subtree.end); auto proof = SubtreeConsistencyProof(tree, subtree, fullest_tree); - auto computed_root_hash = EvaluateMerkleSubtreeConsistencyProof( - fullest_tree.end, subtree, proof, tree.SubtreeHash(subtree)); - EXPECT_EQ(computed_root_hash, root_hash); + EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof( + fullest_tree.end, subtree, proof, tree.SubtreeHash(subtree), + root_hash)); } } @@ -449,49 +444,37 @@ } const Subtree subtree{start, end}; - // TODO(crbug.com/452986180): Temporary workaround to skip a test vector - // because empty subtrees are incorrectly considered invalid. - if (!subtree.IsValid()) { - return; - } - TreeHashConstSpan subtree_hash_span(subtree_hash); TreeHashConstSpan tree_hash_span(tree_hash); - auto computed_root_hash = EvaluateMerkleSubtreeConsistencyProof( - tree_size, subtree, proof, subtree_hash_span); - EXPECT_TRUE(computed_root_hash.has_value()); - EXPECT_EQ(*computed_root_hash, tree_hash_span); + EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof( + tree_size, subtree, proof, subtree_hash_span, tree_hash_span)); // Truncated consistency proofs don't work. const size_t original_proof_size = proof.size(); if (original_proof_size > 0) { - EXPECT_FALSE(EvaluateMerkleSubtreeConsistencyProof( + EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof( tree_size, subtree, Span(proof).subspan(original_proof_size - 1), - subtree_hash_span)); - EXPECT_FALSE(EvaluateMerkleSubtreeConsistencyProof( + subtree_hash_span, tree_hash_span)); + EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof( tree_size, subtree, Span(proof).subspan(original_proof_size - EVP_MD_size(EVP_sha256())), - subtree_hash_span)); + subtree_hash_span, tree_hash_span)); } // Extended consistency proofs don't work. proof.resize(original_proof_size + EVP_MD_size(EVP_sha256())); - EXPECT_FALSE(EvaluateMerkleSubtreeConsistencyProof( + EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof( tree_size, subtree, Span(proof).subspan(original_proof_size + 1), - subtree_hash_span)); - EXPECT_FALSE(EvaluateMerkleSubtreeConsistencyProof(tree_size, subtree, proof, - subtree_hash_span)); + subtree_hash_span, tree_hash_span)); + EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof( + tree_size, subtree, proof, subtree_hash_span, tree_hash_span)); - // Bitflipped input subtree hash should either fail to evaluate or produce a - // wrong tree hash. + // Bitflipped input subtree hash should either fail verification. proof.resize(original_proof_size); subtree_hash[0] ^= 1; - computed_root_hash = EvaluateMerkleSubtreeConsistencyProof( - tree_size, subtree, proof, subtree_hash_span); - if (computed_root_hash) { - EXPECT_NE(*computed_root_hash, tree_hash_span); - } + EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof( + tree_size, subtree, proof, subtree_hash_span, tree_hash_span)); } TEST(MerkleTreeTest, LargeConsistencyProofs) {