Multi-proof certificates

[davidben]

(Not a fully-baked idea, just exploring the design space a bit.)

Should we support something like multi-proof certificates? The idea would be that the certificate looks something like:

struct {
    TrustAnchorIdentifier trust_anchor;
    opaque proof_data<0..2^16-1>;
} Proof;

struct {
    Assertion assertion;
    Proof proofs<0..2^16>;
} Certificate;

Then pair with something like https://github.com/davidben/tls-trust-expressions/issues/54 so that the server has a bunch of proofs available and the client can ask for some subset of them.

Things we could model this way:

• Signature-like proofs where you expect multiple independent entities to attest to it
• Something X.509 + CT-like where you have one signature from a domain validating entity and some signatures from logging entities
• MTCs with optional signatures over the tree head when the client isn't up-to-date

This also enables somewhat more compact representations on the subscriber. The assertion will contain a big PQ key and this way you just need the one blob in memory. Or if different clients' requests overlap, you only need to keep one copy of each individual component around.

One subtlety: if one proof depends on another proof, this structure flattens it and loses the information. That would need to be sufficiently encoded into the trust anchor identifiers and/or different credentials that you get a good combination.

[davidben]

Some other subtleties:

• CertificatePropertyList applies to the whole Certificate. The properties get more complicated if they have to correlate with individual proofs
• Different proofs might expire at different times (e.g. MTCs have an upper bound). I'm thinking that, in #83, the expiry should be part of the Proof, with individual proofs being allowed to expire at different times

Other directions:

• Explode the structure in the protocol. First "certificate" in the TLS certificate list is the Assertion, the rest are individual Proofs
• Explode the structure in the subscriber / CA bit. Abandon the assertion size optimization and say you just get a bunch of assertion + single-proof tuples, stitch them back together by looking for matching assertions

[bwesterb]

One subtlety: if one proof depends on another proof, this structure flattens it and loses the information.

Which is the case for https://github.com/davidben/tls-trust-expressions/issues/54. However, we should think about what an analogue would look like when we have MTC in place.

I'd say the CA would create a signed promise that it will include a certain assertion in a future batch. One can then gather cosignatures of witnesses that will check whether the CA indeed will include the assertion is the batch. The promise is akin to the regular certificate today, and the cosignature is like an SCT.

I can't quite make this fit neatly. Format of promise is alright.

struct {
    uint32 batch_number;
    Signature signature;
} SignedPromiseProofData;

Here signature is over

struct {
    TrustAnchorIdentifier anchor; // with batch number
    Assertion assertion;
} Promise;

Promise can use the base TrustAnchorIdentifier of the CA. (One could move the batch_number into the TrustAnchorIdentifier, but would need to allocate a different TrustAnchorIdentifier. I do not think that makes sense as you wouldn't want to negotiate on the promised batch number.)

Negotiation for promises works nicely: servers just need to install the regular MTC proofs with higher preference over the promises.

Format of cosignatures is alright too:

struct {
   TrustAnchorIdentifier anchor; // CA that made the promise including batch number
   Signature cosignature;
} WitnessProofData;

cosignature is over Promise as before.

The difficulty is the negotiation. The client trusts certain witnesses and certain CAs. It wants, say, three cosignatures of trusted witnesses on the same promise. If we use a single TAI for the witness, then the negotiation of https://github.com/davidben/tls-trust-expressions/issues/54 is unsatisfactory in two ways: 1. it could return three cosignatures on promises of different CAs and ; 2. it could return cosignatures on promises of an untrusted CA.

Instead of a global TAI, we could assign a separate TAI for the combination of witness and CA. (Say, simply witness-TAI.ca-TAI.) That solves the second problem, but not the first.

[davidben]

Instead of a global TAI, we could assign a separate TAI for the combination of witness and CA.

Yeah, I've been assuming that they'd be paired up like that.

That solves the second problem, but not the first.

Hmm. I'm assuming the client knows the details of its policy and how they translate to TAIs, so it can request a collection of things that works correctly, given the server list in DNS or EncryptedExtensions. I.e. the server-offer, client-select flow is nice in that the client policy can be somewhat arbitrarily complicated and we don't need to express it on the wire.

But it's true that, when, the selection isn't flipped, then things get tricky. The client may not be able to fully express its policy, and then the server might not quite do the right thing, since the server does not have knowledge of all these details.

(Cllllearly we need to allow the client to express an arbitrary boolean expression. 😉 We could call it... "trust expressions", except that name is already taken.)

Yeah, I dunno. I suspect there's more iterating on this idea to do here. Life is very easy when we flip to server-offer / client-select, but I don't know how strongly we can bank on that since the DNS stuff is so early.

(For completeness, the trust expressions version of this would probably have required the multi-proof policy get backed into the trust store name itself, and then the CA would provision pre-assembled proof lists, which is a lot less flexible than assembling the proof lists on the fly.)

[bwesterb]

But it's true that, when, the selection isn't flipped, then things get tricky.

There is another difficulty. How does the server know which witnesses to provision? At the moment it's easy, because there is essentially one global small list of trusted CT Logs. Do we really want to assume that'll continue? One solution is for clients to be happy with an SCT from a specific log, which the TLS server could fetch on demand. That doesn't quite fit with the flow. As fallback (for servers that can't fetch), a client could be happy with an annoyingly long list of SCTs.

[davidben]

For a design like that, I think that's where ACME servers and CAs and whatnot come in. Their role is already to keep up with client requirements and get servers the thing they need.

TLS servers fetching things on demand is an interesting idea but seems much harder to get to from where we are. Servers, quite reasonably, have a lot of reasons to not want to be directed to connect to arbitrary other servers.