Subject: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

From: Eric Rescorla <[email-masked]>
Date: Mon, 12 Jul 2021 17:30:26 -0700

Hi folks,

I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
read. I'm struggling a bit with the rationale, which I take to be
these paragraphs:

   In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
   We believe KEMs are especially worth discussing in the context of the
   TLS protocol because NIST is in the process of standardizing post-
   quantum KEM algorithms to replace "classic" key exchange (based on
   elliptic curve or finite-field Diffie-Hellman [NISTPQC]).

   This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
   which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
   However, these proposals require a non-interactive key exchange: they
   combine the client's public key with the server's long-term key.
   This imposes a requirement that the ephemeral and static keys use the
   same algorithm, which this proposal does not require.  Additionally,
   there are no post-quantum proposals for a non-interactive key
   exchange currently considered for standardization, while several KEMs
   are on the way.

I see why this motivates using a KEM for key establishment, but I'm
not sure it motivates this design, which seems like a fairly radical
change to TLS. As I understand the situation, in the post-quantum
world we're going to have:

- non-interactive KEMs (as you indicate above)
- some sort of signature system (otherwise we won't have certificates).

This certainly argues that we need a KEM for key establishment, but
not for authentication. Instead, why can't we use signatures for
authentication, as TLS does today? I.e., the certificates would have a
(potentially post-quantum) signing key in them and you then use the
KEM for key establishment and the signing key for authentication.
That would give us a design much closer to the present TLS 1.3
(effectively just defining a new group for the KEM).

What am I missing?

-Ekr

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 12 Jul 2021 20:58:27 -0400

Hi Eric,

The main motivation is that, in some cases, post-quantum signatures are larger in terms of communication size compared to a post-quantum KEM, under the same cryptographic assumption.  

For example, the KEM Kyber (based on module LWE) at the 128-bit security level has 800-byte public keys and 768-byte ciphertexts.  The matching signature scheme Dilithium (also based on module LWE) has 1312-byte public keys and 2420-byte signatures.  Doing KEM-based server authentication rather than signature-based server authentication would thus save 2164 bytes per handshake.  

We would still need digital signatures for a PKI (i.e., the root and intermediate CAs would sign certificates using PQ digital signature schemes), but the public key of the endpoint server can be a KEM public key, not a digital signature public key.

Douglas

> On Jul 12, 2021, at 20:30, Eric Rescorla <[email-masked]> wrote:
> 
> Hi folks,
> 
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 12 Jul 2021 18:10:04 -0700

On Mon, Jul 12, 2021 at 5:58 PM Douglas Stebila <[email-masked]> wrote:

> Hi Eric,
>
> The main motivation is that, in some cases, post-quantum signatures are
> larger in terms of communication size compared to a post-quantum KEM, under
> the same cryptographic assumption.
>
> For example, the KEM Kyber (based on module LWE) at the 128-bit security
> level has 800-byte public keys and 768-byte ciphertexts.  The matching
> signature scheme Dilithium (also based on module LWE) has 1312-byte public
> keys and 2420-byte signatures.  Doing KEM-based server authentication
> rather than signature-based server authentication would thus save 2164
> bytes per handshake.
>

Doug,

Thanks for the explanation.

I agree that all things being equal it's good to save bytes, but in this
case, I think this is the wrong tradeoff.

In general, TLS handshake latency is dominated not by message size but by
the number of round trips you have to use to perform the handshake, which
is only loosely coupled to the number of bytes.

Specifically:
- If you are doing TLS over TCP, then the server can use IW10 as specified
in RFC 6928. This will allow the server's first flight to be about 14 KB,
which should be large enough.
- If you are doing QUIC, then the server is restricted to 3x the client's
initial message, which is potentially a problem with very large server
first flights, but the client can add extra bytes to its Initial messages
to increase the limit [0]

And of course, there are mechanisms for shrinking the handshake, such as
RFC 8879 certificate compression or draft=thomson-tls-sic.

So, while I'm not that enthusiastic about paying a few K, I think on
balance it's a better than doing this kind of major rearchitecture of TLS.

-Ekr

[0] Or the server can send a Retry packet, incurring a round trip, but this
only needs to be done the first time as long as the client's IP doesn't
change.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 13 Jul 2021 03:38:38 +0000

Let me emphasize the reasons Douglas brought up. Note that I need to use NIST Sec Level 5 algorithms. So, Kyber-1024 and Dilithium5 (other algorithms show even worse ratio between KEM and signature!). 

Communications costs:
- Difference in public key sizes: 1568 bytes of Kyber vs. 2592 bytes of Dilithium => 1024 extra bytes to carry over channel each way;
- Signature: extra 4595 bytes each way, because in addition to exchanging certs (aka "signed public keys", which is inevitable) you need to sign the exchange and communicate that signature across;
- Total: 5619 extra bytes each way. For peer-to-peer broadband connections, you can say "so what?". But my links are *very* austere.

Computation costs (ballpark, on a powerful CPU):
- KEM: keygen 15us, encap 18us, decap 14us (say, double encap and decap for PFS-providing exchange); 
- Signature: sign 113us, verify 55us;
- Comparison: 134us for signature-less KEM vs. 215us for TLS-like exchange => almost twice as long;
- Difference may be negligible for Intel Xeon, but for my much weaker hardware it matters.

So, for constrained environments with austere comm links, signature-less "authkem" is God-sent. 
Big servers that need to support many clients (so they care how much CPU cycles and comm bytes they spend on every connection) would appreciate these savings too.

@ekr,I hope this provides convincing explanation why "authkem" is needed. 

P.S. I know that Falcon has much more favorable sizes - but (a) it takes three times as long to sign, and (b) it uses FP calculations, which isn't great to implement in my environment. 
--
Regards,
Uri
 
There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

On 7/12/21, 20:59, "TLS on behalf of Douglas Stebila" <[email-masked] on behalf of [email-masked]> wrote:

    Hi Eric,

    Douglas

---

From: "Kampanakis, Panos" <[email-masked]>
Date: Tue, 13 Jul 2021 04:09:30 +0000

> So, while I'm not that enthusiastic about paying a few K, I think on balance it's a better than doing this kind of major rearchitecture of TLS.

+1. KEMTLS is a great scheme but significantly changes the TLS state machine. It introduces implicit and explicit auth concepts which do not exist in TLS 1.3 and would need further security proofs and study. Also, it may save ~1-2KB of data (Falcon, Dilithium assumed), but still uses PQ Sigs in the PKI which means we go to 10+ KB for the cert chain. So we alleviate 1-2KB, but still have to deal with 10+. Also note ia.cr/2019/1447<https://ia.cr/2019/1447> which makes the argument that the more the data the more the slowdown in lossy environments (which intuitively makes sense as the loss probability (1-(1-p)n) increases with more packets). Imo the draft-celi-wiggers-tls-authkem should be considered for future versions of TLS as the drastic changes do not justify the marginal benefit.

And a couple of comments regarding Ekr’s points:

> - If you are doing TLS over TCP, then the server can use IW10 as specified in RFC 6928. This will allow the server's first flight to be about 14 KB, which should be large enough.

That is not completely accurate. The smallest Dilithium parameters will fit in 10MSS only when doing plain TLS (no SCTs, no OCSP staples) with up to 2 ICAs. Anything else will go beyond 14KB. Now if we talk web (include SCTs), then only 1 ICA would fit with Dilithium-II.

Having said that, if we talk about the other lattice based NIST PQ Sig Finalist, Falcon-512, then there are more TLS cases (up to 3 ICAs) where the data would fit in an TCP initcwnd.  For Falcon-1024 that is not the case either.

> - If you are doing QUIC, then the server is restricted to 3x the client's initial message, which is potentially a problem with very large server first flights, but the client can add extra bytes to its Initial messages to increase the limit [0]

Padding to the client initial message to 1200B would mean the QUIC amplification attack protection would kick in for any PQ KEM Round 3 Finalist and any PQ Sig Finalist, even Falcon-512 which is the smallest one. The smallest PQ Sig will still be >3x when used with X25519+the biggest PQ KEM Finalists. I am not sure what dummy key exchange data and how much of it someone could put in the client message in order to reach 2.5KB in the request in order for the response to fit in the 3x2.5 window necessary (assuming 2 ICAs).

I think the best answer to the extra round-trip problems which are inevitable for PQ Sigs (as shown in ia.cr/2020/071<https://ia.cr/2020/071> , dl.acm.org/<https://dl.acm.org/doi/10.1145/3386367.3431305>doi<https://dl.acm.org/doi/10.1145/3386367.3431305>/10.1145/3386367.3431305<https://dl.acm.org/doi/10.1145/3386367.3431305>) is Martin’s draft-<https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>thomson<https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>-<https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>tls<https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>-sic<https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic> which should be revived imo.

Cert compression will not help as these big certs mostly consist of big keys or sigs which are random sequences and thus do not benefit from compression.

Rgs,
Panos

From: TLS <[email-masked]> On Behalf Of Eric Rescorla
Sent: Monday, July 12, 2021 9:10 PM
To: Douglas Stebila <[email-masked]>
Cc: <[email-masked]> <[email-masked]>
Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

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.

On Mon, Jul 12, 2021 at 5:58 PM Douglas Stebila <[email-masked]<mailto:[email-masked]>> wrote:
Hi Eric,

Doug,

I agree that all things being equal it's good to save bytes, but in this case, I think this is the wrong tradeoff.

In general, TLS handshake latency is dominated not by message size but by the number of round trips you have to use to perform the handshake, which is only loosely coupled to the number of bytes.

Specifically:
- If you are doing TLS over TCP, then the server can use IW10 as specified in RFC 6928. This will allow the server's first flight to be about 14 KB, which should be large enough.
- If you are doing QUIC, then the server is restricted to 3x the client's initial message, which is potentially a problem with very large server first flights, but the client can add extra bytes to its Initial messages to increase the limit [0]

And of course, there are mechanisms for shrinking the handshake, such as RFC 8879 certificate compression or draft=thomson-tls-sic.

So, while I'm not that enthusiastic about paying a few K, I think on balance it's a better than doing this kind of major rearchitecture of TLS.

-Ekr

[0] Or the server can send a Retry packet, incurring a round trip, but this only needs to be done the first time as long as the client's IP doesn't change.

> On Jul 12, 2021, at 20:30, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:
>
> Hi folks,
>
> [email-masked]<mailto:[email-masked]>

---

From: "Kampanakis, Panos" <[email-masked]>
Date: Tue, 13 Jul 2021 04:19:54 +0000

Hi Uri,

If we are talking NIST Level 5 (and I am assuming you are discussing mTLS), have you calculated the total CertVerify+cert chain sizes there assuming 2 ICAs let's say? 

And would constrained devices or mediums that sweat about 5KB really be able to support PQ KEMs and Sigs at NIST Level 5?

-----Original Message-----
From: TLS <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Monday, July 12, 2021 11:39 PM
To: Douglas Stebila <[email-masked]>; Eric Rescorla <[email-masked]>
Cc: <[email-masked]> <[email-masked]>
Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

Communications costs:

    Hi Eric,

    Douglas

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 13 Jul 2021 05:17:29 +0000

> If we are talking NIST Level 5 (and I am assuming you are
> discussing mTLS), 

Yes. ;-)

> ...have you calculated the total CertVerify+cert chain sizes
> there assuming 2 ICAs let's say? 

More or less. ;-)

