Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Fri, 09 April 2021 20:09 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 AB65A3A0B59 for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 13:09:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable 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 vseU0pOfmNB0 for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 13:09:06 -0700 (PDT)
Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2056.outbound.protection.outlook.com [40.107.21.56]) (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 B39D23A0B56 for <cfrg@irtf.org>; Fri, 9 Apr 2021 13:09:05 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=EaVtsbNOUHap6je3CIquT3TCvm09fzE6/nzvVqXsMAOa62oK/NJLxM7Ziib0B2k7I7rUzRmIMS16A7zzM+QWBfQjK3Xh8QpBpb7txoupw+uJXCon2WmestXThGOgPymwPBzN5NAFDZ3X1Lp/SEfelKis9bTwTm9gwWDRj1TxYkeyLIwUnXfhQ6UPBvSi336CiEju+uF6PWYxhXtoeX/asf2eaiXZkWvQ/iyiPketd0iXJg3HZLXPCKKtNgB6FCbfmDdBUFpFSpSD7DCed8/Y2TbokKSlCTfSocdQdQ8MGcDTls/0DhIFIF5gcgwGLQz52MgjvltbFcn4bdXLftn2rg==
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=lI9UAE3E/yWGfVreIBu+iPr9NPnex1BwUKY9i6FBOw4=; b=HyZ7jDkeKGXaFfRJPg/PsDXTXxnsSUdzQC2IlEXuk5w1aDfFll1EDtUsFVp+XFpP0aDZEmhp3d5fj69NuoAEI0jcs18l758nyI6UqJ7NVyrSnYMe4M2ZeA6epOTWnPEmLyUUxvyowEiNzpxRz9jTYYMGD4NisFJzrk5yHBKtB9IYxs9Xohq4hWyRouHCE/WPmZBxcno5Je0E4K06XotddtQ0HeiLowHR8deXwdEaqf/1ZqXAfai5iaWHzRC0N8e+cKrLphBZTuVg/M2AdOUhVrpLDeXSq6TzKS19htTQ5UGj8EBHeeptOeIlMzjaesOIGVVlZ1LUPnVOPqjLqoOaug==
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 VI1SPR01MB0357.eurprd01.prod.exchangelabs.com (2603:10a6:803:8d::12) by VI1PR0101MB2480.eurprd01.prod.exchangelabs.com (2603:10a6:800:52::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.18; Fri, 9 Apr 2021 20:09:02 +0000
Received: from VI1SPR01MB0357.eurprd01.prod.exchangelabs.com ([fe80::5865:9e5a:626f:8953]) by VI1SPR01MB0357.eurprd01.prod.exchangelabs.com ([fe80::5865:9e5a:626f:8953%4]) with mapi id 15.20.3999.032; Fri, 9 Apr 2021 20:09:01 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, "Scott Fluhrer (sfluhrer)" <sfluhrer=40cisco.com@dmarc.ietf.org>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsQ0gAgAADtICAAAg2loAAGaoAgAAVuYCAAAJqgIAAB5lAgAAIdACAAAW8/A==
Date: Fri, 9 Apr 2021 20:09:01 +0000
Message-ID: <VI1SPR01MB0357E3DA99C4A4357E4E536ED6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <d0778523-5f5d-4327-b795-279918c1899c@www.fastmail.com> <CAMr0u6=PBX1W5zQFmpxKQ=ViUXN9QK00BREL4M0=2HOkaXaiZw@mail.gmail.com> <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <4590aaa512acf5a482c9890ebe48f1760e5831a5.camel@loup-vaillant.fr> <F9593D27-3244-470E-89BE-85215B2DC9E7@shiftleft.org> <VI1SPR01MB0357AE729116A79C8DF70516D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <6F4F0566-3465-4C9C-8993-1B3FDFDDD792@shiftleft.org> <BN7PR11MB26410E0EB14DFE5DFB4B4F6EC1739@BN7PR11MB2641.namprd11.prod.outlook.com>, <BN7PR11MB264116DF63B9930B6C421DEEC1739@BN7PR11MB2641.namprd11.prod.outlook.com> <VI1SPR01MB03579AD8C245CD62078DF831D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>, <BN7PR11MB26412EA5842D1B166C1F740DC1739@BN7PR11MB2641.namprd11.prod.outlook.com>
In-Reply-To: <BN7PR11MB26412EA5842D1B166C1F740DC1739@BN7PR11MB2641.namprd11.prod.outlook.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: cisco.com; dkim=none (message not signed) header.d=none;cisco.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: 91d6fce7-8db4-4480-0c4b-08d8fb93517e
x-ms-traffictypediagnostic: VI1PR0101MB2480:
x-microsoft-antispam-prvs: <VI1PR0101MB24809CB2CD1E518D461E83ECD6739@VI1PR0101MB2480.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: /4XonVCEmHiP8TVhxepohzvRWZfZH2l7FckT7Pd1Fontakw9jQzp8abxxT8wpb4rirO5TgG2r8aJ3Pq0up/R5OnTg/BFDJU4rKGkZDvYCrm0J36M8HL5mn2A+oFr2peOBxj6c8JCuUiwLPc6x17BFUqqb1+YythQYahRR3CEono9racp3W+/wY8vJrP+PRJVGSVvRQBBQ9RuxSAVWvVVqRWc0UKf5PTV0PGUTEgYuzK7RhJF9kp6yyS9+gzQx/TS2TIVFC7cykAKYC34QSkuY5HBP0QLjgumic0QwKRyHtBvvwsnEaNzMnuDcotT8e/AAZbJ5E1InOu0vEK1ZX4c9/4S+YimQspaUiPnY5AiAC7/CWen0PpQEX0fWv0uMWXC7z7uNl7XmDCew4dQ5QfAG/TIpdM9hMjyoIvzMaRoxW+zOJMfynUhS+tspW/6YHcZMuBa3wsPItNrMYXIjlvUvMyH/V3UJDPn/lAs4I+vCbr2dAEClsjZYOATunIijFoponef/h44v7N5sCu/dlzUFYdU1GpBIH1/aKvPCCBK8LRwM6MoCO+k649uTVVJFtPWu4qKpWvr1KfCOBkPmH8VVnP7NksZKYnOlBb8NaT3uKNBGFABuaLXbpC8JJudAxmzmHfJdDEB2pOQ5Lt5kiDLqycutO39udLVP25vx+ahH8E=
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1SPR01MB0357.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(136003)(396003)(376002)(366004)(346002)(39850400004)(2906002)(8676002)(52536014)(7696005)(71200400001)(186003)(6506007)(8936002)(26005)(4326008)(478600001)(66446008)(64756008)(91956017)(76116006)(83380400001)(66556008)(66946007)(86362001)(66476007)(38100700001)(316002)(786003)(5660300002)(9686003)(9326002)(55016002)(33656002)(53546011)(110136005); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?IPFbDvgyvRq7QVjuA0AJGhkRMxEbDdQuRDmL60MVvo80ARnrY52qtxAM?= =?Windows-1252?Q?9E7bllKKGSsrFcR2WPLlZLIZjv3Yky77VDoE9TWtXoMX+Kz/2CKwZJ3w?= =?Windows-1252?Q?UnH70+nSPRy8/Hh12ohMOo7drkasV6LYI+zxqK9yMyVsn8h02oHJUllN?= =?Windows-1252?Q?Ud4hLoscjhYaUDUzCDQVt319wz9oxHwqj96UYJ/Xmt5zU/oCL4B6om2B?= =?Windows-1252?Q?SMAk0SFce6jbW6FfMZU//EsjDgVVhrCmh+JiGXYx9dbZm77zdZGWojNO?= =?Windows-1252?Q?vwN831SdlsJpKc+Yx5tESTviRiddwknfVStrfgV+yuwpWzevOHMuaBmM?= =?Windows-1252?Q?pjON3TBdl+lNCz+3POiXwoVpCFeqKKVS1SVsVtUOcChuY+BjJT4PnxAe?= =?Windows-1252?Q?t1FA4UvlmH+7k1YPPOyqL69y8TpDN89KF1jaPJN1psNo7XYqsTILtCod?= =?Windows-1252?Q?N+HLZE6iLmct2HOiY5z44fLa9b/t3r4xFJg8fWALyHxMbNNRd3+mWKBU?= =?Windows-1252?Q?R0Uoq9C8dDdq1e2PUmXq9VmewklsXR5LFHFWx5F40b8rLx48gpGQmgp5?= =?Windows-1252?Q?CC4HuAEFQtu/KKhhVJBEiP9ShpZX4irKesGXWMs3kQh4cUxwGh3MXV0g?= =?Windows-1252?Q?vNYS68H6t6JezhKgoVkpfhDMCRKN8su8chWjC38bx3XVL6I1x10NJtqq?= =?Windows-1252?Q?jLxcPMvYCyAnK1bbIp8PKy0bAYRppX0rAP3mqf/ka65uqHuJhJ1iAAsg?= =?Windows-1252?Q?hb47ewaFozODsS8ETrhkY27+k+0FnRndXzU5jZsh4WxDDxekaqVlXWDe?= =?Windows-1252?Q?dqDK+AdjwCzu7b+B7X6EqUT3Xgjm+6CoLmfcVjb+zeBF7h9dyu1Ivj7t?= =?Windows-1252?Q?LnYyIGev6vEkY9cQYbC2AERqx9RycVxM4mc6HhzNHVTEZmf0Cmk5K7Jw?= =?Windows-1252?Q?zEdRzMdeLwuB+AIaDmjdUFnpA/+xp8At59cV6WIi0Q3zARu7M6k/qIfx?= =?Windows-1252?Q?lrK9+SVAQjoYt40KNnD8oIdov3j6PnoWgYxGia66A8UBUA4f1YexglmC?= =?Windows-1252?Q?AT/D17LsyQf2tDLF7Sca/QHMYCJIECAPwTwFLT6qfyMZHkNqpeYSPyz9?= =?Windows-1252?Q?6AUgSR9z1/rMrNmx8aWLpQP9+Zqtt3nT/5Wczo06C64CJwVtpuB2DqXP?= =?Windows-1252?Q?hXdX3Gs1w1bHBrihXC7QnVKDpVTA6CNH+E0v1OroemnLuKhIG9TU1psV?= =?Windows-1252?Q?nI72jkB8ZQLhnYewGGWj9vIxhJ1UElT5o6xYQRZvxbG9o8WqwVj1PFNX?= =?Windows-1252?Q?iSGp8lw+CHTS0tD1HTA4CLeRAmUFvfKwRe3h6BCjJeH6yDM9iUP+e3iy?= =?Windows-1252?Q?C2la6tJ0WjWyph4aHIy3pc+j5CLQqBofMX2A+ZNXQm7sOLZv8wsB6w6X?= =?Windows-1252?Q?xoIGneqgBU8NhUsDsnXX1A=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB0357E3DA99C4A4357E4E536ED6739VI1SPR01MB0357eu_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: VI1SPR01MB0357.eurprd01.prod.exchangelabs.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 91d6fce7-8db4-4480-0c4b-08d8fb93517e
X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Apr 2021 20:09:01.8055 (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: njjU5I0xA0YwiFB1SaOsacldHC4xiFFk02sRUD/yF+TLjdXaVrVE7IEoTeGGpzixwYChNR6CnyY70yo2C6vjL4a/gaRttLe45kln3gJ64z8=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0101MB2480
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JJXFk3CsEuIhOPgWnaqMd0ypYZs>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
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: Fri, 09 Apr 2021 20:09:12 -0000

Hi Scott,

Apologies if I didn’t make this clear. By the timing side channel, I mean an “offline” attack. The fact of rejecting/aborting (or delaying in responding) reveals that the password (maybe with some auxiliary public data) is hashed to a low-order point. Given that low-order points are rare, offline dictionary attacks to recover the password will be trivial.

I’m not claiming this attack must be practical. So far it’s just theoretic analysis. I’m highlighting here the possibility that what the mapping functions returns may be a small subgroup and that can significantly mess up the security proofs/arguments (and cause real damage in practice if the attacker were able to directly influence the input to the map-to-curve function as Rene pointed out).

Cheers,
Feng

From: Scott Fluhrer (sfluhrer) <sfluhrer@cisco.com>
Date: Friday, 9 April 2021 at 20:23
To: Hao, Feng <Feng.Hao@warwick.ac.uk>uk>, Scott Fluhrer (sfluhrer) <sfluhrer=40cisco.com@dmarc.ietf.org>rg>, Mike Hamburg <mike@shiftleft.org>
Cc: CFRG <cfrg@irtf.org>
Subject: RE: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Is this a nontrivial concern?

Both CPace and Opaque are PAKEs; what that means is that if the attacker has a guess to the password, he can verify (or refute) that guess by performing a single exchange with the honest server.

So, if the user selects a password with 128 bits of minentropy (which is a far better password than what almost any human would use), that gives a 2^-128 failure probability against an attacker that tries just one exchange.  This probability is inherent in the system, and (other than asking users to use even better passwords), there isn’t anything we can do about it.

In contrast, what it the probability of a hash-to-curve generating a low-order point?  If it is (say) 2^-252 (I don’t know the exact probability; that is the approximate probability of a random Curve25519 point being a low order one), then that is far smaller than the inherent failure probability already in the system.

For PAKE uses of hash-to-curve, that wouldn’t appear (IMHO) to be worth worrying about.  Of course, this logic need not apply to other uses of hash-to-curve…

From: Hao, Feng <Feng.Hao@warwick.ac.uk>
Sent: Friday, April 9, 2021 3:01 PM
To: Scott Fluhrer (sfluhrer) <sfluhrer@cisco.com>om>; Scott Fluhrer (sfluhrer) <sfluhrer=40cisco.com@dmarc.ietf.org>rg>; Mike Hamburg <mike@shiftleft.org>
Cc: CFRG <cfrg@irtf.org>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Hi Scott,

It’s not a simple case of testing and aborting. Suppose in a system, hash-to-curve returns a low-order point to the higher protocol (say CPace/OPAQUE) that is calling it, you can’t accept this value (insecure base generator) nor can you reject it (timing side channel will reveal the password). The failure mode here is non-recoverable.

Cheers,
Feng

From: Scott Fluhrer (sfluhrer) <sfluhrer@cisco.com<mailto:sfluhrer@cisco.com>>
Date: Friday, 9 April 2021 at 19:26
To: Scott Fluhrer (sfluhrer) <sfluhrer=40cisco.com@dmarc.ietf.org<mailto:sfluhrer=40cisco.com@dmarc.ietf.org>>, Mike Hamburg <mike@shiftleft.org<mailto:mike@shiftleft.org>>, Hao, Feng <Feng.Hao@warwick.ac.uk<mailto:Feng.Hao@warwick.ac.uk>>
Cc: CFRG <cfrg@irtf.org<mailto:cfrg@irtf.org>>
Subject: RE: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Correction: Opaque does use a hash-to-curve operation (used to translate the password into an elliptic curve point); if it happens to translate a specific password to a low order point, then that specific password is easy to test for; however there are no other implications…

From: CFRG <cfrg-bounces@irtf.org<mailto:cfrg-bounces@irtf.org>> On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Friday, April 9, 2021 2:17 PM
To: Mike Hamburg <mike@shiftleft.org<mailto:mike@shiftleft.org>>; Hao, Feng <Feng.Hao@warwick.ac.uk<mailto:Feng.Hao@warwick.ac.uk>>
Cc: CFRG <cfrg@irtf.org<mailto:cfrg@irtf.org>>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Opaque doesn’t use a hash-to-curve operation.

CPace does; it also automatically aborts (fails) if the hash-to-curve operation happens to return a low order point (that is, a point that, after multiplying by the cofactor, is the neutral element).

From: CFRG <cfrg-bounces@irtf.org<mailto:cfrg-bounces@irtf.org>> On Behalf Of Mike Hamburg
Sent: Friday, April 9, 2021 1:00 PM
To: Hao, Feng <Feng.Hao@warwick.ac.uk<mailto:Feng.Hao@warwick.ac.uk>>
Cc: CFRG <cfrg@irtf.org<mailto:cfrg@irtf.org>>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

I don’t know if the same holds for OPAQUE or CPace: for all I know, they may have specification holes and/or end in failure in that case.