pki: Import accumulated test vectors for Merkle Trees Copies the accumulated tests from the spec, which were already running on the crypto/x509 implementation, to also test the libpki implementation. Uses a common helper function in the crypto/x509 tests instead of duplicating the code. Fixes a bug in the test-only function to generate a subtree consistency proof that was missed when allowing empty subtrees in boringssl-review.googlesource.com/c/boringssl/+/102227. Bug: 452986180 Change-Id: I82d58acdd394102a91c104681dea80a56a6a6964 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/102527 Reviewed-by: David Benjamin <davidben@google.com> Auto-Submit: Lily Chen <chlily@google.com> Commit-Queue: Lily Chen <chlily@google.com>
diff --git a/crypto/x509/x509_test.cc b/crypto/x509/x509_test.cc index a83d5bc..57d5e4e 100644 --- a/crypto/x509/x509_test.cc +++ b/crypto/x509/x509_test.cc
@@ -17,8 +17,6 @@ #include <algorithm> #include <functional> #include <initializer_list> -#include <iomanip> -#include <ios> #include <iterator> #include <memory> #include <sstream> @@ -10860,6 +10858,7 @@ // Generate test entries compatible with the "accumulated" tests described // in appendix C of draft-ietf-plants-merkle-tree-certs. + entries_.reserve(limit); for (uint64_t index = entries_.size(); index < limit; ++index) { Entry entry; uint64_t num = index; @@ -11120,16 +11119,6 @@ std::vector<Level> levels_; }; -// Helper to format bytes as hex. -std::string ToHexStr(const std::vector<uint8_t> &bytes) { - std::stringstream hex; - hex << std::hex << std::setfill('0'); - for (uint8_t b : bytes) { - hex << std::setw(2) << static_cast<int>(b); - } - return hex.str(); -} - // This executes the "accumulated" Subtree Hashes test from appendix C.1 of // draft-ietf-plants-merkle-tree-certs. (This is more a test of the // X509MerkleTreeTest harness, to ensure that it is able to correctly test @@ -11147,7 +11136,7 @@ } std::stringstream ss; ss << "[" << std::to_string(start) << ", " << std::to_string(end) << ") " - << ToHexStr(GetSubtreeHash(start, end)) << "\n"; + << EncodeHex(GetSubtreeHash(start, end)) << "\n"; std::string str = ss.str(); EVP_DigestUpdate(ctx.get(), str.data(), str.size()); } @@ -11186,7 +11175,7 @@ << std::to_string(end) << ")"; for (const Hash &hash : GenerateSubtreeInclusionProof(index, start, end)) { - ss << " " << ToHexStr(hash); + ss << " " << EncodeHex(hash); } ss << "\n"; std::string str = ss.str();
diff --git a/pki/merkle_tree_unittest.cc b/pki/merkle_tree_unittest.cc index 39cb1a7..4738649 100644 --- a/pki/merkle_tree_unittest.cc +++ b/pki/merkle_tree_unittest.cc
@@ -17,12 +17,16 @@ #include <cassert> #include <cstdint> #include <limits> +#include <sstream> +#include <string> #include <gmock/gmock.h> #include <gtest/gtest.h> #include <openssl/digest.h> +#include <openssl/sha2.h> #include "../crypto/test/file_test.h" +#include "../crypto/test/test_util.h" BSSL_NAMESPACE_BEGIN @@ -40,6 +44,9 @@ BSSL_CHECK(tree.IsValid()); BSSL_CHECK(tree.Contains(subtree)); + if (subtree.Size() == 0) { + return {}; + } if (subtree == tree) { if (known_hash) { return {}; @@ -83,6 +90,18 @@ return entries; } +// Generates test entries compatible with the "accumulated" tests described +// in appendix C of draft-ietf-plants-merkle-tree-certs. +// This works for `n` up to 255. +std::vector<std::vector<uint8_t>> MakeAccumulatedTestEntries(size_t n) { + std::vector<std::vector<uint8_t>> entries; + entries.reserve(n); + for (size_t i = 0; i < n; i++) { + entries.push_back({static_cast<uint8_t>(i)}); + } + return entries; +} + std::vector<uint8_t> ConcatProof(const std::vector<TreeHash> &proof) { std::vector<uint8_t> out; for (const auto &p : proof) { @@ -129,6 +148,126 @@ EXPECT_EQ((Subtree{u64_max - 3, u64_max}).Split(), u64_max - 1); } +// This executes the "accumulated" Subtree Hashes test from appendix C.1 of +// draft-ietf-plants-merkle-tree-certs. +TEST(MerkleTreeTest, AccumulatedSubtreeHashes) { + auto entries = MakeAccumulatedTestEntries(256); + MerkleTreeInMemory tree(entries); + + ScopedEVP_MD_CTX ctx; + EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr); + + for (uint64_t end = 0; end < 131; ++end) { + for (uint64_t start = 0; start < end + 1; ++start) { + Subtree subtree{start, end}; + if (!subtree.IsValid()) { + continue; + } + std::stringstream ss; + ss << "[" << std::to_string(start) << ", " << std::to_string(end) << ") " + << EncodeHex(tree.SubtreeHash(subtree)) << "\n"; + std::string str = ss.str(); + EVP_DigestUpdate(ctx.get(), str.data(), str.size()); + } + } + std::vector<uint8_t> final(EVP_MAX_MD_SIZE); + unsigned final_size; + EVP_DigestFinal_ex(ctx.get(), final.data(), &final_size); + final.resize(final_size); + + const uint8_t kExpected[] = { + 0xb8, 0x28, 0x06, 0xad, 0x42, 0x65, 0xbb, 0x15, 0x1c, 0x11, 0x19, + 0xc0, 0xf4, 0xdb, 0x43, 0x7b, 0xb4, 0xd1, 0xa1, 0xf8, 0x87, 0xb3, + 0xa7, 0xfb, 0xa1, 0xcd, 0x4e, 0xbf, 0x55, 0x2e, 0x3e, 0x81, + }; + EXPECT_EQ(Bytes(final), Bytes(kExpected)); +} + +// This executes the "accumulated" Subtree Inclusion Proofs test from appendix +// C.2 of draft-ietf-plants-merkle-tree-certs. +TEST(MerkleTreeTest, AccumulatedSubtreeInclusionProofs) { + auto entries = MakeAccumulatedTestEntries(256); + MerkleTreeInMemory tree(entries); + + ScopedEVP_MD_CTX ctx; + EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr); + + for (uint64_t end = 0; end < 131; ++end) { + for (uint64_t start = 0; start < end + 1; ++start) { + Subtree subtree{start, end}; + if (!subtree.IsValid()) { + continue; + } + for (uint64_t index = start; index < end; ++index) { + std::stringstream ss; + ss << std::to_string(index) << " [" << std::to_string(start) << ", " + << std::to_string(end) << ")"; + auto proof = tree.SubtreeInclusionProof(index, subtree); + for (size_t i = 0; i < proof.size(); i += SHA256_DIGEST_LENGTH) { + ss << " " << EncodeHex(Span(proof).subspan(i, SHA256_DIGEST_LENGTH)); + } + ss << "\n"; + std::string str = ss.str(); + EVP_DigestUpdate(ctx.get(), str.data(), str.size()); + } + } + } + std::vector<uint8_t> final(EVP_MAX_MD_SIZE); + unsigned final_size; + EVP_DigestFinal_ex(ctx.get(), final.data(), &final_size); + final.resize(final_size); + + const uint8_t kExpected[] = { + 0xac, 0x2a, 0x8f, 0x98, 0x9e, 0x44, 0xd9, 0x9e, 0x39, 0x9d, 0xb4, + 0x48, 0x05, 0x0f, 0xf5, 0xf1, 0x97, 0x57, 0xdf, 0x53, 0xcf, 0xb7, + 0x16, 0xaa, 0x81, 0x01, 0x5d, 0x39, 0x55, 0xd8, 0x16, 0x3f, + }; + EXPECT_EQ(Bytes(final), Bytes(kExpected)); +} + +// This executes the "accumulated" Subtree Consistency Proofs test from appendix +// C.3 of draft-ietf-plants-merkle-tree-certs. +TEST(MerkleTreeTest, AccumulatedSubtreeConsistencyProofs) { + auto entries = MakeAccumulatedTestEntries(256); + MerkleTreeInMemory tree(entries); + + ScopedEVP_MD_CTX ctx; + EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr); + + for (size_t n = 0; n < 131; ++n) { + Subtree final_tree{0, n}; + for (uint64_t end = 0; end < n + 1; ++end) { + for (uint64_t start = 0; start < end + 1; ++start) { + Subtree subtree{start, end}; + if (!subtree.IsValid()) { + continue; + } + std::stringstream ss; + ss << "[" << std::to_string(start) << ", " << std::to_string(end) + << ") " << std::to_string(n); + auto proof = SubtreeConsistencyProof(tree, subtree, final_tree); + for (size_t i = 0; i < proof.size(); i += SHA256_DIGEST_LENGTH) { + ss << " " << EncodeHex(Span(proof).subspan(i, SHA256_DIGEST_LENGTH)); + } + ss << "\n"; + std::string str = ss.str(); + EVP_DigestUpdate(ctx.get(), str.data(), str.size()); + } + } + } + std::vector<uint8_t> final(EVP_MAX_MD_SIZE); + unsigned final_size; + EVP_DigestFinal_ex(ctx.get(), final.data(), &final_size); + final.resize(final_size); + + const uint8_t kExpected[] = { + 0x10, 0xfa, 0x99, 0xb3, 0x7b, 0xf9, 0xbf, 0x9f, 0xfa, 0x26, 0xb4, + 0x12, 0xfb, 0xd9, 0x8b, 0xd7, 0x53, 0x63, 0x25, 0x6d, 0x0b, 0x75, + 0xd6, 0x1b, 0xc4, 0x53, 0x8b, 0x9c, 0x9c, 0x5a, 0x0a, 0x74, + }; + EXPECT_EQ(Bytes(final), Bytes(kExpected)); +} + TEST(MerkleTreeTest, VerifySubtreeInclusionProof) { auto entries = MakeTestEntries("label", 847); MerkleTreeInMemory tree(entries);