Re: [TLS] Merkle Tree Certificates

[David Benjamin <[e-mail]>]

On Tue, Mar 21, 2023 at 8:01 AM Hubert Kario <[e-mail]> wrote:

> On Monday, 20 March 2023 19:54:24 CET, David Benjamin wrote:
> > I don't think flattening is the right way to look at it. See my
> > other reply for a discussion about flattening, and how this does
> > a bit more than that. (It also handles SCTs.)
> >
> > As for RFC 7924, in this context you should think of it as a
> > funny kind of TLS resumption. In clients that talk to many
> > servers[0], the only plausible source of cached information is a
> > previous TLS exchange. Cached info is then: if I previously
> > connected to you and I am willing to correlate that previous
> > connection to this new one, we can re-connect more efficiently.
> > It's a bit more flexible than resumption---it doesn't replace
> > authentication, so we could conceivably use larger lifetimes.
> > But it's broadly the same w.r.t. when it can be used. It doesn't
> > help the first connection to a service, or a service that was
> > connected long enough ago that it's fallen off the cache. And it
> > doesn't help across contexts where we don't want correlation.
> > Within a web browser, things are a bit more partitioned these
> > days,
> > see
> https://github.com/MattMenke2/Explainer---Partition-Network-State/blob/main/README.md
> > and https://github.com/privacycg/storage-partitioning.
>
> Sorry, but as long as the browsers are willing to perform session
> resumption
> I'm not buying the "cached info is a privacy problem".
>

I'm not seeing where this quote comes from. I said it had analogous
properties to resumption, not that it was a privacy problem in the absolute.

The privacy properties of resumption and cached info on the situation. If
you were okay correlating the two connections, both are okay in this
regard. If not, then no. rfc8446bis discusses this:
https://tlswg.org/tls13-spec/draft-ietf-tls-rfc8446bis.html#appendix-C.4

In browsers, the correlation boundaries (across *all* state, not just TLS)
were once browsing-profile-wide, but they're shifting to this notion of
"site". I won't bore the list with the web's security model, but roughly
the domain part of the top-level (not the same as destination!) URL. See
the links above for details.

That equally impacts resumption and any hypothetical deployment of cached
info. So, yes, within those same bounds, a browser could deploy cached
info. Whether it's useful depends on whether there are many cases where
resumption wouldn't work, but cached info would. (E.g. because resumption
has different security properties than cached info.)


> It also completely ignores the encrypted client hello
>

ECH helps with outside observers correlating your connections, but it
doesn't do anything about the server correlating connections. In the
context of correlation boundaries within a web browser, we care about the
latter too.


> Browser doesn't have to cache the certs since the beginning of time to be
> of benefit, a few hours or even just current boot would be enough:
>
> 1. if it's a page visited once then all the tracking cookies and javascript
>    will be an order of magnitude larger download anyway
> 2. if it's a page visited many times, then optimising for the subsequent
>    connections is of higher benefit anyway
>

I don't think that's quite the right dichotomy. There are plenty of reasons
to optimize for the first connection, time to first bytes, etc. Indeed,
this WG did just that with False Start and TLS 1.3 itself. (Prior to those,
TLS 1.2 was 2-RTT for the first connection and 1-RTT for resumption.)

I suspect a caching for a few hours would not justify cached info because
you may as well use resumption at that point.

> In comparison, this design doesn't depend on this sort of
> > per-destination state and can apply to the first time you talk
> > to a server.
>
> it does depend on complex code instead, that effectively duplicates the
> functionality of existing code
>
> > David
> >
> > [0] If you're a client that only talks to one or two servers,
> > you could imagine getting this cached information pushed
> > out-of-band, similar to how this document pushes some valid tree
> > heads out-of-band. But that doesn't apply to most clients,
> > certainly not a web browser.
>
> web browser could get a list of most commonly accessed pages/cert pairs,
> randomised to some degree by addition of not commonly accessed pages to
> hide if
> the connection is new or not, and make inference about previous visits
> worthless
>

True, we could preload cached info for a global list of common
certificates. I'm personally much more interested in mechanisms that
benefit popular and unpopular pages alike.


> > On Tue, Mar 14, 2023 at 9:46 AM Kampanakis, Panos <[e-mail]>
> wrote:
> > Hi Hubert,
> >
> > I am not an author of draft-davidben-tls-merkle-tree-certs, but
> > I had some feedback on this question:
> >
> > RFC7924 was a good idea but I don’t think it got deployed. It
> > has the disadvantage that it allows for connection correlation
> > and it is also challenging to demand a client to either know all
> > its possible destination end-entity certs or be able to have a
> > caching mechanism that keeps getting updated. Given these
> > challenges and that CAs are more static and less (~1500 in
> > number) than leaf certs, we have proposed suppressing the ICAs
> > in the chain (draft-kampanakis-tls-scas-latest which replaced
> > draft-thomson-tls-sic ) , but not the server cert.
> >
> > I think draft-davidben-tls-merkle-tree-certs is trying to
> > achieve something similar by introducing a Merkle tree structure
> > for certs signed by a CA. To me it seems to leverage a Merkle
> > tree structure which "batches the public key + identities" the
> > CA issues. Verifiers can just verify the tree and thus assume
> > that the public key of the peer it is talking to is "certified
> > by the tree CA". The way I see it, this construction flattens
> > the PKI structure, and issuing CA's are trusted now instead of a
> > more limited set of roots. This change is not trivial in my
> > eyes, but the end goal is similar, to shrink the amount of auth
> > data.
> >
> >
> >
> > -----Original Message-----
> > From: TLS <[e-mail]> On Behalf Of Hubert Kario
> > Sent: Monday, March 13, 2023 11:08 AM
> > To: David Benjamin <[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.
> >
> >
> >
> > Why not rfc7924?
> >
> > On Friday, 10 March 2023 23:09:10 CET, David Benjamin wrote:
> >> 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-0
> >> 0.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-0
> >> 0.html
> >> Htmlized:
> >>
> >> https://datatracker.ietf.org/doc/html/draft-davidben-tls-merkle-tree-c
> >> erts
> >>
> >>
> >> 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
> >>
> >>
> >>
> >
> > --
> > Regards,
> > Hubert Kario
> > Principal Quality Engineer, RHEL Crypto team
> > Web: www.cz.redhat.com
> > Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic
> >
>
> --
> Regards,
> Hubert Kario
> Principal Quality Engineer, RHEL Crypto team
> Web: www.cz.redhat.com
> Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic
>
>