Re: [TLS] Merkle Tree Certificates

[David Benjamin <[e-mail]>]

Hi Panos,

> - Previously, in the ICA suppression draft you had correctly brought up
the challenge of keeping an up-to-date ICA cache while most browsers are
not up to date. The Merkle tree mechanism requires constant updates. Would
that be even more of challenge with browsers that have not been updated?

I think you misunderstood my comments on the ICA suppression draft. :-)
Most browsers can be kept mostly up-to-date, and I agree that is an
opportunity to reduce sizes for most connections, including addressing ICAs.

The key word here is "most". The challenge isn't keeping most RPs
up-to-date, but addressing the remaining out-of-date RPs. My feedback was
on how the draft handled this. It uses something time-based and makes
implicit assumptions about the structure of the PKI. This document instead
tries to have a more robust negotiation scheme. I also think this is better
thought of as a trust agility problem, and it's a missed opportunity to not
address that. More on this below.

I also agree with [0]. X.509 has grown to be a pretty poor fit for TLS and
HTTPS, and led to a slew of complexity, deployment problems, and security
problems. The PQ transition, and things we do motivated by PQ's unique
constraints, are a good place to rethink what parts of X.509 do and don't
still make sense. This draft doesn't directly address this---it's not, on
its own, a replacement and can coexist either X.509 or a non-X.509
mechanism---but I think the certificate negotiation and deployment ideas
are worth exploring for that space.

[0] https://mailarchive.ietf.org/arch/msg/pqc/Q8GDQPTsmhOIblYECcaEMIwRhP0/

> - To make this work for WebPKI, would the Transparency Service need to
fetch from all WebPKI issuing CAs and update them every hour?

Almost. This document describes a new kind of CA. X.509 CAs and Merkle Tree
CAs are distinct roles, though having some entities operate both kinds of
CAs would be a natural deployment strategy. So, to clarify, yes, the TS
would need to fetch from all trusted Merkle Tree CAs every hour. It would
not need to fetch from CAs for other mechanisms, such as existing X.509 CAs.

> - CAs would also need to publish their Merkle tree logs similarly to CT,
right?

Merkle Tree CAs would need to publish some state described in sections 5.2
and 8. This document doesn't affect existing X.509 CAs. The new state is
similar to CT in that it is a Merkle Tree and aims to provide a
transparency property. It differs from CT in that:

- Rather than appending to a single tree, with consistency proofs, each
batch forms an independent tree. The tradeoffs we make reduce the number of
valid trees enough that there's no need to link them together into a larger
structure to optimize consistency checks.
- CT logs attest that something was logged. By putting an assertion in a
tree and signing the root, Merkle Tree CAs are certifying the assertions
themselves.
- CT logs are operated separately from X.509 CAs. In this design, the
Merkle Tree CA logs its own assertions, and the TS is just a mirror of this
state.
- CT logs are trusted to maintain transparency, which results in some tight
availability requirements. This document moves the availability
requirements to the TS. The TS can (and we expect often will) be operated
by the RP. So while the CA must publish everything it certifies in a
particular format, we don't need to impose those same availability
requirements. Transparency isn't compromised by CA outage, though issuance
may be interrupted.

> - To me this draft eliminates the need for a PKI and basically makes the
structure flat. Each CA issues certs in the form of a batched tree. Relying
parties that “trust and are aware” of this issuing CA’s tree can verify the
signed window structure and then trust it. So in a TLS handshake we would
have (1 subscriber public key + 2 signatures + some relatively small tree
structure) compared to (1 signature + (3 sigs + 1 public key) for server
cert + (1 Sig + 1 Public key) per ICA cert in the chain). If we borrowed
the same flat PKI logic though and started “trusting” on a per issuer CA
basis then the comparison becomes (1 public key + 2 signatures + some small
tree structure) vs (1 public key + 4 sigs). So we are saving 2 PQ sig minus
the small tree structure size . Am I misunderstanding the premise here?

I don't think that's quite right. First, I'll correct your math slightly. I
assume by "tree structure", you mean the inclusion proof? There are no
signatures involved in that. This document removes all signatures in the
Certificate message and replaces it with this inclusion proof. It leaves
the CertificateVerify signature, which is mostly orthogonal to the PKI
 strategy. (E.g. KEMTLS is one proposal in that space.) So, with a