My use case has all the ICAs pre-loaded - the transmitted chain contains only one entity cert. I'm sacrificing flexibility for performance under constraints. Size is the real enemy here.

> And would constrained devices or mediums that sweat about 5KB
> really be able to support PQ KEMs and Sigs at NIST Level 5?

My tests showed that they *do* support PQ KEMs (NTRU and Kyber - haven't tried McEliece ;) and Sigs (Falcon and Dilithium - haven't tried Rainbow ;) at Level 5. Caveat - they do only Sig *verification* (which suits me fine).

(I posted benchmarks from Intel Core i9, but they work acceptably well on the "smaller" chips.)

Also, sorry if I did not make it clear - it's not the *devices* themselves that sweat 5KB, it's their austere links.

    -----Original Message-----
    From: TLS <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
    Sent: Monday, July 12, 2021 11:39 PM
    To: Douglas Stebila <[email-masked]>; Eric Rescorla <[email-masked]>
    Cc: <[email-masked]> <[email-masked]>
    Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

    Communications costs:

        Hi Eric,

        Douglas

---

From: Watson Ladd <[email-masked]>
Date: Tue, 13 Jul 2021 21:39:12 -0700

On Mon, Jul 12, 2021 at 9:10 PM Kampanakis, Panos <kpanos=
[email-masked]> wrote:

