Re: [TLS] Merkle Tree Certificates

["Kampanakis, Panos" <[e-mail]>]

Thx David. The spirit of the draft is clearer now.

ACK about the miscalculated signature. I was counting the sig in the signed window, but indeed that does not take place with every connection.

I think I understand your point about delegating trust. You basically say that if we could have an accurate picture of all ICAs at the RP we would be doing the same thing already. And the way you address the problem in this draft is by introducing the window within which you can rest assured you have the accurate picture of all certs.

The non-updated RP is an issue that can’t be neglected (your draft addresses it with the time window). Let’s say we assumed RPs are up-to-date, and the ones that are not can retry without assuming an accurate ICA picture. How bad is having a non-updated RP retry? Is the problem keeping a connection state issue as someone had mentioned before?

Another operational question: So this draft would work for ACME issued certs where the client can acquire the tree structure from the Merkle Tree CA which tracks ACME certs. But if you generalized this, wouldn’t that mean that either the RP needs to keep track and negotiate tree roots from multiple Merkle Tree CAs or a central Merkle Tree CA needs to aggregate all kinds of issued certs from CT or somewhere else?

Another random comment: The tree version approach resembles the CA dictionary approach of cTLS. You basically have snapshots of the delegated trust book and if the peer recognizes it then you no longer need to establish trust.


From: David Benjamin <[e-mail]>
Sent: Monday, March 20, 2023 2:43 PM
To: Kampanakis, Panos <[e-mail]>
Cc: <[e-mail]> <[e-mail]>; Devon O'Brien <[e-mail]>
Subject: RE: [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 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]<mailto:[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]<mailto:[e-mail]>> On Behalf Of David Benjamin
Sent: Friday, March 10, 2023 5:09 PM
To: <[e-mail]<mailto:[e-mail]>> <[e-mail]<mailto:[e-mail]>>
Cc: Devon O'Brien <[e-mail]<mailto:[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]<mailto:[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