Re: [TLS] Merkle Tree Certificates

[Ilari Liusvaara <[e-mail]>]

On Mon, Jun 05, 2023 at 03:35:17PM -0400, David Benjamin wrote:
> Thanks for such detailed feedback! Responses inline.
> 
> On Wed, Mar 22, 2023 at 12:49 PM Ilari Liusvaara <[e-mail]>
> wrote:
> 
> > Some quick comments / ideas:
> >
> > - I think it would be easier for subscribers to get inclusion proofs
> >   from transparency service than certificate authority.
> >
> >   This is because issuance is heavily asynchronous, whereas most
> >   servers assume ACME is essentially synchronous.
> >
> >   If certificates are canonicalized (this is mostly matter of ensuring
> >   the names are always sorted), this could be endpoint to download known
> >   inclusion proofs by certificate hash.
> >
> >   Or maybe even have both, and subscribers can use whichever is more
> >   convinient.
> >
> 
> We’re currently envisioning that the transparency services will potentially
> vary by RP. They’re effectively the RP’s CT policy. The different TSs all
> see the same trees, just later than the CA. It seems simpler then to get it
> from the CA, which will be the least behind. This also means RPs can adjust
> TS preferences without impacting subscribers or CAs at all. The equivalent
> of a CT log migration and distrust is much less invasive.
> 
> Also, subscribers already talk to CAs via, e.g., ACME, so it seemed natural
> to rely on that existing relationship. Especially as subscribers will need
> a fallback credential from a CA anyway.
> 
> I suppose there’s no reason why the subscriber couldn’t fetch from the TS.
> Though I’m not seeing how it would be more convenient. Could you elaborate?

Well, maybe that was a bit X-Y.

What I am really after is some mechanism of downloading certificates
outside ACME, because the issuance wait is likely prohibitive for many
ACME clients.
 

> >   I don't see rule for how claims are sorted within each type,
> >   only how different types are sorted.
> >
> > - If each claim was in its own Claim, then one could maybe even
> >   shorten it to 8 bits. Similarly, one could merge ipv4/ipv6 and
> >   dns/dns_wildcard.
> >
> >   This could also simplify sorting: Sort by type, lexicographic
> >   sort by claim contents.
> >
> 
> Thanks! Yeah, the actual Claim bits were just a naive transcription of
> X.509 SANs for now without much thought. I filed
> https://github.com/davidben/merkle-tree-certs/issues/31 to track those.

One use of strict canonical encoding would be to let the subscriber
compute the certificate body itself. E.g., so it could look up the
certificates by body hash.


> > - I don't think anybody is going to use signatures with >64kB keys,
> >   so subject_info length could be shortened to 16 bits.
> >
> 
> Added to https://github.com/davidben/merkle-tree-certs/pull/29

As a note about signature sizes, TLS (1.2 and 1.3) have 64kB signature
limit. IIRC, in NISTPQC outside the "interesting" stuff, only PICNIC
had trouble with that. However, when it comes to PQC stuff, IIRC there
is second call for proposals going on right now.

> 
> > - I think it would be easier if lifetime was expressed in batch
> >   durations. Then one would not need window size, and especially not
> >   handle lifetime / batch_duration not being an integer!
> >
> 
> I think we’d still need to be able measure it in both units, but maybe I’m
> missing something?
> 
> We need something in units of batch duration (currently window size) to
> size the signed windows, etc.
> 
> But the RP can’t just use the window in lieu of expiry, because it can’t
> simply assume all batches are valid, because the RP may be unable to fetch
> new windows for a long period of time, such that the old (or all!) batches
> have fallen off.
> 
> We could do that calculation in batch durations, but then we need to
> measure the current time in batch numbers, which seemed unintuitive to me.
> And then once that was in seconds, it didn’t seem that aligning it on batch
> duration did much.

Well, actually doesn't look like things get too annoying if lifetime /
batch_duration is not an integer:

- window size can be just the ceiling of that.
- RPs can calculate explicit expiry via t = t_0 + p * t_p + t_l.

Neither of which needs floating-point (which one definitely does not
want to use here).


> > - The root hash being dependent on issuer and batch number iff there
> >   are multiple assertions looks very odd.
> >
> >   Empty assertion list might be special. But this also happens for
> >   one assertion.
> >
> 
> Thanks! That’s indeed inconsistent, we’ll fix it.
> https://github.com/davidben/merkle-tree-certs/issues/32

Hmm... Looking at that construct, why is the pad there? And why are
index and level after pad instead of before?