> +1. KEMTLS is a great scheme but significantly changes the TLS state
> machine. It introduces implicit and explicit auth concepts which do not
> exist in TLS 1.3 and would need further security proofs and study. Also, it
> may save ~1-2KB of data (Falcon, Dilithium assumed), but still uses PQ Sigs
> in the PKI which means we go to 10+ KB for the cert chain. So we alleviate
> 1-2KB, but still have to deal with 10+. Also note ia.cr/2019/1447 which
> makes the argument that the more the data the more the slowdown in lossy
> environments (which intuitively makes sense as the loss probability (1-(1-p)
> n) increases with more packets). Imo the draft-celi-wiggers-tls-authkem
> should be considered for future versions of TLS as the drastic changes do
> not justify the marginal benefit.
>

Part of what came out of the work on TLS 1.3 is a reusable formal model of
TLS, and at least some of the work in KEMTLS has repeated this formal
analysis.

> > - If you are doing TLS over TCP, then the server can use IW10 as
> specified in RFC 6928. This will allow the server's first flight to be
> about 14 KB, which should be large enough.
>
>
>
> That is not completely accurate. The smallest Dilithium parameters will
> fit in 10MSS only when doing plain TLS (no SCTs, no OCSP staples) with up
> to 2 ICAs. Anything else will go beyond 14KB. Now if we talk web (include
> SCTs), then only 1 ICA would fit with Dilithium-II.
>
>
>
> Having said that, if we talk about the other lattice based NIST PQ Sig
> Finalist, Falcon-512, then there are more TLS cases (up to 3 ICAs) where
> the data would fit in an TCP initcwnd.  For Falcon-1024 that is not the
> case either.
>
>
>
> > - If you are doing QUIC, then the server is restricted to 3x the
> client's initial message, which is potentially a problem with very large
> server first flights, but the client can add extra bytes to its Initial
> messages to increase the limit [0]
>
>
>
> Padding to the client initial message to 1200B would mean the QUIC
> amplification attack protection would kick in for any PQ KEM Round 3
> Finalist and any PQ Sig Finalist, even Falcon-512 which is the smallest
> one. The smallest PQ Sig will still be >3x when used with X25519+the
> biggest PQ KEM Finalists. I am not sure what dummy key exchange data and
> how much of it someone could put in the client message in order to reach
> 2.5KB in the request in order for the response to fit in the 3x2.5 window
> necessary (assuming 2 ICAs).
>
>
>

