TLS Trust Expressions

2.1. Time

Times in this document are represented by POSIX timestamps, which are 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 as per Section 4.16 of [POSIX]. 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

This document discusses four roles:¶

Subscriber:

The party whose identity is being validated in the protocol. In TLS, this is the side sending the Certificate and CertificateVerify message.¶

Relying party:

The party that authenticates the subscriber. In TLS, this is the side that validates a Certificate and CertificateVerify message.¶

Certification authority (CA):

The service that issues certificates to the subscriber.¶

Root program:

An entity that manages a set of common trusted CAs for a set of relying parties.¶

While the first three roles are common to most X.509 deployments, this document discusses the role of a root program as distinct from the relying party. Trust decisions are often common between related relying parties, such as multiple clients running the same application. The root program is the entity making those common decisions, such as the software vendor for the application or operating system.¶

Additionally, there are several terms used throughout this document to describe this proposal:¶

Trust anchor:

A pre-distributed public key or certificate that relying parties use to determine whether a certification path is trusted.¶

Trust store:

A collection of trust anchors managed by the root program.¶

Certification path:

An ordered list of X.509 certificates starting the target certificate. Each certificate is issued by the next certificate, except the last, which is issued by a trust anchor.¶

Trust store manifest:

A structure describing a series of versioned trust stores.¶

Trust expression:

A compact description of a relying party's trust store contents, referencing named, versioned trust stores.¶

CertificatePropertyList:

A structure associated with a certification path, containing additional information from the CA, for use by the subscriber when presenting the certification path.¶

TrustStoreInclusionList:

A property in the CertificatePropertyList which describes the corresponding trust anchor's inclusion in trust stores. This is used by the subscriber when evaluating trust expressions.¶

4.1. Trust Store Entry Expiration

The max_age and max_lifetime fields define an expiration time for trust store entries in versions other than the latest version. For a trust store entry in version V, the expiration time is the sum of:¶

• The timestamp of the subsequent version, i.e. version V+1¶

• The max_age of the manifest¶

• The max_lifetime of the trust store entry¶

Expiration times for entries in the latest version are not defined. They are determined once the root store appends a new version.¶

Trust store entries are not removed from their containing version after they expire. Rather, the expiration time is the point at which all unexpired certificates have incorporated information about subsequent trust store versions, per Section 5.2. This ensures the negotiation procedures in Section 6.3 and Section 6.5 interoperate.¶

4.2. Labels

Trust store entries reference labels, which are 24-bit integers that identify subsets of a trust store version. These integers are defined relative to the trust store manifest and are not globally unique. Root programs allocate labels when defining versions of a trust store.¶

Labels are used in trust expressions (Section 6.1) to exclude trust anchor entries from the expression. A label may identify an individual trust anchor if it is the only one with that label, or multiple trust anchors if they share the label.¶

The root program's label allocation scheme determines which sets may be efficiently represented. In particular, when trust anchors are removed in a later version of a trust store, trust expressions must express the removed set with labels as described in Section 6.5. Root programs SHOULD allocate individual labels for each trust anchor, and shared labels for trust anchors that will likely be removed together. For example, the root program may allocate shared labels for trust anchors with the same operator, or trust anchors that use some signature algorithm if it expects some relying parties to exclude by algorithm.¶

When allocating labels, root programs MAY repurpose a previously allocated label value after all previous entries referencing it have expired (Section 4.1).¶

5.1. Trust Store Inclusion

The trust_stores property specifies which trust stores contain the certification path's trust anchor. Its data field contains a TrustStoreInclusionList, defined below:¶

enum {
    previous_version(0),
    latest_version_at_issuance(1)
} TrustStoreStatus;

struct {
    opaque name<1..2^8-1>;
    uint24 version;
} TrustStore;

struct {
    TrustStore trust_store;
    TrustStoreStatus status;
    uint24 labels<1..2^16-1>;
} TrustStoreInclusion;

TrustStoreInclusion TrustStoreInclusionList<1..2^16-1>;

Each TrustStoreInclusion describes a trust store version which contains this certification path's trust anchor. trust_store specifies a version of the trust store, and labels specifies the trust anchor's labels within that trust store.¶

