Implement plants-04 landmark relative MTC verification. Change-Id: I81733dd7b7b4f7048e53fd17d8fbdcaccbde129b Bug: 452986180 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/96247 Reviewed-by: Nick Harper <nharper@chromium.org> Commit-Queue: Matt Mueller <mattm@google.com>

diff --git a/gen/sources.bzl b/gen/sources.bzl
index 8b57aa8..a7ff8d4 100644
--- a/gen/sources.bzl
+++ b/gen/sources.bzl

@@ -2324,6 +2324,9 @@
     "pki/testdata/path_builder_unittest/mtc/leaf.pem",
     "pki/testdata/path_builder_unittest/mtc/mtc-ica.pem",
     "pki/testdata/path_builder_unittest/mtc/mtc-leaf.pem",
+    "pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem",
+    "pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem",
+    "pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem",
     "pki/testdata/path_builder_unittest/multi-root-A-by-B.pem",
     "pki/testdata/path_builder_unittest/multi-root-B-by-C.pem",
     "pki/testdata/path_builder_unittest/multi-root-B-by-F.pem",

diff --git a/gen/sources.cmake b/gen/sources.cmake
index 9acba30..e04e968 100644
--- a/gen/sources.cmake
+++ b/gen/sources.cmake

@@ -2382,6 +2382,9 @@
   pki/testdata/path_builder_unittest/mtc/leaf.pem
   pki/testdata/path_builder_unittest/mtc/mtc-ica.pem
   pki/testdata/path_builder_unittest/mtc/mtc-leaf.pem
+  pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem
+  pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem
+  pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem
   pki/testdata/path_builder_unittest/multi-root-A-by-B.pem
   pki/testdata/path_builder_unittest/multi-root-B-by-C.pem
   pki/testdata/path_builder_unittest/multi-root-B-by-F.pem

diff --git a/gen/sources.gni b/gen/sources.gni
index 8b13bb5..611aab5 100644
--- a/gen/sources.gni
+++ b/gen/sources.gni

@@ -2324,6 +2324,9 @@
   "pki/testdata/path_builder_unittest/mtc/leaf.pem",
   "pki/testdata/path_builder_unittest/mtc/mtc-ica.pem",
   "pki/testdata/path_builder_unittest/mtc/mtc-leaf.pem",
+  "pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem",
+  "pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem",
+  "pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem",
   "pki/testdata/path_builder_unittest/multi-root-A-by-B.pem",
   "pki/testdata/path_builder_unittest/multi-root-B-by-C.pem",
   "pki/testdata/path_builder_unittest/multi-root-B-by-F.pem",

diff --git a/gen/sources.json b/gen/sources.json
index 92e375e..6309f27 100644
--- a/gen/sources.json
+++ b/gen/sources.json

@@ -2304,6 +2304,9 @@
       "pki/testdata/path_builder_unittest/mtc/leaf.pem",
       "pki/testdata/path_builder_unittest/mtc/mtc-ica.pem",
       "pki/testdata/path_builder_unittest/mtc/mtc-leaf.pem",
+      "pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem",
+      "pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem",
+      "pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem",
       "pki/testdata/path_builder_unittest/multi-root-A-by-B.pem",
       "pki/testdata/path_builder_unittest/multi-root-B-by-C.pem",
       "pki/testdata/path_builder_unittest/multi-root-B-by-F.pem",

diff --git a/gen/sources.mk b/gen/sources.mk
index fa0b051..87b3d53 100644
--- a/gen/sources.mk
+++ b/gen/sources.mk

@@ -2296,6 +2296,9 @@
   pki/testdata/path_builder_unittest/mtc/leaf.pem \
   pki/testdata/path_builder_unittest/mtc/mtc-ica.pem \
   pki/testdata/path_builder_unittest/mtc/mtc-leaf.pem \
+  pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem \
+  pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem \
+  pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem \
   pki/testdata/path_builder_unittest/multi-root-A-by-B.pem \
   pki/testdata/path_builder_unittest/multi-root-B-by-C.pem \
   pki/testdata/path_builder_unittest/multi-root-B-by-F.pem \

diff --git a/pki/path_builder_unittest.cc b/pki/path_builder_unittest.cc
index ee1a852..f83af58 100644
--- a/pki/path_builder_unittest.cc
+++ b/pki/path_builder_unittest.cc

@@ -2452,6 +2452,133 @@
   EXPECT_EQ(0xB33F, data->value);
 }
 
