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

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Tue, 30 July 2019 18:41 UTC

Return-Path: <sfluhrer@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 05490120154 for <tls@ietfa.amsl.com>; Tue, 30 Jul 2019 11:41:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.501
X-Spam-Level:
X-Spam-Status: No, score=-14.501 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-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=k9v8fWA4; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=SiSC6VVM
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 ASr7iGqJYjAR for <tls@ietfa.amsl.com>; Tue, 30 Jul 2019 11:41:44 -0700 (PDT)
Received: from rcdn-iport-3.cisco.com (rcdn-iport-3.cisco.com [173.37.86.74]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D7C9D12008D for <tls@ietf.org>; Tue, 30 Jul 2019 11:41:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=6154; q=dns/txt; s=iport; t=1564512103; x=1565721703; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=QnG/pkj6RVPYaikB1XDg2rsTJiUCA8qCn1ZYusfK1+w=; b=k9v8fWA4o62Hrs3czMKK5L93e5UPPEc4Qq+ydvnx0x/P1CTLrQqe3kh+ XNLlWuyaZgenYxLFP6b59kmPJwP8aWuDf9R8yjkWoAGdp1Se6Vym/jJEu fUKEKiVty9fbz3IkMp4NCWz9tNg/CzK7mAjWvjDDdSSPv2EkgylaJvyHa c=;
IronPort-PHdr: =?us-ascii?q?9a23=3AAzrVzxApsidtL6F8Iz6TUyQJPHJ1sqjoPgMT9p?= =?us-ascii?q?ssgq5PdaLm5Zn5IUjD/qs03kTRU9Dd7PRJw6rNvqbsVHZIwK7JsWtKMfkuHw?= =?us-ascii?q?QAld1QmgUhBMCfDkiuN/DuciwgEd5qX15+9Hb9Ok9QS47z?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CqAADSjkBd/4cNJK1lGgEBAQEBAgE?= =?us-ascii?q?BAQEHAgEBAQGBZ4FEUAOBQiAECyoKhBSDRwONBYJbiVSOAIJSA1QJAQEBDAE?= =?us-ascii?q?BLQIBAYRAAheCKyM4EwEDAQEEAQECAQZthR4MhUoBAQEBAgESEREMAQE3AQQ?= =?us-ascii?q?LAgEGAhUDAgIjAwICAh8RFAEQAQEEDgUIGoRrAw4PAZEFkGECgTiIYHGBMoJ?= =?us-ascii?q?6AQEFhQ4NC4ITCYEMKItgF4FAP4ERRoIeLj6CGoIUGIMJMoImjFiCJpsWLUA?= =?us-ascii?q?JAoIakB+EEpgRln6OGQIEAgQFAg4BAQWBZyGBWHAVO4JsgkKDcYpTcoEpjCw?= =?us-ascii?q?BgSABAQ?=
X-IronPort-AV: E=Sophos;i="5.64,327,1559520000"; d="scan'208";a="595320231"
Received: from alln-core-2.cisco.com ([173.36.13.135]) by rcdn-iport-3.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 30 Jul 2019 18:41:42 +0000
Received: from XCH-RCD-015.cisco.com (xch-rcd-015.cisco.com [173.37.102.25]) by alln-core-2.cisco.com (8.15.2/8.15.2) with ESMTPS id x6UIfgVZ012316 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Tue, 30 Jul 2019 18:41:42 GMT
Received: from xhs-rcd-001.cisco.com (173.37.227.246) by XCH-RCD-015.cisco.com (173.37.102.25) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Tue, 30 Jul 2019 13:41:41 -0500
Received: from xhs-rcd-002.cisco.com (173.37.227.247) by xhs-rcd-001.cisco.com (173.37.227.246) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Tue, 30 Jul 2019 13:41:40 -0500
Received: from NAM04-SN1-obe.outbound.protection.outlook.com (72.163.14.9) by xhs-rcd-002.cisco.com (173.37.227.247) with Microsoft SMTP Server (TLS) id 15.0.1473.3 via Frontend Transport; Tue, 30 Jul 2019 13:41:40 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=UIG8llnYgigo69AiH6xkpEIxBebKnce3JIDSS0QIMoIZaxmlUVHFXsI99ogVUQVAMc2MgCxXJDPBMy5Z1lHhcIY39l1r+Lfp2gbyrSiiNbnhDqlYjbYnp4NeykS9QZJ1Yc/c36Em2W/Z7RLTMY4WKH2xEdrTfHLaCCiUdck8mOdgxcQf/JmtIg9kNFATMSuQ8I9Ksq82NFURgnLixiof9H0ovV+GpoHHYczAh0ihhYlmetoehzoKFK62rfQgR/foBOgh5Bg1gtMLXBHUa0/V9yg6Q443CfNSFcHr8zv+nC3t2/XVShqt8QkOe+ReeV3/snTBycBvLfdonMOHy8Vi5A==
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=QnG/pkj6RVPYaikB1XDg2rsTJiUCA8qCn1ZYusfK1+w=; b=iTEvzDJaYpc7IjJq6fUS8g4jrsCcpEQLCOQVR5/03SNNE7gDA+kWYjD1zN6mjeThQuD8fd2rqajO6g1MiHB+ebtdrzo/beA3DENf5nmjsTunwAyOX9KrE4HpS9q+HJd1VwLnsxlqlLS0Ztp2wO1UPjEGQRKh2LsbNS1zM9+lqEelGHMpzc3ubHROJshB36JScyUupAmdq0tmX8BMznpJR+D4pomdOGlax2mpP0829LOQ2d5TUUIYz+gd4bl+Z3jjL/UGiBtQ477DZs4CO45z0G5FCTuURr96O86KAgiIasL/bJj9TCldsiwR8RmGOxNSWUHRu/SLwciuAUt+1qqeNA==
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=QnG/pkj6RVPYaikB1XDg2rsTJiUCA8qCn1ZYusfK1+w=; b=SiSC6VVM02GAlbDXpJ4QQ8EuhmzfXm8wAupZ9ADvacSTyb5L8LwhZ7DdxNFL/5oqTNEJGlzArBd3SFG2eKSFu38+9fz1zujq1cELR3nHdJPv+HwZGtF/g6EStYS+0ia5+I6fz0ShX3wOp89dmiyNt47qZETfEV42PimdHZRkHE4=
Received: from MN2PR11MB3871.namprd11.prod.outlook.com (10.255.180.204) by MN2PR11MB3773.namprd11.prod.outlook.com (20.178.253.160) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2115.15; Tue, 30 Jul 2019 18:41:39 +0000
Received: from MN2PR11MB3871.namprd11.prod.outlook.com ([fe80::4c5:965:c7b7:387b]) by MN2PR11MB3871.namprd11.prod.outlook.com ([fe80::4c5:965:c7b7:387b%3]) with mapi id 15.20.2115.005; Tue, 30 Jul 2019 18:41:39 +0000
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Watson Ladd <watsonbladd@gmail.com>
CC: TLS List <tls@ietf.org>
Thread-Topic: [TLS] Options for negotiating hybrid key exchanges for postquantum
Thread-Index: AdVG1haOE+yO4N1wQQSyYtQ5VKKSwAAHEKmAAAOq4EA=
Date: Tue, 30 Jul 2019 18:41:39 +0000
Message-ID: <MN2PR11MB3871829A35631EE2724335C7C1DC0@MN2PR11MB3871.namprd11.prod.outlook.com>
References: <MN2PR11MB38719A31081434FEF6A84999C1DC0@MN2PR11MB3871.namprd11.prod.outlook.com> <CACsn0c=bmsyDPhTUtCcEv1WnnsR8OmDO67TFTu1aWSxikESOEA@mail.gmail.com>
In-Reply-To: <CACsn0c=bmsyDPhTUtCcEv1WnnsR8OmDO67TFTu1aWSxikESOEA@mail.gmail.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=sfluhrer@cisco.com;
x-originating-ip: [173.38.117.65]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 67fff5ea-e90e-47c3-a87c-08d7151d8f17
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600148)(711020)(4605104)(1401327)(2017052603328)(7193020); SRVR:MN2PR11MB3773;
x-ms-traffictypediagnostic: MN2PR11MB3773:
x-microsoft-antispam-prvs: <MN2PR11MB377353B4389AC6F86AD5F787C1DC0@MN2PR11MB3773.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:6790;
x-forefront-prvs: 0114FF88F6
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(366004)(396003)(376002)(136003)(346002)(39860400002)(15404003)(189003)(199004)(68736007)(14444005)(6916009)(316002)(2906002)(14454004)(33656002)(256004)(11346002)(478600001)(8676002)(6436002)(229853002)(4326008)(81166006)(81156014)(476003)(25786009)(52536014)(86362001)(7736002)(8936002)(74316002)(446003)(66446008)(64756008)(6506007)(5660300002)(486006)(66066001)(76116006)(99286004)(102836004)(6116002)(55016002)(1411001)(66476007)(66556008)(71190400001)(71200400001)(3846002)(9686003)(53936002)(76176011)(6246003)(66946007)(305945005)(7696005)(26005)(186003); DIR:OUT; SFP:1101; SCL:1; SRVR:MN2PR11MB3773; H:MN2PR11MB3871.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: rwiWEOspSen3szane84ZmS6dZoqtTC91u6jYoaJHZrVVBlBfWFn2ES7Zh55DyxWgLR+oO8+yS8rui3YhGL/BDxKq20i39xQBqtoBcpOsB5cfMUS5wRhIw/lIHMPfAs78OnO7JMGGkFan9Fw8PTo43/tbw9s9UJFttTds6BxSZwZDrhLzItjkcsvWk6mFkcy9v8j5OK3vtZ+8VNWDbsNn3ehoAOsO1IcNnu3fWgW8JTvKgBV6M//kLl/RpHxmBTj9SztqXLom2fGJR3QKqs6wiwDtqdgDyOcP0aFXXI1WcjmcwhoM/QYvTOZHOwvtDOINvJ2nzvn8lPwvIZSAi8sWoMR59PHdYhhGGIy1zTdmuKsH18edPJroLUxuAcHxbJwb/fgtSQjWSNnHEQBSrM5uf+luPmKOstqJ03FMOy3Pmtc=
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 67fff5ea-e90e-47c3-a87c-08d7151d8f17
X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Jul 2019 18:41:39.2703 (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: sfluhrer@cisco.com
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR11MB3773
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.37.102.25, xch-rcd-015.cisco.com
X-Outbound-Node: alln-core-2.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/l4bf6X1EzzzGQpmgMjyM7obkll4>
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 18:41:46 -0000


From: Watson Ladd <watsonbladd@gmail.com>; 

> On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <mailto:sfluhrer@cisco.com> 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. 
>> 
>
> 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. 

it sounds like you are questioning, not between option 1 or option 2, but instead whether we need either of them at all.  Those are both methods of negotiating multiple keygroups; it appears that you don’t see any need for such an option.

Perhaps we need to have such a debate.  Here is one opinion (mine, but I'm pretty sure it is shared by others): the various NIST candidates are based on hard problems that were only recently studied (e.g. supersingular isogenies, Quasicyclic codes), or have cryptanalytic methods that are quite difficult to fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed one or more of them, it would seem reasonable to me that we wouldn't want to place all our security eggs in that one basket.  We currently place all our trust in DH or ECDH; however those have been studied for 30+ years - we are not there yet for most of the postquantum algorithms.

Hence, it seems reasonable to me that we give users the option of being able to rely on multiple methods.

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

Actually, I personally don't see the messiness; if the client wants to propose X25519 + NTRUPR653, he places hybrid_marker_1 in the supported groups list, and adds hybrid_marker_1 = X25519 + NTRUPR653 to his hybrid group extension.  If the server sees hybrid_marker_1 in the client's supported group list, he looks for the definition in the hybrid group extension, and processes the policy accordingly.  The logic in both direction would appear (at least to me) to be reasonably simple (and it doesn’t get more complex if we feel the need to negotiate three or more key exchanges).

As for the expense, that is for the user to judge.  If the user decides that he is willing to pay for a series of expensive key exchanges, that should be his decision to make.  Option 1 gives the user the ability to negotiate a series of expensive (but perhaps more trusted) algorithms, it doesn't mandate that the user do so.

And, as for a need for a hybrid scheme (either option 1, option 2 or something else), I do believe that there will be a demand for it, even after NIST and CFRG has given their blessing, as their will be users who will not fully trust a new scheme that was just endorsed (but they do want some protection against future quantum computers).