Re: [TLS] Merkle Tree Certificates
On Wed, Mar 22, 2023 at 11:22 AM Ilari Liusvaara wrote: > On Wed, Mar 22, 2023 at 01:54:22PM +0100, Bas Westerbaan wrote: > > > > > > Unpopular pages are much more likely to deploy a solution that > > > doesn't require a parallel CA infrastructure and a cryptographer > > > on staff. > > I don't think the server-side deployment difficulties with this have > anything to do with parallel CA infrastructure or admins having to > understand cryptography. > > > > CAs, TLS libraries, certbot, and browsers would need to make changes, > > but I think we can deploy this without webservers or relying parties > > having to make any changes if they're already using an ACME client > > except upgrading their dependencies, which they would need to do > > anyway to get plain X.509 PQ certs. > > I don't agree. > > I think deploying this is much much harder than deploying X.509 PQ > certificates. X.509 PQ certificates are mostly dependency update. This > looks to require some nontrivial configuration work that can not be > done completely automatically. > > And then in present form, this could be extremely painful for ACME > clients to implement (on level of complete rewrite for many). > It’s true that this would require code changes in more components. But TLS, ACME, etc., are deployed many more times than they are implemented. As the code changes happen per software package, hopefully the per-deployment cost beyond that can be minimal. (Though, of course, that will depend on exactly how each package's existing configuration interface looks, and how/whether they apply it to the new thing. Understanding what protocol properties would make this easy or hard would be very useful, but I also suspect it depends on a lot of details we've still left as placeholders right now.) These things also don’t have to happen all at once. It can be a transition over time, or perhaps some sites just stay with the fast-issuance mechanism (be it X.509 PQ or something else) if they’re happy with it. Merkle Tree Certificates themselves cannot be your only certificate type anyway, since they only work with up-to-date RPs. To ACME specifically, we definitely don’t want it to be painful for ACME clients to implement! It’s probably a bit hard to discuss that in the abstract, with our ACME section being just a placeholder. Perhaps, when we’ve gotten an initial draft of that, we can figure out which bits we got wrong and iterate on that? David ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Merkle Tree Certificates
Thanks for such detailed feedback! Responses inline. On Wed, Mar 22, 2023 at 12:49 PM Ilari Liusvaara 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? > - I don't think there are any sane uses for >64kB claims, so the > claim_info length could be shortened to 16 bits. > Works for me. https://github.com/davidben/merkle-tree-certs/pull/29 > 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. > - 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 > - What does it mean that in this document the hash is always SHA-256? > Just that the hash function used in building the trees, etc. is SHA-256. (It’s the only ProofType we’ve defined. One could define others, but I don’t particularly care to.) > - Apparently issuer id is limited to 32 octets. This could be noted in > the definition. > Also added to https://github.com/davidben/merkle-tree-certs/pull/29 > - 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. > - 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 > - I think LabeledWindow should add 64 spaces in front, so it > reuses the TLS 1.3 signature format. > > This reduces risks of cross-protocol attack if the key gets > reused anyway (despite there being MUST NOT requirement). > Filed https://github.com/davidben/merkle-tree-certs/issues/30. I’m slightly torn on this. The part of me that doesn’t trust people to keep keys separate wants to do it. But the part of me that’s sick of chasing this down in every new protocol would rather we just stop pretending using the same key for multiple things is remotely sensible. :-) > - 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
Re: [TLS] Merkle Tree Certificates
On Tue, Mar 14, 2023 at 1:47 PM Watson Ladd wrote: > Come embrace the temptations of the Sea-SIDH! > > Intermediate certs are rarely used, so that would achieve 204 byte sig > on intermediate+ 64 byte intermediate key + 204 byte sig of EE cert > since the signing time doesn't matter. Then with SCT and OCSP, it's > 204 bytes each. > I wasn’t able to find a reference to a Sea-SIDH signature scheme. Do you have a pointer? Do you mean this thing? https://eprint.iacr.org/2020/1240.pdf Taking 2 seconds to generate a signature is... certainly a constraint. :-) > As for the actual proposal, I like the idea of per-protocol subjects. > I am worried about the way this makes the PKI a more distributed > system, in the Lamportian sense. A certificate being used successfully > depends now on the transparency service propagating the batch from the > CA and the CA creating the batch, and the user-agent, not the site, > determines what transparency service is used. This makes it much more > difficult for sites to be sure their certificates will actually work. > To some degree, subscribers already rely on this. RPs have various requirements, and it is up to the CA to provide subscribers with certificates that meet the requirements. Some requirements can be checked by the subscriber, but some cannot. In X.509, the certificate chain and signatures can be checked by the subscriber. (Although X.509 is so complex and variable that it’s unlikely the subscriber’s checks exactly matched the RP’s!) But other requirements, notably future policy actions, cannot. The certificate may later be revoked, the CA or CT log may be distrusted, etc. In this proposal, we could have the CA pass the subscriber the signed window alongside the proof (not currently in the draft, but this is a good reason to include it). The subscriber can then check the inclusion proof, hopefully with much less implementation variability than X.509. The subscriber still needs to know if the RP recognizes that batch. These are more dynamic than X.509 roots, but are covered by the negotiation mechanism. On mismatch, you just pick another certificate, such as an X.509 one which is as checkable as before. So this part isn’t so much checked as made moot. (A negotiation mechanism is ultimately “tell me if the RP will accept this cert, so I can filter down to the ones that work”.) Finally, subscriber and RP must agree on what, e.g, root hash #42 was. This flows from CA to TS to RP, which is indeed hard for the subscriber to directly check. (Though the subscriber could always fetch hashes from known TSs to compare.) However, a mismatch here means the CA produced a split view. The responsibilities have shifted, but analogous misbehavior in X.509 + CT would typically result in a policy action, something the subscriber already cannot check offline. David ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Merkle Tree Certificates
Hi all, Sorry for the late reply on all these, and thanks for the feedback so far! I lost track of this thread as I was putting together slides for IETF 116 and whatnot. I’ll reply to various outstanding emails individually... On Sat, Mar 11, 2023 at 2:43 PM Stephen Farrell wrote: > > Hiya, > > I had a read and think this is a great topic for > discussion. > > A few points: > > - I think we'd benefit from trying to think through > the dynamics of this, e.g. how many of each entity > might we see and how'd that differ from the current > web PKI and possibly affect the web? (It's fine that > that analysis emerge in time, not asking for it now.) > Yup. I think how deployments end up looking will definitely be interesting to figure out. As you say, how this shakes out will emerge in time, but sections 9 and 11 contain some initial thoughts. One thing I think we could have conveyed more clearly is the relationship between an overall certificate negotiation framework and this draft. We’re interested in certificate negotiation because we think it’s a good fit for a host of problems in the PKI, particularly around agility. Notable for this draft is it gives more room to explore the tradeoff space, since we can deploy different solutions for different requirements. Merkle Tree Certificates represent one point in the tradeoff space. We started with this draft because it was fairly self-contained. I’m hoping we’ll have a more refined and concrete negotiation write-up next, which might make some of this clearer. (What’s in there now is somewhat of a placeholder.) > - I do think the trust_anchors extension values might > be better off as e.g. truncated hashes of public keys > or something like that. > That doesn’t quite fit with some directions we’re envisioning, but I agree having the IDs specified tightly would be nice. How about we put a pin in this, and when we’ve got the write-up above ready, we can ponder this? > - Aside from better on-the-wire efficiency, I think > another reason to examine designs like this is that > adding multiple public keys and signatures to x.509 > certs (one of the alternative designs) seems like it > might be a bit of a nightmare, as PKI libraries are > buggily updated to try handle that - designs like > this seem better in terms of keeping the new code in > a less risky place. > > Cheers, > S. > > On 10/03/2023 22:09, 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 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: > >