If status is latest_version_at_issuance, trust_store was the latest trust store of its name at the time the certificate was issued. In this case, the trust expression evaluation algorithm (Section 6.3) predicts this information additionally applies to all versions greater than trust_store's version, up to the expiration of the certification path.¶

A TrustStoreInclusionList MUST satisfy the following invariants:¶

• Each TrustStoreInclusion has a unique trust_store value.¶

• The TrustStoreInclusion structures are sorted, first by length of trust_store's name, then by trust_store's name lexicographically, then by trust_store's version.¶

• If status is latest_version_at_issuance in some TrustStoreInclusion, no trust_store with the same name but higher version appears in the list.¶

5.2. Computing Trust Store Inclusions

Each CA regularly fetches trust store manifests from root programs in which it participates, caching the most recently fetched manifest from each root program. When issuing a certification path to a subscriber, it runs the following procedure on each root program's trust store manifest, to compute a list of TrustStoreInclusions:¶

1. If the cached manifest was fetched more than max_age seconds ago, fetch and cache a new copy.¶

2. For each trust store version in the cached manifest's versions:¶

   1. Look for a trust store entry whose id, when indexed into trust_anchors, matches the certification path's trust anchor.¶

   2. If found, output a TrustStoreInclusion structure:¶

      • Set trust_store to the manifest's name, encoded in UTF-8 [RFC3629], and the version's version number.¶

      • Set status to latest_version_at_issuance if the trust store version is currently the latest version. Otherwise, set it to previous_version.¶

      • Set labels to the trust store entry's labels.¶

If the above procedure outputs a TrustStoreInclusion with status of latest_version_at_issuance, the certification path's lifetime MUST NOT exceed the corresponding trust store entry's max_lifetime field. This ensures the procedures in Section 6.3 and Section 6.5 interoperate correctly.¶

The CA combines the outputs of this procedure for each known manifest to form the final TrustStoreInclusionList. To aid the CA in collecting manifests, repositories such as [CCADB] can publish a directory of trust store manifests from participating root programs.¶

5.3. Media Type

A certification path with its associated CertificationPropertyList may be represented in a PEM [RFC7468] structure in a file of type "application/pem-certificate-chain-with-properties". Files of this type MUST use the strict encoding and MUST NOT include explanatory text. The ABNF [RFC5234] for this format is as follows, where "stricttextualmsg" and "eol" are as defined in Section 3 of [RFC7468]:¶

certchainwithproperties = stricttextualmsg eol stricttextualmsg
                          *(eol stricttextualmsg)

The first element MUST be the encoded CertificatePropertyList. The second element MUST be an end-entity certificate. Each following certificate MUST directly certify the one preceding it. The certificate representing the trust anchor MUST be omitted from the path.¶

CertificatePropertyLists are encoded using the "CERTIFICATE PROPERTIES" label. The encoded data is a serialized CertificatePropertyList, defined in Section 5.¶

Certificates are encoded as in Section 5.1 of [RFC7468], except DER [X690] MUST be used.¶

The following is an example file with a certification path containing an end-entity certificate and an intermediate certificate.¶

-----BEGIN CERTIFICATE PROPERTIES-----
TODO fill in an example
-----END CERTIFICATE PROPERTIES-----
-----BEGIN CERTIFICATE-----
TODO fill in an example
-----END CERTIFICATE-----
-----BEGIN CERTIFICATE-----
TODO fill in an example
-----END CERTIFICATE-----

The IANA registration for this media type is described in Section 12.2.¶

6.1. Trust Expressions

When the trust_expressions extension is sent in ClientHello and CertificateRequest, the extension_data field is a TrustExpressionList, defined below:¶

enum { trust_expressions(TBD), (2^16-1) } ExtensionType;

struct {
    TrustStore trust_store;
    uint24 excluded_labels<0..2^16-1>;
} TrustExpression;

TrustExpression TrustExpressionList<1..2^16-1>;

A TrustExpressionList is an unordered set of TrustExpression objects. When a relying party sends a TrustExpressionList, it indicates support for all trust anchors specified by any TrustExpression contained in the list. A TrustExpression specifies a list of trust anchors in two parts:¶

