Merkle Tree Certificates for TLS
draft-davidben-tls-merkle-tree-certs-04
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Active".
|
|
|---|---|---|---|
| Authors | David Benjamin , Devon O'Brien , Bas Westerbaan | ||
| Last updated | 2025-03-03 (Latest revision 2024-09-05) | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-davidben-tls-merkle-tree-certs-04
Transport Layer Security D. Benjamin
Internet-Draft D. O'Brien
Intended status: Experimental Google LLC
Expires: 4 September 2025 B. E. Westerbaan
Cloudflare
3 March 2025
Merkle Tree Certificates for TLS
draft-davidben-tls-merkle-tree-certs-04
Abstract
This document describes Merkle Tree certificates, a new certificate
type for use with TLS. A relying party that regularly fetches
information from trusted mirrors can use this certificate type as a
size optimization over more conventional mechanisms with post-quantum
signatures. Merkle Tree certificates integrate the roles of X.509
and Certificate Transparency, achieving comparable security
properties with a smaller message size, at the cost of more limited
applicability.
About This Document
This note is to be removed before publishing as an RFC.
The latest revision of this draft can be found at
https://davidben.github.io/merkle-tree-certs/draft-davidben-tls-
merkle-tree-certs.html. Status information for this document may be
found at https://datatracker.ietf.org/doc/draft-davidben-tls-merkle-
tree-certs/.
Discussion of this document takes place on the Transport Layer
Security Working Group mailing list (mailto:tls@ietf.org), which is
archived at https://mailarchive.ietf.org/arch/browse/tls/. Subscribe
at https://www.ietf.org/mailman/listinfo/tls/.
Source for this draft and an issue tracker can be found at
https://github.com/davidben/merkle-tree-certs.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Benjamin, et al. Expires 4 September 2025 [Page 1]
Internet-Draft Merkle Tree Certificates for TLS March 2025
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 4 September 2025.
Copyright Notice
Copyright (c) 2025 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 5
2.1. Time . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Terminology and Roles . . . . . . . . . . . . . . . . . . 5
3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4. Assertions . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1. DNS Claims . . . . . . . . . . . . . . . . . . . . . . . 10
4.2. IP Claims . . . . . . . . . . . . . . . . . . . . . . . . 11
5. Issuing Certificates . . . . . . . . . . . . . . . . . . . . 11
5.1. Merkle Tree CA Parameters . . . . . . . . . . . . . . . . 11
5.2. Identifying CAs and Batches . . . . . . . . . . . . . . . 13
5.3. Batch State . . . . . . . . . . . . . . . . . . . . . . . 13
5.4. Issuance Queue and Scheduling . . . . . . . . . . . . . . 14
5.5. Certifying a Batch of Assertions . . . . . . . . . . . . 14
5.5.1. Building the Merkle Tree . . . . . . . . . . . . . . 14
5.5.2. Signing a ValidityWindow . . . . . . . . . . . . . . 16
5.5.3. Certificate Format . . . . . . . . . . . . . . . . . 18
5.6. Size Estimates . . . . . . . . . . . . . . . . . . . . . 20
6. Using Certificates . . . . . . . . . . . . . . . . . . . . . 20
6.1. Relying Party State . . . . . . . . . . . . . . . . . . . 20
Benjamin, et al. Expires 4 September 2025 [Page 2]
Internet-Draft Merkle Tree Certificates for TLS March 2025
6.2. Certificate Verification . . . . . . . . . . . . . . . . 21
7. Transparency Ecosystem . . . . . . . . . . . . . . . . . . . 22
7.1. Mirrors . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.1.1. Updating a Mirror . . . . . . . . . . . . . . . . . . 23
7.2. Relying Party Policy . . . . . . . . . . . . . . . . . . 24
7.3. Monitors . . . . . . . . . . . . . . . . . . . . . . . . 25
8. HTTP Interface . . . . . . . . . . . . . . . . . . . . . . . 26
9. ACME Extensions . . . . . . . . . . . . . . . . . . . . . . . 27
10. Use in TLS . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.1. TLS Subjects . . . . . . . . . . . . . . . . . . . . . . 28
10.2. The Bikeshed Certificate Type . . . . . . . . . . . . . 29
10.3. Certificate Negotiation . . . . . . . . . . . . . . . . 31
11. Deployment Considerations . . . . . . . . . . . . . . . . . . 32
11.1. Fallback Mechanisms . . . . . . . . . . . . . . . . . . 32
11.2. Rolling Renewal . . . . . . . . . . . . . . . . . . . . 32
11.3. Deploying New Keys . . . . . . . . . . . . . . . . . . . 33
11.4. Batch State Availability . . . . . . . . . . . . . . . . 33
12. Privacy Considerations . . . . . . . . . . . . . . . . . . . 34
13. Security Considerations . . . . . . . . . . . . . . . . . . . 34
13.1. Authenticity . . . . . . . . . . . . . . . . . . . . . . 34
13.2. Cross-protocol attacks . . . . . . . . . . . . . . . . . 35
13.3. Revocation . . . . . . . . . . . . . . . . . . . . . . . 36
13.4. Transparency . . . . . . . . . . . . . . . . . . . . . . 36
13.4.1. Unauthorized Certificates . . . . . . . . . . . . . 36
13.4.2. Misbehaving Certification Authority . . . . . . . . 37
13.4.3. Misbehaving Mirror . . . . . . . . . . . . . . . . . 38
13.5. Security of Fallback Mechanisms . . . . . . . . . . . . 38
14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 39
15.1. Normative References . . . . . . . . . . . . . . . . . . 39
15.2. Informative References . . . . . . . . . . . . . . . . . 41
Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 43
A.1. (Abridged)Assertions . . . . . . . . . . . . . . . . . . 43
Appendix B. TLS Certificate Type Negotiation Challenges . . . . 44
B.1. Indicate in First CertificateEntry . . . . . . . . . . . 45
B.1.1. Change Certificate Syntax . . . . . . . . . . . . . . 46
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 46
Change log . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Since draft-davidben-tls-merkle-tree-certs-00 . . . . . . . . . 47
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 47
1. Introduction
Authors' Note: This is an early draft of a proposal with many parts.
While we have tried to make it as concrete as possible, we anticipate
that most details will change as the proposal evolves.
Benjamin, et al. Expires 4 September 2025 [Page 3]
Internet-Draft Merkle Tree Certificates for TLS March 2025
A typical TLS [RFC8446] handshake uses many signatures to
authenticate the server public key. In a certificate chain with an
end-entity certificate, an intermediate certificate, and an implicit
trust anchor, there are two X.509 signatures [RFC5280]. Intermediate
certificates additionally send an extra public key. If the handshake
uses Certificate Transparency (CT) [RFC6962], each Signed Certificate
Timestamp (SCT) also carries a signature. CT policies often require
two or more SCTs per certificate [APPLE-CT] [CHROME-CT]. If the
handshake staples an OCSP response [RFC6066] for revocation, that
adds an additional signature.
Current signature schemes can use as few as 32 bytes per key and 64
bytes per signature [RFC8032], but post-quantum replacements are much
larger. For example, ML-DSA-65 [FIPS204] uses 1,952 bytes per public
key and 3,309 bytes per signature. A TLS Certificate message with,
say, four ML-DSA-65 signatures (two X.509 signatures and two SCTs)
and one intermediate CA's ML-DSA-65 public key would total 15,188
bytes of authentication overhead. Falcon-512 and Falcon-1024
[Falcon] would, respectively, total 3,561 and 6,913 bytes.
This document introduces Merkle Tree Certificates, an optimization
that authenticates a TLS key using under 1,000 bytes. See
Section 5.6. To achieve this, it reduces its scope from general
authentication:
* Certificates are short-lived. The authenticating party is
expected to use an automated issuance protocol, such as ACME
[RFC8555].
* Certificates are issued in batches after a significant processing
delay of, in the recommended parameters (Section 5.1), about an
hour. Authenticating parties that need a certificate issued
quickly are expected to use a different mechanism.
* Certificates are only usable with relying parties that have, via a
background update process, obtained out-of-band assurance that a
batch of certificates is publicly accessible. See Section 7.
To support the reduced scope, this document also describes a
certificate negotiation mechanism. Authenticating parties send these
more efficient certificates when available, and otherwise fall back
to other mechanisms.
Benjamin, et al. Expires 4 September 2025 [Page 4]
Internet-Draft Merkle Tree Certificates for TLS March 2025
Merkle Tree Certificates are not intended to replace existing Public
Key Infrastructure (PKI) mechanisms but, in applications where a
significant portion of authentications meet the above requirements,
complement them as an optional optimization. In particular, it is
expected that, even within applications that implement it, this
mechanism will not be usable for all TLS connections.
2. Conventions and Definitions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
This document additionally uses the TLS presentation language defined
in Section 3 of [RFC8446].
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:
Authenticating party: 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 authenticating party, and
publishes logs of all certificates.
Benjamin, et al. Expires 4 September 2025 [Page 5]
Internet-Draft Merkle Tree Certificates for TLS March 2025
Relying party: The party whom the authenticating party presents its
identity to. In TLS, this is the side receiving the Certificate
and CertificateVerify message.
Mirror: A service that mirrors the issued certificates for others to
monitor.
Monitor: A party who monitors CAs and/or mirrors 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.
3. Overview
The process of issuing and using a certificate occurs in three
stages.
Benjamin, et al. Expires 4 September 2025 [Page 6]
Internet-Draft Merkle Tree Certificates for TLS March 2025
First, the CA issues a certificate to the authenticating party:
1. The authenticating party requests a certificate from the CA.
Section 9 describes ACME [RFC8555] extensions for this.
2. The CA collects certificate requests into a batch (see
Section 5.1) and builds the Merkle Tree and computes the tree
head (see Section 5.5.1). It then signs the validity window
ending at this tree head (see Section 5.5.2) and publishes (see
Section 8) the result.
3. The CA constructs a certificate using the inclusion proof. It
sends this certificate to the authenticating party. See
Section 5.5.3.
Next, tree heads flow to the relying party, after being durably and
consistently logged. This occurs periodically in the background,
unconnected from uses of individual certificates:
4. Mirrors periodically download the abridged assertions, recreate
the Merkle Tree, and validate the window signature. They mirror
the contents for monitors to observe. See Section 7.1.
5. The relying party periodically obtains an updated validity
window, after the window's contents have been logged in mirrors
that it trusts. See Section 7.2.
Once the relying party has a validity window with the new tree head,
the certificate is usable in an application protocol such as TLS:
6. The relying party communicates its currently saved validity
window to the authenticating party.
7. If the relying party’s validity window contains the
authenticating party’s certificate, the authenticating party
negotiates this protocol and sends the Merkle Tree certificate.
See Section 10.3 for details. If there is no match, the
authenticating party proceeds as if this protocol were not in use
(e.g., by sending a traditional X.509 certificate chain).
Figure 1 below shows the three stages combined.
Benjamin, et al. Expires 4 September 2025 [Page 7]
Internet-Draft Merkle Tree Certificates for TLS March 2025
+--------------+ 1. issuance request +-------------------------+
| +---------------------->| |
| Auth. Party | | Certification Authority |
| |<----------------------+ |
+---------+----+ 3. inclusion proof +-----------+-------------+
^ | |
| | | 2. sign and
6. accepted | | 7. inclusion proof | publish tree
tree heads | | |
| v v
+-------+---------+ +----------------------+
| | 5. batch tree heads | +-+
| Relying Party |<---------------------+ Mirrors | |
| | | | |
+-----------------+ +-+--------------------+ |
+--------+-------------+
|
| 4. publish tree
v
+------------+
| |
| Monitors |
| |
+------------+
Figure 1: An overview of a Merkle Tree certificate deployment
The remainder of this document discusses this process in detail,
followed by concrete instantions of it in TLS [RFC8446] and ACME
[RFC8555].
4. Assertions
[[TODO: The protocol described in this document is broadly
independent of the assertion format. We describe, below, one
possible structure, but welcome feedback on how best to structure the
encoding. The main aims are simplicity and to improve on handling
cross-protocol attacks per Section 13.2.]]
TLS certificates associate some application-specific identifier with
a TLS signing key. When TLS is used to authenticate HTTPS [RFC9110]
servers, these identifiers specify DNS names or HTTP origins. Other
protocols may require other kinds of assertions.
To represent this, this document defines an Assertion structure:
Benjamin, et al. Expires 4 September 2025 [Page 8]
Internet-Draft Merkle Tree Certificates for TLS March 2025
enum { tls(0), (2^16-1) } SubjectType;
enum {
dns(0),
dns_wildcard(1),
ipv4(2),
ipv6(3),
(2^16-1)
} ClaimType;
struct {
ClaimType claim_type;
opaque claim_info<0..2^16-1>;
} Claim;
struct {
SubjectType subject_type;
opaque subject_info<0..2^16-1>;
Claim claims<0..2^16-1>;
} Assertion;
An Assertion is roughly analogous to an X.509 TBSCertificate
(Section 4.1.2 of [RFC5280]). It describes a series of claims about
some subject. The subject_info field is interpreted according to the
subject_type value. For TLS, the subject_type is tls, and the
subject_info is a TLSSubjectInfo structure. TLSSubjectInfo is
defined in full in Section 10.1 below, but as an illustrative
example, it is reproduced below:
struct {
SignatureScheme signature;
opaque public_key<1..2^16-1>;
} TLSSubjectInfo;
This structure represents the public half of a TLS signing key. The
semantics are thus that each claim in claims applies to the TLS
client or server. This is analogous to X.509's SubjectPublicKeyInfo
structure (Section 4.1.2.7 of [RFC5280]) but additionally
incorporates the protocol. Protocols consuming an Assertion MUST
check the subject_type is a supported value before processing
subject_info. If unrecognized, the structure MUST be rejected.
Other protocols aiming to integrate with this structure allocate a
SubjectType codepoint and describe how it is interpreted.
Likewise, a Claim structure describes some claim about the subject.
The claim_info field is interpreted according to the claim_type.
Each Claim structure in an Assertion's claims field MUST have a
Benjamin, et al. Expires 4 September 2025 [Page 9]
Internet-Draft Merkle Tree Certificates for TLS March 2025
unique claim_type and all values MUST be sorted in order of
increasing claim_type. Structures violating this constraint MUST be
rejected.
When a relying party interprets an Assertion certified by the CA, it
MUST ignore any Claim values with unrecognized claim_type. When a CA
interprets an Assertion in a certification request from an
authenticating party, it MUST reject any Claim values with
unrecognized claim_type.
This document defines claim types for DNS names and IP addresses, but
others can be defined.
[[TODO: For now, the claims below just transcribe the X.509
GeneralName structure. Should these be origins instead? For HTTPS,
it's a pity to not capture the scheme and port. We do mandate ALPN
in Section 10.2, so cross-protocol attacks are mitigated, but it's
unfortunate that authenticating parties cannot properly separate
their HTTPS vs FTPS keys, or their port 443 vs port 444 keys. One
option here is to have HTTPS claims instead, and then other protocols
can have FTPS claims, etc. #35 ]]
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 [RFC9525].
Benjamin, et al. Expires 4 September 2025 [Page 10]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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. Issuing Certificates
This section describes the structure of Merkle Tree certificates and
defines the process of how a Merkle Tree certification authority
issues certificates for an authenticating party.
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.ietf-tls-trust-anchor-ids]) that identifies the CA. See
Section 5.2 for details.
public_key: The public half of a signing key. For convenience, we
use TLS' format, and represent the public key as a TLSSubjectInfo,
see Section 10.1. 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.
Benjamin, et al. Expires 4 September 2025 [Page 11]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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 -> Authenticating
Party -> RP flow does not depend on the signature, only the CA ->
Mirror -> 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 authenticating party.
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.
Benjamin, et al. Expires 4 September 2025 [Page 12]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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.ietf-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, called a batch_id. It is determined by
appending the batch number, as an OID component, 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 batch_id 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.
Benjamin, et al. Expires 4 September 2025 [Page 13]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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 an authenticating party 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.
5.5.1. Building the Merkle Tree
First, the CA then builds a Merkle Tree from the list as follows:
Let n be the number of input assertions. If n > 0, the CA builds a
binary tree with l levels numbered 0 to l-1, where l is the smallest
positive integer such that n <= 2^(l-1). Each node in the tree
contains a hash value. Hashes in the tree are built from the
following functions:
Benjamin, et al. Expires 4 September 2025 [Page 14]
Internet-Draft Merkle Tree Certificates for TLS March 2025
HashEmpty(level, index) = hash(HashEmptyInput)
HashNode(left, right, level, index) = hash(HashNodeInput)
HashAssertion(assertion, index) = hash(HashAssertionInput)
HashEmpyInput, HashNodeInput and HashAssertionInput are computed by
encoding the structures defined below:
struct {
uint8 distinguisher = 0;
TrustAnchorIdentifier batch_id;
uint64 index;
uint8 level;
} HashEmptyInput;
struct {
uint8 distinguisher = 1;
TrustAnchorIdentifier batch_id;
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;
TrustAnchorIdentifier batch_id;
uint64 index;
AbridgedAssertion abridged_assertion;
} HashAssertionInput;
The batch_id is set to the batch-specific trust anchor identifier,
i.e. the issuer_id with the batch number appended as described in
Section 5.2. HashAssertionInput.abridged_assertion.subject_info_hash
is set to hash(assertion.subject_info) from the function input
assertion, and the remaining fields of
HashAssertionInput.abridged_assertion are taken unmodified from
assertion. The remaining fields, such as index, are set to inputs of
the function.
Tree levels are computed iteratively as follows:
Benjamin, et al. Expires 4 September 2025 [Page 15]
Internet-Draft Merkle Tree Certificates for TLS March 2025
1. Initialize level 0 with n elements. For j between 0 and n-1,
inclusive, set element j to the output of
HashAssertion(assertion[j], j).
2. For i between 1 and l-1, inclusive, compute level i from level
i-1 as follows:
* If level i-1 has an odd number of elements j, append
HashEmpty(i-1, j) to the level.
* Initialize level i with half as many elements as level i-1.
For all j, set element j to the output of HashNode(left,
right, i, j) where left is element 2*j of level i-1 and right
is element 2*j+1 of level i-1. left and right are the left and
right children of element j.
At the end of this process, level l-1 will have exactly one root
element. This element is called the tree head. Figure 2 shows an
example tree for three assertions. The tree head in this example is
t20.
level 2: ___ t20 ___
/ \
/ \
level 1: t10 t11
/ \ / \
/ \ / \
level 0: t00 t01 t02 empty
| | |
a0 a1 a2
Figure 2: An example Merkle Tree for three assertions
If n is zero, the CA does not build a tree and the tree head is
HashEmpty(0, 0).
If n is one, the tree contains a single level, level 0, and has a
tree head of HashAssertion(assertion, 0).
5.5.2. Signing a ValidityWindow
Batches are grouped into consecutive ranges of validity_window_size
batches, called validity windows. As validity_window_size is
computed to cover the full certificate lifetime, a validity window
that ends at the latest batch number covers all certificates that may
still be valid from a CA.
Validity Windows are serialized into the following structure:
Benjamin, et al. Expires 4 September 2025 [Page 16]
Internet-Draft Merkle Tree Certificates for TLS March 2025
opaque TreeHead[hash.length];
struct {
uint32 batch_number;
TreeHead tree_heads[validity_window_size*hash.length];
} ValidityWindow;
batch_number is the batch number of the highest batch in the validity
window.
tree_heads value contains the last validity_window_size tree heads.
(Recall the TLS presentation language brackets the total length of a
vector in bytes; not the number of elements.) tree_heads starts from
batch_number, in decreasing batch number order. That is,
tree_heads[0] is the tree head for batch batch_number, tree_heads[1]
is the tree head for batch_number - 1, and so on. If batch_number <
validity_window_size - 1, any tree heads for placeholder negative
batch numbers are filled with HashEmpty(0, 0), computed with
batch_number set to 0.
After the CA builds the Merkle Tree for a batch, it constructs the
ValidityWindow structure whose batch_number is the number of the
batch being issued. It then computes a digital signature over the
following structure:
struct {
uint8 label[32] = "Merkle Tree Crts ValidityWindow\0";
TrustAnchorIdentifier issuer_id;
ValidityWindow window;
} LabeledValidityWindow;
The signature algorithm used is determined by public_key.signature as
described in Section 4.3.2 of [RFC8446]. (Signatures are created
without the domain separation of Section 4.4.3 of [RFC8446].)
The label field is an ASCII string. The final byte of the string,
"\0", is a zero byte, or ASCII NULL character. The issuer_id field
is the CA's issuer_id. Other parties can verify the signature by
constructing the same input and verifying with the CA's public_key.
The CA saves this signature as the batch's validity window signature.
It then updates the latest batch to point to batch_number. A CA
which generates such a signature is considered to have certified
every assertion contained in every value in the tree_heads list, with
expiry determined by batch_number, the position of the tree head in
the list, and the CA's input parameters as described in Section 5.1.
Benjamin, et al. Expires 4 September 2025 [Page 17]
Internet-Draft Merkle Tree Certificates for TLS March 2025
A CA MUST NOT generate signatures over inputs that are parseable as
LabeledValidityWindow, except via the above process. If a
LabeledValidityWindow structure that was not produced in this way has
a valid signature by CA's public_key, this indicates misuse of the
private key by the CA, even if the preimages to the tree_heads
values, or intermediate nodes, or subject_info_hash values are not
known.
5.5.3. Certificate Format
[[TODO: BikeshedCertificate is a placeholder name until someone comes
up with a better one. #15 ]]
[[TODO: An authenticating party has no way to know when a certificate
expires. We need to define a mandatory expiration certificate
property, or do #83, which, depending on how it's done could avoid
that.]]
For each assertion in the tree, the CA constructs a
BikeshedCertificate structure containing the assertion and a proof.
A proof is a message that allows the relying party to accept the
associated assertion, provided it trusts the CA and recognizes the
tree head. The structures are defined below:
/* See Section 4.1 of draft-ietf-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;
A proof's trust_anchor field is a trust anchor identifier (see
Section 3 of [I-D.ietf-tls-trust-anchor-ids] and Section 4.1 of
[I-D.ietf-tls-trust-anchor-ids]), which determines the proof's type
and issuer. It is analogous to an X.509 trust anchor's subject name.
When the issuer is a Merkle Tree CA, the trust_anchor is a batch's
batch_id, as described in Section 5.2.
Benjamin, et al. Expires 4 September 2025 [Page 18]
Internet-Draft Merkle Tree Certificates for TLS March 2025
The proof_data is a byte string, opaque to the authenticating party,
in some format agreed upon by the proof issuer and relying party. If
the issuer is a Merkle Tree CA, as defined in this document, the
proof_data contains a MerkleTreeProofSHA256, described below. Future
mechanisms using the BikeshedCertificate may define other formats.
opaque HashValueSHA256[32];
struct {
uint64 index;
HashValueSHA256 path<0..2^16-1>;
} MerkleTreeProofSHA256;
After building the tree, the CA constructs a MerkleTreeProofSHA256
for each assertion as follows. For each index i in the batch's
assertion list:
1. Set index to i. This will be a value between 0 and n-1,
inclusive.
2. Set path to an array of l-1 hashes. Set element j of this array
to element k of level j, where k is (i >> j) ^ 1. >> denotes a
bitwise right-shift, and ^ denotes a bitwise exclusive OR (XOR)
operation. This element is the sibling of an ancestor of
assertion i in the tree. Note the tree head is never included.
For example, the path value for the third assertion in a batch of
three assertions would contain the marked nodes in Figure 3, from
bottom to top.
level 2: ___ t20 ___
/ \
/ \
level 1: *t10 t11
/ \ / \
/ \ / \
level 0: t00 t01 t02 *empty
| | |
a0 a1 a2
Figure 3: An example Merkle Tree proof for the third of three
assertions
If the batch only contained one assertion, path will be empty and
index will be zero.
For each assertion, the CA assembles a BikeshedCertificate structure
and sends it to the authenticating party.
Benjamin, et al. Expires 4 September 2025 [Page 19]
Internet-Draft Merkle Tree Certificates for TLS March 2025
This certificate can be presented to supporting relying parties as
described in Section 6. It is valid until the batch expires.
5.6. Size Estimates
Merkle Tree proofs scale logarithmically in the batch size.
Section 11.2 recommends authenticating parties 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. Using Certificates
This section describes how authenticating parties present and relying
parties verify Merkle Tree 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 mirrors, 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).
Benjamin, et al. Expires 4 September 2025 [Page 20]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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 an authenticating party 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:
Benjamin, et al. Expires 4 September 2025 [Page 21]
Internet-Draft Merkle Tree Certificates for TLS March 2025
* 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. Transparency Ecosystem
This section discusses how relying parties achieve transparency, via
a combination of _mirrors_ (Section 7.1), who republish information
from the CA; _relying party policy_ (Section 7.2), which determines
which validity windows to accept; and _monitors_ (Section 7.3), who
watch for certificates of interest.
7.1. Mirrors
A mirror is a service that consumes and saves information hosted by
CAs (or other mirrors) and presents it to other parties in the
ecosystem. Mirrors are used to ensure transparency even in the face
of CA misbehavior or outage. A mirror performs the following
functions:
* Record all abridged assertions certified by the CA and mirror them
to monitors
* Ensure all tree heads and validity windows that it records and
mirrors are self-consistent
* Provide information about the latest valid validity window
recorded
In doing so, the mirror MUST satisfy the following requirements:
* The mirrored CA state is append-only. That is, the hashes,
signatures, and assertions for a given batch number MUST NOT
change, even if a CA signs conflicting information.
* All tree hashes that it reports MUST be reflected in the mirrored
CA state.
Benjamin, et al. Expires 4 September 2025 [Page 22]
Internet-Draft Merkle Tree Certificates for TLS March 2025
The mirror publishes its state using the same interface as Section 8.
7.1.1. Updating a Mirror
A mirror maintains a copy of the CA's latest batch number, and batch
state. Roughly once every batch_duration, it polls the HTTP
interface (see Section 8) from the CA, or another mirror, and runs
the following steps:
1. Fetch the 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:
1. If the source is the CA, or if old_latest_batch was fetched
from this mirror, abort this procedure with an error.
2. Otherwise, finish this procedure without reporting an error.
A mirror that combines multiple sources may observe a source
mirror that is behind.
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.
Benjamin, et al. Expires 4 September 2025 [Page 23]
Internet-Draft Merkle Tree Certificates for TLS March 2025
[[TODO: If the mirror gets far behind, or 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. Relying Party Policy
In order to accept certificates from a CA that it trusts, a relying
party must, in the background, obtain an up-to-date copy of the CA's
validity window. In doing so, a relying party SHOULD ensure the
following properties:
Authenticity: The relying party only accepts validity windows that
were certified by the CA
Transparency: The relying party only accepts validity windows
covering certificates that are published in some publicly-
accessible form, so that, in particular, the subject of the
certificate can notice any unauthorized certificates
How the relying party does this has no direct impact on certificate
issuance (Section 5) or usage (Section 6). Different relying parties
can obtain validity windows from different sources or apply different
policies, while supporting the same unmodified certificates and CAs.
Thus this section does not prescribe particular policies or
mechanisms, but provides examples and general guidance. Relying
parties MAY implement policies other than those described below, and
MAY incorporate entities acting in roles not described in this
document.
Relying parties SHOULD ensure transparency by obtaining validity
windows from the CA and/or some combination of trusted mirrors. The
relying party picks sources which, together, are trusted to satisfy
the requirements described in Section 7.1. Mirrors allow the relying
party to maintain transparency in the face of a misbehaving or
compromised CA that may, for example, stop serving some unauthorized
certificate in a batch to evade detection.
A relying party might trust a combination of mirrors, and only accept
a validity window once some minimum number of mirrors have consumed
it. When combining multiple mirrors, the following procedure
determines the latest validity window for an update:
1. Fetch the latest batch number from each mirror.
Benjamin, et al. Expires 4 September 2025 [Page 24]
Internet-Draft Merkle Tree Certificates for TLS March 2025
2. Compute the highest batch number that satisfies the policy. For
example, if requiring windows be represented in at least two
mirrors, use the second-to-last batch number after sorting in
ascending order.
3. Fetch the validity window from each mirror that contains it.
4. Check that each fetched window gives identical tree hashes. If
so, accept the updated window.
To avoid the relying party directly contacting each mirror, this
procedure can be performed with some aggregating service on behalf of
the relying party, or the relying party's update service. [[TODO: If
the relying party doesn't trust the aggregator, this requires mirrors
re-sign validity windows, but we still need to define that. #101]]
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]. If the
relying party considers the service sufficiently trusted (e.g. if the
service provides the trust anchor list or certificate validation
software), a mirror operated by that service could be used as a
single trusted mirror.
Relying parties SHOULD ensure authenticity by verifying the CA's
signature on the validity window. If a relying party has an
authenticated channel to some service trusted to perform this check,
it MAY rely on that service to validate signatures, instead of
downloading the signature itself.
When fetching any of the above information, the relying party MAY use
the interfaces described in Section 8, or it MAY use some other
application-specific channel.
7.3. 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
may be a mirror or the CA itself. 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.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
Benjamin, et al. Expires 4 September 2025 [Page 25]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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.
8. HTTP Interface
[[TODO: This section hasn't been written yet. For now, this is just
an informal sketch. The real text will need to define request/
response formats more precisely, with MIME types, etc. #12 ]]
CAs and mirrors publish state over an HTTP [RFC9110] interface
described below.
CAs and any mirrors that maintain validity window information
implement the following interfaces:
* GET {prefix}/latest returns the latest batch number.
* GET {prefix}/validity-window/latest returns the ValidityWindow
structure and signature (see Section 5.5.2) for the latest batch
number.
* GET {prefix}/validity-window/{number} returns the ValidityWindow
structure and signature (see Section 5.5.2) for batch number, if
it is in the "issued" state, and a 404 error otherwise.
* GET {prefix}/batch/{number}/info returns the validity window
signature and tree head for batch number, if batch number is in
the "issued" state, and a 404 error otherwise.
CAs and any mirrors that maintain the full abridged assertion list
additionally implement the following interface:
* GET {prefix}/batch/{number}/assertions returns the abridged
assertion list for batch number, if number is in the issued state,
and a 404 error otherwise.
Benjamin, et al. Expires 4 September 2025 [Page 26]
Internet-Draft Merkle Tree Certificates for TLS March 2025
If the interface is implemented by a distributed service, with
multiple servers, updates may propagate to servers at different
times, which will cause temporary inconsistency. This inconsistency
can impede this system's transparency goals (Section 13.4).
Services implementing this interface SHOULD wait until batch state is
fully propagated to all servers before updating the latest batch
number. That is, if any server returns a latest batch number of N in
either of the first two HTTP endpoints, batch numbers N and below
SHOULD be available under the last three batch-number-specific HTTP
endpoints in all servers. If this property does not hold at any
time, it is considered a service unavailability.
Individual servers in a service MAY return different latest batch
numbers. Individual servers MAY also differ on whether a batch
number has a response available or return a 404 error. Provided the
above consistency property holds, these two inconsistencies do not
constitute service unavailability.
Section 11.4 discusses service availability requirements.
[[TODO: Once a batch has expired, do we allow a CA to stop publishing
it? A mirror can already log it for as long, or as little, as it
wishes. We effectively have CT log temporal sharding built into the
system. #2 ]]
[[TODO: If we have the validity window endpoint, do we still need to
separate "info" and "assertions"? #12]]
9. ACME Extensions
[[TODO: This section hasn't been written yet. Instead, what follows
is an informal discussion. #13 ]]
Section 6 of [I-D.ietf-tls-trust-anchor-ids] defines the bulk of
what's needed. The missing parts are:
* Some way to specify that the client supports BikeshedCertificate.
At minimum a separate MIME type, but it likely needs to be known
at order creation.
* Some way to accommodate MTC's long issuance time. ACME has the
"processing" state, and the Retry-After header can tell the
authenticating party when to query again. But the fallback
certificate will issue much faster, so they cannot be issued
together in the same ACME order, as
[I-D.ietf-tls-trust-anchor-ids] currently does.
Benjamin, et al. Expires 4 September 2025 [Page 27]
Internet-Draft Merkle Tree Certificates for TLS March 2025
* Use [I-D.ietf-acme-ari] to move the renewal logic in Section 11.2
from the authenticating party to the ACME server.
We should also define a certificate request format, though it is
broadly just reusing the Assertion structure. If the CA wishes to
check possession of the private key, it'll need to come with a
signature or do some online operation (e.g. if it's a KEM key). This
is inherently protocol-specific, because the mechanism needs to
coexist with the target protocol. (Signed CSRs implicitly assume the
target protocol's signature payloads cannot overlap with that of a
CSR.)
10. Use in TLS
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 authenticating party'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]
Benjamin, et al. Expires 4 September 2025 [Page 28]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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:
Benjamin, et al. Expires 4 September 2025 [Page 29]
Internet-Draft Merkle Tree Certificates for TLS March 2025
enum { Bikeshed(TBD), (255) } CertificateType;
struct {
select (certificate_type) {
/* Certificate type defined in this document */
case Bikeshed:
opaque bikeshed_cert_data<1..2^24-1>;
/* 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 authenticating party 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.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.
Benjamin, et al. Expires 4 September 2025 [Page 30]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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.ietf-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.ietf-tls-trust-anchor-ids] and the DNS hint described in
Section 5 of [I-D.ietf-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 authenticating party's list of candidate certification paths (see
Section 3.3 of [I-D.ietf-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
authenticating party's policies. Like an X.509 credential, a
BikeshedCertificate credential also has a CertificatePropertyList
(see Section 3.1 of [I-D.ietf-tls-trust-anchor-ids]).
Benjamin, et al. Expires 4 September 2025 [Page 31]
Internet-Draft Merkle Tree Certificates for TLS March 2025
For each of the authenticating party'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 authenticating party then selects certificates as described in
Section 4.2 of [I-D.ietf-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. Deployment Considerations
11.1. Fallback Mechanisms
Authenticating parties 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, or are unable to, fetch a sufficiently new
validity window.
If the pipeline of updates from the CA to mirrors 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 an authenticating party 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 trusted mirrors, then
pushed to relying parties.
Benjamin, et al. Expires 4 September 2025 [Page 32]
Internet-Draft Merkle Tree Certificates for TLS March 2025
To account for this, authenticating parties 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. Authenticating parties
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 cannot validate the certificate until
they have received a validity window containing said certificate.
The authenticating party 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 authenticating party 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 mirrors 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, mirrors will be
unavailable to update. This will prevent relying parties from
accepting new certificates, so authenticating parties will need to
Benjamin, et al. Expires 4 September 2025 [Page 33]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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 authenticating parties or trusted by relying parties.
However, if a mirror's interface becomes unavailable, monitors may be
unable to check for unauthorized certificates, if the certificates
are not available in another mirror. This does compromise
transparency goals. This can be partially mitigated by a combination
of state being replicated in additional mirrors, a relying party
requiring multiple mirrors log a batch (see Section 7.2), or a
relying party requiring a sufficiently trusted and reliable mirror
log a batch.
12. Privacy Considerations
The Privacy Considerations described in Section 9 of
[I-D.ietf-tls-trust-anchor-ids] apply to its use with Merkle Tree
Certificates.
In particular, relying parties that share an update process will
fetch the same stream of updates. However, updates may reach
different users at different times, resulting in some variation
across users. This variation may contribute to a fingerprinting
attack [RFC6973]. If the Merkle Tree CA trust anchors are sent
unconditionally in trust_anchors, this variation will be passively
observable. If they are sent conditionally, e.g. with the DNS-
mechanism, the trust anchor list will require active probing.
13. Security Considerations
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.2 discusses achieving the first property.
Benjamin, et al. Expires 4 September 2025 [Page 34]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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.
Benjamin, et al. Expires 4 September 2025 [Page 35]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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 mechanisms described in Section 7 do not prevent unauthorized
certificates, but they aim to provide comparable security properties
to Certificate Transparency [RFC6962]. Before the relying party
accepts a Merkle Tree Certificate, the relying party should have
assurance the certificate was published in some form that monitors
and, in particular, the subject of the certificate will be able to
notice.
13.4.1. Unauthorized Certificates
If a CA issues an unauthorized Merkle Tree certificate, the
certificate will be rejected by the relying party, publicly logged
among the relying party's trusted mirrors, or both:
The relying party will only accept the certificate if has been
configured with the corresponding tree head (see Section 6.1). For
this to happen, the tree head must be in some validity window that
satisfied the relying party's policy (see Section 7.2), which is
expected to only accept validity windows whose contents are publicly
logged. For example, if the relying party requires a quorum of
trusted mirrors, the certificate will be visible as long as
sufficiently many trusted mirrors are correctly operated.
Benjamin, et al. Expires 4 September 2025 [Page 36]
Internet-Draft Merkle Tree Certificates for TLS March 2025
If the certificate did not meet relying party policy because, e.g.,
the CA withheld publishing the certificate or mirrors could not reach
the CA, the certificate may not be publicly visible. However, in
that case, the relying party will not trust the corresponding tree
head and thus reject the certificate.
This is analogous to Certificate Transparency, but has some
differences:
Unlike Certificate Transparency, the mechanisms in this document do
not provide the preimages for subject_info_hash, only the hashed
values. This is intended to reduce serving costs, particularly with
large post-quantum keys. As a result, monitors look for unrecognized
hashes instead of unrecognized keys. Any unrecognized hash, even if
the preimage is unknown, indicates an unauthorized certificate.
This optimization complicates studies of weak public keys, e.g.
[SharedFactors]. Such studies will have to retrieve the public keys
separately, such as by connecting to the TLS servers, or fetching
from the CA if it retains the unabridged assertion. This document
does not define a mechanism for doing this.
Additionally, accepted Merkle Tree certificates are expected to be
immediately publicly visible, rather than after a Maximum Merge Delay
(see Section 3 of [RFC6962]). Relying party policies SHOULD require
that certificates be fully mirrored before accepting a tree head.
Merkle Tree certificates do not aim to support immediate issuance, as
described in Section 11.
13.4.2. Misbehaving Certification Authority
Although CAs in this document publish structures similar to a
Certificate Transparency log, they do not need to function correctly
to provide transparency.
A CA could violate the append-only property of its batch state, and
present differing views to different parties. Unlike a misbehaving
Certificate Transparency log, this would not compromise transparency.
Whichever view is presented to the relying party's trusted mirrors at
the time of updates determines the canonical batch state for both
relying parties and monitors. Certificates that are inconsistent
with that view will be rejected by relying parties. If a mirror
observes multiple views, the procedure in Section 7.1.1 will prevent
conflicting views from overwriting the originally saved view.
Instead, the update process will fail and further certificates will
not be accepted.
Benjamin, et al. Expires 4 September 2025 [Page 37]
Internet-Draft Merkle Tree Certificates for TLS March 2025
A CA could also sign a validity window containing an unauthorized
certificate and feign an outage when asked to serve the corresponding
assertions. However, if the assertion list was never mirrored, the
tree head will never be pushed to relying parties, so the relying
party will reject the certificate. If the assertion list was
mirrored, the unauthorized certificate continues to be available to
monitors.
As a consequence, when looking for unauthorized certificates that
some relying party may accept, monitors SHOULD use tree heads from
each of the relying party's trusted mirrors. A monitor MAY skip
downloading the contents of a batch if an identical tree head was
already checked from another source. Monitors MAY also monitor the
CA directly, but this alone is not sufficient to avoid missing
certificates if the CA misbehaves.
13.4.3. Misbehaving Mirror
This document divides CA and mirror responsibilities differently from
how [RFC6962] divides CA and Certificate Transparency log
responsibilities. The previous section describes the implications of
a failure to meet the log-like responsibilities of a CA, provided
trusted mirrors are operating correctly.
For the remainder of log-like responsibilities, a relying party's
policy (see Section 7.2) trusts its choice of mirrors to, together,
ensure the validity windows it uses are consistent with what monitors
observe. If untrustworthy, a malicious mirror and CA could collude
to cause a relying party to accept an unauthorized certificate not
visible to monitors. If the relying party requires a quorum of
trusted mirrors, all or most of the mirrors must collude to succeed
in this attack.
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.
Benjamin, et al. Expires 4 September 2025 [Page 38]
Internet-Draft Merkle Tree Certificates for TLS March 2025
14. IANA Considerations
IANA is requested to create the following entry in the TLS
Certificate Types registry [RFC8447]. The "Reference" column should
be set to this document.
+=======+==========+=============+
| Value | Name | Recommended |
+=======+==========+=============+
| TBD | Bikeshed | TBD |
+-------+----------+-------------+
Table 1: Additions to the TLS
Certificate Types Registry
[[ TODO: Define registries for the enums introduced in this document.
#42]]
* SubjectType
* ClaimType
15. References
15.1. Normative References
[I-D.ietf-tls-trust-anchor-ids]
Beck, B., Benjamin, D., O'Brien, D., and K. Nekritz, "TLS
Trust Anchor Identifiers", Work in Progress, Internet-
Draft, draft-ietf-tls-trust-anchor-ids-00, 25 February
2025, <https://datatracker.ietf.org/doc/html/draft-ietf-
tls-trust-anchor-ids-00>.
[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>.
Benjamin, et al. Expires 4 September 2025 [Page 39]
Internet-Draft Merkle Tree Certificates for TLS March 2025
[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>.
Benjamin, et al. Expires 4 September 2025 [Page 40]
Internet-Draft Merkle Tree Certificates for TLS March 2025
[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>.
[RFC9525] Saint-Andre, P. and R. Salz, "Service Identity in TLS",
RFC 9525, DOI 10.17487/RFC9525, November 2023,
<https://www.rfc-editor.org/rfc/rfc9525>.
[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
Benjamin, et al. Expires 4 September 2025 [Page 41]
Internet-Draft Merkle Tree Certificates for TLS March 2025
Symposium on Security and Privacy (SP) pp. 539-556,
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/>.
[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>.
[FIPS204] National Institute of Standards and Technology (NIST),
"Module-Lattice-based Digital Signature Standard", FIPS
PUB 204, August 2023, <https://csrc.nist.gov/projects/
post-quantum-cryptography>.
[FIREFOX] Mozilla, "Firefox Remote Settings", 20 August 2022,
<https://wiki.mozilla.org/Firefox/RemoteSettings>.
[I-D.ietf-acme-ari]
Gable, A., "Automated Certificate Management Environment
(ACME) Renewal Information (ARI) Extension", Work in
Progress, Internet-Draft, draft-ietf-acme-ari-08, 26
February 2025, <https://datatracker.ietf.org/doc/html/
draft-ietf-acme-ari-08>.
[I-D.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>.
Benjamin, et al. Expires 4 September 2025 [Page 42]
Internet-Draft Merkle Tree Certificates for TLS March 2025
[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>.
Appendix A. Examples
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 00120000 000e000c 0b657861 6d706c65 2e636f6d
The corresponding AbridgedAssertion:
00000022 0807d8e2 c44fc82e 175e5698 b1c25324 6c9a996f c37bad29 fd59b6aa
838b0a93 0b000012 0000000e 000c0b65 78616d70 6c652e63 6f6d
Benjamin, et al. Expires 4 September 2025 [Page 43]
Internet-Draft Merkle Tree Certificates for TLS March 2025
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 00010028 0001000e 000c0b65
78616d70 6c652e63 6f6d0002 00120010 c0000225 c0000c00 c633643c cb007100
The corresponding AbridgedAssertion:
00000022 08049a04 087a4d52 033a0a20 04333359 ccf29703 25684c5f a96f1ca1
35cb2ab1 f2670028 0001000e 000c0b65 78616d70 6c652e63 6f6d0002 00120010
c0000225 c0000c00 c633643c cb007100
Appendix B. TLS Certificate Type Negotiation Challenges
[[TODO: We may need a new TLS certificate types extension, either in
this document or a separate one. For now, this section just
informally describes the problem. #18 ]]
The server certificate type is negotiated as follows:
* The client sends server_certificate_type in ClientHello with
accepted certificate types.
* The server selects a certificate type to use, It sends it in
server_certificate_type in EncryptedExtensions.
* The server sends a certificate of the server-selected type in
Certificate.
This model allows the server to select its certificate type based on
not just server_certificate_type, but also other ClientHello
extensions like certificate_authorities or trust_anchors
([I-D.ietf-tls-trust-anchor-ids]). In particular, if there is no
match in trust_anchors, it can fallback to X.509, rather than staying
within the realm of BikeshedCertificate.
However, the client certificate type is negotiated differently:
Benjamin, et al. Expires 4 September 2025 [Page 44]
Internet-Draft Merkle Tree Certificates for TLS March 2025
* The client sends client_certificate_type in ClientHello with
certificates it can send
* The server selects a certificate type to request. It sends it in
client_certificate_type in EncryptedExtensions.
* The server requests a client certificate in CertificateRequest
* The client sends a certificate of the server-selected type in
Certificate.
Here, the client (authenticating party) does not select the
certificate type. The server (relying party) does. Moreover, this
selection is made before the client can see the server's
certificate_authorities or trust_anchors value, in
CertificateRequest. There is no opportunity for the client to
fallback to X.509.
The cert_types extension behaves similarly, but additionally forces
the client and server types to match. These extensions were defined
when TLS 1.2 was current, but TLS 1.3 aligns the client and server
certificate negotiation. Most certificate negotiation extensions,
such as certificate_authorities or compress_certificate [RFC8879] can
be offered in either direction, in ClientHello or CertificateRequest.
They are then symmetrically accepted in the Certificate message.
A more corresponding TLS 1.3 negotiation would be to defer the client
certificate type negotiation to CertificateRequest, with the server
offering the supported certificate types. The client can then make
its selection, taking other CertificateRequest extensions into
account, and indicate its selection in the Certificate message.
Two possible design sketches:
B.1. Indicate in First CertificateEntry
We can have the authenticating party 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.
Benjamin, et al. Expires 4 September 2025 [Page 45]
Internet-Draft Merkle Tree Certificates for TLS March 2025
B.1.1. Change Certificate Syntax
Alternatively, we can negotiate an extension that changes the syntax
to Certificate to:
struct {
CertificateType certificate_type;
opaque certificate_request_context<0..2^8-1>;
CertificateEntry certificate_list<0..2^24-1>;
} Certificate;
The negotiation can be:
* Client sends its accepted certificate types in ClientHello.
Offering this new extension also signatures it is willing to
accept the new message format. Unlike the existing extensions, an
X.509-only client still sends the extension with just X509 in the
list.
* Server, if it implements the new syntax, acknowledges the syntax
change with an empty extension in EncryptedExtensions. (It
doesn't indicate its selection yet.)
* If both of the above happen, Certificate's syntax has changed.
Server indicates its selection with the certificate_type field
* Server can also send this extension in CertificateRequest to offer
non-X.509 certificate types
* Client likewise indicates its selection with the certificate_type
field.
This is a bit cleaner to parse, but the negotiation is more complex.
Acknowledgements
This document stands on the shoulders of giants and builds upon
decades of work in TLS authentication and X.509. The authors would
like to thank all those who have contributed over the history of
these protocols.
The authors additionally thank Bob Beck, Ryan Dickson, Nick Harper,
Dennis Jackson, Ryan Sleevi, and Emily Stark for many valuable
discussions and insights which led to this document. We wish to
thank Mia Celeste in particular, whose implementation of an earlier
draft revealed several pitfalls.
Benjamin, et al. Expires 4 September 2025 [Page 46]
Internet-Draft Merkle Tree Certificates for TLS March 2025
Change log
*RFC Editor's Note:* Please remove this section prior to
publication of a final version of this document.
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
* Elaborate on CA public key and signature format. #27
* Miscellaneous changes.
* Replace the negotiation mechanism with TLS Trust Anchor
Identifiers.
* Switch terminology from "subscriber" to "authenticating party".
* Use <1..2^24-1> encoding for all certificate types in the
CertificateEntry TLS message
* Clarify discussion and roles in transparency ecosystem
* Update references
Authors' Addresses
David Benjamin
Google LLC
Benjamin, et al. Expires 4 September 2025 [Page 47]
Internet-Draft Merkle Tree Certificates for TLS March 2025
Email: davidben@google.com
Devon O'Brien
Google LLC
Email: asymmetric@google.com
Bas Westerbaan
Cloudflare
Email: bas@cloudflare.com
Benjamin, et al. Expires 4 September 2025 [Page 48]