And there does not seem to be any way to salt the hash. WebPKI requires
what effectively amounts to salting the hash via serial number (even
for SHA-256).

 
> > - Is there reason for type of trust_anchor_data to vary by proof_type?
> >   Why not always have MerkleTreeTrustAnchor there?
> >
> 
> The thinking was to be extensible for other proof types that may not have
> the (issuer, number) structure. E.g. perhaps a fast-issuance model that’s
> more analogous to X.509 with CT, if we get a meaningful enough improvement?
> 
> This isn’t strictly necessary. We could simply lift ProofType into
> CertificateType and use the existing extension point. That would be simpler
> in a lot of ways. But we thought this idea was interesting and wanted to
> explore it.
> 
> Specifically, the subscriber doesn’t actually need to know anything about
> the Proof contents. It only needs to know the Assertion (which identity am
> I using?), and how to match TrustAnchors against the ClientHello or
> CertificateRequest (which opaque proof will make the peer believe my
> assertion?). This means, by making the right things opaque and with the
> right deployment model, we could introduce new proof types without having
> to update subscribers! There are far more subscribers than CAs, so this
> could be attractive for agility.
 
That is not quite the only things that subscriber needs to know. It must
also be able to calculate expiry (either directly or via oldest batch),
for which it also must know the batch number, CA epoch, batch duration
and lifetime.

 
> > - And proof_data length field should probably be 16 bits. I don't think
> >   proof_data will ever exceed 8kB.
> >
> 
> 8KiB might be tight for some signature-based ProofTypes if we reuse the
> same structure (see above), but hopefully 64KiB is plenty?
> 
> I've put that in https://github.com/davidben/merkle-tree-certs/pull/29 too.

That was bit unclear, I was not suggesting 8kB limit. Just that 64kB
should be more than enough given expected proof sizes.
 

> > - For type-independent expiry info to be helpful, this must be somehow
> >   plumbed to the TLS server.
> >
> 
> Yup! That is in the next batch of ideas we want to write up. :-)

... Plumbing new stuff around is always fun when modifying systems. :-)
 

> > - Even if ACME itself allows for long processing delays, many (most?)
> >   ACME clients do not.
> >
> > - Multiple orders from single newOrder or multiple certificates in
> >   single order sounds like it would break assumption made in ACME
> >   rather badly, and thus recipe for trouble.
> >
> 
> This is a new format and all, and we already have to update things for PQ
> once, so we’re assuming we can require one update to ACME clients to
> implement whatever extension we define. (Existing ACME clients will just
> continue to request X.509 certificates from their existing endpoints.)

The problem is not requiring update. It is requiring update what will
play absolute hell with architecture of ACME client.

I have written an ACME client, and I can say that implementing this in
that will require a complete rewrite. 

Hence wanting a mechanism that lets certificate to be downloaded via
non-ACME mechanism, even if certificate order is made via ACME. Then
the ACME client could just abandon order after submitting request and
not have to wait for it.


> Of course, to get to that one update, any such extension will definitely
> need to slot in nicely with ACME’s existing model. We’re aiming to write
> something up as an initial proposal, but I'm not an ACME expert, so this is
> especially a place where feedback is welcome! I'm sure it will take
> multiple iterations before we get it right. :-)

AFAIK, the way ACME is meant to work is that each newOrder creates one
order, and each order ends up with only one certificate.

One problem with this is that is that if one wants multiple certificates
for same set of identifiers, one must first submit the previous request
first (since ACME servers may reuse orders, which is actually required
to paper over a race condition in ACME protocol).

 
> > - Isn't cert_type deprecated?
> >
> 
> Is it? We weren’t planning on using it anyway (server_certificate_type is
> just better), but I didn't find the document that deprecated it.

There is no explicit document deprecating it.

However, AFAICT, it is implicitly deprecated by RFC 8446 (which can
be interpretted to contain an explicit list of every allowed extension
(that existed back then)).


> 
> > - I think the uniform certificate format is already a requirement in
> >   TLS 1.3. And OpenPGP format is banned in TLS 1.3 anyway. So parsing
> >   to extension blocks without knowing certificate type is no problem.
> >
> 
> Ah, that makes using CertificateEntry extensions more attractive, though
> the processing order is a bit messy. I wasn’t able to find the requirement
> you mention though. Do you have a pointer?

The OpenPGP ban is in RFC 8446 section 4.4.2.

Well, there might not actually be an explicit requirement. However, every
certificate type allowed in TLS 1.3 so far follows the same format.

I think technically only allowing types that do follow the format would
work?




-Ilari