SQISign is short! It's just slow to sign, which KEMTLS avoids. Also with a
known set of intermediates the public keys do not need transmission, and
the tradeoffs between signature, public key, verification, and signing
speed further shift. One could conceivably use XMSS roots to sign SQISign
intermediates of moderate duration signing FALCON or Dilthium KEM keys,
balancing security and performance at each level. I think this fits in 14KB
with realistic conditions. We shouldn't assume that NIST candidate
signature schemes are the last word here.

I think the best answer to the extra round-trip problems which are
> inevitable for PQ Sigs (as shown in ia.cr/2020/071 , dl.acm.org/
> <https://dl.acm.org/doi/10.1145/3386367.3431305>doi
> <https://dl.acm.org/doi/10.1145/3386367.3431305>/10.1145/3386367.3431305
> <https://dl.acm.org/doi/10.1145/3386367.3431305>) is Martin’s draft-
> <https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>thomson
> <https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>-
> <https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>tls
> <https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic>-sic
> <https://datatracker.ietf.org/doc/html/draft-thomson-tls-sic> which
> should be revived imo.
>
>
>
> Cert compression will not help as these big certs mostly consist of big
> keys or sigs which are random sequences and thus do not benefit from
> compression.
>

In some sense draft-thompson-tls-sic is compression with a dictionary of
known intermediates.

> Panos

Sincerely,
Watson Ladd
-- 
Astra mortemque praestare gradatim

---

From: "Kampanakis, Panos" <[email-masked]>
Date: Thu, 22 Jul 2021 04:25:52 +0000

> SQISign is short! It's just slow to sign, which KEMTLS avoids. Also with a known set of intermediates the public keys do not need transmission, and the tradeoffs between signature, public key, verification, and signing speed further shift. One could conceivably use XMSS roots to sign SQISign intermediates of moderate duration signing FALCON or Dilthium KEM keys, balancing security and performance at each level. I think this fits in 14KB with realistic conditions. We shouldn't assume that NIST candidate signature schemes are the last word here.

My argument is that suppressing ICA certs and not doing KEMTLS will be immaterially slower than using KEMTLS and suppressing ICA certs. Or alternatively I am arguing that using Dilithium without KEMTLS will be immaterially slower than using KEMTLS. It was shown in  ia.cr/2020/071<https://ia.cr/2020/071> , dl.acm.org/<https://dl.acm.org/doi/10.1145/3386367.3431305>doi<https://dl.acm.org/doi/10.1145/3386367.3431305>/10.1145/3386367.3431305<https://dl.acm.org/doi/10.1145/3386367.3431305> , ia.cr/2019/1447<https://ia.cr/2019/1447> that a couple of KB do not slow down the handshake even in lossy (not too lossy) conditions

But I am willing to change my mind if you have experimental proof.

I am also arguing that KEMTLS introduces significant changes to TLS 1.3. And that in order to avoid an extra round-trip it requires the client to get the server identity public key some out-of-band way. OK ECH does that for an encryption public key, but doing it for the identity public key is an extra complication.

From: Watson Ladd <[email-masked]>
Sent: Wednesday, July 14, 2021 12:39 AM
To: Kampanakis, Panos <[email-masked]>
Cc: Eric Rescorla <[email-masked]>; <[email-masked]> <[email-masked]>
Subject: [EXTERNAL] [UNVERIFIED SENDER] Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

Part of what came out of the work on TLS 1.3 is a reusable formal model of TLS, and at least some of the work in KEMTLS has repeated this formal analysis.

SQISign is short! It's just slow to sign, which KEMTLS avoids. Also with a known set of intermediates the public keys do not need transmission, and the tradeoffs between signature, public key, verification, and signing speed further shift. One could conceivably use XMSS roots to sign SQISign intermediates of moderate duration signing FALCON or Dilthium KEM keys, balancing security and performance at each level. I think this fits in 14KB with realistic conditions. We shouldn't assume that NIST candidate signature schemes are the last word here.

In some sense draft-thompson-tls-sic is compression with a dictionary of known intermediates.

Rgs,
Panos

Sincerely,
Watson Ladd