signature-based TLS key, it's 1 subscriber public key + 1 signature + 1
Merkle Tree inclusion proof. There are no signatures from the CA at all
because the RP already trusts the tree head out-of-band.

Compared to a single intermediate, two SCTs, and no OCSP response, we're
saving 4 PQ sigs and a PQ public key, minus an inclusion proof. Compared to
a chain with two SCTs, no intermediate (but more on this in a bit), and no
OCSP response, it's 3 PQ sigs minus an inclusion proof. The key is that
inclusion proofs can replace both CA signatures *and* SCTs, but applying to
more limited situations. (Roughly the RP had to be updated sometime after
your certificate was issued.)

> To me this draft eliminates the need for a PKI and basically makes the
structure flat. [...] If we borrowed the same flat PKI logic though and
started “trusting” on a per issuer CA basis [...]

I don't think that's the right characterization. This draft doesn't
eliminate the need for delegation overall. Rather, it observes that
delegation is not *always* necessary.

X.509 ICAs provide delegation and constraints. We're trading proof size
against some deployment goals. Without changing the RP, ICAs delegate trust
to another key. If operated by another entity, this might be to add trust
to someone else. If operated by the same entity, this might be to add
constraints, e.g. a shorter lifetime. ICAs allow root keys to be kept
offline while cycling through shorter-lived online keys that perform the
actual issuance.

To eliminate that need and use a flat PKI, we have to address the
underlying need: doing this without RP changes. Now, for *up-to-date* RPs,
ICAs are less important. You may as well have told the RP about the
delegated CA at update time. That's why this draft doesn't use a delegation
mechanism. We're not saying delegation mechanisms are unnecessary. We're
saying they're unnecessary *within the scope of this scheme*, where we
already assume unupdated RPs will negotiate something else. But those RPs
still exist. The problem is the Web PKI, and many other TLS ecosystems,
typically use a single certificate for all RPs. That cert must target the
lowest common denominator: an unupdated RP.

So I think trying to make the PKI structure flat, or "ICA suppression", is
intrinsically tied to breaking through that barrier. I think we should do
that. It gives us much more room to apply different tradeoffs for different
situations. Once we do, an ICA cache is equivalent to some clients trusting
the ICAs directly, constraints and all. And so this is really about
selecting between a long-lived CA with larger proofs, and a short-lived CA
with shorter proofs.

All these solutions can even coexist. You might imagine three layers: If
there's a match on a Merkle Tree trust anchor, send that proof. If the
short-lived trust anchor matches, use that ("ICA suppression"). Then try
the long-lived one. And then probably, for the latter two, somehow thread
in an SCT selection story because we're also in a "one size fits all" world
for SCTs, and sending lots of SCTs will no longer be free.

(Of course, if the first two become sufficiently close in size and
applicability, then we don't need both. I won't be sad to have fewer
mechanisms! Though, per above, you've undercounted the gap by a PQ
signature.)

Whatever the options, I'm interested in fitting into common negotiation
mechanisms where possible. The document describes a deployment model where
the ACME server picks a collection of proofs, and the subscribers just
opaquely evaluate the negotiation mechanism. Done right, and combined with
automated issuance, I think this would be a compelling agility story. There
are fewer ACME servers than subscribers, and the ACME server is in a
position to keep up with evolving RP trust requirements and optimizations.

But now we're getting into a large and unwieldy design space, so we've
started with the ideas in this draft. It's self-contained, can stand alone,
has some interesting transparency properties, and is a nice, concrete
illustration of the agility and negotiation ideas.

David

On Tue, Mar 14, 2023 at 9:39 AM Kampanakis, Panos <[e-mail]> wrote:

