Merkle Tree Certificates for TLS

2.1. Time

All time computations in this document are represented by POSIX timestamps, defined in this document to be integers containing a number of seconds since the Epoch, defined in Section 4.16 of [POSIX]. That is, the number of seconds after 1970-01-01 00:00:00 UTC, excluding leap seconds. A UTC time is converted to a POSIX timestamp as described in [POSIX].¶

Durations of time are integers, representing a number of seconds not including leap seconds. They can be added to POSIX timestamps to produce other POSIX timestamps.¶

The current time is a POSIX timestamp determined by converting the current UTC time to seconds since the Epoch. One POSIX timestamp is said to be before (respectively, after) another POSIX timestamp if it is less than (respectively, greater than) the other value.¶

2.2. Terminology and Roles

There are five roles involved in a Merkle Tree certificate deployment:¶

Subscriber:

The party that authenticates itself in the protocol. In TLS, this is the side sending the Certificate and CertificateVerify message.¶

Merkle Tree certification authority (CA):

The service that issues Merkle Tree certificates to the subscriber, and publishes logs of all certificates.¶

Relying party:

The party authenticating the subscriber. In TLS, this is the side receiving the Certificate and CertificateVerify message.¶

Transparency service:

The service that mirrors the issued certificates for others to monitor. It additionally summarizes the CA's activity for relying parties, in order for certificates to be accepted. This is conceptually a single service, but may be multiple services, run by multiple entities in concert. See Section 7. For example, if the relying party is a web browser, the browser vendor might run the transparency service, or it may trust a collection of third-party mirrors.¶

Monitors:

Parties who monitor the list of valid certificates, published by the transparency service, for unauthorized certificates.¶

Additionally, there are several terms used throughout this document to describe this proposal. This section provides an overview. They will be further defined and discussed in detail throughout the document.¶

Assertion:

A protocol-specific statement that the CA is certifying. For example, in TLS, the assertion is that a TLS signing key can speak on behalf of some DNS name or other identity.¶

Abridged assertion:

A partially-hashed Assertion to save space. For example, in TLS, an abridged assertion replaces the subject public key by a hash.¶

Certificate:

A structure, generated by the CA, that proves to the relying party that the CA has certified some assertion. A certificate consists of the assertion itself accompanied by an associated proof string.¶

Batch:

A collection of assertions certified at the same time. CAs in this proposal only issue certificates in batches at a fixed frequency.¶

Batch tree head:

A hash computed over all the assertions in a batch, by building a Merkle Tree. The Merkle Tree construction and this hash are described in more detail in Section 5.5.1.¶

Inclusion proof:

A structure which proves that some assertion is contained in some tree head. See Section 5.5.3.¶

Validity window:

A range of consecutive batch tree heads. A relying party maintains a copy of the CA's latest validity window. At any time, it will accept only assertions contained in tree heads contained in the current validity window.¶

4.1. DNS Claims

The dns and dns_wildcard claims indicate that the subject is authoritative for a set of DNS names. They use the DNSNameList structure, defined below:¶

opaque DNSName<1..255>;

struct {
    DNSName dns_names<1..2^16-1>;
} DNSNameList;

DNSName values use the "preferred name syntax" as specified by Section 3.5 of [RFC1034] and as modified by Section 2.1 of [RFC1123]. Alphabetic characters MUST additionally be represented in lowercase. IDNA names [RFC5890] are represented as A-labels. For example, possible values include example.com or xn--iv8h.example. Values EXAMPLE.COM and <U+1F50F>.example would not be permitted.¶

Names in a dns claim represent the exact DNS name specified. Names in a dns_wildcard claim represent wildcard DNS names and are processed as if prepended with the string "*." and then following the steps in Section 6.3 of [I-D.draft-ietf-uta-rfc6125bis].¶

4.2. IP Claims

The ipv4 and ipv6 claims indicate the subject is authoritative for a set of IPv4 and IPv6 addresses, respectively. They use the IPv4AddressList and IPv6AddressList structures, respectively, defined below. IPv4Address and IPv6Address are interpreted in network byte order.¶

uint8 IPv4Address[4];
uint8 IPv6Address[16];

struct {
    IPv4Address addresses<4..2^16-1>;
} IPv4AddressList;

struct {
    IPv6Address addresses<16..2^16-1>;
} IPv6AddressList;

5.1. Merkle Tree CA Parameters

A Merkle Tree certification authority is defined by the following values:¶

hash:

A cryptographic hash function. In this document, the hash function is always SHA-256 [SHS], but others may be defined.¶

issuer_id:

A trust anchor identifier (see Section 3 of [I-D.beck-tls-trust-anchor-ids]) that identifies the CA. See Section 5.2 for details.¶

public_key:

The public half of a signing keypair. The corresponding private key, private_key, is known only to the CA.¶

start_time:

The issuance time of the first batch of certificates, represented as a POSIX timestamp (see Section 2.1).¶

batch_duration:

A number of seconds which determines how frequently the CA issues certificates. See details below.¶

lifetime:

A number of seconds which determines the lifetime of certificates issued by this CA. MUST be a multiple of batch_duration.¶

validity_window_size:

An integer describing the maximum number of unexpired batches which may exist at a time. This value is determined from lifetime and batch_duration by lifetime / batch_duration.¶

These values are public and known by the relying party and the CA. They may not be changed for the lifetime of the CA. To change these parameters, the entity operating a CA may deploy a second CA and either operate both during a transition, or stop issuing from the previous CA.¶

