Re: [CFRG] Modifying SPAKE2 draft for more curves (was Re: Attack on a Real World SPAKE2 Implementation)

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Mon, 10 May 2021 11:25 UTC

Return-Path: <Feng.Hao@warwick.ac.uk>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8DA2E3A18FC for <cfrg@ietfa.amsl.com>; Mon, 10 May 2021 04:25:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.327
X-Spam-Level:
X-Spam-Status: No, score=-1.327 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, URI_DOTEDU=1.273] autolearn=no autolearn_force=no
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 m9AWLxCr9Z1d for <cfrg@ietfa.amsl.com>; Mon, 10 May 2021 04:25:01 -0700 (PDT)
Received: from EUR01-HE1-obe.outbound.protection.outlook.com (mail-eopbgr130070.outbound.protection.outlook.com [40.107.13.70]) (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 3292D3A18F9 for <cfrg@irtf.org>; Mon, 10 May 2021 04:25:00 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=gskc45WLgOQt8L6SzMZjYeQnlgjUjfVRNqYvaQQMRqIz9NYs67/zWNwG7RcbNwKJDFyj/9IEVvrbFbLZUNIG9wm1HomFucE/2dfxbO43DtJSB+KAoCla4r61WZTDnD6Yyd0fr4GIG5cwZAw/uwGQrUvyyqkYqarii0PUWL89mMjfQM3uyEMOLoYl/xFidM+waHh0MIiHk9zpQ3V08Fdt8jK/Ki/fjI6perLPlUTeu+MAHePaeljlvvFr51pOKN2zsmo8yYAqeSoZZbAF8dJySiJdB3RipQGecOFSO6BnhBwUuRR0QQOyp6z9aVmdxIqrXe0i+tfEbPb1dWokDkuuTw==
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=81dmL6l8RnHxrgY4VauzgYX7DecJm/lCk8jAbnaWV80=; b=XHcVEWQlj/Xk1hFThj7n6FylGuF3c132z/gmk4xRC/eugufRwwuM4cEh14SfhidLkObpevv0kjwK7zyLw033fSAKBkkJVTCSkjIu/zce2ihudukrAeufIXEATOtjKi3wfDRd3tfQJ7hcxwzqinVc6XJstqDa8w97AKH425DTD1fsWskkWNJP2Xex/XJms3Ai6/REw4WPuDs0Z/x1Niu0xrpTx7+7ZFWi+29/Man0btGmK+v756ppOiFHzhBvB5uQLDLoFfHWgaalH64xIdlAwtqwoBr/s2X+V0IMJD9a1V1DRrA7Y37P8ykIr+zmbAG05x6eEQipR6fvm2PxZ/a/9Q==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=warwick.ac.uk; dmarc=pass action=none header.from=warwick.ac.uk; dkim=pass header.d=warwick.ac.uk; arc=none
Received: from VI1PR01MB4285.eurprd01.prod.exchangelabs.com (2603:10a6:803:65::27) by VI1PR01MB4798.eurprd01.prod.exchangelabs.com (2603:10a6:803:8d::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4108.24; Mon, 10 May 2021 11:24:57 +0000
Received: from VI1PR01MB4285.eurprd01.prod.exchangelabs.com ([fe80::a40d:fa46:a80a:610c]) by VI1PR01MB4285.eurprd01.prod.exchangelabs.com ([fe80::a40d:fa46:a80a:610c%7]) with mapi id 15.20.4108.031; Mon, 10 May 2021 11:24:57 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Watson Ladd <watsonbladd@gmail.com>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Modifying SPAKE2 draft for more curves (was Re: Attack on a Real World SPAKE2 Implementation)
Thread-Index: AQHXRUcchdwzpYPiKkmQL3KaoNTJzarcfWLU
Date: Mon, 10 May 2021 11:24:57 +0000
Message-ID: <VI1PR01MB42853A2FB1564C1F08DDF5E5D6549@VI1PR01MB4285.eurprd01.prod.exchangelabs.com>
References: <2bfbd767-b93a-42bd-be7d-1dae9e32e555@ruben-gonzalez.de> <SY4PR01MB625110F1F7633D989FCF183EEE579@SY4PR01MB6251.ausprd01.prod.outlook.com> <e88bae26-ff1f-42e3-babf-c5de3ee1d781@www.fastmail.com> <e47d0509-2b47-b811-7fd5-8846c11dc055@web.de>, <CACsn0c=6FgTHzTp7zuFri-gSYG3dBr6sASBMH34mBO5YDE7Ejw@mail.gmail.com>
In-Reply-To: <CACsn0c=6FgTHzTp7zuFri-gSYG3dBr6sASBMH34mBO5YDE7Ejw@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: gmail.com; dkim=none (message not signed) header.d=none;gmail.com; dmarc=none action=none header.from=warwick.ac.uk;
x-originating-ip: [86.1.162.194]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 38196bd5-6c39-4221-7d94-08d913a63dfd
x-ms-traffictypediagnostic: VI1PR01MB4798:
x-microsoft-antispam-prvs: <VI1PR01MB4798538AB96EE1F0C8613421D6549@VI1PR01MB4798.eurprd01.prod.exchangelabs.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: wcadaraFsbKfdxkGzfmwdF+6BMJuOU7MYIr5Rvb7YF21O5bh8rYLI7mjrqc3lOuDGVFehoLeORlH/Tel1WWpGopJe9Ta5Kk1fnPo2q/FMIfGidsZljOXke8Cik0v1V3VY6S+qlfWLIwkhiGVmJRQZoQtc56ZoaxjRnrEP4vx7j507kjbMuSlGxj/abd+5odnrl2N5YlrpOd+pjCo+phsm2OimCIaakP9SW0mLmYwhWTJixRdlLVzuz2MlTBVNSjh86fBPeiET9XN5awFb05eeL3Jl5o8MoH3w1ScVYjZY9qIWC7K14arb9x8fKejavh4Ly7oPksIBadm3TibwHP0TBI2uB/v/G31XDk5fwZHSnkOC24fmDBKjONXVS91Ld0bNBIoXLewqu46VVe4J7z4yzeAxwA9NmhxTfUCbMm5bhfZRdJP8xYimgeDqL0EGcQl+QvS4glwi61sEiPl94otrZoa+mRdtMLL17L9QQRxCMxMQpzbbdu5Ixd2GQb+ICbOxd5KC0X7fmyB6A8SWzTAfdfDjK8kGTL3z4G/0v3yUPZwye4hE1DzjtCS1eWZl2x+rxrY9klWQNYacz+gWAJYC5MqEhawKkae9u5+2+avqI7CrqkN+a2T+O7ZcatcFeGDT13ahBNmXE9k9RikBEK/85OfIAS0SzDZdpnQGb2b7CHU6M9EMWWa+tC7gfChbseu
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1PR01MB4285.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(396003)(346002)(366004)(39850400004)(376002)(136003)(38100700002)(2906002)(6916009)(66946007)(4326008)(66476007)(66446008)(64756008)(316002)(66556008)(55016002)(76116006)(786003)(8676002)(91956017)(86362001)(52536014)(122000001)(83380400001)(9326002)(5660300002)(166002)(7696005)(8936002)(33656002)(6506007)(71200400001)(966005)(478600001)(26005)(9686003)(186003); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?/uFDFhbalCsZYKF/zSW4vP2zwTucTZPfs3mPwwa74Q0/TwpGAXopsJ+D?= =?Windows-1252?Q?SjJip4THQg5qYAf7zrBnohomxyYesofwnRa831Y9s3oy7uCFxJi9nwqw?= =?Windows-1252?Q?JIYQcoOWRyjK/Uz8Ddbif1ms6h1BKNUmnrQ/+70eTfh6L9YHbfbeW7Re?= =?Windows-1252?Q?2jPcVFohz8c1WjMs3S/7YgseFS7BTZqWNPViltsZeEFam18VwE7jl6ZT?= =?Windows-1252?Q?4fzK56rkhcaas43yLqCeQAXz4cxgGBQtH1s19IEigMlxLwWijTT7msfo?= =?Windows-1252?Q?vm9l06xWpKD9Tb60OFkxXRslWolucUz/86/CzdfGwWhUxIqQLTzzKYnI?= =?Windows-1252?Q?xGeDlwMxU9oM3MWcxFsLKJEQepDaRnzf/1TpkbWw9G3T8L8xkxxT77oe?= =?Windows-1252?Q?RmKpLuSfo/XAcaNq/G6tMg/fW4E8eumgI8kGWYM6u9H0ZXcXTg6A5VoZ?= =?Windows-1252?Q?hyVblz4BBuURC9lj8Y9QP/ySXCqLL1on/4k+e3wcuIOF/nLseXekSiXk?= =?Windows-1252?Q?wfiM9Gg6MbDJu/hYRaGyD9GcR+hrHcTMkyOfLxgxc88d9iP63aPDMezj?= =?Windows-1252?Q?oZFqggSUuTWjX/XwTg1/FN9eDQE74JogzKdBxEDODJd0obmgDc1MAwSE?= =?Windows-1252?Q?pO/FUChypAB5MqjzbRau54W14lzIptRmAZxx9RIsoccghgByt8YSqbxO?= =?Windows-1252?Q?z84XvBeytH+w+3BhUw9te4RUbrbBbMOBJ29svxSzE3nH9fxTwr9BI5g0?= =?Windows-1252?Q?6Bm7eeih/CwTXvM8xJ2ke5s1RCdPeW0SGSMTtRtew4nuSZOuev5PeXYb?= =?Windows-1252?Q?Zda5WUkDyCVf3xXVdXd4pcJxvhocxdUkVkEkEfkg7rait+QtmWaNOSAc?= =?Windows-1252?Q?HcCWKkMmJw4jDtGMSL+ajxbZlYMhbsbXLi7xh59wVKF1lYPMT/CAbcOj?= =?Windows-1252?Q?xA+GtivQm10R4UOPB7AvssJiGJ+aR60Cjz9x2CsNGWMWHyo8E+c5K/hN?= =?Windows-1252?Q?aZV/or8z9z1uzn0zmqo9+8T2t6UTr2hAXXC1Rd/UBGQFb2gFjZCYuxWk?= =?Windows-1252?Q?gNUwAyvp18TXGVfYA8oRVBlbHBGZeMTG/z58k1kRHTxF0hNQwQ0odwyD?= =?Windows-1252?Q?J03Fa4ClGfHCyUiEXAvkdgDZgwe/hgbObYX9vQGJR2B02VckDM3QUp43?= =?Windows-1252?Q?wTQK4Fe8h2ctKaONBvZw6MPu2L3FMKM+CUKSs5TeAJfQXqENLKcF6VpT?= =?Windows-1252?Q?5fthJLG+qFHPpsVnC37JrtYaEoIkTrxv0rf7zlzVu47HpEh+RlWp8J6/?= =?Windows-1252?Q?Je6b/w+/ALGuO5cgmQuROG8TzWONFaXIs1EcTlGncb0oOrTUghWLFetc?= =?Windows-1252?Q?8EdjEqDDpkHIScyDg3UJ4LBhOsiDWISI6+OAdwxCV+j2e4jB/xSjs297?= =?Windows-1252?Q?9SIYPfsfOtl2Zi6OcKcuLw=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1PR01MB42853A2FB1564C1F08DDF5E5D6549VI1PR01MB4285eurp_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: VI1PR01MB4285.eurprd01.prod.exchangelabs.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 38196bd5-6c39-4221-7d94-08d913a63dfd
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 May 2021 11:24:57.4667 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 09bacfbd-47ef-4465-9265-3546f2eaf6bc
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: ddLkQsc7BLibApHIuDQ7xRv+vEOmAxNv5ZdDikvRFUKBNxHIrUv0S9qAo7SmNQv2Y1psokclKHhRQfEHK+JPYK9aLuL/DpTsnk9KguT0IUg=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB4798
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/fjeJSikdXxT0Z0Vbr5QOPbYKUcs>
Subject: Re: [CFRG] Modifying SPAKE2 draft for more curves (was Re: Attack on a Real World SPAKE2 Implementation)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 10 May 2021 11:25:07 -0000

Hi Watson,

I had some comments on the SPAKE2 draft, but I didn’t know how they were addressed. Maybe there is an implicit feedback loop that I’ve missed. Anyway, I had another look at the latest version (v18). I think the draft can be improved in a few places. The following comments are for your consideration.


  1.  Section 3.1, “Let G be a group in which the gap Diffie-Hellman (CDH) problem is hard.”

Do you mean GCDH instead of CDH? It looks a typo. It’s worth noting that CDH is assumed in the original SPAKE2 paper [1], but in the updated version [2] that includes the consideration of forward secrecy, the assumption has been changed to GCDH.


  1.  Section 3.1, “In the case of a composite order group we will work in the quotient group.”

How exactly does the protocol work in a composite order group? This is not consistent with the statement that the proposed protocol operates in a prime-order group, which is also stated in the original SPAKE2 paper.


  1.  Section 3.2, “SPAKE2 is a one round protocol to establish a shared secret with an additional round for key confirmation.”

This is not precise for two reasons. First, “round” has an established definition in a two/multi-party secure computation setting which refers to a step that parties can do without depending on each other. The order of the items in the KDF defined in SPAKE2 implies a sequence of actions which cannot be done in one round. Therefore, strictly speaking, it’s 2-round. But you can also say it’s 2-flow, which can be completed in one round trip. I think the one-round trip is what you wanted to emphasize here. Second, the one-round trip, as stated in the original SPAKE2 paper, is based on treating the explicit key confirmation as an optional step. But in your draft, you have made it mandatory (see my comment later). When a mandatory explicit key confirmation process is considered, the SPAKE2 protocol should be 3-flows (or 1.5 round trips). I suggest the technical claims be made more precise.


  1.  Section 3.2., “Both parties MUST NOT consider the protocol complete prior to receipt and validation of these key confirmation messages.”

This makes the explicit key confirmation mandatory, which is different from the specification in the original SPAKE2 paper. It’s fine that you change it to “mandatory”, but you need to consider the implication on your claim on round-efficiency. These need to be consistent.


  1.  Section 3.3, “To begin, A picks x randomly and uniformly from the integers in [0,p)”

I take it that you mean [1, p] instead of [0, p]? I don’t know what 0 means here. The spec for B on choosing y will need to be changed accordingly.


  1.  Section 3.3, “Both A and B calculate a group element K.  A calculates it as h*x*(T-w*N), while B calculates it as h*y*(S-w*M).  A knows S because it has received it, and likewise B knows T.  The multiplication by h prevents small subgroup confinement attacks by computing a unique value in the quotient group.  This is a common mitigation against this kind of attack.”

This is confusing. Why do you multiply the value by h? Given that the public key validation is done properly on the received item, the multiplication by h appears not necessary at all. The statement that “The multiplication by h prevents small subgroup confinement attacks by computing a unique value in the quotient group.” Is potentially misleading and should be removed (more comment on public key validation later).


  1.  Section 3.3., “If an identity is absent, it is encoded as a zero-length string. This MUST only be done for applications in which identities are implicit.  Otherwise, the protocol risks Unknown Key Share attacks (discussion of Unknown Key Share attacks in a specific protocol is given in [I-D.ietf-mmusic-sdp-uks]).”

When the identities are implicitly known, is there any reason why they cannot be stated explicitly? Allowing an empty identity introduces unnecessary risks and only invites implementation errors and attacks.


  1.  Section 5, “In addition M and N may be equal to have a symmetric variant.”

It’s very vague. First of all, you didn’t define how M and N can be equal. Second, if M and N are allowed to be equal, why you still have the M!=N variant? The more variants of a protocol that you introduce, the more likely the protocol and the implementation may be attacked.


  1.  Section 5, “The security of these variants is examined in [MNVAR].”

This is potentially misleading. This gives the reader the impression that the variants that you describe in Section 5 have been examined in [MNVAR], but I don’t think that’s the case. The option of M = N is discussed in [2], but not for the per-user M and N setting as far as I can tell. You need to give an appropriate reference for the security analysis of the variants that you describe (to my knowledge, there is no such reference, but I may have missed something). If you refer to the M=N variant for the main protocol in Section 3.2, then there is a question, why you can’t just use M=N for the main protocol as it’s simpler? In general, having lots of variants is not a good idea, and should be avoided as much as possible.


  1.  Section 5, “This variant may not be suitable for protocols that require the messages to be exchanged symmetrically and do not know the exact identity of the parties before the flow begins.”

The SPAKE2 protocol is not symmetrical. So “exchanging symmetrically” is not applicable here. The variant can be of course be used in the scenario you describe. It just needs an additional flow to send the user identity. This implies that this variant can’t be completed in 1 round trip. It’s best to be explicit on these to give the reader a full pictures.


  1.  Section 7, “A security proof of SPAKE2 for prime order groups is found in [REF], reducing the security of SPAKE2 to the gap Diffie-Hellman assumption.”

As said above, the proof based on gap DH is in a different paper; see [2] below. The reference should be updated.


  1.  Section 7, “The generation methods specified in this document are designed to eliminate concerns related to knowing discrete logs of M and N.”

I suggest to use “mitigating concerns” rather than “eliminating concerns”. Given that M and N are static value in a global setup, once the relation of the two static values becomes somehow known later, the system will be compromised without the users being aware. To address this threat, you might need to update the M and N values regularly, say every few years. A procedure that describes the regular update of the values would be useful (which may include some time information in the hash).


  1.  Section 7, “Elements received from a peer MUST be checked for group membership: failure to properly validate group elements can lead to attacks.  It is essential that endpoints verify received points are members of G.”

It’s good that you explicitly mandate the group membership. Given that it’s a crucial step, I suggest you give more details on how the validation is done. You can refer to Algorithm 6, in p. 25 of [3] for the steps to validate a received item. The Algorithm 6 is described for ECDSA, but the same applies to SPAKE2.


  1.  Section 7, “Some implementations of elliptic curve multiplication may leak information about the length of the scalar: these MUST NOT be used.”

A bit vague. I would suggest you give more details on which exact implementations must not be used.


  1.  Test vectors

For cases where the user identity is an empty string, these should be removed. The user identities should be explicitly defined. An empty user identity string will only lead to confusion and potential attacks.

[1] https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf
[2] https://eprint.iacr.org/2019/1194.pdf
[3] https://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf