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

"Kampanakis, Panos" <kpanos@amazon.com> Tue, 13 July 2021 04:09 UTC

Return-Path: <prvs=8210fd490=kpanos@amazon.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 558843A1216 for <tls@ietfa.amsl.com>; Mon, 12 Jul 2021 21:09:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -10.048
X-Spam-Level:
X-Spam-Status: No, score=-10.048 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.452, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_SPF_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=amazon.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id NnRpvoqI3NrN for <tls@ietfa.amsl.com>; Mon, 12 Jul 2021 21:09:50 -0700 (PDT)
Received: from smtp-fw-9103.amazon.com (smtp-fw-9103.amazon.com [207.171.188.200]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 00DA53A1219 for <tls@ietf.org>; Mon, 12 Jul 2021 21:09:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1626149390; x=1657685390; h=from:to:cc:date:message-id:references:in-reply-to: mime-version:subject; bh=u9wlyobsC6aXG25z2HuEtBsFzAMyPAGYyySuq9Jxzao=; b=s1X/Zps5/XnZB/t4rlxwY2XCeZ+SIjLdvyEw4/yohOyS+UkjasoLicrb EIsioRIycQ1bEqgIL3glgtEwRROq7+P0zUNhOi9+rw70uinVGSGwFAQSO vvwnCWeHNFEU12hWYvpFVSPD/1rqETagRVJAIFGZSDkvczJzOsiKpCQMs U=;
X-IronPort-AV: E=Sophos;i="5.84,235,1620691200"; d="scan'208,217";a="943217837"
Thread-Topic: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt
Received: from pdx4-co-svc-p1-lb2-vlan2.amazon.com (HELO email-inbound-relay-2b-4e24fd92.us-west-2.amazon.com) ([10.25.36.210]) by smtp-border-fw-9103.sea19.amazon.com with ESMTP; 13 Jul 2021 04:09:35 +0000
Received: from EX13MTAUWB001.ant.amazon.com (pdx1-ws-svc-p6-lb9-vlan2.pdx.amazon.com [10.236.137.194]) by email-inbound-relay-2b-4e24fd92.us-west-2.amazon.com (Postfix) with ESMTPS id 84535A1D90; Tue, 13 Jul 2021 04:09:35 +0000 (UTC)
Received: from EX13D01ANC004.ant.amazon.com (10.43.157.237) by EX13MTAUWB001.ant.amazon.com (10.43.161.207) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Tue, 13 Jul 2021 04:09:31 +0000
Received: from EX13D01ANC003.ant.amazon.com (10.43.157.68) by EX13D01ANC004.ant.amazon.com (10.43.157.237) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Tue, 13 Jul 2021 04:09:31 +0000
Received: from EX13D01ANC003.ant.amazon.com ([10.43.157.68]) by EX13D01ANC003.ant.amazon.com ([10.43.157.68]) with mapi id 15.00.1497.018; Tue, 13 Jul 2021 04:09:31 +0000
From: "Kampanakis, Panos" <kpanos@amazon.com>
To: Eric Rescorla <ekr@rtfm.com>
CC: "<tls@ietf.org>" <tls@ietf.org>, Douglas Stebila <dstebila@gmail.com>
Thread-Index: AQHXd36VMyBQcGynkEORYKmMYIU5jKtAFWOAgAADPwCAAChlYA==
Date: Tue, 13 Jul 2021 04:09:30 +0000
Message-ID: <76bf3aa9e18c475590b6fab7c050b851@EX13D01ANC003.ant.amazon.com>
References: <CABcZeBN4y40o7T3hx4RH3LogbMDEScxGY4SVuCWuQ67oW+XZ3w@mail.gmail.com> <DF9C8D2D-4B2A-414D-AD7A-0ED424CD98FE@gmail.com> <CABcZeBNH4Hg5v99+MmsgTNKD54jvxLRzrj55fCM+m8drxajQKA@mail.gmail.com>
In-Reply-To: <CABcZeBNH4Hg5v99+MmsgTNKD54jvxLRzrj55fCM+m8drxajQKA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.43.157.101]
Content-Type: multipart/alternative; boundary="_000_76bf3aa9e18c475590b6fab7c050b851EX13D01ANC003antamazonc_"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/P9-fdIAi__8KEHMr3M7aJD6cI0Q>
Subject: Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 13 Jul 2021 04:09:55 -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 <tls-bounces@ietf.org> On Behalf Of Eric Rescorla
Sent: Monday, July 12, 2021 9:10 PM
To: Douglas Stebila <dstebila@gmail.com>
Cc: <tls@ietf.org> <tls@ietf.org>
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 <dstebila@gmail.com<mailto:dstebila@gmail.com>> 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.


> On Jul 12, 2021, at 20:30, Eric Rescorla <ekr@rtfm.com<mailto:ekr@rtfm.com>> wrote:
>
> 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
>
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org<mailto:TLS@ietf.org>
> https://www.ietf.org/mailman/listinfo/tls