pki: Add trusted subtrees to CertificateTrust Makes the trusted_subtrees_ field of MTCAnchor store it as a std::shared_ptr, which is then copied into the CertificateTrust representing the MTCAnchor. Along the way, remove constexpr from CertificateTrust, and make a new type, TrustedSubtreeSet, holding a std::vector<LogTrustedSubtrees> to handle validation and lookup of trusted subtrees. After this change, logic for handling trusted subtrees no longer lives in MTCAnchor. Changes the TrustAnchor::CertTrust() getter to return a reference since CertificateTrust copies are no longer free. This is a step towards making trust anchors uniformly representable as a (ParsedCertificate, CertificateTrust) pair, pivoting away from the earlier plan of migrating the representation of all trust anchors to the TrustAnchor type. Bug: 575507260 Change-Id: I45aea0a3f0a1f1e75093d8b8408ec3086a6a6964 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/104988 Presubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Matt Mueller <mattm@google.com> Reviewed-by: David Benjamin <davidben@google.com> Commit-Queue: Lily Chen <chlily@google.com>
diff --git a/pki/trust_store.cc b/pki/trust_store.cc index 291c30a..fd31acb 100644 --- a/pki/trust_store.cc +++ b/pki/trust_store.cc
@@ -53,6 +53,92 @@ } // namespace +TrustedSubtreeSet::TrustedSubtreeSet( + TrustedSubtreeSet::Token, std::vector<LogTrustedSubtrees> trusted_subtrees) + : trusted_subtrees_(std::move(trusted_subtrees)) {} + +// static +std::shared_ptr<const TrustedSubtreeSet> TrustedSubtreeSet::Create( + std::vector<LogTrustedSubtrees> trusted_subtrees) { + if (!IsValid(trusted_subtrees)) { + return nullptr; + } + return std::make_shared<TrustedSubtreeSet>(Token(), + std::move(trusted_subtrees)); +} + +std::optional<TreeHashConstSpan> TrustedSubtreeSet::LookupSubtreeHash( + uint16_t log_number, Subtree target_range) const { + // The `trusted_subtrees_` is generally expected to have one, or rarely two, + // elements, so just using a simple find rather than a binary search. + auto subtrees_it = + std::find_if(trusted_subtrees_.begin(), trusted_subtrees_.end(), + [log_number](const LogTrustedSubtrees &logsubtree) -> bool { + return logsubtree.log_number == log_number; + }); + if (subtrees_it == trusted_subtrees_.end()) { + return std::nullopt; + } + + const auto &subtrees = subtrees_it->trusted_subtrees; + auto it = std::lower_bound( + subtrees.begin(), subtrees.end(), target_range, + [](const TrustedSubtree &subtree, Subtree range) -> bool { + return subtree.range < range; + }); + if (it == subtrees.end() || it->range != target_range) { + return std::nullopt; + } + return it->hash; +} + +std::string TrustedSubtreeSet::DebugString() const { + if (trusted_subtrees_.empty()) { + return "none"; + } + std::string result; + + for (const auto &[log_number, subtrees] : trusted_subtrees_) { + if (!result.empty()) { + result += ", "; + } + result += "log " + std::to_string(log_number) + ":"; + if (subtrees.empty()) { + result += "empty"; + } else { + // Just showing the start of first range to end of last range is an + // oversimplification, but showing every single range is probably too + // verbose. + result += std::to_string(subtrees.size()) + " subtrees(" + + std::to_string(subtrees.front().range.start) + ".." + + std::to_string(subtrees.back().range.end) + ")"; + } + } + return result; +} + +// static +bool TrustedSubtreeSet::IsValid( + const std::vector<LogTrustedSubtrees> &trusted_subtrees) { + uint16_t min_log_number = 0; + for (const auto &[log_number, subtrees] : trusted_subtrees) { + if (log_number <= min_log_number) { + // Log numbers must be greater than zero, and `trusted_subtrees` must be + // in sorted order without repeated log numbers. + return false; + } + min_log_number = log_number; + Subtree min_subtree; + for (const auto &subtree : subtrees) { + if (!subtree.range.IsValid() || subtree.range < min_subtree) { + return false; + } + min_subtree = subtree.range; + } + } + return true; +} + bool CertificateTrust::IsTrustAnchor() const { switch (type) { case CertificateTrustType::DISTRUSTED: @@ -148,6 +234,11 @@ result += '+'; result += kRequireLeafSelfsigned; } + if (trusted_subtrees != nullptr) { + result += "+trusted_subtrees("; + result += trusted_subtrees->DebugString(); + result += ')'; + } return result; } @@ -223,31 +314,13 @@ ca_id_(ca_id.begin(), ca_id.end()), ca_signature_algorithm_(ca_signature_algorithm), ca_key_(std::move(ca_key)), - trusted_subtrees_(std::move(log_trusted_subtrees)) { + trusted_subtrees_( + TrustedSubtreeSet::Create(std::move(log_trusted_subtrees))) { CreateSyntheticCert(ca_id); } bool MTCAnchor::IsValid() const { - if (!synthetic_cert_) { - return false; - } - uint16_t min_log_number = 0; - for (const auto &[log_number, subtrees] : trusted_subtrees_) { - if (log_number <= min_log_number) { - // Log numbers must be greater than zero, and `trusted_subtrees_` must be - // in sorted order without repeated log numbers. - return false; - } - min_log_number = log_number; - Subtree min_subtree; - for (const auto &subtree : subtrees) { - if (!subtree.range.IsValid() || subtree.range < min_subtree) { - return false; - } - min_subtree = subtree.range; - } - } - return true; + return synthetic_cert_ != nullptr && trusted_subtrees_ != nullptr; } der::Input MTCAnchor::NormalizedSubject() const { @@ -257,6 +330,7 @@ CertificateTrust MTCAnchor::CertTrust() const { CertificateTrust trust; trust.type = CertificateTrustType::TRUSTED_ANCHOR; + trust.trusted_subtrees = trusted_subtrees_; return trust; } @@ -265,54 +339,18 @@ } std::optional<TreeHashConstSpan> MTCAnchor::SubtreeHash( - uint16_t log_number, - Subtree target_range) const { - // The `trusted_subtrees_` is generally expected to have one, or rarely two, - // elements, so just using a simple find rather than a binary search. - auto subtrees_it = std::find_if( - trusted_subtrees_.begin(), trusted_subtrees_.end(), - [log_number](const LogTrustedSubtrees &logsubtree) -> bool { - return logsubtree.log_number == log_number; - }); - if (subtrees_it == trusted_subtrees_.end()) { + uint16_t log_number, Subtree target_range) const { + if (trusted_subtrees_ == nullptr) { return std::nullopt; } - - const auto& subtrees = subtrees_it->trusted_subtrees; - auto it = std::lower_bound( - subtrees.begin(), subtrees.end(), target_range, - [](const TrustedSubtree &subtree, Subtree range) -> bool { - return subtree.range < range; - }); - if (it == subtrees.end() || it->range != target_range) { - return std::nullopt; - } - return it->hash; + return trusted_subtrees_->LookupSubtreeHash(log_number, target_range); } std::string MTCAnchor::TrustedSubtreesDebugString() const { - if (trusted_subtrees_.empty()) { - return "none"; + if (trusted_subtrees_ == nullptr) { + return "Invalid"; } - std::string result; - - for (const auto &[log_number, subtrees] : trusted_subtrees_) { - if (!result.empty()) { - result += ", "; - } - result += "log " + std::to_string(log_number) + ":"; - if (subtrees.empty()) { - result += "empty"; - } else { - // Just showing the start of first range to end of last range is an - // oversimplification, but showing every single range is probably too - // verbose. - result += std::to_string(subtrees.size()) + " subtrees(" + - std::to_string(subtrees.front().range.start) + ".." + - std::to_string(subtrees.back().range.end) + ")"; - } - } - return result; + return trusted_subtrees_->DebugString(); } void MTCAnchor::CreateSyntheticCert(bssl::Span<const uint8_t> ca_id) { @@ -411,7 +449,7 @@ trust_ = new_trust; } -CertificateTrust TrustAnchor::CertTrust() const { return trust_; } +const CertificateTrust &TrustAnchor::CertTrust() const { return trust_; } std::shared_ptr<const MTCAnchor> TrustAnchor::MTCAnchor() const { return mtc_anchor_;
diff --git a/pki/trust_store.h b/pki/trust_store.h index 9a1dcf1..42c37fb 100644 --- a/pki/trust_store.h +++ b/pki/trust_store.h
@@ -61,59 +61,100 @@ std::vector<TrustedSubtree> trusted_subtrees; }; +// Represents an ordered list of trusted subtrees for an MTC CA. +class OPENSSL_EXPORT TrustedSubtreeSet { + public: + class Token { + private: + explicit Token() = default; + friend TrustedSubtreeSet; + }; + + // Wraps `trusted_subtrees` in a TrustedSubtreeSet instance if valid, + // otherwise returns nullptr. Returned TrustedSubtreeSet is guaranteed to be + // valid. + static std::shared_ptr<const TrustedSubtreeSet> Create( + std::vector<LogTrustedSubtrees> trusted_subtrees); + + // This constructor is conceptually private, but needs to be public for + // make_shared to work. Uses the "passkey idiom" to prevent callers outside + // of the class from calling it. Outside callers should use Create(). + TrustedSubtreeSet(Token, std::vector<LogTrustedSubtrees> trusted_subtrees); + + TrustedSubtreeSet(const TrustedSubtreeSet &) = delete; + TrustedSubtreeSet &operator=(const TrustedSubtreeSet &) = delete; + + ~TrustedSubtreeSet() = default; + + // Looks up a `target_range`'s subtree hash within the trusted subtrees for + // `log_number`. Returns std::nullopt if not found. + std::optional<TreeHashConstSpan> LookupSubtreeHash( + uint16_t log_number, Subtree target_range) const; + + std::string DebugString() const; + + private: + // Returns whether log numbers are greater than zero, and are in sorted order + // without repeated log numbers, and within each log number the subtrees are + // valid and listed in order. (An empty list for a log number is valid, and + // equivalent to that log number being absent.) + static bool IsValid(const std::vector<LogTrustedSubtrees> &trusted_subtrees); + + // Entries in the vector must be sorted by log number, and each + // `TrustedSubtree` within must be sorted by their subtree ranges. + std::vector<LogTrustedSubtrees> trusted_subtrees_; +}; + // Describes the level of trust in a certificate. struct OPENSSL_EXPORT CertificateTrust { - static constexpr CertificateTrust ForTrustAnchor() { + static CertificateTrust ForTrustAnchor() { CertificateTrust result; result.type = CertificateTrustType::TRUSTED_ANCHOR; return result; } - static constexpr CertificateTrust ForTrustAnchorOrLeaf() { + static CertificateTrust ForTrustAnchorOrLeaf() { CertificateTrust result; result.type = CertificateTrustType::TRUSTED_ANCHOR_OR_LEAF; return result; } - static constexpr CertificateTrust ForTrustedLeaf() { + static CertificateTrust ForTrustedLeaf() { CertificateTrust result; result.type = CertificateTrustType::TRUSTED_LEAF; return result; } - static constexpr CertificateTrust ForUnspecified() { + static CertificateTrust ForUnspecified() { CertificateTrust result; return result; } - static constexpr CertificateTrust ForDistrusted() { + static CertificateTrust ForDistrusted() { CertificateTrust result; result.type = CertificateTrustType::DISTRUSTED; return result; } - constexpr CertificateTrust WithEnforceAnchorExpiry(bool value = true) const { + CertificateTrust WithEnforceAnchorExpiry(bool value = true) const { CertificateTrust result = *this; result.enforce_anchor_expiry = value; return result; } - constexpr CertificateTrust WithEnforceAnchorConstraints( - bool value = true) const { + CertificateTrust WithEnforceAnchorConstraints(bool value = true) const { CertificateTrust result = *this; result.enforce_anchor_constraints = value; return result; } - constexpr CertificateTrust WithRequireAnchorBasicConstraints( - bool value = true) const { + CertificateTrust WithRequireAnchorBasicConstraints(bool value = true) const { CertificateTrust result = *this; result.require_anchor_basic_constraints = value; return result; } - constexpr CertificateTrust WithRequireLeafSelfSigned( - bool value = true) const { + CertificateTrust WithRequireLeafSelfSigned(bool value = true) const { CertificateTrust result = *this; result.require_leaf_selfsigned = value; return result; @@ -126,6 +167,8 @@ std::string ToDebugString() const; + // FromDebugString does not parse trusted subtrees from the debug string. If + // there are any trusted_subtrees, they will not round-trip. static std::optional<CertificateTrust> FromDebugString( const std::string &trust_string); @@ -146,6 +189,14 @@ // Optionally, require trusted leafs to be self-signed to be trusted. bool require_leaf_selfsigned = false; + + // For an MTC CA, a list of trusted subtrees + // (draft-ietf-plants-merkle-tree-certs, Section 7.4) that are known to be + // consistent with the relying party's cosigner requirements. A null pointer + // is equivalent to an empty set (no landmark-relative MTCs from this MTC CA + // are recognized). Ignored (and should be null) unless this is the trust for + // an MTC CA. + std::shared_ptr<const TrustedSubtreeSet> trusted_subtrees; }; class OPENSSL_EXPORT MTCAnchor { @@ -208,11 +259,10 @@ return ca_signature_algorithm_; } const CRYPTO_BUFFER *ca_key() const { return ca_key_.get(); } - // TODO(nharper): Move this function to TrustAnchor. der::Input NormalizedSubject() const; - // TODO(nharper): Remove this function in favor of TrustAnchor's version. CertificateTrust CertTrust() const; - // TODO(nharper): Move this function to TrustAnchor. + // TODO(crbug.com/575507260): Replace synthesized certificate with a real MTC + // CA certificate. std::shared_ptr<const ParsedCertificate> AsCert() const; std::optional<TreeHashConstSpan> SubtreeHash(uint16_t log_number, @@ -227,33 +277,26 @@ SignatureAlgorithm ca_signature_algorithm_; UniquePtr<CRYPTO_BUFFER> ca_key_; std::shared_ptr<const ParsedCertificate> synthetic_cert_; - std::vector<LogTrustedSubtrees> trusted_subtrees_; + // If `trusted_subtrees_` is null, `Create*()` failed and `IsValid()` is + // false. + std::shared_ptr<const TrustedSubtreeSet> trusted_subtrees_; }; // A TrustAnchor contains information about how a trust anchor is trusted and -// what is trusted. It should be used in place of a (ParsedCertificate, -// CertificateTrust) tuple as some trust information, e.g. MTC anchors, is not +// what is trusted. +// +// TODO(crbug.com/575507260): This class was formerly the first step of a large +// refactor to use TrustAnchor in place of a (ParsedCertificate, +// CertificateTrust) tuple as some trust information, e.g. MTC anchors, was not // representable by such a tuple. -// -// TODO(nharper): This class is the first step of a large refactor to stop -// representing TrustAnchors as ParsedCertificates. Prior to the introduction of -// Merkle Tree Certs, the information about a trust anchor was split between -// a ParsedCertificate (containing the anchor's Subject name and public key) and -// a CertificateTrust struct (informing when/how the trust anchor is trusted, as -// well as whether any additional constraints should be applied). With the -// introduction of Merkle Tree Certs, some of this information about how to use -// an MTC trust anchor fits in neither place. The eventual goal is that the -// TrustAnchor class is the single place that contains all information about a -// trust anchor, rather than that information being split across multiple -// objects. This will allow a further goal of removing the dependency of -// requiring that a trust anchor be representable as a ParsedCertificate: MTC -// trust anchors only have a ParsedCertificate accessor for compatibility -// reasons, and while draft-ietf-lamps-x509-alg-none improves the efficiency of -// storing trust anchors in X.509 certs, this refactor will allow further -// improvements for classical (non-MTC) roots. -// -// See also internal design doc: +// Original internal TrustAnchor design doc: // https://docs.google.com/document/d/1wqHAmZqtF8oJzNObFBm41lzDt2JWRhjM32A3z6ampJE/edit +// +// The current plan is to align with the X.509 certificate representation of MTC +// CAs in draft-ietf-plants-merkle-tree-certs-05 and up, and make the +// (ParsedCertificate, CertificateTrust) representation work for all trust +// anchors. After migrating to the X.509 representation, TrustAnchor will be +// removed. class OPENSSL_EXPORT TrustAnchor { public: // Creates a default TrustAnchor with an unspecified CertificateTrust. @@ -261,6 +304,8 @@ // Creates a TrustAnchor with no associated MTCAnchor. explicit TrustAnchor(CertificateTrust trust) : TrustAnchor(trust, nullptr) {} + + // Creates a TrustAnchor with an associated MTCAnchor. TrustAnchor(CertificateTrust trust, std::shared_ptr<const MTCAnchor> mtc_anchor) : trust_(trust), mtc_anchor_(std::move(mtc_anchor)) {} @@ -278,7 +323,7 @@ // TODO(nharper): Remove this function as part of the larger TrustAnchor // refactor. void OverrideCertTrust(CertificateTrust new_trust); - CertificateTrust CertTrust() const; + const CertificateTrust &CertTrust() const; std::shared_ptr<const bssl::MTCAnchor> MTCAnchor() const; private:
diff --git a/pki/trust_store_in_memory_unittest.cc b/pki/trust_store_in_memory_unittest.cc index 87b6228..1ac1b40 100644 --- a/pki/trust_store_in_memory_unittest.cc +++ b/pki/trust_store_in_memory_unittest.cc
@@ -15,6 +15,8 @@ #include "trust_store_in_memory.h" #include <memory> +#include <optional> +#include <string> #include <vector> #include <gtest/gtest.h> @@ -280,5 +282,232 @@ EXPECT_FALSE(in_memory2.ContainsMTCAnchor(anchor1.get())); } +class TrustedSubtreeSetTest : public testing::Test { + protected: + // Returns a TrustedSubtree for [start, end) whose hash is filled with + // `hash_byte`, so that lookup results can be told apart. + static TrustedSubtree MakeSubtree(uint64_t start, uint64_t end, + uint8_t hash_byte) { + TrustedSubtree subtree; + subtree.range = Subtree{start, end}; + subtree.hash.fill(hash_byte); + return subtree; + } + + // Returns the expected hash for a subtree made with MakeSubtree(..., + // `hash_byte`). + static std::vector<uint8_t> ExpectedHash(uint8_t hash_byte) { + return std::vector<uint8_t>(SHA256_DIGEST_LENGTH, hash_byte); + } + + static std::optional<std::vector<uint8_t>> Lookup( + const TrustedSubtreeSet &set, uint16_t log_number, Subtree range) { + std::optional<TreeHashConstSpan> hash = + set.LookupSubtreeHash(log_number, range); + if (!hash) { + return std::nullopt; + } + return std::vector<uint8_t>(hash->begin(), hash->end()); + } + + static std::shared_ptr<const MTCAnchor> MakeMTCAnchor( + std::vector<LogTrustedSubtrees> subtrees) { + static const uint8_t kCaId[] = {42}; // relative OID of 42 + // The ca_key doesn't need to be valid for these tests. + UniquePtr<CRYPTO_BUFFER> ca_spki(CRYPTO_BUFFER_new({}, 0, nullptr)); + return std::make_shared<MTCAnchor>(kCaId, SignatureAlgorithm::kMldsa44, + std::move(ca_spki), std::move(subtrees)); + } +}; + +TEST_F(TrustedSubtreeSetTest, CreateValid) { + const TrustedSubtree a = MakeSubtree(0, 4, 1); + const TrustedSubtree b = MakeSubtree(0, 6, 2); + const TrustedSubtree c = MakeSubtree(8, 9, 3); + + const struct { + const char *name; + std::vector<LogTrustedSubtrees> subtrees; + } kTests[] = { + {"Empty", {}}, + {"OneLogNoSubtrees", {{1, {}}}}, + {"OneLogOneSubtree", {{1, {a}}}}, + {"OneLogSortedSubtrees", {{1, {a, b, c}}}}, + {"MultipleSortedLogs", {{1, {a, c}}, {2, {b}}, {7, {a}}}}, + {"MaxLogNumber", {{1, {a}}, {UINT16_MAX, {b}}}}, + }; + for (const auto &t : kTests) { + SCOPED_TRACE(t.name); + EXPECT_TRUE(TrustedSubtreeSet::Create(t.subtrees)); + } +} + +TEST_F(TrustedSubtreeSetTest, CreateInvalid) { + const TrustedSubtree a = MakeSubtree(0, 4, 1); + const TrustedSubtree b = MakeSubtree(0, 6, 2); + const TrustedSubtree c = MakeSubtree(8, 9, 3); + // Ragged left edge: 4 is only divisible by 4, but the subtree has 5 elements. + const TrustedSubtree ragged = MakeSubtree(4, 9, 4); + const TrustedSubtree backwards = MakeSubtree(9, 8, 5); + + const struct { + const char *name; + std::vector<LogTrustedSubtrees> subtrees; + } kTests[] = { + {"LogNumberZero", {{0, {a}}}}, + {"LogNumberZeroBeforeValid", {{0, {a}}, {1, {b}}}}, + {"LogsOutOfOrder", {{2, {a}}, {1, {b}}}}, + {"DuplicateLogNumber", {{1, {a}}, {1, {b}}}}, + {"RaggedSubtree", {{1, {ragged}}}}, + {"BackwardsSubtree", {{1, {backwards}}}}, + {"InvalidSubtreeInSecondLog", {{1, {a}}, {2, {ragged}}}}, + {"SubtreesOutOfOrder", {{1, {b, a, c}}}}, + {"SubtreesOutOfOrderInSecondLog", {{1, {a}}, {2, {c, a}}}}, + }; + for (const auto &t : kTests) { + SCOPED_TRACE(t.name); + EXPECT_FALSE(TrustedSubtreeSet::Create(t.subtrees)); + } +} + +// Duplicate subtree ranges within a log are accepted as valid, because +// validation only rejects ranges that sort strictly before their predecessor. +TEST_F(TrustedSubtreeSetTest, CreateDuplicateRanges) { + std::vector<LogTrustedSubtrees> subtrees = { + {1, {MakeSubtree(0, 4, 1), MakeSubtree(0, 4, 2)}}}; + EXPECT_TRUE(TrustedSubtreeSet::Create(subtrees)); +} + +TEST_F(TrustedSubtreeSetTest, LookupSubtreeHash) { + std::shared_ptr<const TrustedSubtreeSet> set = TrustedSubtreeSet::Create({ + {1, {MakeSubtree(0, 4, 1), MakeSubtree(0, 8, 2), MakeSubtree(8, 12, 3)}}, + {3, {MakeSubtree(0, 4, 4), MakeSubtree(16, 32, 5)}}, + }); + ASSERT_TRUE(set); + + // First, middle and last subtree in the first log. + EXPECT_EQ(Lookup(*set, 1, Subtree{0, 4}), ExpectedHash(1)); + EXPECT_EQ(Lookup(*set, 1, Subtree{0, 8}), ExpectedHash(2)); + EXPECT_EQ(Lookup(*set, 1, Subtree{8, 12}), ExpectedHash(3)); + + // The same range in a different log has a different hash. + EXPECT_EQ(Lookup(*set, 3, Subtree{0, 4}), ExpectedHash(4)); + EXPECT_EQ(Lookup(*set, 3, Subtree{16, 32}), ExpectedHash(5)); + + // Unknown log numbers, including one between two known logs. + EXPECT_FALSE(Lookup(*set, 0, Subtree{0, 4})); + EXPECT_FALSE(Lookup(*set, 2, Subtree{0, 4})); + EXPECT_FALSE(Lookup(*set, 4, Subtree{0, 4})); + + // Ranges not in the log: before the first, between two existing ranges, + // sharing only a start or end with an existing range, after the last, and a + // range present only in the other log. + EXPECT_FALSE(Lookup(*set, 3, Subtree{0, 2})); + EXPECT_FALSE(Lookup(*set, 1, Subtree{0, 6})); + EXPECT_FALSE(Lookup(*set, 1, Subtree{4, 8})); + EXPECT_FALSE(Lookup(*set, 1, Subtree{8, 10})); + EXPECT_FALSE(Lookup(*set, 1, Subtree{12, 16})); + EXPECT_FALSE(Lookup(*set, 1, Subtree{16, 32})); +} + +TEST_F(TrustedSubtreeSetTest, LookupSubtreeHashEmpty) { + std::shared_ptr<const TrustedSubtreeSet> empty = + TrustedSubtreeSet::Create({}); + ASSERT_TRUE(empty); + EXPECT_FALSE(Lookup(*empty, 1, Subtree{0, 4})); + + std::shared_ptr<const TrustedSubtreeSet> empty_log = + TrustedSubtreeSet::Create({{1, {}}}); + ASSERT_TRUE(empty_log); + EXPECT_FALSE(Lookup(*empty_log, 1, Subtree{0, 4})); +} + +TEST_F(TrustedSubtreeSetTest, DebugString) { + std::shared_ptr<const TrustedSubtreeSet> set = TrustedSubtreeSet::Create({}); + ASSERT_TRUE(set); + EXPECT_EQ(set->DebugString(), "none"); + + set = TrustedSubtreeSet::Create({{1, {}}}); + ASSERT_TRUE(set); + EXPECT_EQ(set->DebugString(), "log 1:empty"); + + set = TrustedSubtreeSet::Create({ + {1, {MakeSubtree(0, 4, 1), MakeSubtree(8, 12, 2)}}, + {2, {}}, + {3, {MakeSubtree(16, 32, 3)}}, + }); + ASSERT_TRUE(set); + EXPECT_EQ(set->DebugString(), + "log 1:2 subtrees(0..12), log 2:empty, log 3:1 subtrees(16..32)"); +} + +TEST_F(TrustedSubtreeSetTest, MTCAnchorCertTrust) { + std::shared_ptr<const MTCAnchor> anchor = + MakeMTCAnchor({{1, {MakeSubtree(0, 4, 1), MakeSubtree(8, 12, 2)}}}); + ASSERT_TRUE(anchor->IsValid()); + + CertificateTrust trust = anchor->CertTrust(); + EXPECT_TRUE(trust.IsTrustAnchor()); + ASSERT_TRUE(trust.trusted_subtrees); + // CertTrust() shares the MTCAnchor's TrustedSubtreeSet rather than copying. + EXPECT_EQ(trust.trusted_subtrees.get(), + anchor->CertTrust().trusted_subtrees.get()); + + // The CertificateTrust's subtrees agree with the MTCAnchor. + for (Subtree range : {Subtree{0, 4}, Subtree{8, 12}, Subtree{4, 8}}) { + SCOPED_TRACE(std::to_string(range.start) + ".." + + std::to_string(range.end)); + std::optional<std::vector<uint8_t>> from_trust = + Lookup(*trust.trusted_subtrees, 1, range); + std::optional<TreeHashConstSpan> from_anchor = + anchor->SubtreeHash(1, range); + ASSERT_EQ(from_trust.has_value(), from_anchor.has_value()); + if (from_trust) { + EXPECT_EQ(*from_trust, + std::vector<uint8_t>(from_anchor->begin(), from_anchor->end())); + } + } + + EXPECT_EQ(trust.ToDebugString(), + "TRUSTED_ANCHOR+trusted_subtrees(log 1:2 subtrees(0..12))"); +} + +TEST_F(TrustedSubtreeSetTest, MTCAnchorCertTrustNoSubtrees) { + std::shared_ptr<const MTCAnchor> anchor = MakeMTCAnchor({}); + ASSERT_TRUE(anchor->IsValid()); + + CertificateTrust trust = anchor->CertTrust(); + ASSERT_TRUE(trust.trusted_subtrees); + EXPECT_EQ(trust.ToDebugString(), "TRUSTED_ANCHOR+trusted_subtrees(none)"); +} + +TEST_F(TrustedSubtreeSetTest, NonMTCCertTrust) { + for (const CertificateTrust &trust : + {CertificateTrust::ForTrustAnchor(), + CertificateTrust::ForTrustAnchorOrLeaf(), + CertificateTrust::ForTrustedLeaf(), CertificateTrust::ForUnspecified(), + CertificateTrust::ForDistrusted()}) { + SCOPED_TRACE(trust.ToDebugString()); + EXPECT_FALSE(trust.trusted_subtrees); + EXPECT_EQ(trust.ToDebugString().find("trusted_subtrees"), + std::string::npos); + } +} + +// An MTCAnchor constructed directly with invalid subtrees reports itself as +// invalid, and lookups through it fail rather than crashing. +TEST_F(TrustedSubtreeSetTest, MTCAnchorInvalidSubtrees) { + std::shared_ptr<const MTCAnchor> anchor = + MakeMTCAnchor({{1, {MakeSubtree(8, 12, 1), MakeSubtree(0, 4, 2)}}}); + EXPECT_FALSE(anchor->IsValid()); + EXPECT_FALSE(anchor->SubtreeHash(1, Subtree{0, 4})); + EXPECT_FALSE(anchor->SubtreeHash(1, Subtree{8, 12})); + EXPECT_EQ(anchor->TrustedSubtreesDebugString(), "Invalid"); + + CertificateTrust trust = anchor->CertTrust(); + EXPECT_FALSE(trust.trusted_subtrees); + EXPECT_EQ(trust.ToDebugString(), "TRUSTED_ANCHOR"); +} + } // namespace BSSL_NAMESPACE_END