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

"Panos Kampanakis (pkampana)" <pkampana@cisco.com> Tue, 30 July 2019 19:36 UTC

Return-Path: <pkampana@cisco.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 A0E26120156 for <tls@ietfa.amsl.com>; Tue, 30 Jul 2019 12:36:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.499
X-Spam-Level:
X-Spam-Status: No, score=-14.499 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com header.b=FwG7st/q; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=Pa2Zorry
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 u802AfS-DSXZ for <tls@ietfa.amsl.com>; Tue, 30 Jul 2019 12:36:36 -0700 (PDT)
Received: from rcdn-iport-1.cisco.com (rcdn-iport-1.cisco.com [173.37.86.72]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E6B3312001E for <tls@ietf.org>; Tue, 30 Jul 2019 12:36:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=23615; q=dns/txt; s=iport; t=1564515395; x=1565724995; h=from:to:subject:date:message-id:references:in-reply-to: mime-version; bh=LR5iyZqFjAbM+cbDfz3imA8Q1cG57QFwbwouzhDik/M=; b=FwG7st/qieLzmB4k7Y3ynlNEfcDcGSofvD5K4HR6c9U+YOOQ8r419IYC IEQlif7Lnfb5gNhrmh8Vig34BC8UcLOreAp4qPLizhQD8U6bETjXQZj2q 4k84tDWktMw05/ICMhPJ80YciG5L/QSpvznIMqXuD/D512UfmKqBPzv4W I=;
IronPort-PHdr: =?us-ascii?q?9a23=3A++wyxxxHu64o1fzXCy+N+z0EezQntrPoPwUc9p?= =?us-ascii?q?sgjfdUf7+++4j5YhWN/u1j2VnOW4iTq+lJjebbqejBYSQB+t7A1RJKa5lQT1?= =?us-ascii?q?kAgMQSkRYnBZudCkT+NPfsZgQxHd9JUxlu+HToeUU=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0D6AAAFm0Bd/5pdJa1lGgEBAQEBAgE?= =?us-ascii?q?BAQEHAgEBAQGBZ4EVL1ADbVUgBAsqCodbA40FTIIPfpZWglIDVAkBAQEMAQE?= =?us-ascii?q?tAgEBhEACgkIjOBMBAwEBBAEBAgEGbYUeDIVKAQEBAQMSGxMBATgPAgEIEQQ?= =?us-ascii?q?BASEOMh0IAQEEARIIGoMBgR1NAx0BAqFZAoE4iGCCI4J6AQEFhQ0YghMJgTS?= =?us-ascii?q?LYBeBQD+BEUaCFwcuPoFUgloYgzuCJowFh3mWFm0JAoIalDGYEY09l1oCBAI?= =?us-ascii?q?EBQIOAQEFgWchgVhwFTuCbIJCg3GKU3KBKYwsAYEgAQE?=
X-IronPort-AV: E=Sophos;i="5.64,327,1559520000"; d="scan'208,217";a="605684453"
Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by rcdn-iport-1.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 30 Jul 2019 19:36:34 +0000
Received: from XCH-ALN-013.cisco.com (xch-aln-013.cisco.com [173.36.7.23]) by rcdn-core-3.cisco.com (8.15.2/8.15.2) with ESMTPS id x6UJaYg0018138 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL) for <tls@ietf.org>; Tue, 30 Jul 2019 19:36:34 GMT
Received: from xhs-aln-003.cisco.com (173.37.135.120) by XCH-ALN-013.cisco.com (173.36.7.23) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Tue, 30 Jul 2019 14:36:33 -0500
Received: from xhs-rtp-001.cisco.com (64.101.210.228) by xhs-aln-003.cisco.com (173.37.135.120) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Tue, 30 Jul 2019 14:36:24 -0500
Received: from NAM02-BL2-obe.outbound.protection.outlook.com (64.101.32.56) by xhs-rtp-001.cisco.com (64.101.210.228) with Microsoft SMTP Server (TLS) id 15.0.1473.3 via Frontend Transport; Tue, 30 Jul 2019 15:36:24 -0400
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=TcM6ViV1m6JDOY+mInvRC/83KtqOH5QgOyjLi/fPXsNfa294pqfrsq0b1P+vPTAW+hMyzZSSXCYdUcN96HCn0tB+zdsKc5L6r40bqcgOtzEWmNv4X+bWKylQt6jhKIpkv5auTomjLSow/6f5RUs8VyXW0h9BLVOmxLYhmO2N5WtEs4193yhU15lTvmqHwLYXVgr/2ny8l7lMCY3mneULyGgmq8lY7oF7YJ+5tJR/XDqfF5My0f8PDm0mspAYLa79cyw4vx39XSv9bmD4eGBv//HAfxgbJWIJ3kiPkTGt5khol+Jfksnb4pkS/3bcDfZYDHNCNC8c/5A23j2CF0tXtg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=4qrOD8dXiDW31B4tyt69+d1n/siZHXGf66DQ3LnwNaQ=; b=Hh4ArAnHFfSHDU62dTfKq0rUCKgWd55MuWVSXl1zY85XZfb60oh/6yQJBqwHjJN7aUsOoeyuw9peDTM11jCR7A+nQRG+91FxFkkDga0G72BpaicwYTWqYuCZCtcfowOU4b9CMAjMMWdlJZyDlDr+135qT7sirR1FM4uMHCMhyKf4UaipOV6hrLzEBRZ/NIVPURysjOyJ6vRqOOewce8r7pHmcfm/X+wfU/l6h7yKFu4L5Jp0/sUyuoGxFJCSAmas8yLMcSEfJrNd/f98Y7SO8yMqW/NykIS7/Weuve+x0nZZgvlbmYnw6UQ+lbKU3RR8uR06OXD9Fd/mHKKx+GEcmA==
ARC-Authentication-Results: i=1; mx.microsoft.com 1;spf=pass smtp.mailfrom=cisco.com;dmarc=pass action=none header.from=cisco.com;dkim=pass header.d=cisco.com;arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cisco.onmicrosoft.com; s=selector2-cisco-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=4qrOD8dXiDW31B4tyt69+d1n/siZHXGf66DQ3LnwNaQ=; b=Pa2ZorryHuR6sS9/m8xPbSjoLDRpVwOY4jbF1VfWvsVOdptPfSjy2s5M/Naw9flU8fPENEpgjxr5QkOdy0p8c8EJb6bUb1Lf6umPd3eGhRh4fXtnPdtYRppfqeAsxsDkXA7v6JMqyGloDkBzewp/cJS3C08kATpbHQWKMMAZwyQ=
Received: from DM6PR11MB2555.namprd11.prod.outlook.com (20.176.98.161) by DM6PR11MB3675.namprd11.prod.outlook.com (20.178.231.76) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2115.14; Tue, 30 Jul 2019 19:36:23 +0000
Received: from DM6PR11MB2555.namprd11.prod.outlook.com ([fe80::61ac:42a5:2f3e:5e70]) by DM6PR11MB2555.namprd11.prod.outlook.com ([fe80::61ac:42a5:2f3e:5e70%7]) with mapi id 15.20.2115.005; Tue, 30 Jul 2019 19:36:23 +0000
From: "Panos Kampanakis (pkampana)" <pkampana@cisco.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, "<tls@ietf.org>" <tls@ietf.org>
Thread-Topic: Options for negotiating hybrid key exchanges for postquantum
Thread-Index: AdVG1haOE+yO4N1wQQSyYtQ5VKKSwAAN/CPg
Date: Tue, 30 Jul 2019 19:36:23 +0000
Message-ID: <DM6PR11MB2555BB65C283C0F08C4F7E3AC9DC0@DM6PR11MB2555.namprd11.prod.outlook.com>
References: <MN2PR11MB38719A31081434FEF6A84999C1DC0@MN2PR11MB3871.namprd11.prod.outlook.com>
In-Reply-To: <MN2PR11MB38719A31081434FEF6A84999C1DC0@MN2PR11MB3871.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=pkampana@cisco.com;
x-originating-ip: [173.38.117.86]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 810f498f-20c7-4a7b-c47f-08d71525346d
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(5600148)(711020)(4605104)(1401327)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(2017052603328)(7193020); SRVR:DM6PR11MB3675;
x-ms-traffictypediagnostic: DM6PR11MB3675:
x-ms-exchange-purlcount: 2
x-microsoft-antispam-prvs: <DM6PR11MB367580AF1167E85291A79FF4C9DC0@DM6PR11MB3675.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:9508;
x-forefront-prvs: 0114FF88F6
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(346002)(39860400002)(136003)(376002)(396003)(366004)(189003)(199004)(15404003)(64756008)(68736007)(14454004)(6306002)(81166006)(55016002)(8676002)(71190400001)(71200400001)(3846002)(25786009)(2906002)(81156014)(478600001)(9686003)(6116002)(6436002)(8936002)(54896002)(33656002)(53936002)(446003)(26005)(6246003)(66476007)(53546011)(66446008)(66574012)(66946007)(66066001)(86362001)(52536014)(76116006)(186003)(14444005)(5660300002)(7696005)(476003)(229853002)(256004)(790700001)(7736002)(486006)(110136005)(76176011)(6506007)(74316002)(102836004)(11346002)(99286004)(316002)(66556008)(491001); DIR:OUT; SFP:1101; SCL:1; SRVR:DM6PR11MB3675; H:DM6PR11MB2555.namprd11.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: cisco.com does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: POcJ8sE930pJ0r0BZSD1xsbZNw41+rdUoMnUGGIzFDHEwx3e0XBT84+OydlKGMd32D7bkohMlwjhPuNwl27voEKVyBUXzg1GCRuhKofnV8x26tnL/vF924ZSYTHN6AEWS9FW1UcUqCPIHovFUiCiu1eAQieVytg5ioZcIHEHQjkrxm2/eCrvdUIKs/DkDhOherqBW7wOnePRMgTUvaamz4iCnhmH6mGgGX1kmeBU7goDEbyQ6EPXywWUyZkIwV//brR0n8PfuCyanbP7Ia+vEiNnB/HBoeq4NwUk892cuarCdc31O7k/hB8kYhBF08Nfko/luo6ipmF+bfAgBKcs/id03j2Ee4Emr4vQM4MfpNIONz1RtneRKO+SKrCs9ZuiMFnwtEZsYUMFc2cPDN4LOI+yQvi6t/krimHbSZU7e2g=
Content-Type: multipart/alternative; boundary="_000_DM6PR11MB2555BB65C283C0F08C4F7E3AC9DC0DM6PR11MB2555namp_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 810f498f-20c7-4a7b-c47f-08d71525346d
X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Jul 2019 19:36:23.0998 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 5ae1af62-9505-4097-a69a-c1553ef7840e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: pkampana@cisco.com
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR11MB3675
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.23, xch-aln-013.cisco.com
X-Outbound-Node: rcdn-core-3.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/acN2fHYgrzZzJmGNEjg7ibmsAqM>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum
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, 30 Jul 2019 19:36:41 -0000

+1 for option 2. The combinatoric explosion and complexity of 1 is unnecessary. I expect that just a few, conservative, acceptably efficient, classical+PQ combinations need to be standardized and used. Combining a classical algo with more than one postquantum algorithms in a key exchange does not seem practical based on the PQ candidates key sizes and performance.

Panos


From: TLS <tls-bounces@ietf.org>; On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Tuesday, July 30, 2019 11:21 AM
To: <tls@ietf.org>; <tls@ietf.org>;
Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

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

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.