Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

Andrei Popov <> Tue, 30 July 2019 19:09 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BA0DB12027C for <>; Tue, 30 Jul 2019 12:09:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 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, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 1oRU9oaYWqXy for <>; Tue, 30 Jul 2019 12:09:41 -0700 (PDT)
Received: from ( [IPv6:2a01:111:f400:fe52::71f]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A414B1201D6 for <>; Tue, 30 Jul 2019 12:09:41 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901;; cv=none; b=Dpxd12SAvpjiX5dKfMLyNISrsDlRqKVj4GO8NHKIa1F6TnRkGA2AWeC1NCZljFcsTDmfe+i6KtFb4V63gBp5OLZrLMYMS+ciTQX2RT6LJYBk6LLBjSm5eXzGZABGEQZde+gnfn0L9HMVELHBjfQmB1lFQbRDFYc5QLToWteCy7F3KlRCA6mEMn5yQX7QBNie7hffz/6EMkonIR7wc5D8lAxWZJHPnZkCOeQxp6+c5/a8EhWyHamSaQa3kcHtbbOwk0ycvHo1d7Zdw9726sUQctQ9LjX7PLB0910agHmEmbkgU9RZ/Kinn7FxbKYZ14enlI4Z25/wfZOVW5cU69eK9Q==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed;; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=QlXx/0CvvCDppLDKAAFjFIc15ZW9+CnDrAMuwAF3urw=; b=mKoKIYS2WBSfPSoksAN8o+spTcP7KAvfi5QnUqk/PsAHlpAYNW/JH2LkZEUuRioMEvc4RKpBpbU+F+lTeR3A9jLCtQV+casZsgLRCQMHYizDPngJfZqVQS94yyD05u6z8CwThuPUQksBgh650sM5bJbmTcsrp63nPveHuJcOspDn+CkIuNd/uxOLemJUk5RKAiofsboQFfm9H7EaXymqxMs7HFBBgpXF0DxIHq3r/fkiWTE/gJMLvQDimSfy3Pt+fTbG8z1OnNesIKzl3YyB/7gLLF4v+T8H9lKfHlYc83I1p2GdR9Ji/oT/auLCgpwQCyGDHuzUyfFaFT46Gz8LwQ==
ARC-Authentication-Results: i=1; 1; spf=pass; dmarc=pass action=none; dkim=pass; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=QlXx/0CvvCDppLDKAAFjFIc15ZW9+CnDrAMuwAF3urw=; b=DlaA5nR+2a5VhhuS2UtQZjnuGjYfGx9MxxeL93aq1td9eeM87irVlzxhddJT7srR6uEb0rhu8594hRiUPokYfLDdDwtuwmT138i3E1wHz5GnTyt3pAaJGxD3fgR5ZHEWXyWb0dNugA7nugQA+TtIqK/0Fej8lrMbnRVV1vNlp4U=
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2157.2; Tue, 30 Jul 2019 19:09:39 +0000
Received: from ([fe80::6cee:c549:a46c:9e5c]) by ([fe80::6cee:c549:a46c:9e5c%7]) with mapi id 15.20.2157.001; Tue, 30 Jul 2019 19:09:39 +0000
From: Andrei Popov <>
To: David Benjamin <>
CC: Watson Ladd <>, TLS List <>
Thread-Topic: [TLS] Options for negotiating hybrid key exchanges for postquantum
Date: Tue, 30 Jul 2019 19:09:39 +0000
Message-ID: <>
References: <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
authentication-results: spf=none (sender IP is );
x-originating-ip: [2001:4898:80e8:a:28b3:a023:971b:e42c]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: d8a98b3f-cc2e-4c8b-06c8-08d7152178a9
x-ms-office365-filtering-ht: Tenant
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600148)(711020)(4605104)(1401327)(4618075)(2017052603328)(7193020); SRVR:DM5PR2101MB1046;
x-ms-traffictypediagnostic: DM5PR2101MB1046:
x-ms-exchange-purlcount: 3
x-microsoft-antispam-prvs: <>
x-ms-oob-tlc-oobclassifiers: OLM:7691;
x-forefront-prvs: 0114FF88F6
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(4636009)(39860400002)(376002)(396003)(136003)(366004)(346002)(15404003)(51444003)(199004)(189003)(790700001)(99286004)(66476007)(10090500001)(14454004)(9686003)(8990500004)(66446008)(66946007)(236005)(76116006)(30864003)(55016002)(52536014)(5070765005)(64756008)(25786009)(86362001)(5660300002)(10290500003)(606006)(966005)(478600001)(6246003)(4326008)(68736007)(74316002)(46003)(14444005)(22452003)(7696005)(53546011)(2906002)(8676002)(71200400001)(71190400001)(33656002)(186003)(6506007)(102836004)(81156014)(81166006)(256004)(229853002)(8936002)(76176011)(486006)(54906003)(11346002)(446003)(7736002)(6436002)(54896002)(6306002)(6116002)(476003)(6916009)(66556008)(53936002)(316002); DIR:OUT; SFP:1102; SCL:1; SRVR:DM5PR2101MB1046;; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1;
received-spf: None ( does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: iX7Y19IA+XiRB/Inya59W160xteWtKMjj/oYsuVdos4vrCVxdAFTfRRG0s0zrKM470cSwBgVXm4O4mKncPAjxnb1FKYFuVyn2I+/1HqDUY8oExQgHWKdQh0BxNrsz/9KtcrN/AxRkICs6GFKrNI6V/AFoDkmkqQW6HD7M7z6r7bhymlILOx+3/q2sVk2STroA7ESFqbXKlmRedQw3WN/CKklnIoCDosGRQwg8bC30GpAt/25JNgKGumeZ7LphHTaopRgkogcjLj1iAOCKeFPkwZ4KlvQvl5+XE4rGiW66KoGamyvVg20bnZ8D02srN7ZyB7D0lb6gaMV3a7ZyF2E7RyQ1/8I9KxC7R5SHbtZ/1A1EibCVsTNpVl7BdxWsktYYGKSi9qgLTIQKwW2Jo0AG/G2+hVQc7qohIpp33g4oMU=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_DM5PR2101MB0917D921E7C79CAA4D2AAA5A8CDC0DM5PR2101MB0917_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: d8a98b3f-cc2e-4c8b-06c8-08d7152178a9
X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Jul 2019 19:09:39.6902 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: TO3tlevdRD0PLzlV/9UWBjOBBK6kuq0ioazJEkVaQx5ksRGAtxVOQv8F6iwAIl3t4wffhdchuKtfxUHP1wexhg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM5PR2101MB1046
Archived-At: <>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum
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." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 30 Jul 2019 19:09:55 -0000

Yes, I see your point WRT clients expressing preferences.

Regardless of the protocol option we choose, I anticipate some difficulty in agreeing on what’s “reasonable”.
E.g. I’ve had several customers ask about the possibility of combining a couple of traditional algorithms (e.g. national vanity + NIST).
Some of them ended up doing TLS-in-TLS, which of course only works between their particular clients and servers.

From: David Benjamin <>;
Sent: Tuesday, July 30, 2019 11:59 AM
To: Andrei Popov <>;
Cc: Watson Ladd <>;; TLS List <>;
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

The nuisance with just a flag is the client can't express [what I think are] reasonable preferences. It should be able to say things like:

* Don't do X25519 + P-256. This is just silly.
* Don't do PQ1 on its own. I really want the PQ scheme paired with something more established.
* Don't do PQ1 + PQ2. I said something more established, please.
* PQ1 + X25519 is cool. I like that combo.
* Don't do PQ1 + X25519 + P-256. Why are you doing three of these?
* Don't do PQ1 + PQ2 + PQ3 + PQ4 + X25519 + P-256 + P-384 + FFDHE2048 + FFDHE3072, oww my head.

We can make things implicit by categorizing named groups and building all this into the protocol itself, but I think that's an unnecessary moving part.

On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov <<>> wrote:
Given these options, I also prefer option 2, for some of the same reasons.

For my understanding though, why not have the client advertise support for hybrid-key-exchange (e.g. via a “flag” extension) and then KeyShareServerHello can contain two KeyShareEntries (essentially, using the same format as KeyShareClientHello? This would solve the Cartesian product issue.



From: TLS <<>> On Behalf Of David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd <<>>
Cc: TLS List <<>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

I think this underestimates the complexity cost of option 1 to the protocol and implementations. Option 1 means group negotiation includes entire codepoints whose meaning cannot be determined without a parallel extension. This compounds across everything which interacts with named groups, impacting everything from APIs to config file formats to even UI surfaces. Other uses of NamedGroups are impacted too. For instance, option 2 fits into draft-ietf-tls-esni as-is. Option 1 requires injecting hybrid_extension into ESNI somehow. Analysis must further check every use, say, incorporates this parallel lookup table into transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split ones. Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints required cross-referencing against the supported curves list. The verifier could not express some preferences (signing SHA-512 with P-256 is silly, and mixing hash+curve pairs in ECDSA is slightly off in general). As analogy to option 1's ESNI problem, we even forgot to allow the server to express curve preferences. TLS 1.3 combined signature algorithm considerations into a single codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE key exchange, but you need to check if you have a NamedGroup in common first. It said to use ECDSA, but you need to check signature algorithms (which themselves cross-reference curves) first. Early drafts of TLS 1.3 had it even worse, where a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full handshake morphed into TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption. Thus, TLS 1.3 cipher suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's evolution over time as incremental extensions over SSL 3.0. And sometimes we do need to pay costs like these. But hybrid key exchanges fit into the NamedGroup "API" just fine, so option 2 is the clear answer. Code points are cheap. Protocol complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF should finish the job, not pass all variations through. RSA-PSS is a clear example of what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and usual parameters" in X.509 than to encode an entire ECDSA signature! We should not define more than a handful of options, regardless of the encoding..

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd <<>> wrote:

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <<>> wrote:
During the physical meeting in Montreal, we had a discussion about postquantum security, and in particular, on how one might want to negotiate several different ‘groups’ simultaneously (because there might not be one group that is entirely trusted, and I put ‘groups’ in scarequotes because postquantum key exchanges are typically not formed from a Diffie-Hellman group).

At the meeting, there were two options presented:

Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an extension that map lists which combination the hybrid marker stands for)
                For example, the client might list in his supported groups hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 in the extension, and then compare that against his security policy.
In this option, we would ask IANA to allocate code points for the various individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), as well a range of code points for the various hybrid_markers.