First, trust_store specifies a trust store by name and version (see Section 4). Any trust anchors contained in the specified trust store are included.¶

Second, excluded_labels specifies a set of labels, each of which identify one or more trust anchors in a trust store manifest. Any trust anchors identified by any label in excluded_labels are excluded. Section 6.5 discusses this set in more detail.¶

excluded_labels MUST be sorted in ascending order and contain no duplicate values to be valid. If invalid, receivers MUST terminate the connection with an illegal_parameter alert.¶

Together, a TrustExpression indicates that the relying party accepts all trust anchors in the referenced trust store version, except for any that were excluded via excluded_labels.¶

6.2. Subscriber Acknowledgement

When the trust_expressions extension is sent in a Certificate message, the extension MUST be in the first CertificateEntry and the extension_data field MUST be empty. This extension indicates the subscriber selected a certification path using trust expressions.¶

In this case, the certificate_list flexibility described in Section 4.4.2 of [RFC8446] no longer applies. The certificate_list MUST contain a complete certification path, correctly ordered and with no extraneous certificates. That is, each certificate MUST certify the one immediately preceding it, and the trust anchor MUST certify the final certificate.¶

If a relying party receives this extension in the Certificate message, it SHOULD NOT use path building [RFC4158] to validate the result.¶

6.3. Evaluating Trust Expressions

Given a certification path with a trust_store certificate property (Section 5.1), a subscriber can evaluate a TrustExpressionList to determine whether the certification path matches.¶

A TrustExpression is said to match a TrustStoreInclusionList if there is at least one TrustStoreInclusion in the TrustStoreInclusionList such that all of the following are true:¶

• The name fields of two structures' trust_store fields are equal.¶

• Either the version fields of the two structures' trust_store fields are equal, or the TrustStoreInclusion's status is latest_version_at_issuance and the version field of TrustExpression's trust_store is greater than that of the TrustStoreInclusion's trust_store.¶

• There is no value in common between the TrustStoreInclusion's labels field and the TrustExpression's excluded_labels field.¶

The invariants in Section 5.1 imply that at most one TrustStoreInclusion will satisfy the first two properties. Implementations may evaluate this efficiently by performing a binary search over the TrustStoreInclusionList, and then checking the third property.¶

A TrustExpressionList is said to match a TrustStoreInclusionList if any TrustExpression in the TrustExpressionList matches the TrustStoreInclusionList.¶

When a TrustStoreInclusion's status is latest_version_at_issuance, the above criteria predicts that trust anchors in the latest version will continue to be present in later versions. This allows relying parties using later trust store versions to continue to interoperate with certification paths that predate the later version. If this prediction is incorrect and the trust anchor has been removed from the later version, Section 6.5 requires that the TrustExpression include appropriate excluded_labels values to mitigate this.¶

6.4. Subscriber Behavior

Subscribers using this negotiation scheme are configured with a list of certification paths, with corresponding CertificatePropertyList (Section 5) structures, in some preference order. When responding to a ClientHello (as a server) or CertificateRequest (as a client) containing the trust_expressions extension, the subscriber collects all candidate certification paths such that all of the following are true:¶

• The certification path has not expired.¶

• The CertificatePropertyList has a trust_store property with a TrustStoreInclusionList.¶

• The matching algorithm described in Section 6.3 returns true.¶

• The certification path is suitable for use based on other TLS criteria. For example, the TLS signature_algorithms (Section 4.2.3 of [RFC8446]) extension constrains the types of keys which may be used.¶

• The certification path satisfies any other application-specific constraints which may apply. For example, TLS servers often select certificates based on the server_name (Section 3 of [RFC6066]) extension.¶

Once all candidate paths are determined, the subscriber picks one to present to the relying party. The subscriber MUST include an empty trust_expressions extension in the first CertificateEntry. If multiple candidates match, the subscriber picks its most preferred option. For example, it may try to minimize message size, or prefer options with more performant private keys.¶

If no candidates match, or if the peer did not send a trust_expressions extension, the subscriber falls back to preexisting behavior outside the scope of this document, without including a trust_expressions extension. For example, the subscriber may have a default certificate configured, or select a certificate using the certificate_authorities extension.¶

6.5. Constructing Trust Expressions

