Re: [TLS] Merkle Tree Certificates

David Benjamin <> Mon, 05 June 2023 19:36 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id B73C3C15107E for <>; Mon, 5 Jun 2023 12:36:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -9.247
X-Spam-Status: No, score=-9.247 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001, USER_IN_DEF_SPF_WL=-7.5] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Enr7HrJYbjlf for <>; Mon, 5 Jun 2023 12:36:05 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::b31]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id D13B6C151083 for <>; Mon, 5 Jun 2023 12:35:34 -0700 (PDT)
Received: by with SMTP id 3f1490d57ef6-bacfb7acdb7so6184147276.0 for <>; Mon, 05 Jun 2023 12:35:34 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; t=1685993734; x=1688585734; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=rtYUD5I2QQd9grlB3QWxZb6pJa7Jcr6FBtA3xUcUQZQ=; b=jEjwnjreVHpuwe9bmHJneyS58kHk9unE17UhHABQlKNHS5uXH28nKaklgWdkj1Jazs sOKYHZigHUAPGw03iKSsMb7Z+yoGxvmS+Xwh3I00AmfOKNU2tmqB4h1YP6YgFdyIHp5z AbFznhZSzKCM+KZYReogXhf/9bfNt4+TBhock=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20221208; t=1685993734; x=1688585734; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=rtYUD5I2QQd9grlB3QWxZb6pJa7Jcr6FBtA3xUcUQZQ=; b=JVETNP5VOBtI7uVXkumNlwd80SrzCTfPMe5aidC2aEOHlKhMUf/tvqIFx1xoxpaCfq 5HuTivrJ1VBUdPAPVHGPwMC30FyK4hO7I0IkWSOo7HdPuV8eej7RltDMQGCDEVVHrij1 dd4z9PQJD5JHZ4kA74yqGPP51BuoX1aK0oe58aTUDmdwhDdvSL3kT0+zJZrR+51MqRoh FVxSFpjIGdA8o2v3VFzfhsOcxCoqvdnZj0Hr+XU/oP7gqDNQyMLf1pNDMRW/takeILUR ZhI8Oy0qZUk/lC1dVXgjAYeKuS6RAcOgBRkBhCiy4UJbzx6gvVGRvQS/S9Mw8IdrrVj2 zNGA==
X-Gm-Message-State: AC+VfDyycYxJRli094Am4947o4RKEE21T3nyk++lZ5Z0Fp2iayvCVFPL kF6ZWJzD3GTInGCgVt6FKlUYikdNDSWjfcj+mNtM5MRu926yZFirkIKF
X-Google-Smtp-Source: ACHHUZ6k1txlxWkQRUOw4n9l3XGEqsT/e2RhRDSdYyeWrPTvlUMgstbzwJxYEIW5Si7fpj4W12nEheabYMvrv9glkEI=
X-Received: by 2002:a25:3486:0:b0:b9d:b399:64b2 with SMTP id b128-20020a253486000000b00b9db39964b2mr12970308yba.28.1685993733658; Mon, 05 Jun 2023 12:35:33 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <ZBsxgM/cv+vuBPEj@LK-Perkele-VII2.locald>
In-Reply-To: <ZBsxgM/cv+vuBPEj@LK-Perkele-VII2.locald>
From: David Benjamin <>
Date: Mon, 05 Jun 2023 15:35:17 -0400
Message-ID: <>
To: Ilari Liusvaara <>
Cc: "<>" <>
Content-Type: multipart/alternative; boundary="0000000000009711f105fd6701de"
Archived-At: <>
Subject: Re: [TLS] Merkle Tree Certificates
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 05 Jun 2023 19:36:09 -0000

Thanks for such detailed feedback! Responses inline.

On Wed, Mar 22, 2023 at 12:49 PM Ilari Liusvaara <>

> 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.

>   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 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

> - 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

> - 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.

> - 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 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 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.

Whether this idea will stick, I’m not sure. (I wasn't kidding about this
being truly a draft-00. :-) ) We could decide this property isn’t that
useful, or perhaps we can’t come up with an opaque TrustAnchor comparison
model that is flexible enough. I think that’ll depend a lot on how the
negotiation story shakes out, and that’s next in our queue to refine.
(We’ve got some ideas we want to write up here.)

> - 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 too.

> - 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. :-)

> - 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.)

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. :-)

> - 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.

> - "We may need to define a third one.", you men fourth one?

Ah yeah, typo. Thanks! Fixed that in

> - 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?