[[TODO: The signing key case is interesting. A CA could actually maintain a single stream of Merkle Trees, but then sign everything with multiple keys to support rotation. The CA -> Subscriber -> RP flow does not depend on the signature, only the CA -> Transparency Service -> RP flow. The document is not currently arranged to capture this, but it probably should be. We probably need to decouple the signing half and the Merkle Tree half slightly. #36 ]]¶

Certificates are issued in batches. Batches are numbered consecutively, starting from zero. All certificates in a batch have the same issuance time, determined by start_time + batch_duration * batch_number. This is known as the batch's issuance time. That is, batch 0 has an issuance time of start_time, and issuance times increment by batch_duration. A CA can issue no more frequently than batch_duration. batch_duration determines how long it takes for the CA to return a certificate to the subscriber.¶

All certificates in a batch have the same expiration time, computed as lifetime past the issuance time. After this time, the certificates in a batch are no longer valid. Merkle Tree certificates uses a short-lived certificates model, such that certificate expiration replaces an external revocation signal like CRLs [RFC5280] or OCSP [RFC6960]. lifetime SHOULD be set accordingly. For instance, a deployment with a corresponding maximum OCSP [RFC6960] response lifetime of 14 days SHOULD use a value no higher than 14 days. See Section 13.3 for details.¶

CAs are RECOMMENDED to use a batch_duration of one hour, and a lifetime of 14 days. This results in a validity_window_size of 336, for a total of 10,752 bytes in SHA-256 hashes.¶

To prevent cross-protocol attacks, the key used in a Merkle Tree CA MUST be unique to that Merkle Tree CA. It MUST NOT be used in another Merkle Tree CA, or for another protocol, such as X.509 certificates.¶

5.2. Identifying CAs and Batches

A Merkle Tree CA's issuer_id is a trust anchor identifier, defined in Section 3 of [I-D.beck-tls-trust-anchor-ids]. However, unlike an X.509 CA, the entire OID arc rooted at the identifier is associated with the CA. OIDs under this arc are used to identify batches below.¶

An individual batch from a Merkle Tree CA also has an associated trust anchor identifier. It is determined by appending the batch number to the CA's issuer_id.¶

For example, a Merkle Tree CA may have an issuer_id of 32473.1, in the ASCII representation. The batch with batch number 42 would then have a trust anchor identifier of 32473.1.42.¶

5.3. Batch State

Each batch is in one of three states:¶

pending:

The current time is before the batch's issuance time¶

ready:

The current time is not before the batch's issuance time, but the batch has not yet been issued¶

issued:

Certificates have been issued for this batch¶

The CA also maintains a latest batch number, which is the number of the last batch in the "issued" state. As an invariant, all batches before this value MUST also be in the "issued" state.¶

For each batch in the "issued" state, the CA maintains the following batch state:¶

• The list of abridged assertions certified in this batch.¶

• The tree head, a hash computed over this list, described in Section 5.5.1.¶

• A validity window signature computed as described in Section 5.5.2.¶

The CA exposes all of this information in an HTTP [RFC9110] interface described in Section 8.¶

5.4. Issuance Queue and Scheduling

The CA additionally maintains an issuance queue, not exposed via the HTTP interface.¶

When a subscriber requests a certificate for some assertion, the CA first validates it per its issuance policy. For example, it may perform ACME identifier validation challenges (Section 8 of [RFC8555]). Once validation is complete and the CA is willing to certify the assertion, the CA appends it to the issuance queue.¶

The CA runs a regularly-scheduled issuance job which converts this queue into certificates. This job runs the following procedure:¶

1. If no batches are in the "ready" state, do nothing and abort this procedure. Schedule a new job to run sometime after the earliest "pending" batch's issuance time.¶

2. For each batch in the "ready" state other than the latest one, run the procedure in Section 5.5 with an empty assertion list, in order of increasing batch number. Batches cannot be skipped.¶

3. Empty the issuance queue into an ordered list of assertions. Run the procedure in Section 5.5 using this list and the remaining batch in the "ready" state. This batch's issuance time will be at or shortly before the current time.¶

5.5. Certifying a Batch of Assertions

This section describes how to certify a given list of assertions at a given batch number. The batch MUST be in the "ready" state, and all preceding batches MUST be in the "issued" state.¶

    HashEmpty(level, index) = hash(HashEmptyInput)
    HashNode(left, right, level, index) = hash(HashNodeInput)
    HashAssertion(assertion, index) = hash(HashAssertionInput)

struct {
    uint8 distinguisher = 0;
    opaque issuer_id<1..32>;
    uint32 batch_number;
    uint64 index;
    uint8 level;
} HashEmptyInput;

struct {
    uint8 distinguisher = 1;
    opaque issuer_id<1..32>;
    uint32 batch_number;
    uint64 index;
    uint8 level;
    opaque left[hash.length];
    opaque right[hash.length];
} HashNodeInput;

struct {
    SubjectType subject_type;
    opaque subject_info_hash[hash.length];
    Claim claims<0..2^16-1>;
} AbridgedAssertion;

struct {
    uint8 distinguisher = 2;
    opaque issuer_id<1..32>;
    uint32 batch_number;
    uint64 index;
    AbridgedAssertion abridged_assertion;
} HashAssertionInput;

opaque TreeHead[hash.length];

struct {
    uint32 batch_number;
    TreeHead tree_heads[validity_window_size*hash.length];
} ValidityWindow;

struct {
    uint8 label[32] = "Merkle Tree Crts ValidityWindow\0";
    opaque issuer_id<1..32>;
    ValidityWindow window;
} LabeledValidityWindow;

/* See Section 4.1 of draft-beck-tls-trust-anchor-ids */
opaque TrustAnchorIdentifier<1..2^8-1>;

struct {
    TrustAnchorIdentifier trust_anchor;
    opaque proof_data<0..2^16-1>;
} Proof;

struct {
    Assertion assertion;
    Proof proof;
} BikeshedCertificate;

opaque HashValueSHA256[32];

struct {
    uint64 index;
    HashValueSHA256 path<0..2^16-1>;
} MerkleTreeProofSHA256;

5.6. Size Estimates

Merkle Tree proofs scale logarithmically in the batch size. Section 11.2 recommends subscribers renew halfway through the previous certificate's lifetime. Batch sizes will thus, on average, be subscriber_count * 2 / validity_window_size, where subscriber_count is a CA's active subscriber count. The recommended parameters in Section 5.1 give an average of subscriber_count / 168.¶

Some organizations have published statistics which can estimate batch sizes for the Web PKI. On March 7th, 2023, [LetsEncrypt] reported around 330,000,000 active subscribers for a single CA. [MerkleTown] reported around 3,800,000,000 unexpired certificates in Certificate Transparency logs, and an issuance rate of around 257,000 per hour. Note the numbers from [MerkleTown] represent, respectively, all Web PKI CAs combined and issuance rates for longer-lived certificates and may not be representative of a Merkle Tree certificate deployment.¶

These three estimates correspond to batch sizes of, respectively, around 2,000,000, around 20,000,000, and 257,000. The corresponding path lengths will be 20, 24, and 17, given proof sizes of, respectively, 640 bytes, 768 bytes, and 544 bytes.¶

For larger batch sizes, 32 hashes, or 1024 bytes, is sufficient for batch sizes up to 2^33 (8,589,934,592) certificates.¶

6.1. Relying Party State

For each Merkle Tree CA it trusts, a relying party maintains a copy of the most recent validity window from the CA. This structure determines which certificates the relying party will accept. It is regularly updated from the transparency service, as described in Section 7.¶

Each batch in the relying party's validity window is a trust anchor for purposes of certificate verification (see Section 6.2) and certificate negotiation (see Section 10.3).¶

6.2. Certificate Verification

This section describes the verification process for a BikeshedCertificate. It describes error conditions with TLS alerts, defined in Section 6.2 of [RFC8446]. Non-TLS applications SHOULD map these error conditions to the corresponding application-specific errors. When multiple error conditions apply, the application MAY return any applicable error.¶

When a subscriber presents a BikeshedCertificate, the relying party runs the following procedure:¶

1. Determines if trust_anchor corresponds to a supported trust anchor, and the type of that trust anchor. If trust_anchor is unrecognized, the relying party rejects the certificate with an unknown_ca error.¶

2. Run the verification subroutine corresponding to that trust anchor, defined below.¶

3. Optionally, perform any additional application-specific checks on the assertion and issuer. For example, an HTTPS client might constrain an issuer to a particular DNS subtree.¶

4. If all the preceding checks succeed, the certificate is valid and the application can proceed with using the assertion.¶

Step 2 in the above procedure runs a trust-anchor-specific verification subroutine. This subroutine is determined by the type of trust anchor. Each mechanism using the BikeshedCertificate format MUST define a verification subroutine.¶

For a Merkle Tree trust anchor, the trust anchor will identify a batch in the relying party's validity window. (See Section 5.2 and Section 6.1.) The batch's verification subroutine is defined below:¶

1. Compute the batch's expiration time, as described in Section 5.1. If this value is before the current time, abort this procedure with a certificate_expired error.¶

2. Set hash to the output of HashAssertion(assertion, index). Set remaining to the certificate's index value.¶

3. For each element v at zero-based index i of the certificate's path field, in order:¶

   • If remaining is odd, set hash to the output of HashNode(v, hash, i + 1, remaining >> 1). Otherwise, set hash to the output of HashNode(hash, v, i + 1, remaining >> 1)¶

   • Set remaining to remaining >> 1.¶

4. If remaining is non-zero, abort this procedure with an error.¶

5. If hash is not equal to the batch's tree head in the relying party's saved validity window (see Section 6.1), abort this procedure with a bad_certificate error.¶

6. If all the preceding checks succeed, the Merkle Tree certificate verification subroutine completes successfully.¶

7.1. Single Trusted Service

Some relying parties regularly contact a trusted update service, either for software updates or to update individual components, such as the services described in [CHROMIUM] and [FIREFOX]. Where these services are already trusted for the components such as the trust anchor list or certificate validation software, a single trusted transparency service may be a suitable model.¶

The transparency service maintains a mirror of the CA's latest batch number, and batch state. Roughly once every batch_duration, it polls the CA's HTTP interface (see Section 8) and runs the following steps:¶

1. Fetch the CA's latest batch number. If this fetch fails, abort this procedure with an error.¶

2. Let new_latest_batch be the result and old_latest_batch be the currently mirrored value. If new_latest_batch equals old_latest_batch, finish this procedure without reporting an error.¶

3. If new_latest_batch is less than old_latest_batch, abort this procedure with an error.¶

4. If the issuance time for batch new_latest_batch is after the current time (see Section 5.1), abort this procedure with an error.¶

5. For all i such that old_latest_batch < i <= new_latest_batch:¶

   1. Fetch the signature, tree head, and abridged assertion list for batch i. If this fetch fails, abort this procedure with an error.¶

   2. Compute the tree head for the assertion list, as described in Section 5.5.1. If this value does not match the fetched tree head, abort this procedure with an error.¶

   3. Compute the ValidityWindow structure and verify the signature, as described in Section 5.5.2. Set tree_heads[0] to the tree head fetched above. Set the other values in tree_heads to the previously mirrored values. If signature verification fails, abort this procedure with an error.¶

   4. Set the mirrored latest batch number to i and save the fetched batch state.¶

[[TODO: If the mirror gets far behind, if the CA just stops publishing for a while, it may suddenly have to catch up on many batches. Should we allow the mirror to catch up to the latest validity window and skip the intervening batches? The intervening batches are guaranteed to have been expired #37 ]]¶

7.2. Single Update Service with Multiple Mirrors

If the relying party has a trusted update service, but the update service does not have the resources to mirror the full batch state, the transparency service can be composed of this update service and several, less trusted mirrors. In this model, the mirrors are not trusted to serve authoritative trust anchor information to relying parties, but the update service trusts at least half of them to faithfully and consistently mirror the batch state.¶

Each mirror follows the procedure in Section 7.1 to maintain and publish a mirror of the CA's batch state.¶

The update server maintains the latest validity window validated to appear in all mirrors. It updates this by polling the mirrors and running the following steps:¶

1. For each mirror, fetch the latest batch number.¶

2. Let new_latest_batch be the highest batch number that is bounded by the value fetched from at least half of the mirrors. Let old_latest_batch be the batch number of the currently stored validity window.¶

3. If new_latest_batch equals old_latest_batch, finish this procedure without reporting an error.¶

4. If new_latest_batch is less than old_latest_batch, abort this procedure with an error.¶

5. If the issuance time for batch new_latest_batch is after the current time (see Section 5.1), abort this procedure with an error.¶

6. Fetch the validity window with new_latest_batch from each mirror that returned an equal or higher latest batch number. If any fetches fail, or if the results do not match across all mirrors, abort this procedure with an error.¶

7. Verify the validity window signature, as described in Section 5.5.2. If the signature is invalid, abort this procedure with an error.¶

8. If the old and new validity windows contain overlapping batch numbers, verify that the tree hashes match. If not, abort this procedure with an error.¶

9. Update the saved validity window with the new value.¶

Compared to Section 7.1, this model reduces trust in the mirror services, but can delay certificate usability if some of the mirrors consume CA updates too slowly. This can be tuned by adjusting the threshold in step 2.¶

In a transparency service using this model, each mirror independently publishes the batch state via Section 8.¶

7.3. Multiple Transparency Services

Relying parties without a trusted update service can fetch from mirrors directly. Rather than relying on the update service to fetch the validity window state, the relying party runs the procedure described in Section 7.2, and uses the saved validity window to verify certificates.¶

7.4. Monitors

Monitors in this document are analogous to monitors in [RFC6962]. Monitors watch an implementation of the HTTP APIs in Section 8 to verify correct behavior and watch for certificates of interest. This is typically the transparency service. A monitor needs to, at least, inspect every new batch. It may also maintain a copy of the batch state.¶

It does so by following the procedure in Section 7.1, fetching from the service being monitored. If the procedure fails for a reason other than the service availability, this should be viewed as misbehavior on the part of the service. If the procedure fails due to service availability and the service remains unavailable for an extended period, this should also be viewed as misbehavior. If the monitor is not maintaining a copy of the batch state, it skips saving the abridged assertions.¶

[RFC6962] additionally defines the role of auditor, which validates that Signed Certificate Timestamps (SCTs) and Signed Tree Heads (STHs) in Certificate Transparency are correct. There is no analog to SCTs in this document. The signed validity window structure (Section 5.5.2) is analogous to an STH, but consistency is checked simply by ensuring overlapping tree heads match, so this document does not define this as an explicit role. If two inconsistent signed validity windows are ever observed from a Merkle Tree CA, this should be viewed as misbehavior on the part of the CA.¶

10.1. TLS Subjects

This section describes the SubjectType for use with TLS [RFC8446]. The SubjectType value is tls, and the subject_info field contains a TLSSubjectInfo structure, defined below:¶

enum { tls(0), (2^16-1) } SubjectType;

struct {
    SignatureScheme signature;
    opaque public_key<1..2^16-1>;
    /* TODO: Should there be an extension list? #38 */
} TLSSubjectInfo;

A TLSSubjectInfo describes a TLS signing key. The signature field is a SignatureScheme Section 4.2.3 of [RFC8446] value describing the key type and signature algorithm it uses for CertificateVerify.¶

The public_key field contains the subscriber's public key. The encoding is determined by the signature field as follows:¶

RSASSA-PSS algorithms:

The public key is an RSAPublicKey structure [RFC8017] encoded in DER [X.690]. BER encodings which are not DER MUST be rejected.¶

ECDSA algorithms:

The public key is a UncompressedPointRepresentation structure defined in Section 4.2.8.2 of [RFC8446], using the curve specified by the SignatureScheme.¶

EdDSA algorithms:

The public key is the byte string encoding defined in [RFC8032]¶

This document does not define the public key format for other algorithms. In order for a SignatureScheme to be usable with TLSSubjectInfo, this format must be defined in a corresponding document.¶

[[TODO: If other schemes get defined before this document is done, add them here. After that, it's on the other schemes to do it. #39 ]]¶

10.2. The Bikeshed Certificate Type

[[TODO: Bikeshed is a placeholder name until someone comes up with a better one. #15]]¶

This section defines the Bikeshed TLS certificate type, which may be negotiated with the client_certificate_type, server_certificate_type [RFC7250], or cert_type [RFC6091] extensions. It can only be negotiated with TLS 1.3 or later. Servers MUST NOT negotiate it in TLS 1.2 or below. If the client receives a ServerHello that negotiates it in TLS 1.2 or below, it MUST abort the connection with an illegal_parameter alert.¶

[[TODO: None of these three extensions is quite right for client certificates because the negotiation isn't symmetric. See discussion in Appendix B. We may need to define another one. #18]]¶

When negotiated, the Certificate message MUST contain a single CertificateEntry structure. CertificateEntry is updated as follows:¶

enum { Bikeshed(TBD), (255) } CertificateType;

struct {
    select (certificate_type) {
        /* Certificate type defined in this document */
        case Bikeshed:
            BikeshedCertificate certificate;

        /* From RFC 7250 */
        case RawPublicKey:
            opaque ASN1_subjectPublicKeyInfo<1..2^24-1>;

        case X509:
            opaque cert_data<1..2^24-1>;

        /* Additional certificate types based on the
          "TLS Certificate Types" registry */
    };
    Extension extensions<0..2^16-1>;
} CertificateEntry;

The subject_type field in the certificate MUST be of type tls (Section 10.1). The CertificateVerify message is computed and processed as in [RFC8446], with the following modifications:¶

• The signature is computed and verified with the key described in the TLSSubjectInfo. The relying party uses the key decoded from the public_key field, and the subscriber uses the corresponding private key.¶

• The SignatureScheme in the CertificateVerify MUST match the signature field in the TLSSubjectInfo.¶

The second modification differs from [RFC8446]. Where [RFC8446] allowed an id-rsaEncryption key to sign both rsa_pss_rsae_sha256 and rsa_pss_rsae_sha384, TLSSubjectInfo keys are specific to a single algorithm. Future documents MAY relax this restriction for a new SignatureScheme, provided it was designed to be used concurrently with the value in TLSSubjectInfo. In particular, the underlying signature algorithm MUST match, and there MUST be appropriate domain separation between the two modes. For example, [I-D.draft-ietf-tls-batch-signing] defines new SignatureSchemes, but the same keypair can be safely used with one of the new values and the corresponding base SignatureScheme.¶

If this certificate type is used for either the client or server certificate, the ALPN [RFC7301] extension MUST be negotiated. If no application protocol is selected, endpoints MUST close the connection with a no_application_protocol alert.¶

[[TODO: Suppose we wanted to introduce a second SubjectType for TLS, either to add new fields or capture a new kind of key. That would need to be negotiated. We could use another extension, but defining a new certificate type seems most natural. That suggests this certificate type isn't about negotiating BikeshedCertificate in general, but specifically SubjectType.tls and TLSSubjectInfo. So perhaps the certificate type should be TLSSubjectInfo or BikeshedTLS. #7 ]]¶

10.3. Certificate Negotiation

Merkle Tree certificates will only be accepted in up-to-date relying parties, and require a negotiation mechanism to use. Merkle Tree certificate implementations SHOULD use the trust_anchors extension [I-D.draft-beck-tls-trust-anchor-ids] as described below:¶

For each Merkle Tree CA trusted by the relying party, the batches in the validity window each determine a trust anchor, as described in Section 6.1. The trust anchor's identifier is the batch identifier, as described in Section 5.2. Future mechanisms using the BikeshedCertificate format (see Section 5.5.3) MUST similarly define how relying parties determine trust anchor identifiers.¶

As even a single validity window results in validity_window_size trust anchors, sending all trust anchors in the trust_anchors extension would be prohitively large in most cases. Instead, relying parties SHOULD use the retry mechanism described in Section 4.3 of [I-D.draft-beck-tls-trust-anchor-ids] and the DNS hint described in Section 5 of [I-D.draft-beck-tls-trust-anchor-ids].¶

[[TODO: We could reduce the reliance on DNS by adding https://github.com/davidben/tls-trust-expressions/issues/62, either in this draft or the main trust anchor IDs draft.]]¶

The subscriber's list of candidate certification paths (see Section 3.3 of [I-D.beck-tls-trust-anchor-ids]) is extended to carry both X.509 and BikeshedCertificate credentials. The two types of credentials MAY appear in any relative preference order, based on the subscriber's policies. Like an X.509 credential, a BikeshedCertificate credential also has a CertificatePropertyList (see Section 3.1 of [I-D.beck-tls-trust-anchor-ids]).¶

For each of the subscriber's BikeshedCertificate credentials, the corresponding trust anchor identifier is the trust_anchor field in the BikeshedCertificate structure. This differs from X.509 credentials, which require an out-of-band value in the CertificatePropertyList. It is an error for a BikeshedCertificate credential's CertificatePropertyList to contain the trust_anchor_identifier property.¶

The subscriber then selects certificates as described in Section 4.2 of [I-D.draft-beck-tls-trust-anchor-ids]. In doing so, it SHOULD incorporate trust anchor negotiation and certificate type negotiation (see Section 10.2) into the selection criteria for BikeshedCertificate-based credentials.¶

[[TODO: Certificate type negotiation doesn't work right for client certificates. See Appendix B]]¶

11.1. Fallback Mechanisms

Subscribers using Merkle Tree certificates SHOULD additionally provision certificates from another PKI mechanism, such as X.509. This ensures the service remains available to relying parties that have not recently fetched validity window updates, or lack connectivity to the transparency service.¶

If the pipeline of updates from the CA to the transparency service to relying parties is interrupted, certificate issuance may halt, or newly issued certificates may no longer be usable. When this happens, the optimization in this document may fail, but fallback mechanisms ensure services remain available.¶

11.2. Rolling Renewal

When a subscriber requests a certificate, the CA cannot fulfill the request until the next batch is ready. Once published, the certificate will not be accepted by relying parties until the batch state is mirrored by their respective transparency services, then pushed to relying parties.¶

To account for this, subscribers SHOULD request a new Merkle Tree certificate significantly before the previous Merkle Tree certificate expires. Renewing halfway into the previous certificate's lifetime is RECOMMENDED. Subscribers additionally SHOULD retain both the new and old certificates in the certificate set until the old certificate expires. As the new tree hash is delivered to relying parties, certificate negotiation will transition relying parties to the new certificate, while retaining the old certificate for clients that are not yet updated.¶

11.3. Deploying New Keys

Merkle Tree certificates' issuance delays make them unsuitable when rapidly deploying a new service and reacting to key compromise.¶

When a new service is provisioned with a brand new Merkle Tree certificate, relying parties will not yet have received a validity window containing this certificate from the transparency service and can therefore not validate this certificate until receiving them. The subscriber SHOULD, in parallel, also provision a certificate using another PKI mechanism (e.g. X.509). Certificate negotiation will then switch over to serving the Merkle Tree certificate as relying parties are updated.¶

If the service is performing a routine key rotation, and not in response to a known compromise, the subscriber MAY use the process described in Section 11.2, allowing certificate negotiation to also switch the private key used. This slightly increases the lifetime of the old key but maintains the size optimization continuously.¶

If the service is rotating keys in response to a key compromise, this option is not available. Instead, the service SHOULD immediately discard the old key and request a more immediate issuance mechanism. As in the initial deployment case, it SHOULD request a Merkle Tree certificate in parallel, which will restore the size optimization over time.¶

11.4. Batch State Availability

CAs and transparency services serve an HTTP interface defined in Section 8. This service may be temporarily unavailable, either from service outage or if the service does not meet the consistency condition mid-update. Exact availability requirements for these services are out of scope for this document, but this section provides some general guidance.¶

If the CA's interface becomes unavailable, the transparency service will be unavailable to update. This will prevent relying parties from accepting new certificates, so subscribers will need to use fallback mechanisms per Section 11.1. This does not compromise transparency goals per Section 13.4.2. However, a CA which is persistently unavailable may not offer sufficient benefit to be used by subscribers or trusted by relying parties.¶

However, if the transparency service's interface becomes unavailable, monitors will be unable to check for unauthorized certificates. This does compromise transparency goals. Mirrors of the batch state partially mitigate this, but service unavailability may prevent mirrors from replicating a batch that relying parties accept.¶

13.1. Authenticity

A key security requirement of any PKI scheme is that relying parties only accept assertions that were certified by a trusted certification authority. This is achieved by the following two properties:¶

• The relying party MUST NOT accept any validity window that was not authenticated as coming from the CA.¶

• For any tree head computed from a list of assertions as in Section 5.5.1, it is computationally infeasible to construct an assertion not this list, and some inclusion proof, such that the procedure in Section 6.2 succeeds.¶

Section 7 discusses achieving the first property.¶

The second property is achieved by using a collision-resistant hash in the Merkle Tree construction. The HashEmpty, HashNode, and HashAssertion functions use distinct initial bytes when calling the hash function, to achieve domain separation.¶

13.2. Cross-protocol attacks

Using the same key material in different, incompatible ways risks cross-protocol attacks when the two uses overlap. To avoid this, Section 5.1 forbids the reuse of Merkle Tree CA private keys in another protocol. A CA MUST NOT generate signatures with its private key, except as defined in Section 5.5.2, or an extension of this protocol. Any valid signature of a CA's public_key that does not meet these requirements indicates misuse of the private key by the CA.¶

To reduce the risk of attacks if this guidance is not followed, the LabeledValidityWindow structure defined in Section 5.5.2 includes a label string, and the CA's issuer_id. Extensions of this protocol MAY be defined which reuse the keys, but any that do MUST use a different label string and analyze the security of the two uses concurrently.¶

Likewise, key material included in an assertion (Section 4) MUST NOT be used in another protocol, unless that protocol was designed to be used concurrently with the original purpose. The Assertion structure is designed to facilitate this. Where X.509 uses an optional key usage extension (see Section 4.2.1.3 of [RFC5280]) and extended key usage extension (see Section 4.2.1.12 of [RFC5280]) to specify key usage, an Assertion is always defined first by a SubjectType value. Subjects cannot be constructed without first specifying the type, and subjects of different types cannot be accidentally interpreted as each other.¶

The TLSSubjectInfo structure additionally protects against cross-protocol attacks in two further ways:¶

• A TLSSubjectInfo specifies the key type not with a SubjectPublicKeyInfo Section 4.1.2.7 of [RFC5280] object identifier, but with a SignatureScheme structure. Where [RFC8446] allows an id-rsaEncryption key to sign both rsa_pss_rsae_sha256 and rsa_pss_rsae_sha384, this protocol specifies the full signature algorithm parameters.¶

• To mitigate cross-protocol attacks at the application protocol [ALPACA], this document requires connections using it to negotiate the ALPN [RFC7301] extension.¶

13.3. Revocation

Merkle Tree certificates avoid sending an additional signature for OCSP responses by using a short-lived certificates model. Per Section 5.1, Merkle Tree CA's certificate lifetime MUST be set such that certificate expiration replaces revocation. Existing revocation mechanisms like CRLs and OCSP are themselves short-lived, signed messages, so a low enough certificate lifetime provides equivalent revocation capability.¶

Relying parties with additional sources of revocation such as [CRLite] or [CRLSets] SHOULD provide a mechanism to express revoked assertions in such systems, in order to opportunistically revoke assertions in up-to-date relying parties sooner. It is expected that, in most deployments, relying parties can fetch this revocation data and Merkle Tree CA validity windows from the same service.¶

[[TODO: Is it worth defining an API for Merkle Tree CAs to publish a revocation list? That would allow automatically populating CRLite and CRLSets. Maybe that's a separate document. #41]]¶

13.4. Transparency

The transparency service does not prevent unauthorized certificates, but it aims to provide comparable security properties to Certificate Transparency [RFC6962]. If a subscriber presents an acceptable Merkle Tree certificate to a relying party, the relying party should have assurance it was published in some form that monitors and, in particular, the subject of the certificate will be able to notice.¶

13.5. Security of Fallback Mechanisms

Merkle Tree certificates are intended to be used as an optimization over other PKI mechanisms. More generally, certificate negotiation allows relying parties to support many kinds of certificates, to meet different goals. This document discusses the security properties of Merkle Tree certificates, but the overall system's security properties depend on all of a relying party's trust anchors.¶

In particular, in relying parties that require a publicly auditable PKI, the supported fallback mechanisms must also provide a transparency property, either with Certificate Transparency [RFC6962] or another mechanism.¶

15.1. Normative References

[I-D.beck-tls-trust-anchor-ids]

Beck, B., Benjamin, D., and D. O'Brien, "TLS Trust Anchor Identifiers", Work in Progress, Internet-Draft, draft-beck-tls-trust-anchor-ids-01, 5 September 2024, <https://datatracker.ietf.org/doc/html/draft-beck-tls-trust-anchor-ids-01>.

[I-D.draft-beck-tls-trust-anchor-ids]

Beck, B., Benjamin, D., and D. O'Brien, "TLS Trust Anchor Identifiers", Work in Progress, Internet-Draft, draft-beck-tls-trust-anchor-ids-01, 5 September 2024, <https://datatracker.ietf.org/doc/html/draft-beck-tls-trust-anchor-ids-01>.

[I-D.draft-ietf-uta-rfc6125bis]

Saint-Andre, P. and R. Salz, "Service Identity in TLS", Work in Progress, Internet-Draft, draft-ietf-uta-rfc6125bis-15, 10 August 2023, <https://datatracker.ietf.org/doc/html/draft-ietf-uta-rfc6125bis-15>.

[POSIX]

"IEEE Standard for Information Technology--Portable Operating System Interface (POSIX(TM)) Base Specifications, Issue 7", IEEE, DOI 10.1109/ieeestd.2018.8277153, ISBN ["9781504445429"], January 2018, <https://doi.org/10.1109/ieeestd.2018.8277153>.

[RFC1034]

Mockapetris, P., "Domain names - concepts and facilities", STD 13, RFC 1034, DOI 10.17487/RFC1034, November 1987, <https://www.rfc-editor.org/rfc/rfc1034>.

[RFC1123]

Braden, R., Ed., "Requirements for Internet Hosts - Application and Support", STD 3, RFC 1123, DOI 10.17487/RFC1123, October 1989, <https://www.rfc-editor.org/rfc/rfc1123>.

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC5890]

Klensin, J., "Internationalized Domain Names for Applications (IDNA): Definitions and Document Framework", RFC 5890, DOI 10.17487/RFC5890, August 2010, <https://www.rfc-editor.org/rfc/rfc5890>.

[RFC6091]

Mavrogiannopoulos, N. and D. Gillmor, "Using OpenPGP Keys for Transport Layer Security (TLS) Authentication", RFC 6091, DOI 10.17487/RFC6091, February 2011, <https://www.rfc-editor.org/rfc/rfc6091>.

[RFC7250]

Wouters, P., Ed., Tschofenig, H., Ed., Gilmore, J., Weiler, S., and T. Kivinen, "Using Raw Public Keys in Transport Layer Security (TLS) and Datagram Transport Layer Security (DTLS)", RFC 7250, DOI 10.17487/RFC7250, June 2014, <https://www.rfc-editor.org/rfc/rfc7250>.

[RFC7301]

Friedl, S., Popov, A., Langley, A., and E. Stephan, "Transport Layer Security (TLS) Application-Layer Protocol Negotiation Extension", RFC 7301, DOI 10.17487/RFC7301, July 2014, <https://www.rfc-editor.org/rfc/rfc7301>.

[RFC8017]

Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, <https://www.rfc-editor.org/rfc/rfc8017>.

[RFC8032]

Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017, <https://www.rfc-editor.org/rfc/rfc8032>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[RFC8446]

Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, <https://www.rfc-editor.org/rfc/rfc8446>.

[RFC8447]

Salowey, J. and S. Turner, "IANA Registry Updates for TLS and DTLS", RFC 8447, DOI 10.17487/RFC8447, August 2018, <https://www.rfc-editor.org/rfc/rfc8447>.

[RFC8555]

Barnes, R., Hoffman-Andrews, J., McCarney, D., and J. Kasten, "Automatic Certificate Management Environment (ACME)", RFC 8555, DOI 10.17487/RFC8555, March 2019, <https://www.rfc-editor.org/rfc/rfc8555>.

[RFC9110]

Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke, Ed., "HTTP Semantics", STD 97, RFC 9110, DOI 10.17487/RFC9110, June 2022, <https://www.rfc-editor.org/rfc/rfc9110>.

[SHS]

"Secure hash standard", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.180-4, 2015, <https://doi.org/10.6028/nist.fips.180-4>.

[X.690]

ITU-T, "Information technology - ASN.1 encoding Rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)", ISO/IEC 8824-1:2021 , February 2021.

15.2. Informative References

[ALPACA]

Brinkmann, M., Dresen, C., Merget, R., Poddebniak, D., Müller, J., Somorovsky, J., Schwenk, J., and S. Schinzel, "ALPACA: Application Layer Protocol Confusion - Analyzing and Mitigating Cracks in TLS Authentication", August 2021, <https://www.usenix.org/conference/usenixsecurity21/presentation/brinkmann>.

[APPLE-CT]

Apple, "Apple's Certificate Transparency policy", 5 March 2021, <https://support.apple.com/en-us/HT205280>.

[CHROME-CT]

Google Chrome, "Chrome Certificate Transparency Policy", 17 March 2022, <https://googlechrome.github.io/CertificateTransparency/ct_policy.html>.

[CHROMIUM]

Chromium, "Component Updater", 3 March 2022, <https://chromium.googlesource.com/chromium/src/+/main/components/component_updater/README.md>.

[CRLite]

Larisch, J., Choffnes, D., Levin, D., Maggs, B., Mislove, A., and C. Wilson, "CRLite: A Scalable System for Pushing All TLS Revocations to All Browsers", IEEE, 2017 IEEE Symposium on Security and Privacy (SP), DOI 10.1109/sp.2017.17, May 2017, <https://doi.org/10.1109/sp.2017.17>.

[CRLSets]

Chromium, "CRLSets", 4 August 2022, <https://www.chromium.org/Home/chromium-security/crlsets/>.

[Dilithium]

Bai, S., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and D. Stehlé, "CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation", 8 February 2021, <https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf>.

[Falcon]

Fouque, P., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., and Z. Zhang, "Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU", 10 January 2020, <https://falcon-sign.info/falcon.pdf>.

[FIREFOX]

Mozilla, "Firefox Remote Settings", 20 August 2022, <https://wiki.mozilla.org/Firefox/RemoteSettings>.

[I-D.draft-ietf-acme-ari]

Gable, A., "Automated Certificate Management Environment (ACME) Renewal Information (ARI) Extension", Work in Progress, Internet-Draft, draft-ietf-acme-ari-05, 23 August 2024, <https://datatracker.ietf.org/doc/html/draft-ietf-acme-ari-05>.

[I-D.draft-ietf-tls-batch-signing]

Benjamin, D., "Batch Signing for TLS", Work in Progress, Internet-Draft, draft-ietf-tls-batch-signing-00, 13 January 2020, <https://datatracker.ietf.org/doc/html/draft-ietf-tls-batch-signing-00>.

[LetsEncrypt]

Let's Encrypt, "Let's Encrypt Stats", 7 March 2023, <https://letsencrypt.org/stats/>.

[MerkleTown]

Cloudflare, Inc., "Merkle Town", 7 March 2023, <https://ct.cloudflare.com/>.

[RFC5280]

Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, <https://www.rfc-editor.org/rfc/rfc5280>.

[RFC6066]

Eastlake 3rd, D., "Transport Layer Security (TLS) Extensions: Extension Definitions", RFC 6066, DOI 10.17487/RFC6066, January 2011, <https://www.rfc-editor.org/rfc/rfc6066>.

[RFC6960]

Santesson, S., Myers, M., Ankney, R., Malpani, A., Galperin, S., and C. Adams, "X.509 Internet Public Key Infrastructure Online Certificate Status Protocol - OCSP", RFC 6960, DOI 10.17487/RFC6960, June 2013, <https://www.rfc-editor.org/rfc/rfc6960>.

[RFC6962]

Laurie, B., Langley, A., and E. Kasper, "Certificate Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013, <https://www.rfc-editor.org/rfc/rfc6962>.

[RFC6973]

Cooper, A., Tschofenig, H., Aboba, B., Peterson, J., Morris, J., Hansen, M., and R. Smith, "Privacy Considerations for Internet Protocols", RFC 6973, DOI 10.17487/RFC6973, July 2013, <https://www.rfc-editor.org/rfc/rfc6973>.

[RFC8879]

Ghedini, A. and V. Vasiliev, "TLS Certificate Compression", RFC 8879, DOI 10.17487/RFC8879, December 2020, <https://www.rfc-editor.org/rfc/rfc8879>.

[SharedFactors]

Våge, H. F. and University of Bergen, "Finding shared RSA factors in the Certificate Transparency logs", 13 May 2022, <https://bora.uib.no/bora-xmlui/bitstream/handle/11250/3001128/Masters_thesis__for_University_of_Bergen.pdf>.

A.1. (Abridged)Assertions

The following is an Assertion claiming example.com for a TLS subject with Ed25519 public key c5d2080fa9a489a226b58166dad00be8120931a769c9c6f1f8eefafc38af9065.¶

00000024 08070020 c5d2080f a9a489a2 26b58166 dad00be8 120931a7 69c9c6f1
f8eefafc 38af9065 00130000 000f000d 000b6578 616d706c 652e636f 6d

The corresponding AbridgedAssertion:¶

00000022 0807d8e2 c44fc82e 175e5698 b1c25324 6c9a996f c37bad29 fd59b6aa
838b0a93 0b000013 0000000f 000d000b 6578616d 706c652e 636f6d

Next, we have an Assertion claiming *.example.com, 192.0.2.37, 192.0.12.0, 198.51.100.60 and 203.0.113.0 for a TLS subject with RSASSA-PSS public key with modulus 264851…51544459 and exponent 65537.¶

00000112 0804010e 3082010a 02820101 00d1cd9c d613c050 929e6418 14b4957c
40f30d07 0927f653 bde7054c 06d53a89 36228b70 72fad4db a186c379 7e00300b
a5b6de8e 7ab3fed4 cb5a537e 7674916a 130a0435 664428a9 7f1983b7 e028b9ab
f24700de 1d6478c9 ae361176 daa64c2f 89b42ec0 270add68 85323401 35d22724
c7bd8f65 075b25b8 96a89ab8 2a2b2194 49b029b8 97e130dc dc96fce1 37351f2b
7a28f1d0 7b710afb 2c796211 d9ba1feb 43d30810 63f19afd b7ba2ab0 e19fd008
e719491d d10ed235 5d4790f0 3039e3a3 31aa2644 2d656716 ebe710f2 4260599a
2d082db1 eccfaa8f f51cfb8e 3dfca0eb e1af59c2 f007b35e 02b0582f 50090018
b78a6b06 c0188ab3 514d60d6 6243e017 8b020301 00010029 0001000f 000d000b
6578616d 706c652e 636f6d00 02001200 10c00002 25c0000c 00c63364 3ccb0071
00

The corresponding AbridgedAssertion:¶

00000022 08049a04 087a4d52 033a0a20 04333359 ccf29703 25684c5f a96f1ca1
35cb2ab1 f2670029 0001000f 000d000b 6578616d 706c652e 636f6d00 02001200
10c00002 25c0000c 00c63364 3ccb0071 00

B.1. Indicate in First CertificateEntry

We can have the subscriber indicate the certificate type in an extension of the first CertificateEntry. One challenge is the extensions come after the certificate, so the relying party must seek to the extensions field independent of the certificate type. Thus all certificate types must be updated to use a consistent opaque cert_data<0..2^24> syntax, with any type-specific structures embedded inside.¶

RawPublicKey and X509 already meet this requirement. OpenPGP and Bikeshed need an extra length prefix.¶

struct {
    CertificateType certificate_type;
    opaque certificate_request_context<0..2^8-1>;
    CertificateEntry certificate_list<0..2^24-1>;
} Certificate;

Since draft-davidben-tls-merkle-tree-certs-00

• Simpify hashing by removing the internal padding to align with block size. #72¶

• Avoid the temptation of floating points. #66¶

• Require lifetime to be a multiple of batch_duration. #65¶

• Rename window to validity window. #21¶

• Split Assertion into Assertion and AbridgedAssertion. The latter is used in the Merkle Tree and HTTP interface. It replaces subject_info by a hash, to save space by not serving large post-quantum public keys. The original Assertion is used everywhere else, including BikeshedCertificate. #6¶

• Add proper context to every node in the Merkle tree. #32¶

• Clarify we use a single CertificateEntry. #11¶

• Clarify we use POSIX time. #1¶

• Miscellaneous changes.¶

• Replace the negotiation mechanism with TLS Trust Anchor Identifiers.¶