Relying parties send the trust_expressions extension to advertise a set of accepted trust anchors. Section 10 discusses which trust anchors to advertise. Each trust expression to be sent advertises a subset of some trust store version. To communicate a set of trust anchors that span multiple trust stores, relying parties MAY send multiple trust expressions, each referencing a different trust store.¶

For each referenced trust store version, the following procedure constructs a trust expression. This procedure is expected to be run by the root program, as part of defining new trust store versions and provisioning supported trust anchors in relying parties.¶

[[TODO: This is written as a procedure, but we expect root programs to fill in the expected exclusions when they define a new trust store version, and then trim the compatibility exclusions as they expire. Also the root programs know their label allocation scheme and are the ones deciding on removals, so they're best situated to pick a set of excluded_labels. Perhaps this should get moved to the manifest?]]¶

1. Let include_entries and exclude_entries be two empty sets of trust anchor entries.¶

2. For each trust store entry in the trust store version:¶

   1. If the trust store entry's id references a trust anchor that is in the desired subset, add it to include_entries.¶

   2. Otherwise, add it to exclude_entries.¶

3. For all trust store entries in trust store versions before the specified version:¶

   1. If the current time is before the entry's expiration time (Section 4.1) and if the entry's id references a trust anchor that is not in the desired subset, add the entry to exclude_entries.¶

4. Compute a set of labels, excluded_labels such that:¶

   1. No label appears in any entry in include_entries.¶

   2. For each entry in exclude_entries, there is some label in common between excluded_labels and the labels in the entry.¶

   How to compute this set depends on the root program's label allocation scheme (Section 4.2). If the root program allocates a label for each trust anchor, this set is always computable, though more efficient sets may be possible depending on the allocation scheme.¶

5. Output a TrustExpression such that trust_store is the referenced trust store version, and excluded_labels is the computed excluded_labels value.¶

This procedure uses excluded_labels for two kinds of exclusions:¶

First, if the trust store version includes undesired trust anchors, the trust expression should exclude them. This may occur if, for example, the trust store is used by all versions of the relying party's software, but some trust anchors are gated by software version.¶

Second, trust expressions exclude unexpired entries from previous versions. This is because the matching criteria described in Section 6.3 predictively applies TrustStoreInclusion values with status of latest_version_at_issuance to all future versions of a trust store. This allows relying parties to interoperate with subscribers with stale information. Unexpired entries are those for which such an unexpired certification path may still exist. Where this prediction is incorrect, trust expressions MUST mitigate this by excluding the past entries.¶

7.1. ACME Extension

This section extends ACME [RFC8555] to be able to issue certificate paths, each with an associated CertificatePropertyList by defining a new media type in Section 5.3. It extends the ACME order object with a configurable boolean field, "trustExpressions".¶

First, ACME clients indicate they support certification paths selected by trust expressions by setting "trustExpressions" to "true" in the ACME newOrder request (Section 7.4 of [RFC8555]). If the server accepts the request, it MUST reflect the field in the resulting order object.¶

When an ACME server processes an order object with the "trustExpressions" field set to "true", it MAY issue multiple certification paths, each with an associated TrustStoreInclusionList, computed as in Section 5.2. These paths MAY share an end-entity certificate but end at different trust anchors, or they MAY be completely distinct. If the latter, the "trustExpressions" order field allows the ACME server to skip issuing unnecessary end-entity certificates for ACME clients that would be unable to use them. The ACME server encodes each certification path using the application/pem-certificate-chain-with-properties format, defined in Section 5.3). Note this format is required to form a complete certification path. The CA MUST return a result that may be verified by relying parties without path building [RFC4158].¶

The ACME server provides additional results to the client with the link relation header fields described in Section 7.4.2 of [RFC8555]. When fetching certificates, the ACME client includes application/pem-certificate-chain-with-properties in its Accept header to indicate it supports the new format. Unlike the original mechanism described in [RFC8555], these certification paths do not require heuristics to be used. Instead, the ACME client uses the associated TrustStoreInclusionLists to select a path as described in Section 6.4.¶

When the ACME client wishes to renew any of the certification paths issued in this order, it repeats this process to renew each path concurrently. Thus this extension is suitable when the CA is willing to issue and renew all paths together. It may not be appropriate if the paths have significantly different processing times or lifetimes. Future enhancements to ACME may be defined to address these cases, e.g. by allowing the ACME client to make independent orders.¶

9.1. Key Rotation

In most X.509 deployments, a compromise of any root CA's private key compromises the entire PKI. Yet key rotation in PKIs is rare. In 2023, the oldest root in [CHROME-ROOTS] and [MOZILLA-ROOTS] was 25 years old, dating to 1998. Key rotation is challenging in a single-certificate deployment model. As long as any older relying party requires the old root, subscribers cannot switch to the new root, which in turn means relying parties cannot distrust the old root, leaving them vulnerable.¶

A multi-certificate deployment model avoids these transition problems. Key rotation may proceed as follows:¶

1. The CA operator generates a new root CA with a separate key, but continues operating the old root CA.¶

2. Root programs begin trusting the new root CA alongside the old one. They update their root store manifests.¶

3. When subscribers request certificates, the CA issues certificates from both roots and provisions the subscriber with both certificates.¶

4. Relying parties send trust expressions that evaluate to either the old or new root, and are served the appropriate option.¶

5. Once subscribers have been provisioned with new certificates, root programs can safely distrust the old root in new relying parties. The CA operator continues to operate the old root CA for as long as it wishes to serve subscribers that, in turn, wish to serve older relying parties.¶

This process requires no configuration changes to the subscriber, given an automated, multi-certificate-aware certificate issuance process. The subscriber does not need to know why it received two certificates, only how to select between them for each relying party.¶

9.2. Adding CAs

In the single-certificate model, subscribers cannot use TLS certificates issued from a new root CA until all supported relying parties have been updated to trust the new root CA. This can take years or more. Some relying parties, such as IoT devices, may never receive trust store updates at all.¶

As a result, it is very difficult for subscribers that serve a wide variety of relying parties to use a newly-trusted root CA. When trust stores diverge too far, subscribers often must partition their services into multiple TLS endpoints (i.e. different DNS names) and direct different relying parties to different endpoints. Subscribers sometimes resort to TLS fingerprinting, to detect particular relying parties. But, as this repurposes other TLS fields for unintended purposes, this is unreliable and usually requires writing custom service-specific logic.¶

In a multi-certificate deployment model, subscribers can begin serving certificates from new root CAs without interrupting relying parties that depend on existing ones.¶

In some contexts, it may be possible to use other fields to select the new CA. For example, post-quantum-capable clients may be detected with the signature_algorithms and signature_algorithms_cert extensions. However, this assumes all post-quantum CAs are added at the same time. A multi-certificate model avoids this problem and allows for a more gradual deployment of post-quantum CAs.¶

9.3. Removing CAs

Subscribers in a single-certificate model are limited to CAs in the intersection of their supported relying parties. As newer relying parties remove untrusted CAs over time,the intersection with older relying parties shrinks. Moreover, the subscriber may not even know which CAs are in the intersection. Often, the only option is to try the new certificate and monitor errors. For subscribers that serve many diverse relying parties, this is a disruptive and risky process.¶

The multi-certificate model removes this constraint. If a subscriber's CA is distrusted, it can continue to use that CA, in addition to a newer one. This removes the risk that some older relying party required that CA and was incompatible with the new one. The mechanisms in this document will select an appropriate certificate for each relying party.¶

9.4. Other Root Transitions

The mechanisms in this document can aid PKI transitions beyond key rotation. For example, a CA operator may generate a postquantum root CA and use the mechanism in Section 7.1 to issue from the classical and postquantum roots concurrently. The subscriber will then, transparently and with no configuration change, serve both. As in Section 9.1, newer relying parties can then remove the classical roots, while older relying parties continue to function.¶

This same procedure may also be used to transition between newer, more size-efficient signature algorithms, as they are developed.¶

[[TODO: There's one missing piece, which is that some servers may attempt to parse the signature algorithms out of the certificate chain. See https://github.com/davidben/tls-trust-expressions/issues/9 ]]¶

9.5. Intermediate Elision

Today, root CAs typically issue shorter-lived intermediate certificates which, in turn, issue end-entity certificates. The long-lived root key is less exposed to attack, while the short-lived intermediate key can be more easily replaced without changes to relying parties.¶

This operational improvement comes at a bandwidth cost: the TLS handshake includes an extra certificate, which includes a public key, signature, and X.509 metadata. An average X.509 name in the Chrome Root Store [CHROME-ROOTS] or Mozilla CA Certificate Program [MOZILLA-ROOTS] is around 100 bytes alone. Post-quantum signature algorithms will dramatically shift this tradeoff. Dilithium3 [Dilithium], for example, has a total public key and signature size of 5,245 bytes.¶

[I-D.ietf-tls-cert-abridge] proposes to predistribute known intermediate certificates to relying parties, as a compression scheme. A multi-certificate deployment model provides another way to achieve this effect. To relying parties, a predistributed intermediate certificate is functionally equivalent to a root certificate. PKIs use intermediate certificates because changing root certificates requires updating relying parties, but predistributed intermediates already presume updated relying parties.¶

A CA operator could provide subscribers with two certification paths: a longer path ending at a long-lived trust anchor and shorter path the other ending at a short-lived, revocable root. Relying parties would be configured to trust both the long-lived root and the most recent short-lived root. The negotiation mechanism in Section 6 would then send the shorter path to up-to-date relying parties, and the longer path to older relying parties.¶

This achieves the same effect with a more general-purpose multi-certificate mechanism. It is also more flexible, as the two paths need not be related. For example, root CA public keys are not distributed in each TLS connection, so a post-quantum signature algorithm that optimizes for signature size may be preferable. In this model, both the long-lived and short-lived roots may use such an algorithm. In a compression-based model, the same intermediate must optimize both its compressed and uncompressed size, so such an algorithm may not be suitable.¶

9.6. Conflicting Relying Party Requirements

A subscriber may need to support relying parties with different requirements. For example, in contexts where online revocation checks are expensive, unreliable, or privacy-sensitive, user security is best served by short-lived certificates. In other contexts, long-lived certificates may be more appropriate for, e.g., systems that are offline for long periods of time or have unreliable clocks.¶

A single-certificate deployment model forces subscribers to find a single certificate that meets all requirements. User security then suffers in all contexts, as the PKI may not quite meet anyone's needs. In a multi-certificate deployment model, different contexts may use different trust anchors. A subscriber that supports multiple contexts would provision certificates for each, with certificate negotiation logic directing the right one to each relying party.¶

9.7. Backup Certificates

A subscriber may obtain certificate paths from multiple CAs for redundancy in the face of future CA compromises. If one CA is compromised and removed from newer relying parties, the TLS server software will transparently serve the other one.¶

To support this, TLS serving software SHOULD permit users to configure multiple ACME endpoints and select from the union of the certificate paths returned by each ACME server.¶

12.1. TLS ExtensionType Updates

IANA is requested to create the following entry in the TLS ExtensionType Values registry, defined by [RFC8446]:¶

12.2. Media Type Updates

IANA is requested to create the following entry in the "Media Types" registry, defined in [RFC6838]:¶

Type name:

application¶

Subtype name:

pem-certificate-chain-with-properties¶

Required parameters:

None¶

Optional parameters:

None¶

Encoding considerations:

7bit¶

Security considerations:

Carries a cryptographic certificate and its associated certificate chain and additional properties. This media type carries no active content.¶

Interoperability considerations:

None¶

Published specification:

[this-RFC, Section 5.3]¶

Applications that use this media type:

ACME clients and servers, HTTP servers, other applications that need to be configured with a certificate chain¶

Additional information:

Deprecated alias names for this type:

n/a¶

Magic number(s):

n/a¶

File extension(s):

.pem¶

Macintosh file type code(s):

n/a¶

Person & email address to contact for further information:

See Authors' Addresses section.¶

Intended usage:

COMMON¶

Restrictions on usage:

n/a¶

Author:

See Authors' Addresses section.¶

Change controller:

IETF¶

12.3. ACME Order Object Fields Updates

IANA is requested to create the following entry in the ACME Order Object Fields registry, defined by [RFC8555]:¶

12.4. CertificatePropertyType Registry

[[TODO: Establish a CertificatePropertyType registry.]]¶