pki/verify_unittest.cc - boringssl - Git at Google

 // Copyright 2023 The BoringSSL Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     https://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include <string.h>

 #include <cstddef>
 #include <memory>
 #include <optional>
 #include <vector>

 #include <gmock/gmock.h>
 #include <gtest/gtest.h>
 #include <openssl/pki/verify.h>
 #include <openssl/pki/verify_error.h>
 #include <openssl/pool.h>
 #include <openssl/sha2.h>

 #include "encode_values.h"
 #include "merkle_tree.h"
 #include "parse_certificate.h"
 #include "parsed_certificate.h"
 #include "string_util.h"
 #include "test_helpers.h"
 #include "trust_store.h"
 #include "trust_store_in_memory.h"

 BSSL_NAMESPACE_BEGIN

 static std::unique_ptr<VerifyTrustStore> MozillaRootStore() {
   std::string diagnostic;
   return VerifyTrustStore::FromDER(
              bssl::ReadTestFileToString(
                  "testdata/verify_unittest/mozilla_roots.der"),
              &diagnostic);
 }

 using ::testing::UnorderedElementsAre;

 static std::string GetTestdata(std::string_view filename) {
   return bssl::ReadTestFileToString("testdata/verify_unittest/" +
                                     std::string(filename));
 }

 TEST(VerifyTest, GoogleChain) {
   const std::string leaf = GetTestdata("google-leaf.der");
   const std::string intermediate1 = GetTestdata("google-intermediate1.der");
   const std::string intermediate2 = GetTestdata("google-intermediate2.der");
   CertificateVerifyOptions opts;
   opts.leaf_cert = leaf;
   opts.intermediates = {intermediate1, intermediate2};
   opts.time = 1499727444;
   std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
   opts.trust_store = roots.get();

   VerifyError error;
   ASSERT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();

   opts.intermediates = {};
   EXPECT_FALSE(CertificateVerify(opts, &error));
   ASSERT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND)
       << error.DiagnosticString();
 }


 TEST(VerifyTest, ExtraIntermediates) {
   const std::string leaf = GetTestdata("google-leaf.der");
   const std::string intermediate1 = GetTestdata("google-intermediate1.der");
   const std::string intermediate2 = GetTestdata("google-intermediate2.der");

   CertificateVerifyOptions opts;
   opts.leaf_cert = leaf;
   std::string diagnostic;
   const auto cert_pool_status = CertPool::FromCerts(
       {
           intermediate1,
           intermediate2,
       },
       &diagnostic);
   ASSERT_TRUE(cert_pool_status) << diagnostic;
   opts.extra_intermediates = cert_pool_status.get();
   opts.time = 1499727444;
   std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
   opts.trust_store = roots.get();

   VerifyError error;
   ASSERT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
 }

 TEST(VerifyTest, AllPaths) {
   const std::string leaf = GetTestdata("lencr-leaf.der");
   const std::string intermediate1 = GetTestdata("lencr-intermediate-r3.der");
   const std::string intermediate2 =
       GetTestdata("lencr-root-x1-cross-signed.der");
   const std::string root1 = GetTestdata("lencr-root-x1.der");
   const std::string root2 = GetTestdata("lencr-root-dst-x3.der");

   std::vector<std::string> expected_path1 = {leaf, intermediate1, root1};
   std::vector<std::string> expected_path2 = {leaf, intermediate1, intermediate2,
                                              root2};

   CertificateVerifyOptions opts;
   opts.leaf_cert = leaf;
   opts.intermediates = {intermediate1, intermediate2};
   opts.time = 1699404611;
   std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
   opts.trust_store = roots.get();

   auto paths = CertificateVerifyAllPaths(opts);
   ASSERT_TRUE(paths);
   EXPECT_EQ(2U, paths.value().size());
   EXPECT_THAT(paths.value(),
               UnorderedElementsAre(expected_path1, expected_path2));
 }

 TEST(VerifyTest, DepthLimit) {
   const std::string leaf = GetTestdata("google-leaf.der");
   const std::string intermediate1 = GetTestdata("google-intermediate1.der");
   const std::string intermediate2 = GetTestdata("google-intermediate2.der");
   CertificateVerifyOptions opts;
   opts.leaf_cert = leaf;
   opts.intermediates = {intermediate1, intermediate2};
   opts.time = 1499727444;
   // Set the |max_path_building_depth| explicitly to test the non-default case.
   // Depth of 5 is enough to successfully find a path.
   opts.max_path_building_depth = 5;
   std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
   opts.trust_store = roots.get();

   VerifyError error;
   ASSERT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();

   // Depth of 2 is not enough to find a path.
   opts.max_path_building_depth = 2;
   EXPECT_FALSE(CertificateVerify(opts, &error));
   ASSERT_EQ(error.Code(), VerifyError::StatusCode::PATH_DEPTH_LIMIT_REACHED)
       << error.DiagnosticString();
 }

 class VerifyMTCTest : public ::testing::Test {
  public:
   VerifyMTCTest() = default;

   void SetUp() override {
     ASSERT_TRUE(ReadTestCert("mtc-leaf.pem", &generic_cert_));
     ASSERT_TRUE(ReadTestCert("mtc-leaf-bitflip.pem", &bitflip_cert_));
     ASSERT_TRUE(ReadTestCert("mtc-leaf-b.pem", &leaf_b_));
     ASSERT_TRUE(ReadTestCert("mtc-leaf-c.pem", &leaf_c_));

     ASSERT_TRUE(
         CreateTrustedSubtree("Rrynt7BBSfI4WMZ1u1+XOJSNaWnYOdUDjn7VbdF+kQY=", 8,
                              13, &generic_cert_subtree_));
     ASSERT_TRUE(
         CreateTrustedSubtree("S92aoQXoNnSPJ37X1zY5InskJPTpzUs6LRr3TOwInvo=", 8,
                              16, &leaf_b_subtree_));
     ASSERT_TRUE(
         CreateTrustedSubtree("FxyVwc4letskl3WVKXWqlPBvUZsl5NiD5sW7Wr50k+4=", 16,
                              24, &leaf_c_subtree_));
   }

   ::testing::AssertionResult ReadTestCert(const std::string &file_name,
                                           std::string *out_cert) {
     PemBlockMapping mappings[] = {
         {"CERTIFICATE", out_cert},
     };
     return ReadTestDataFromPemFile("testdata/verify_unittest/" + file_name,
                                    mappings);
   }

   bool CreateTrustedSubtree(const std::string &hash_b64, uint64_t start,
                             uint64_t end, TrustedSubtree *out_subtree) const {
     std::string subtree_hash;
     if (!string_util::Base64Decode(hash_b64, &subtree_hash)) {
       return false;
     }
     if (subtree_hash.size() != out_subtree->hash.size()) {
       return false;
     }
     memcpy(out_subtree->hash.data(), subtree_hash.data(), subtree_hash.size());
     out_subtree->range = Subtree{start, end};
     return true;
   }

   std::shared_ptr<const ParsedCertificate> CertFromString(
       const std::string &cert) const {
     UniquePtr<CRYPTO_BUFFER> cert_buf(CRYPTO_BUFFER_new(
         reinterpret_cast<const uint8_t *>(cert.data()), cert.size(), nullptr));
     return ParsedCertificate::Create(std::move(cert_buf),
                                      ParseCertificateOptions{}, nullptr);
   }

   bool PrepareOptsForVerify(const std::string &cert,
                             const VerifyTrustStore *trust_store,
                             CertificateVerifyOptions *out_opts) const {
     out_opts->leaf_cert = cert;
     std::shared_ptr<const ParsedCertificate> parsed_cert = CertFromString(cert);
     if (!parsed_cert) {
       return false;
     }
     // out_opts->time is a std::optional<int64_t>. If we write directly to
     // *out_opts->time, the std::optional will still be a std::nullopt.
     int64_t time;
     if (!der::GeneralizedTimeToPosixTime(parsed_cert->tbs().validity_not_before,
                                          &time)) {
       return false;
     }
     out_opts->time = time;
     out_opts->trust_store = trust_store;
     return true;
   }

   std::unique_ptr<VerifyTrustStore> EmptyTrustStore() const {
     return VerifyTrustStore::FromDER("", nullptr);
   }

  protected:
   std::string generic_cert_;
   std::string bitflip_cert_;
   std::string leaf_b_;
   std::string leaf_c_;

   // the trusted subtree for [8, 13) that is used in |generic_cert_|,
   // |bitflip_cert_|.
   TrustedSubtree generic_cert_subtree_;
   // Subtree for |leaf_b_| which overlaps with |generic_cert_subtree_|.
   TrustedSubtree leaf_b_subtree_;
   // Subtree for |leaf_c_| which does not overlap with any other subtrees.
   TrustedSubtree leaf_c_subtree_;

   // Relative OID encoding of 32473.1, the log ID used for the MTC Anchor that
   // issued the test MTCs in this test fixture.
   static constexpr uint8_t kAnchorLogId[] = {0x81, 0xfd, 0x59, 0x01};
   static constexpr uint8_t kAnchorLogIdBitflip[] = {0x81, 0xfd, 0x59, 0x00};
 };

 TEST_F(VerifyMTCTest, SignaturelessMTC) {
   // Configure the trust store to trust the MTC anchor with the landmark subtree
   // for |generic_cert_|.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
   auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                 MakeSpan(trusted_subtrees));
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
   EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
 }

 TEST_F(VerifyMTCTest, ExplicitlyTrustedLeaf) {
   // Configure the trust store to directly trust the |generic_cert_| leaf.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   trust_store->trust_store->AddCertificate(CertFromString(generic_cert_),
                                            CertificateTrust::ForTrustedLeaf());

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
   EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
 }

 TEST_F(VerifyMTCTest, ExplicitlyDistrustedLeaf) {
   // Configure the trust store to trust the MTC anchor for |generic_cert_|, but
   // also to explicitly distrust that leaf.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   trust_store->trust_store->AddCertificate(CertFromString(generic_cert_),
                                            CertificateTrust::ForDistrusted());
   std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
   auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                 MakeSpan(trusted_subtrees));
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
   EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND);
 }

 TEST_F(VerifyMTCTest, WrongProof) {
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
   auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                 MakeSpan(trusted_subtrees));
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(bitflip_cert_, trust_store.get(), &opts));
   EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   EXPECT_EQ(error.Code(),
             VerifyError::StatusCode::CERTIFICATE_INVALID_SIGNATURE);
 }

 TEST_F(VerifyMTCTest, WrongLogID) {
   // Trust the correct subtree for |generic_cert_| but with the wrong log ID.
   // Verifying the cert should fail because even though the proof evaluates to a
   // valid hash, the hash is for the wrong issuer.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
   auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogIdBitflip),
                                                 MakeSpan(trusted_subtrees));
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
   EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND);
 }

 TEST_F(VerifyMTCTest, ExpiredMTC) {
   // Configure the trust store to trust the MTC anchor with the landmark subtree
   // for |generic_cert_|.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
   auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                 MakeSpan(trusted_subtrees));
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   CertificateVerifyOptions opts;
   opts.trust_store = trust_store.get();
   opts.leaf_cert = generic_cert_;
   std::shared_ptr<const ParsedCertificate> parsed_cert =
       CertFromString(generic_cert_);
   ASSERT_TRUE(parsed_cert);
   int64_t time;
   ASSERT_TRUE(der::GeneralizedTimeToPosixTime(
       parsed_cert->tbs().validity_not_after, &time));
   // set verify time to 1 second after the cert's validity period:
   opts.time = time + 1;
   VerifyError error;
   EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   EXPECT_EQ(error.Code(), VerifyError::StatusCode::CERTIFICATE_EXPIRED);
 }

 TEST_F(VerifyMTCTest, TrustStoreConfiguration) {
   // Test that an MTC isn't trusted if there's no MTCAnchor set on the trust
   // store.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
   EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND);
 }

 TEST_F(VerifyMTCTest, BadMTCAnchorHash) {
   // Test that an MTC isn't trusted if the MTCAnchor's TrustedSubtree has the
   // wrong hash. Configure the trust store to trust the MTC anchor with the
   // landmark subtree for |generic_cert_|.
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
   trusted_subtrees[0].hash[0] ^= 1;
   auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                 MakeSpan(trusted_subtrees));
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   CertificateVerifyOptions opts;
   VerifyError error;
   ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
   EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   EXPECT_EQ(error.Code(),
             VerifyError::StatusCode::CERTIFICATE_INVALID_SIGNATURE);
 }

 TEST_F(VerifyMTCTest, SubtreeRangesMatch) {
   // generic_cert_ and leaf_b_ have proofs to subtree ranges with the same start
   // but different ends. Check that CertificateVerify only succeeds if the trust
   // store has the right MTCAnchor.
   std::vector<TrustedSubtree> trusted_subtrees_a = {generic_cert_subtree_};
   std::vector<TrustedSubtree> trusted_subtrees_b = {leaf_b_subtree_};

   auto mtc_anchor_a = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                   MakeSpan(trusted_subtrees_a));
   auto mtc_anchor_b = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
                                                   MakeSpan(trusted_subtrees_b));

   std::unique_ptr<VerifyTrustStore> trust_store_a = EmptyTrustStore();
   ASSERT_TRUE(trust_store_a->trust_store->AddMTCTrustAnchor(mtc_anchor_a));
   {
     CertificateVerifyOptions opts;
     VerifyError error;
     ASSERT_TRUE(
         PrepareOptsForVerify(generic_cert_, trust_store_a.get(), &opts));
     EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   }
   {
     CertificateVerifyOptions opts;
     VerifyError error;
     ASSERT_TRUE(PrepareOptsForVerify(leaf_b_, trust_store_a.get(), &opts));
     EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   }

   std::unique_ptr<VerifyTrustStore> trust_store_b = EmptyTrustStore();
   ASSERT_TRUE(trust_store_b->trust_store->AddMTCTrustAnchor(mtc_anchor_b));
   {
     CertificateVerifyOptions opts;
     VerifyError error;
     ASSERT_TRUE(PrepareOptsForVerify(leaf_b_, trust_store_b.get(), &opts));
     EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   }
   {
     CertificateVerifyOptions opts;
     VerifyError error;
     ASSERT_TRUE(
         PrepareOptsForVerify(generic_cert_, trust_store_b.get(), &opts));
     EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   }
 }

 TEST_F(VerifyMTCTest, MultipleSubtrees) {
   std::vector<TrustedSubtree> subtrees = {generic_cert_subtree_,
                                           leaf_b_subtree_, leaf_c_subtree_};
   auto mtc_anchor =
       std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId), MakeSpan(subtrees));
   std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
   ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

   // Check that generic_cert_, leaf_b_, and leaf_c_ are all trusted.
   std::vector<std::string> leafs = {generic_cert_, leaf_b_, leaf_c_};
   for (size_t i = 0; i < leafs.size(); i++) {
     SCOPED_TRACE(testing::Message() << "Leaf " << i);
     CertificateVerifyOptions opts;
     VerifyError error;
     ASSERT_TRUE(PrepareOptsForVerify(leafs[i], trust_store.get(), &opts));
     EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
   }
 }

 BSSL_NAMESPACE_END
	// Copyright 2023 The BoringSSL Authors
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// https://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include <string.h>

	#include <cstddef>
	#include <memory>
	#include <optional>
	#include <vector>

	#include <gmock/gmock.h>
	#include <gtest/gtest.h>
	#include <openssl/pki/verify.h>
	#include <openssl/pki/verify_error.h>
	#include <openssl/pool.h>
	#include <openssl/sha2.h>

	#include "encode_values.h"
	#include "merkle_tree.h"
	#include "parse_certificate.h"
	#include "parsed_certificate.h"
	#include "string_util.h"
	#include "test_helpers.h"
	#include "trust_store.h"
	#include "trust_store_in_memory.h"

	BSSL_NAMESPACE_BEGIN

	static std::unique_ptr<VerifyTrustStore> MozillaRootStore() {
	std::string diagnostic;
	return VerifyTrustStore::FromDER(
	bssl::ReadTestFileToString(
	"testdata/verify_unittest/mozilla_roots.der"),
	&diagnostic);
	}

	using ::testing::UnorderedElementsAre;

	static std::string GetTestdata(std::string_view filename) {
	return bssl::ReadTestFileToString("testdata/verify_unittest/" +
	std::string(filename));
	}

	TEST(VerifyTest, GoogleChain) {
	const std::string leaf = GetTestdata("google-leaf.der");
	const std::string intermediate1 = GetTestdata("google-intermediate1.der");
	const std::string intermediate2 = GetTestdata("google-intermediate2.der");
	CertificateVerifyOptions opts;
	opts.leaf_cert = leaf;
	opts.intermediates = {intermediate1, intermediate2};
	opts.time = 1499727444;
	std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
	opts.trust_store = roots.get();

	VerifyError error;
	ASSERT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();

	opts.intermediates = {};
	EXPECT_FALSE(CertificateVerify(opts, &error));
	ASSERT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND)
	<< error.DiagnosticString();
	}


	TEST(VerifyTest, ExtraIntermediates) {
	const std::string leaf = GetTestdata("google-leaf.der");
	const std::string intermediate1 = GetTestdata("google-intermediate1.der");
	const std::string intermediate2 = GetTestdata("google-intermediate2.der");

	CertificateVerifyOptions opts;
	opts.leaf_cert = leaf;
	std::string diagnostic;
	const auto cert_pool_status = CertPool::FromCerts(
	{
	intermediate1,
	intermediate2,
	},
	&diagnostic);
	ASSERT_TRUE(cert_pool_status) << diagnostic;
	opts.extra_intermediates = cert_pool_status.get();
	opts.time = 1499727444;
	std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
	opts.trust_store = roots.get();

	VerifyError error;
	ASSERT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}

	TEST(VerifyTest, AllPaths) {
	const std::string leaf = GetTestdata("lencr-leaf.der");
	const std::string intermediate1 = GetTestdata("lencr-intermediate-r3.der");
	const std::string intermediate2 =
	GetTestdata("lencr-root-x1-cross-signed.der");
	const std::string root1 = GetTestdata("lencr-root-x1.der");
	const std::string root2 = GetTestdata("lencr-root-dst-x3.der");

	std::vector<std::string> expected_path1 = {leaf, intermediate1, root1};
	std::vector<std::string> expected_path2 = {leaf, intermediate1, intermediate2,
	root2};

	CertificateVerifyOptions opts;
	opts.leaf_cert = leaf;
	opts.intermediates = {intermediate1, intermediate2};
	opts.time = 1699404611;
	std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
	opts.trust_store = roots.get();

	auto paths = CertificateVerifyAllPaths(opts);
	ASSERT_TRUE(paths);
	EXPECT_EQ(2U, paths.value().size());
	EXPECT_THAT(paths.value(),
	UnorderedElementsAre(expected_path1, expected_path2));
	}

	TEST(VerifyTest, DepthLimit) {
	const std::string leaf = GetTestdata("google-leaf.der");
	const std::string intermediate1 = GetTestdata("google-intermediate1.der");
	const std::string intermediate2 = GetTestdata("google-intermediate2.der");
	CertificateVerifyOptions opts;
	opts.leaf_cert = leaf;
	opts.intermediates = {intermediate1, intermediate2};
	opts.time = 1499727444;
	// Set the \|max_path_building_depth\| explicitly to test the non-default case.
	// Depth of 5 is enough to successfully find a path.
	opts.max_path_building_depth = 5;
	std::unique_ptr<VerifyTrustStore> roots = MozillaRootStore();
	opts.trust_store = roots.get();

	VerifyError error;
	ASSERT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();

	// Depth of 2 is not enough to find a path.
	opts.max_path_building_depth = 2;
	EXPECT_FALSE(CertificateVerify(opts, &error));
	ASSERT_EQ(error.Code(), VerifyError::StatusCode::PATH_DEPTH_LIMIT_REACHED)
	<< error.DiagnosticString();
	}

	class VerifyMTCTest : public ::testing::Test {
	public:
	VerifyMTCTest() = default;

	void SetUp() override {
	ASSERT_TRUE(ReadTestCert("mtc-leaf.pem", &generic_cert_));
	ASSERT_TRUE(ReadTestCert("mtc-leaf-bitflip.pem", &bitflip_cert_));
	ASSERT_TRUE(ReadTestCert("mtc-leaf-b.pem", &leaf_b_));
	ASSERT_TRUE(ReadTestCert("mtc-leaf-c.pem", &leaf_c_));

	ASSERT_TRUE(
	CreateTrustedSubtree("Rrynt7BBSfI4WMZ1u1+XOJSNaWnYOdUDjn7VbdF+kQY=", 8,
	13, &generic_cert_subtree_));
	ASSERT_TRUE(
	CreateTrustedSubtree("S92aoQXoNnSPJ37X1zY5InskJPTpzUs6LRr3TOwInvo=", 8,
	16, &leaf_b_subtree_));
	ASSERT_TRUE(
	CreateTrustedSubtree("FxyVwc4letskl3WVKXWqlPBvUZsl5NiD5sW7Wr50k+4=", 16,
	24, &leaf_c_subtree_));
	}

	::testing::AssertionResult ReadTestCert(const std::string &file_name,
	std::string *out_cert) {
	PemBlockMapping mappings[] = {
	{"CERTIFICATE", out_cert},
	};
	return ReadTestDataFromPemFile("testdata/verify_unittest/" + file_name,
	mappings);
	}

	bool CreateTrustedSubtree(const std::string &hash_b64, uint64_t start,
	uint64_t end, TrustedSubtree *out_subtree) const {
	std::string subtree_hash;
	if (!string_util::Base64Decode(hash_b64, &subtree_hash)) {
	return false;
	}
	if (subtree_hash.size() != out_subtree->hash.size()) {
	return false;
	}
	memcpy(out_subtree->hash.data(), subtree_hash.data(), subtree_hash.size());
	out_subtree->range = Subtree{start, end};
	return true;
	}

	std::shared_ptr<const ParsedCertificate> CertFromString(
	const std::string &cert) const {
	UniquePtr<CRYPTO_BUFFER> cert_buf(CRYPTO_BUFFER_new(
	reinterpret_cast<const uint8_t *>(cert.data()), cert.size(), nullptr));
	return ParsedCertificate::Create(std::move(cert_buf),
	ParseCertificateOptions{}, nullptr);
	}

	bool PrepareOptsForVerify(const std::string &cert,
	const VerifyTrustStore *trust_store,
	CertificateVerifyOptions *out_opts) const {
	out_opts->leaf_cert = cert;
	std::shared_ptr<const ParsedCertificate> parsed_cert = CertFromString(cert);
	if (!parsed_cert) {
	return false;
	}
	// out_opts->time is a std::optional<int64_t>. If we write directly to
	// *out_opts->time, the std::optional will still be a std::nullopt.
	int64_t time;
	if (!der::GeneralizedTimeToPosixTime(parsed_cert->tbs().validity_not_before,
	&time)) {
	return false;
	}
	out_opts->time = time;
	out_opts->trust_store = trust_store;
	return true;
	}

	std::unique_ptr<VerifyTrustStore> EmptyTrustStore() const {
	return VerifyTrustStore::FromDER("", nullptr);
	}

	protected:
	std::string generic_cert_;
	std::string bitflip_cert_;
	std::string leaf_b_;
	std::string leaf_c_;

	// the trusted subtree for [8, 13) that is used in \|generic_cert_\|,
	// \|bitflip_cert_\|.
	TrustedSubtree generic_cert_subtree_;
	// Subtree for \|leaf_b_\| which overlaps with \|generic_cert_subtree_\|.
	TrustedSubtree leaf_b_subtree_;
	// Subtree for \|leaf_c_\| which does not overlap with any other subtrees.
	TrustedSubtree leaf_c_subtree_;

	// Relative OID encoding of 32473.1, the log ID used for the MTC Anchor that
	// issued the test MTCs in this test fixture.
	static constexpr uint8_t kAnchorLogId[] = {0x81, 0xfd, 0x59, 0x01};
	static constexpr uint8_t kAnchorLogIdBitflip[] = {0x81, 0xfd, 0x59, 0x00};
	};

	TEST_F(VerifyMTCTest, SignaturelessMTC) {
	// Configure the trust store to trust the MTC anchor with the landmark subtree
	// for \|generic_cert_\|.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
	auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees));
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
	EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}

	TEST_F(VerifyMTCTest, ExplicitlyTrustedLeaf) {
	// Configure the trust store to directly trust the \|generic_cert_\| leaf.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	trust_store->trust_store->AddCertificate(CertFromString(generic_cert_),
	CertificateTrust::ForTrustedLeaf());

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
	EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}

	TEST_F(VerifyMTCTest, ExplicitlyDistrustedLeaf) {
	// Configure the trust store to trust the MTC anchor for \|generic_cert_\|, but
	// also to explicitly distrust that leaf.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	trust_store->trust_store->AddCertificate(CertFromString(generic_cert_),
	CertificateTrust::ForDistrusted());
	std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
	auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees));
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND);
	}

	TEST_F(VerifyMTCTest, WrongProof) {
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
	auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees));
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(bitflip_cert_, trust_store.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	EXPECT_EQ(error.Code(),
	VerifyError::StatusCode::CERTIFICATE_INVALID_SIGNATURE);
	}

	TEST_F(VerifyMTCTest, WrongLogID) {
	// Trust the correct subtree for \|generic_cert_\| but with the wrong log ID.
	// Verifying the cert should fail because even though the proof evaluates to a
	// valid hash, the hash is for the wrong issuer.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
	auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogIdBitflip),
	MakeSpan(trusted_subtrees));
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND);
	}

	TEST_F(VerifyMTCTest, ExpiredMTC) {
	// Configure the trust store to trust the MTC anchor with the landmark subtree
	// for \|generic_cert_\|.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
	auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees));
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	CertificateVerifyOptions opts;
	opts.trust_store = trust_store.get();
	opts.leaf_cert = generic_cert_;
	std::shared_ptr<const ParsedCertificate> parsed_cert =
	CertFromString(generic_cert_);
	ASSERT_TRUE(parsed_cert);
	int64_t time;
	ASSERT_TRUE(der::GeneralizedTimeToPosixTime(
	parsed_cert->tbs().validity_not_after, &time));
	// set verify time to 1 second after the cert's validity period:
	opts.time = time + 1;
	VerifyError error;
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	EXPECT_EQ(error.Code(), VerifyError::StatusCode::CERTIFICATE_EXPIRED);
	}

	TEST_F(VerifyMTCTest, TrustStoreConfiguration) {
	// Test that an MTC isn't trusted if there's no MTCAnchor set on the trust
	// store.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND);
	}

	TEST_F(VerifyMTCTest, BadMTCAnchorHash) {
	// Test that an MTC isn't trusted if the MTCAnchor's TrustedSubtree has the
	// wrong hash. Configure the trust store to trust the MTC anchor with the
	// landmark subtree for \|generic_cert_\|.
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	std::vector<TrustedSubtree> trusted_subtrees = {generic_cert_subtree_};
	trusted_subtrees[0].hash[0] ^= 1;
	auto mtc_anchor = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees));
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(generic_cert_, trust_store.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	EXPECT_EQ(error.Code(),
	VerifyError::StatusCode::CERTIFICATE_INVALID_SIGNATURE);
	}

	TEST_F(VerifyMTCTest, SubtreeRangesMatch) {
	// generic_cert_ and leaf_b_ have proofs to subtree ranges with the same start
	// but different ends. Check that CertificateVerify only succeeds if the trust
	// store has the right MTCAnchor.
	std::vector<TrustedSubtree> trusted_subtrees_a = {generic_cert_subtree_};
	std::vector<TrustedSubtree> trusted_subtrees_b = {leaf_b_subtree_};

	auto mtc_anchor_a = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees_a));
	auto mtc_anchor_b = std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId),
	MakeSpan(trusted_subtrees_b));

	std::unique_ptr<VerifyTrustStore> trust_store_a = EmptyTrustStore();
	ASSERT_TRUE(trust_store_a->trust_store->AddMTCTrustAnchor(mtc_anchor_a));
	{
	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(
	PrepareOptsForVerify(generic_cert_, trust_store_a.get(), &opts));
	EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}
	{
	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(leaf_b_, trust_store_a.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}

	std::unique_ptr<VerifyTrustStore> trust_store_b = EmptyTrustStore();
	ASSERT_TRUE(trust_store_b->trust_store->AddMTCTrustAnchor(mtc_anchor_b));
	{
	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(leaf_b_, trust_store_b.get(), &opts));
	EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}
	{
	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(
	PrepareOptsForVerify(generic_cert_, trust_store_b.get(), &opts));
	EXPECT_FALSE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}
	}

	TEST_F(VerifyMTCTest, MultipleSubtrees) {
	std::vector<TrustedSubtree> subtrees = {generic_cert_subtree_,
	leaf_b_subtree_, leaf_c_subtree_};
	auto mtc_anchor =
	std::make_shared<MTCAnchor>(MakeSpan(kAnchorLogId), MakeSpan(subtrees));
	std::unique_ptr<VerifyTrustStore> trust_store = EmptyTrustStore();
	ASSERT_TRUE(trust_store->trust_store->AddMTCTrustAnchor(mtc_anchor));

	// Check that generic_cert_, leaf_b_, and leaf_c_ are all trusted.
	std::vector<std::string> leafs = {generic_cert_, leaf_b_, leaf_c_};
	for (size_t i = 0; i < leafs.size(); i++) {
	SCOPED_TRACE(testing::Message() << "Leaf " << i);
	CertificateVerifyOptions opts;
	VerifyError error;
	ASSERT_TRUE(PrepareOptsForVerify(leafs[i], trust_store.get(), &opts));
	EXPECT_TRUE(CertificateVerify(opts, &error)) << error.DiagnosticString();
	}
	}

	BSSL_NAMESPACE_END