+class PathBuilderMTCPlants04Test : public PathBuilderSimpleChainTest {
+ public:
+  PathBuilderMTCPlants04Test() = default;
+
+ protected:
+  void SetUp() override {
+    PathBuilderSimpleChainTest::SetUp();
+
+    // Set up the MTCAnchor.
+    std::string subtree_hash;
+    ASSERT_TRUE(string_util::Base64Decode(
+        "ir6iVcgTrbuHdXB3lKGny6VKSlE1OB5Q+LrtdFH+qIE=", &subtree_hash));
+    TrustedSubtree subtree;
+    ASSERT_EQ(subtree_hash.size(), subtree.hash.size());
+    memcpy(subtree.hash.data(), subtree_hash.data(), subtree_hash.size());
+    subtree.range.start = 0;
+    subtree.range.end = 10;
+    std::map<uint16_t, std::vector<TrustedSubtree>> subtrees;
+    subtrees[1] = {std::move(subtree)};
+    static constexpr uint8_t ca_id[] = {0x81, 0xfd, 0x59, 0x01};
+    mtc_anchor_ =
+        std::make_shared<MTCAnchor>(MakeSpan(ca_id), std::move(subtrees));
+    ASSERT_EQ(mtc_anchor_->spec_version(), MTCAnchor::kPlants04);
+  }
+
+  CertPathBuilder::Result RunPathBuilder(
+      const std::shared_ptr<const ParsedCertificate> &leaf,
+      TrustStoreInMemory *trust_store, CertIssuerSource *intermediates,
+      CertPathBuilderDelegate *delegate) {
+    SimplePathBuilderDelegate default_delegate(
+        2048, SimplePathBuilderDelegate::DigestPolicy::kStrong);
+    if (!delegate) {
+      delegate = &default_delegate;
+    }
+
+    CertPathBuilder path_builder(
+        leaf, trust_store, delegate, leaf->tbs().validity_not_before,
+        KeyPurpose::ANY_EKU, InitialExplicitPolicy::kFalse,
+        {der::Input(kAnyPolicyOid)}, InitialPolicyMappingInhibit::kFalse,
+        InitialAnyPolicyInhibit::kFalse);
+    if (intermediates) {
+      path_builder.AddCertIssuerSource(intermediates);
+    }
+    return path_builder.Run();
+  }
+
+  std::shared_ptr<MTCAnchor> mtc_anchor_;
+};
+
+TEST_F(PathBuilderMTCPlants04Test, CheckPathAfterVerification) {
+  // Set up MTC leaf and its trust anchor.
+  std::shared_ptr<const ParsedCertificate> mtc_leaf;
+  ASSERT_TRUE(ReadTestCert("mtc_plants04/mtc-leaf.pem", &mtc_leaf));
+  TrustStoreInMemory in_memory;
+  ASSERT_TRUE(in_memory.AddMTCTrustAnchor(mtc_anchor_));
+
+  // Check that the path is valid with no delegate.
+  CertPathBuilder::Result result =
+      RunPathBuilder(mtc_leaf, &in_memory, nullptr, nullptr);
+  ASSERT_TRUE(result.HasValidPath());
+
+  // Check that verification fails when the delegate adds an error.
+  AddOtherErrorPathBuilderDelegate delegate;
+  result = RunPathBuilder(mtc_leaf, &in_memory, nullptr, &delegate);
+  ASSERT_FALSE(result.HasValidPath());
+
+  ASSERT_LT(result.best_result_index, result.paths.size());
+  const CertPathBuilderResultPath *failed_path =
+      result.paths[result.best_result_index].get();
+  ASSERT_TRUE(failed_path);
+
+  // An error should have been added to other errors
+  const CertErrors *other_errors = failed_path->errors.GetOtherErrors();
+  ASSERT_TRUE(other_errors);
+  EXPECT_TRUE(other_errors->ContainsError(kErrorFromDelegate));
+
+  // The newly defined delegate error should map to VERIFICATION_FAILURE
+  // since the error is not associated to a certificate.
+  VerifyError error = result.GetBestPathVerifyError();
+  ASSERT_EQ(error.Code(), VerifyError::StatusCode::VERIFICATION_FAILURE)
+      << error.DiagnosticString();
+}
+
+TEST_F(PathBuilderMTCPlants04Test, PathLength) {
+  std::shared_ptr<const ParsedCertificate> leaf;
+  ASSERT_TRUE(ReadTestCert("mtc_plants04/leaf.pem", &leaf));
+  std::shared_ptr<const ParsedCertificate> ica;
+  ASSERT_TRUE(ReadTestCert("mtc_plants04/mtc-ica.pem", &ica));
+
+  // Test that verifying leaf succeeds using ica as the trusted root.
+  {
+    TrustStoreInMemory in_memory;
+    in_memory.AddTrustAnchor(ica);
+    CertPathBuilder::Result result =
+        RunPathBuilder(leaf, &in_memory, nullptr, nullptr);
+    EXPECT_TRUE(result.HasValidPath());
+  }
+
+  // Test that verifying ica (as a leaf) succeeds using the MTC trust anchor.
+  {
+    TrustStoreInMemory in_memory;
+    ASSERT_TRUE(in_memory.AddMTCTrustAnchor(mtc_anchor_));
+    CertPathBuilder::Result result =
+        RunPathBuilder(ica, &in_memory, nullptr, nullptr);
+    EXPECT_TRUE(result.HasValidPath());
+  }
+
+  // Test that verifying leaf fails when using the MTC trust anchor.
+  {
+    TrustStoreInMemory in_memory;
+    ASSERT_TRUE(in_memory.AddMTCTrustAnchor(mtc_anchor_));
+    CertIssuerSourceStatic intermediates;
+    intermediates.AddCert(ica);
+    CertPathBuilder::Result result =
+        RunPathBuilder(leaf, &in_memory, &intermediates, nullptr);
+    EXPECT_FALSE(result.HasValidPath());
+    VerifyError error = result.GetBestPathVerifyError();
+    EXPECT_EQ(error.Code(), VerifyError::StatusCode::PATH_NOT_FOUND)
+        << error.DiagnosticString();
+    const auto &path = *result.GetBestPathPossiblyInvalid();
+    ASSERT_EQ(3u, path.certs.size());
+    EXPECT_EQ(leaf, path.certs[0]);
+    EXPECT_EQ(ica, path.certs[1]);
+    EXPECT_EQ(mtc_anchor_->AsCert(), path.certs[2]);
+  }
+}
+
 class PathBuilderMTCTest : public PathBuilderSimpleChainTest {
  public:
   PathBuilderMTCTest() = default;
@@ -2473,6 +2600,7 @@
     static const uint8_t log_id[] = {0x81, 0xfd, 0x59, 0x01};
     mtc_anchor_ =
         std::make_shared<MTCAnchor>(MakeSpan(log_id), MakeSpan(subtrees));
+    ASSERT_EQ(mtc_anchor_->spec_version(), MTCAnchor::kDavidben08);
   }
 
   CertPathBuilder::Result RunPathBuilder(

diff --git a/pki/signature_algorithm.h b/pki/signature_algorithm.h
index b518392..ba10e2c 100644
--- a/pki/signature_algorithm.h
+++ b/pki/signature_algorithm.h

@@ -55,7 +55,9 @@
   kRsaPssSha256,
   kRsaPssSha384,
   kRsaPssSha512,
-  kMtcProofDraftDavidben08,
+  kMtcProofDraftPlants04,
+  // The MTC draft versions use the same OID, so make them an alias.
+  kMtcProofDraftDavidben08 = kMtcProofDraftPlants04,
   kMldsa44,
   kMldsa65,
   kMldsa87,

diff --git a/pki/testdata/path_builder_unittest/mtc_plants04/README.md b/pki/testdata/path_builder_unittest/mtc_plants04/README.md
new file mode 100644
index 0000000..3eaecee
--- /dev/null
+++ b/pki/testdata/path_builder_unittest/mtc_plants04/README.md

@@ -0,0 +1,35 @@
+# MTC test certs
+
+This directory contains the following certs:
+
+- `mtc-leaf.pem`
+  - signatureless MTC issued by an MTC CA
+- `mtc-ica.pem`
+  - signatureless MTC issued by the same MTC CA
+  - its BasicConstraints has `cA=TRUE`
+- `leaf.pem`
+  - classical ECDSA cert (SPKI) with ECDSA `signatureAlgorithm`
+  - issued by `mtc-ica.pem`
+
+## (Re)generating test certs
+
+Generating these certs is done in two steps.
+
+The first step is to generate a keypair for the ICA and use the private key to
+sign the leaf cert:
+
+1. Run `go run generate_leaf.go`
+2. Copy the certificate PEM to `leaf.pem`
+3. Copy the ICA SPKI base64 to the first `PublicKey` entry in `mtc-config.json`
+
+The next step is to generate the MTC representation of the ICA:
+
+1. Run `mkdir out`
+2. Run
+   `go run github.com/ietf-plants-wg/merkle-tree-certs.git/demo@9029a99bcfa4e91b8b8e9ba646ac386a6e1c208f -config=mtc-config.json -out=out`
+3. Move `out/cert_0_0.pem` to `mtc-ica.pem`
+4. Move `out/cert_1_0.pem` to `mtc-leaf.pem`
+5. Copy the subtree and hash from the command output into
+   `PathBuilderMTCPlants04Test::SetUp`.
+6. Remove other artifacts created by the merkle-tree-certs/demo tool (e.g.
+   `rm -r out`).

diff --git a/pki/testdata/path_builder_unittest/mtc_plants04/generate_leaf.go b/pki/testdata/path_builder_unittest/mtc_plants04/generate_leaf.go
new file mode 100644
index 0000000..b63e467
--- /dev/null
+++ b/pki/testdata/path_builder_unittest/mtc_plants04/generate_leaf.go

@@ -0,0 +1,73 @@
+package main
+
+import (
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/rand"
+	"crypto/x509"
+	"crypto/x509/pkix"
+	"encoding/base64"
+	"encoding/pem"
+	"fmt"
+	"math/big"
+	"os"
+	"time"
+)
+
+func do() error {
+	key, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
+	if err != nil {
+		return err
+	}
+	leafKey, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
+	if err != nil {
+		return err
+	}
+	icaTempl := &x509.Certificate{
+		Subject: pkix.Name{CommonName: "ICA 1"},
+		IsCA: true,
+		SerialNumber: big.NewInt(1),
+		KeyUsage: x509.KeyUsageCertSign | x509.KeyUsageDigitalSignature,
+		ExtKeyUsage: []x509.ExtKeyUsage{x509.ExtKeyUsageServerAuth},
+		BasicConstraintsValid: true,
+		NotBefore: time.Date(2020, time.January, 1, 0, 0, 0, 0, time.UTC),
+		NotAfter: time.Date(2030, time.December, 31, 23, 59, 59, 0, time.UTC),
+	}
+	ica, err := x509.CreateCertificate(rand.Reader, icaTempl, icaTempl, key.Public(), key)
+	if err != nil {
+		return err
+	}
+	icaCert, err := x509.ParseCertificate(ica)
+	if err != nil {
+		return err
+	}
+
+	leafTempl := &x509.Certificate{
+		Subject: pkix.Name{CommonName: "Leaf 1"},
+		SerialNumber: big.NewInt(1),
+		KeyUsage: x509.KeyUsageDigitalSignature,
+		ExtKeyUsage: []x509.ExtKeyUsage{x509.ExtKeyUsageServerAuth},
+		BasicConstraintsValid: true,
+		NotBefore: time.Date(2020, time.January, 1, 0, 0, 0, 0, time.UTC),
+		NotAfter: time.Date(2030, time.December, 31, 23, 59, 59, 0, time.UTC),
+		DNSNames: []string{"example.com"},
+	}
+
+	cert, err := x509.CreateCertificate(rand.Reader, leafTempl, icaTempl, leafKey.Public(), key)
+	if err != nil {
+		return err
+	}
+
+	pemBlock := &pem.Block{Type: "CERTIFICATE", Bytes: cert}
+	pem.Encode(os.Stdout, pemBlock)
+	ica_spki := base64.StdEncoding.EncodeToString(icaCert.RawSubjectPublicKeyInfo)
+	fmt.Printf("ICA SPKI: %s\n", ica_spki)
+	return nil
+}
+
+func main() {
+	if err := do(); err != nil {
+		fmt.Fprintf(os.Stderr, "Error: %v", err)
+		os.Exit(1)
+	}
+}

diff --git a/pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem b/pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem
new file mode 100644
index 0000000..ebbd09f
--- /dev/null
+++ b/pki/testdata/path_builder_unittest/mtc_plants04/leaf.pem

@@ -0,0 +1,10 @@
+-----BEGIN CERTIFICATE-----
+MIIBXDCCAQOgAwIBAgIBATAKBggqhkjOPQQDAjAQMQ4wDAYDVQQDEwVJQ0EgMTAe
+Fw0yMDAxMDEwMDAwMDBaFw0zMDEyMzEyMzU5NTlaMBExDzANBgNVBAMTBkxlYWYg
+MTBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABHhYrp7qxXYTNqUCG36ka6f7GCgR
+fKd0j7dnYU5oDXmFFfzML2c072nZWLCN3touQ8rqWYEvzu0q5FchiXPTi22jTTBL
+MA4GA1UdDwEB/wQEAwIHgDATBgNVHSUEDDAKBggrBgEFBQcDATAMBgNVHRMBAf8E
+AjAAMBYGA1UdEQQPMA2CC2V4YW1wbGUuY29tMAoGCCqGSM49BAMCA0cAMEQCIFLN
+Ah9IrTtUwJuH6NbthNNE3+SxbZLl0wz7PiBgqvmZAiAO/aT4xctesdxvFGC24s2+
+ewkyTiCBiq2bej/yub5bog==
+-----END CERTIFICATE-----

diff --git a/pki/testdata/path_builder_unittest/mtc_plants04/mtc-config.json b/pki/testdata/path_builder_unittest/mtc_plants04/mtc-config.json
new file mode 100644
index 0000000..8060d9c
--- /dev/null
+++ b/pki/testdata/path_builder_unittest/mtc_plants04/mtc-config.json

@@ -0,0 +1,62 @@
+{
+  "Version": "plants-04",
+  "ID": "32473.1",
+  "LogNumber": 1,
+  "Cosigners": [
+    {
+      "CosignerID": "32473.1",
+      "SignatureAlgorithm": "mldsa44",
+      "PrivateKey": "MDQCAQAwCwYJYIZIAWUDBAMRBCKAIAABAgMEBQYHCAkKCwwNDg8QERITFBUWFxgZGhscHR4f"
+    }
+  ],
+  "Entries": [
+    {
+      "PublicKey": "MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEyXLJquJMGPkBDu854pXQbva4Gqn48F6tH5GW9NQpNJCAzCveJVZpSrriRUt6ira3Nags4ZYniXDDa7VkvaMflA==",
+      "Subject": {
+        "CommonName": "ICA 1"
+      },
+      "NotBefore": "2020-01-01T00:00:00Z",
+      "NotAfter": "2030-12-31T23:59:59Z",
+      "ExtKeyUsage": ["ServerAuth"],
+      "KeyUsage": ["CertSign"],
+      "IsCA": true,
+      "Certificates": [
+        {
+          "SubtreeStart": 0,
+          "SubtreeEnd": 10
+        }
+      ]
+    },
+    {
+      "PublicKey": "MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEyxiC16lts+SOL87OwHhGDzK9/dyUd7sM80jAf53VL+AV38HoHKpmA7LJoYLf4yVhcVleNcxufsAfcPueTLX0Vg==",
+      "NotBefore": "2020-01-01T00:00:00Z",
+      "NotAfter": "2030-12-31T23:59:59Z",
+      "DNSNames": [
+        "a.example",
+        "*.blah.a.example"
+      ],
+      "KeyUsage": [
+        "DigitalSignature"
+      ],
+      "ExtKeyUsage": [
+        "ServerAuth"
+      ],
+      "IsCA": false,
+      "Certificates": [
+        {
+          "SubtreeStart": 0,
+          "SubtreeEnd": 10
+        }
+      ]
+    },
+    {
+      "Repeat": 8,
+      "Subject": {
+        "CommonName": "Filler certificates"
+      },
+      "PublicKey": "MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEyxiC16lts+SOL87OwHhGDzK9/dyUd7sM80jAf53VL+AV38HoHKpmA7LJoYLf4yVhcVleNcxufsAfcPueTLX0Vg==",
+      "NotBefore": "2020-01-01T00:00:00Z",
+      "NotAfter": "2030-12-31T23:59:59Z"
+    }
+  ]
+}

diff --git a/pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem b/pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem
new file mode 100644
index 0000000..141e3dc
--- /dev/null
+++ b/pki/testdata/path_builder_unittest/mtc_plants04/mtc-ica.pem

@@ -0,0 +1,11 @@
+-----BEGIN CERTIFICATE-----
+MIIBqTCCAQGgAwIBAgIHAQAAAAAAADAMBgorBgEEAYLaSy8AMBkxFzAVBgorBgEE
+AYLaSy8BDAczMjQ3My4xMB4XDTIwMDEwMTAwMDAwMFoXDTMwMTIzMTIzNTk1OVow
+EDEOMAwGA1UEAxMFSUNBIDEwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAATJcsmq
+4kwY+QEO7znildBu9rgaqfjwXq0fkZb01Ck0kIDMK94lVmlKuuJFS3qKtrc1qCzh
+lieJcMNrtWS9ox+UozswOTAOBgNVHQ8BAf8EBAMCAgQwFgYDVR0lAQH/BAwwCgYI
+KwYBBQUHAwEwDwYDVR0TAQH/BAUwAwEB/zAMBgorBgEEAYLaSy8AA4GTAAAAAAAA
+AAAAAAAAAAAKAIA5h2IM+KooLFZ06DQOr46/cN+w687YLbzTbiuolmvNCBM4nk7Z
+VC430YX0uWLvZnWWQLtKn27NQ5TTBlhBNe2ANgd/I+JGoIgfURbLdN2pIkCalEIJ
+1a+2c+oBuQqvCbYTOJ5O2VQuN9GF9Lli72Z1lkC7Sp9uzUOU0wZYQTXtgAAA
+-----END CERTIFICATE-----

diff --git a/pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem b/pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem
new file mode 100644
index 0000000..5e72225
--- /dev/null
+++ b/pki/testdata/path_builder_unittest/mtc_plants04/mtc-leaf.pem

@@ -0,0 +1,12 @@
+-----BEGIN CERTIFICATE-----
+MIIBwTCCARmgAwIBAgIHAQAAAAAAATAMBgorBgEEAYLaSy8AMBkxFzAVBgorBgEE
+AYLaSy8BDAczMjQ3My4xMB4XDTIwMDEwMTAwMDAwMFoXDTMwMTIzMTIzNTk1OVow
+ADBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABMsYgtepbbPkji/OzsB4Rg8yvf3c
+lHe7DPNIwH+d1S/gFd/B6ByqZgOyyaGC3+MlYXFZXjXMbn7AH3D7nky19FajYzBh
+MA4GA1UdDwEB/wQEAwIHgDAWBgNVHSUBAf8EDDAKBggrBgEFBQcDATApBgNVHREB
+Af8EHzAdgglhLmV4YW1wbGWCECouYmxhaC5hLmV4YW1wbGUwDAYDVR0TAQH/BAIw
+ADAMBgorBgEEAYLaSy8AA4GTAAAAAAAAAAAAAAAAAAAKAIAZtsOGmmcSEZW9/6yg
+EowPe+S3P3kI+Lry2r5fHt8IGxM4nk7ZVC430YX0uWLvZnWWQLtKn27NQ5TTBlhB
+Ne2ANgd/I+JGoIgfURbLdN2pIkCalEIJ1a+2c+oBuQqvCbYTOJ5O2VQuN9GF9Lli
+72Z1lkC7Sp9uzUOU0wZYQTXtgAAA
+-----END CERTIFICATE-----

diff --git a/pki/trust_store.cc b/pki/trust_store.cc
index ac9af61..5f8fef5 100644
--- a/pki/trust_store.cc
+++ b/pki/trust_store.cc

@@ -15,6 +15,7 @@
 #include "trust_store.h"
 
 #include <cassert>
+#include <cstdint>
 #include <cstring>
 #include <optional>
 
@@ -189,21 +190,38 @@
 
 MTCAnchor::MTCAnchor(bssl::Span<const uint8_t> log_id,
                      Span<const TrustedSubtree> trusted_subtrees)
-    : log_id_(log_id.begin(), log_id.end()),
-      trusted_subtrees_(trusted_subtrees.begin(), trusted_subtrees.end()) {
+    : spec_version_(MTCAnchor::MtcSpecVersion::kDavidben08),
+      ca_id_(log_id.begin(), log_id.end()) {
+  // For davidben-08 anchors (which don't have multiple logs), stick the
+  // subtrees into the map with log_number 0. (log_number 0 is invalid in
+  // plants-04.)
+  trusted_subtrees_.emplace(
+      0, std::vector<TrustedSubtree>(trusted_subtrees.begin(),
+                                     trusted_subtrees.end()));
   CreateSyntheticCert(log_id);
 }
 
+MTCAnchor::MTCAnchor(
+    bssl::Span<const uint8_t> ca_id,
+    std::map<uint16_t, std::vector<TrustedSubtree>> trusted_subtrees)
+    : spec_version_(MTCAnchor::MtcSpecVersion::kPlants04),
+      ca_id_(ca_id.begin(), ca_id.end()),
+      trusted_subtrees_(std::move(trusted_subtrees)) {
+  CreateSyntheticCert(ca_id);
+}
+
 bool MTCAnchor::IsValid() const {
   if (!synthetic_cert_) {
     return false;
   }
-  Subtree min_subtree;
-  for (const auto &subtree : trusted_subtrees_) {
-    if (!subtree.range.IsValid() || subtree.range < min_subtree) {
-      return false;
+  for (const auto &[log_number, subtrees] : trusted_subtrees_) {
+    Subtree min_subtree;
+    for (const auto &subtree : subtrees) {
+      if (!subtree.range.IsValid() || subtree.range < min_subtree) {
+        return false;
+      }
+      min_subtree = subtree.range;
     }
-    min_subtree = subtree.range;
   }
   return true;
 }
@@ -224,18 +242,30 @@
 
 std::optional<TreeHashConstSpan> MTCAnchor::SubtreeHash(
     Subtree target_range) const {
+  BSSL_CHECK(spec_version_ == kDavidben08);
+  return SubtreeHash(0, target_range);
+}
+
+std::optional<TreeHashConstSpan> MTCAnchor::SubtreeHash(
+    uint16_t log_number,
+    Subtree target_range) const {
+  auto subtrees_it = trusted_subtrees_.find(log_number);
+  if (subtrees_it == trusted_subtrees_.end()) {
+    return std::nullopt;
+  }
+  const auto& subtrees = subtrees_it->second;
   auto it = std::lower_bound(
-      trusted_subtrees_.begin(), trusted_subtrees_.end(), target_range,
+      subtrees.begin(), subtrees.end(), target_range,
       [](const TrustedSubtree &subtree, Subtree range) -> bool {
         return subtree.range < range;
       });
-  if (it == trusted_subtrees_.end() || it->range != target_range) {
+  if (it == subtrees.end() || it->range != target_range) {
     return std::nullopt;
   }
   return it->hash;
 }
 
-void MTCAnchor::CreateSyntheticCert(bssl::Span<const uint8_t> log_id) {
+void MTCAnchor::CreateSyntheticCert(bssl::Span<const uint8_t> ca_id) {
   bssl::ScopedCBB cbb;
   CBB cert, tbs_cert, version, validity, subject_seq, subject_set, subject_log,
       signature;
@@ -268,27 +298,27 @@
   BSSL_CHECK(CBB_add_asn1(&subject_seq, &subject_set, CBS_ASN1_SET));
   BSSL_CHECK(CBB_add_asn1(&subject_set, &subject_log, CBS_ASN1_SEQUENCE));
 
-  // Section 5.2: Use OID 1.3.6.1.4.1.44363.47.1 as the attribute type for the
-  // log ID's name. Note that this is the early experimentation OID in the
+  // Section 5.1: Use OID 1.3.6.1.4.1.44363.47.1 as the attribute type for the
+  // CA ID's name. Note that this is the early experimentation OID in the
   // draft rather than the real value of `id-rdna-trustAnchorID`.
-  static uint8_t log_attr_oid[] = {0x2b, 0x06, 0x01, 0x04, 0x01,
+  static uint8_t tai_attr_oid[] = {0x2b, 0x06, 0x01, 0x04, 0x01,
                                    0x82, 0xda, 0x4b, 0x2f, 0x01};
-  BSSL_CHECK(CBB_add_asn1_element(&subject_log, CBS_ASN1_OBJECT, log_attr_oid,
-                                  sizeof(log_attr_oid)));
+  BSSL_CHECK(CBB_add_asn1_element(&subject_log, CBS_ASN1_OBJECT, tai_attr_oid,
+                                  sizeof(tai_attr_oid)));
 
-  // Section 5.2's note for initial experimentation also says to use UTF8String
+  // Section 5.1's note for initial experimentation also says to use UTF8String
   // to represent the attribute's value rather than RELATIVE-OID.
 
-  //  Convert the relative OID `log_id` to a string. This can fail.
-  CBS log_id_oid(log_id);
-  bssl::UniquePtr<char> log_id_text(CBS_asn1_relative_oid_to_text(&log_id_oid));
-  if (!log_id_text) {
+  //  Convert the relative OID `ca_id` to a string. This can fail.
+  CBS ca_id_oid(ca_id);
+  bssl::UniquePtr<char> ca_id_text(CBS_asn1_relative_oid_to_text(&ca_id_oid));
+  if (!ca_id_text) {
     return;
   }
   BSSL_CHECK(
       CBB_add_asn1_element(&subject_log, CBS_ASN1_UTF8STRING,
-                           reinterpret_cast<const uint8_t *>(log_id_text.get()),
-                           strlen(log_id_text.get())));
+                           reinterpret_cast<const uint8_t *>(ca_id_text.get()),
+                           strlen(ca_id_text.get())));
 
   // subjectPublicKeyInfo
   BSSL_CHECK(CBB_add_asn1_element(&tbs_cert, CBS_ASN1_SEQUENCE, nullptr, 0));

diff --git a/pki/trust_store.h b/pki/trust_store.h
index 03cacbb..39c74d8 100644
--- a/pki/trust_store.h
+++ b/pki/trust_store.h

@@ -143,31 +143,62 @@
 
 class OPENSSL_EXPORT MTCAnchor {
  public:
-  // Create an MTCAnchor for a trusted log with `log_id` containing the DER
-  // encoding of the relative OID of the log's ID. The `trusted_subtrees` must
-  // be sorted by their subtree ranges.
+  enum MtcSpecVersion {
+    // draft-davidben-tls-merkle-tree-certs-08
+    kDavidben08,
+    // draft-ietf-plants-merkle-tree-certs-04
+    kPlants04
+  };
+  // Create an MTCAnchor with spec version kDavidben08 for a trusted log with
+  // `log_id` containing the DER encoding of the relative OID of the log's ID.
+  // The `trusted_subtrees` must be sorted by their subtree ranges.
   MTCAnchor(Span<const uint8_t> log_id,
             Span<const TrustedSubtree> trusted_subtrees);
 
+  // Create an MTCAnchor with spec version kPlants04 for a trusted CA with
+  // `ca_id` containing the DER encoding of the relative OID of the CA's ID.
+  // The `trusted_subtrees` must be sorted by their subtree ranges.
+  MTCAnchor(Span<const uint8_t> ca_id,
+            std::map<uint16_t, std::vector<TrustedSubtree>> trusted_subtrees);
+
   // Returns whether this MTCAnchor represents a valid anchor. This function
   // exists because the c'tor inputs could be invalid.
   bool IsValid() const;
 
-  Span<const uint8_t> log_id() const { return log_id_; }
+  MtcSpecVersion spec_version() const { return spec_version_; }
+  Span<const uint8_t> log_id() const {
+    BSSL_CHECK(spec_version_ == kDavidben08);
+    return ca_id_;
+  }
+  Span<const uint8_t> ca_id() const {
+    BSSL_CHECK(spec_version_ == kPlants04);
+    return ca_id_;
+  }
   // 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.
   std::shared_ptr<const ParsedCertificate> AsCert() const;
+
+  // Only valid for spec version kDavidben08.
   std::optional<TreeHashConstSpan> SubtreeHash(Subtree target_range) const;
+  // Only valid for spec version kPlants04.
+  std::optional<TreeHashConstSpan> SubtreeHash(uint16_t log_number,
+                                               Subtree target_range) const;
 
  private:
-  void CreateSyntheticCert(Span<const uint8_t> log_id);
+  void CreateSyntheticCert(Span<const uint8_t> ca_id);
 
-  std::vector<uint8_t> log_id_;
+
+  MtcSpecVersion spec_version_;
+  // (If spec_version_ == kDavidben08, `ca_id` is actually the log id.)
+  std::vector<uint8_t> ca_id_;
   std::shared_ptr<const ParsedCertificate> synthetic_cert_;
-  std::vector<TrustedSubtree> trusted_subtrees_;
+  // If spec_version_ == kDavidben08, the 0th entry in the map will have the
+  // trusted subtrees. Otherwise, this maps from the log_number to the trusted
+  // subtrees for that log.
+  std::map<uint16_t, std::vector<TrustedSubtree>> trusted_subtrees_;
 };
 
 // A TrustAnchor contains information about how a trust anchor is trusted and

diff --git a/pki/verify_certificate_chain.cc b/pki/verify_certificate_chain.cc
index ddbc6c1..21322c5 100644
--- a/pki/verify_certificate_chain.cc
+++ b/pki/verify_certificate_chain.cc

@@ -19,6 +19,7 @@
 
 #include <openssl/base.h>
 #include <openssl/bytestring.h>
+#include <openssl/digest.h>
 #include <openssl/mem.h>
 #include <openssl/sha2.h>
 #include <openssl/span.h>
@@ -1125,8 +1126,8 @@
 
 // This function implements draft-davidben-tls-merkle-tree-certs-08 section 7.2:
 // Verifying Certificate Signatures.
-static bool VerifyMTC(const ParsedCertificate &cert,
-                      const MTCAnchor *mtc_anchor) {
+static bool VerifyMTCDraftDavidben08(const ParsedCertificate &cert,
+                                     const MTCAnchor *mtc_anchor) {
   // Step 1: Check that the TBSCertificate's signature field is id-alg-mtcProof
   // (kMtcProofDraftDavidben08) with omitted parameters.
   if (cert.signature_algorithm() !=
@@ -1263,6 +1264,203 @@
                        expected_subtree_hash->size()) == 0;
 }
 
+// This function implements draft-ietf-plants-merkle-tree-certs-04 section 7.2:
+// Verifying Certificate Signatures.
+static bool VerifyMTCDraftPlants04(const ParsedCertificate &cert,
+                                   const MTCAnchor *mtc_anchor) {
+  // Step 1: Check that the TBSCertificate's signature field is id-alg-mtcProof
+  // (kMtcProofDraftPlants04) with omitted parameters.
+  if (cert.signature_algorithm() !=
+      SignatureAlgorithm::kMtcProofDraftPlants04) {
+    // When we parse the signature algorithm, we check that the parameters are
+    // omitted.
+    return false;
+  }
+
+  // Step 2: Decode the signatureValue as an MTCProof.
+  uint64_t start, end;
+  CBS extensions, inclusion_proof, signatures;
+  CBS mtc_proof(cert.signature_value().bytes());
+  if (cert.signature_value().unused_bits() != 0 ||
+      !CBS_get_u16_length_prefixed(&mtc_proof, &extensions) ||
+      !CBS_get_u48(&mtc_proof, &start) || !CBS_get_u48(&mtc_proof, &end) ||
+      !CBS_get_u16_length_prefixed(&mtc_proof, &inclusion_proof) ||
+      !CBS_get_u16_length_prefixed(&mtc_proof, &signatures) ||
+      CBS_len(&mtc_proof) != 0) {
+    return false;
+  }
+
+  // Step 3: Let serial be the certificate's serial number. If serial is
+  // negative or greater than 2^64-1, abort this process and fail verification.
+  uint64_t serial;
+  if (!der::ParseUint64(cert.tbs().serial_number, &serial)) {
+    return false;
+  }
+
+  // Step 4's revocation check is not performed in this function. The caller is
+  // responsible for performing revocation checks.
+
+  // Step 5: Let index be the least significant 48 bits of serial and let
+  // log_number be serial >> 48. If log_number is zero, abort this process and
+  // fail verification.
+  uint64_t index = serial & ((1ull << 48) - 1);
+  uint16_t log_number = serial >> 48;
+  if (log_number == 0) {
+    return false;
+  }
+
+  // Step 6: Let log_id be the log ID constructed from the CA ID in issuer and
+  // the log_number.
+  //
+  // TODO(crbug.com/452983502): This step is only used for standalone
+  // certificate verification, which isn't implemented yet.
+
+  // Steps 7, 8, and 9 are done in a single pass as described in the procedure
+  // at the end of section 7.2 ("entry_hash can equivalently be computed in a
+  // single pass"):
+  // 1. Initialize a hash instance.
+  bssl::ScopedEVP_MD_CTX entry_hash_ctx;
+  if (!EVP_DigestInit(entry_hash_ctx.get(), EVP_sha256())) {
+    return false;
+  }
+
+  // Write the octet 0x00 to the hash. This is the domain separator for leaf
+  // nodes.
+  // (Note: the procedure as defined in plants-04 is missing this step.)
+  static constexpr uint8_t kDomainSeparator[] = {0x00};
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(), kDomainSeparator,
+                        sizeof(kDomainSeparator))) {
+    return false;
+  }
+
+  // 2. Write the extensions field from the MTCProof to the hash.
+  uint8_t extensions_length[2] = {
+      static_cast<uint8_t>(CBS_len(&extensions) >> 8),
+      static_cast<uint8_t>(CBS_len(&extensions) & 0xff)};
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(), extensions_length,
+                        sizeof(extensions_length)) ||
+      !EVP_DigestUpdate(entry_hash_ctx.get(), CBS_data(&extensions),
+                        CBS_len(&extensions))) {
+    return false;
+  }
+
+  // 3. Write the big-endian, two-byte tbs_cert_entry value to the hash.
+  static constexpr uint8_t kTbsCertEntry[] = {0, 1};
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(), kTbsCertEntry,
+                        sizeof(kTbsCertEntry))) {
+    return false;
+  }
+
+  // 4. Write the TBSCertificate's `version`, `issuer`, `validity`, and
+  // `subject` fields to the hash.
+  // (Note that this is a correction to the instructions in plants-04.)
+  if (cert.tbs().version != CertificateVersion::V1) {
+    ScopedCBB version_outer;
+    CBB version;
+    if (!CBB_init(version_outer.get(), 0) ||
+        !CBB_add_asn1(version_outer.get(), &version,
+                      CBS_ASN1_CONTEXT_SPECIFIC | CBS_ASN1_CONSTRUCTED | 0) ||
+        !CBB_add_asn1_uint64(&version,
+                             static_cast<uint64_t>(cert.tbs().version)) ||
+        !CBB_flush(version_outer.get()) ||
+        !EVP_DigestUpdate(entry_hash_ctx.get(), CBB_data(version_outer.get()),
+                          CBB_len(version_outer.get()))) {
+      return false;
+    }
+  }
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(), cert.tbs().issuer_tlv.data(),
+                        cert.tbs().issuer_tlv.size()) ||
+      !EVP_DigestUpdate(entry_hash_ctx.get(), cert.tbs().validity_tlv.data(),
+                        cert.tbs().validity_tlv.size()) ||
+      !EVP_DigestUpdate(entry_hash_ctx.get(), cert.tbs().subject_tlv.data(),
+                        cert.tbs().subject_tlv.size())) {
+    return false;
+  }
+
+  // 5. Write the subjectPublicKeyInfo's algorithm field to the hash.
+  CBS spki(cert.tbs().spki_tlv);
+  CBS spki_sequence, spki_algorithm_tlv;
+  if (!CBS_get_asn1(&spki, &spki_sequence, CBS_ASN1_SEQUENCE) ||
+      !CBS_get_asn1_element(&spki_sequence, &spki_algorithm_tlv,
+                            CBS_ASN1_SEQUENCE) ||
+      !EVP_DigestUpdate(entry_hash_ctx.get(), CBS_data(&spki_algorithm_tlv),
+                        CBS_len(&spki_algorithm_tlv))) {
+    return false;
+  }
+
+  // 6. Write the octet 0x04 to the hash. This is an OCTET STRING identifier.
+  // 7. Write the octet L to the hash, where L is the hash length. (This
+  // assumes L is at most 127.)
+  static constexpr uint8_t kSpkiHashTagAndLength[] = {CBS_ASN1_OCTETSTRING,
+                                                      SHA256_DIGEST_LENGTH};
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(), kSpkiHashTagAndLength,
+                        sizeof(kSpkiHashTagAndLength))) {
+    return false;
+  }
+
+  // 8. Write H to the hash, where H is the hash of the entire
+  // subjectPublicKeyInfo field.
+  uint8_t spki_hash[SHA256_DIGEST_LENGTH];
+  SHA256(cert.tbs().spki_tlv.data(), cert.tbs().spki_tlv.size(), spki_hash);
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(), spki_hash, sizeof(spki_hash))) {
+    return false;
+  }
+
+  // 9. Write the remainder of the TBSCertificate contents octets to the hash,
+  // starting just after the subjectPublicKeyInfo field.
+  if (!EVP_DigestUpdate(entry_hash_ctx.get(),
+                        cert.tbs().bytes_after_spki.data(),
+                        cert.tbs().bytes_after_spki.size())) {
+    return false;
+  }
+
+  // 10. Finalize the hash and set entry_hash to the result.
+  TreeHash entry_hash;
+  if (!EVP_DigestFinal(entry_hash_ctx.get(), entry_hash.data(), nullptr)) {
+    return false;
+  }
+
+  // Step 10. Let expected_subtree_hash be the result of evaluating the
+  // MTCProof's inclusion_proof
+  Subtree range{start, end};
+  std::optional<TreeHash> expected_subtree_hash =
+      EvaluateMerkleSubtreeInclusionProof(inclusion_proof, index, entry_hash,
+                                          range);
+  if (!expected_subtree_hash) {
+    return false;
+  }
+
+  // Step 11. If log_number, start, and end matches a trusted subtree (Section
+  // 7.4) for the CA, check that expected_subtree_hash is equal to the trusted
+  // subtree's hash.
+  if (!mtc_anchor) {
+    return false;
+  }
+  std::optional<TreeHashConstSpan> trusted_subtree_hash =
+      mtc_anchor->SubtreeHash(log_number, range);
+  if (trusted_subtree_hash) {
+    return CRYPTO_memcmp(expected_subtree_hash->data(),
+                         trusted_subtree_hash->data(),
+                         expected_subtree_hash->size()) == 0;
+  }
+
+  // TODO(crbug.com/452983502): Step 12 would check the MTCProof's signatures
+  // if there's no matching trusted subtree. This implementation does not
+  // support that check yet.
+  return false;
+}
+
+static bool VerifyMTC(const ParsedCertificate &cert,
+                      const MTCAnchor *mtc_anchor) {
+  switch (mtc_anchor->spec_version()) {
+    case MTCAnchor::MtcSpecVersion::kDavidben08:
+      return VerifyMTCDraftDavidben08(cert, mtc_anchor);
+    case MTCAnchor::MtcSpecVersion::kPlants04:
+      return VerifyMTCDraftPlants04(cert, mtc_anchor);
+  }
+  return false;
+}
+
 void PathVerifier::BasicCertificateProcessing(
     const ParsedCertificate &cert, bool is_target_cert,
     bool is_target_cert_issuer, const der::GeneralizedTime &time,