Option 2: we have code points for all the various combinations that we may want to support; hence IANA might allocate a code point X25519_SIKEp434 and another code point for X25519_NTRUPR653.  With this option, the client would list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
                In this option, we would ask IANA to allocate code points for all the various combinations that we want allow to be negotiated.

I would like to make an argument in favor of option 1:

  *   It is likely that not everyone will be satisified with “X25519 plus one of a handful of specific postquantum algorithms”; some may prefer another elliptic curve (for example, x448), or perhaps even a MODP group; I have talked to people who do not trust ECC); in addition, other people might not trust a single postquantum algorithm, and may want to rely on both (for example) SIKE and NewHope (which are based on very different hard problems).  With option 2, we could try to anticipate all the common combintations (such as P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of combinations.
  *   There are likely to be several NIST-approved postquantum key exchanges, and each of those key exchanges are likely to have a number of supported parameter sets (if we take the specific postquantum key exchange as analogous to th ECDH protocool, the “parameter set” could be thought of an analogous to the specific elliptuc curve, and it modifies the key share size, the performance and sometimes the security properties).  In fact, one of the NIST submissoins currently has 30 parameter sets defined.  Hence, even if NIST doesn’t approve all the parameter sets (or some of them do not make sense for TLS in any scenario), we might end up with 20 or more different key exchange/parameter set combinations that do make sense for some scenario that uses tLS (be it in a tranditional PC client/server, a wireless client, two cloud devices communicating or an IOT device).
  *   In addition, we are likely to support additional primitives in the future; possibly National curves (e.g. Brainpool), or additional Postquantum algorithms (or additional parameter sets to existing ones).  Of course, once we add that code point, we’ll need to add the additional code points for all the combinations that it’ll make sense in (very much like we had to add a number of ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

Are people actually going to use hybrid encryption post NIST? The actual deployments today  for experiment have all fit option 2 and hybrids are unlikely in the future.

My objection to 1 is it gets very messy. Do we use only the hybrids we both support? What if I throw a bunch of expensive things together? No reason we need a hybrid scheme!

It seemds reasonable to me that the combination of these two factors are likely to cause us (should we select option 2) to define a very large number of code points to cover all the various options that people need.

Now, this is based on speculation (both of the NIST process, and additional primitives that will be added to the protocol), and one objection I’ve heard is “we don’t know what’s going to happen, and so why would we make decisions based on this speculation?”  I agree that we have lack of knowledge; however it seems to me that a lack of knowledge is an argument in favor of selecting the more flexible option (which, in my opinion, is option 1, as it allows the negotiation of combinations of key exchanges that the WG has not anticipated).

My plea: lets not repeat the TLS 1.2 ciphersuite mess; lets add an extension that keeps the number of code points we need to a reasonable bound.

The costs of option 1?

  *   It does increase the complexity on the server a small amount (I’m not a TLS implementor, however it would seem to me to be only a fairly small amount)
  *   It may increase the size of the client hello a small amount (on the other hand, because it allows us to avoid sending duplicate key shares, it can also reduce the size of the client hello as well, depending on what’s actually negotiated)
IMHO, the small increase in complexity is worth the lack of complexity in the code point table, and the additional flexibility it gives.
TLS mailing list<><>
TLS mailing list<><>