> Hi David,
>
>
>
> Interesting idea. Seems like a radical, hard change but I want to
> understand it better. Some clarifications:
>
>
>
> - Previously, in the ICA suppression draft you had correctly brought up
> the challenge of keeping an up-to-date ICA cache while most browsers are
> not up to date. The Merkle tree mechanism requires constant updates. Would
> that be even more of challenge with browsers that have not been updated?
>
>
>
> - To make this work for WebPKI, would the Transparency Service need to
> fetch from all WebPKI issuing CAs and update them every hour?
>
>
>
> - CAs would also need to publish their Merkle tree logs similarly to CT,
> right?
>
>
>
> - Negotiating a new CertType would be a fingerprint as you say in Section
> 12. The size in the response is also a fingerprint for the Subscriber. It
> is not a huge concern for me personally especially if this got wide
> adoption, but it was brought up before in similar contexts.
>
>
>
> - To me this draft eliminates the need for a PKI and basically makes the
> structure flat. Each CA issues certs in the form of a batched tree. Relying
> parties that “trust and are aware” of this issuing CA’s tree can verify the
> signed window structure and then trust it. So in a TLS handshake we would
> have (1 subscriber public key + 2 signatures + some relatively small tree
> structure) compared to (1 signature + (3 sigs + 1 public key) for server
> cert + (1 Sig + 1 Public key) per ICA cert in the chain). If we borrowed
> the same flat PKI logic though and started “trusting” on a per issuer CA
> basis then the comparison becomes (1 public key + 2 signatures + some small
> tree structure) vs (1 public key + 4 sigs). So we are saving 2 PQ sig minus
> the small tree structure size . Am I misunderstanding the premise here?
>
>
>
>
>
>
>
> *From:* TLS <[e-mail]> *On Behalf Of * David Benjamin
> *Sent:* Friday, March 10, 2023 5:09 PM
> *To:* <[e-mail]> <[e-mail]>
> *Cc:* Devon O'Brien <[e-mail]>
> *Subject:* [EXTERNAL] [TLS] Merkle Tree Certificates
>
>
>
> *CAUTION*: This email originated from outside of the organization. Do not
> click links or open attachments unless you can confirm the sender and know
> the content is safe.
>
>
>
> Hi all,
>
> I've just uploaded a draft, below, describing several ideas we've been
> mulling over regarding certificates in TLS. This is a draft-00 with a lot
> of moving parts, so think of it as the first pass at some of ideas that we
> think fit well together, rather than a concrete, fully-baked system.
>
> The document describes a new certificate format based on Merkle Trees,
> which aims to mitigate the many signatures we send today, particularly in
> applications that use Certificate Transparency, and as post-quantum
> signature schemes get large. Four signatures (two SCTs, two X.509
> signatures) and an intermediate CA's public key gets rather large,
> particularly with something like Dilithium3's 3,293-byte signatures. This
> format uses a single Merkle Tree inclusion proof, which we estimate at
> roughly 600 bytes. (Note that this proposal targets certificate-related
> signatures but not the TLS handshake signature.)
>
> As part of this, it also includes an extensibility and certificate
> negotiation story that we hope will be useful beyond this particular scheme.
>
> This isn't meant to replace existing PKI mechanisms. Rather, it's an
> optional optimization for connections that are able to use it. Where they
> aren't, you negotiate another certificate. I work on a web browser, so this
> has browsers and HTTPS over TLS in mind, but we hope it, or some ideas in
> it, will be more broadly useful.
>
> That said, we don't expect it's for everyone, and that's fine! With a
> robust negotiation story, we don't have to limit ourselves to a single
> answer for all cases at once. Even within browsers and the web, it cannot
> handle all cases, so we're thinking of this as one of several sorts of PKI
> mechanisms that might be selected via negotiation.
>
> Thoughts? We're very eager to get feedback on this.
>
> David
>
>
>
> On Fri, Mar 10, 2023 at 4:38 PM <[e-mail]> wrote:
>
>
> A new version of I-D, draft-davidben-tls-merkle-tree-certs-00.txt
> has been successfully submitted by David Benjamin and posted to the
> IETF repository.
>
> Name:           draft-davidben-tls-merkle-tree-certs
> Revision:       00
> Title:          Merkle Tree Certificates for TLS
> Document date:  2023-03-10
> Group:          Individual Submission
> Pages:          45
> URL:
> https://www.ietf.org/archive/id/draft-davidben-tls-merkle-tree-certs-00.txt
> Status:
> https://datatracker.ietf.org/doc/draft-davidben-tls-merkle-tree-certs/
> Html:
> https://www.ietf.org/archive/id/draft-davidben-tls-merkle-tree-certs-00.html
> Htmlized:
> https://datatracker.ietf.org/doc/html/draft-davidben-tls-merkle-tree-certs
>
>
> Abstract:
>    This document describes Merkle Tree certificates, a new certificate
>    type for use with TLS.  A relying party that regularly fetches
>    information from a transparency service 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.
>
>
>
>
> The IETF Secretariat
>
>