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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sun, 11 April 2021 18:59 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 8B5333A199D for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 11:59:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 TURa38CrPndQ for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 11:59:13 -0700 (PDT)
Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2050.outbound.protection.outlook.com [40.107.21.50]) (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 74FCE3A199C for <cfrg@irtf.org>; Sun, 11 Apr 2021 11:59:13 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=EsNZfY4BPw+XvChF1FrjxbBoVrRL5gPZkkcDO3JuEzYVBb2oWt2WxOBXqH7mCUWKx5gOGQbzgg9NfykPw5f7mRlhWRiJEcgbkNAfjnJ+pRipx6xoWp95Rbb49ajxZJw/2q5fC2sMHXY9p6hENhxYlYlolL+8tnIask+pOVyxpWPoKXw5RHRWbbTbP5T5SzZ1LnfERX/Oet/p4qD4zu4o+NKY91qf9frzrOpjpWBzICWNEdXPICOzODDYd0bhiUsrOhkvA3s1+Jej9cC4Ksg5gYh1dawINwQF2COu2mmY3Y3Qp68JjtFG+Jv14eds9GMWK6D8Zk8bdCiZWZlwq0u8Qw==
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=fkeusVpM3kl4m3mDxXu809cqdBEHr7pshcFMyX/AVQU=; b=Xsc3O39u4rpgc3IJL5u8Up5Tuv69VN2ELr6FHPkchXd+LKgIAKecCO8NYpvKYbA5oeO0QTgYjK2ck+GI8z7aw4cXJ7TUovLYamEtTexHNo7/2fTOJfBQNkMHlpL9n+QhlUnvD1RgnS8Cb/qJMDp8efwa3M19gcJRsh+lo3YqG9esb494d+xuEwFX49nPcM/Yo2HEvPv/NpIiI4xWsOWUDK0pkUImJmrak9Nh4V3MMhxCDJ9AaI8YjoG/dPWA0tjf7Vwq6a3q2cP1FrCC0NtUAc5tFyCCnTMKbTDyqJuizsCg73RUUXR9bP6bIdO9WhE47efHAkfoNENA0s9KFAVvTA==
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 AM6PR01MB4278.eurprd01.prod.exchangelabs.com (2603:10a6:20b:23::18) by AM7PR01MB6867.eurprd01.prod.exchangelabs.com (2603:10a6:20b:1b5::9) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.16; Sun, 11 Apr 2021 18:59:10 +0000
Received: from AM6PR01MB4278.eurprd01.prod.exchangelabs.com ([fe80::44c0:8247:69aa:bcd3]) by AM6PR01MB4278.eurprd01.prod.exchangelabs.com ([fe80::44c0:8247:69aa:bcd3%5]) with mapi id 15.20.4020.018; Sun, 11 Apr 2021 18:59:09 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Mike Hamburg <mike@shiftleft.org>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsrj2AgAANMx6AACTDAIAAhZzVgAB3mgCAACW5gIAAKQYugACNaACAAE7ZD4AAWGOAgAALF4CAAD0U8A==
Date: Sun, 11 Apr 2021 18:59:09 +0000
Message-ID: <AM6PR01MB42783039E9763256D157973AD6719@AM6PR01MB4278.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> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <VI1SPR01MB035772443E4DA3206E4CD4D3D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <7944D4F1-81F8-44FC-95D1-45D47733B385@shiftleft.org> <VI1SPR01MB03574E592790FD59C1ACEB84D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <20210410151254.7ze5pt4lpvblhk3f@muon> <CADi0yUNo7o07qM2Qw8yd_eVw_-cM-9wNy3CrLw_Pif79oD_+Og@mail.gmail.com> <VI1SPR01MB0357253A9BA2C2544D6B3F51D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <CADi0yUP-Q-bjmDn-RpiVkns4c8ruK97SidFycg1cPVPJvdFB4w@mail.gmail.com> <AM6PR01MB427851BEC3094FB01902DA1DD6719@AM6PR01MB4278.eurprd01.prod.exchangelabs.com> <6AD66846-04F2-4152-9BC6-A5AF15D32685@shiftleft.org>, <DF0004BA-A91F-41C6-89FD-78FEC3A37DAA@shiftleft.org>
In-Reply-To: <DF0004BA-A91F-41C6-89FD-78FEC3A37DAA@shiftleft.org>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: shiftleft.org; dkim=none (message not signed) header.d=none;shiftleft.org; 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: acdeed43-7605-4f9b-f1fa-08d8fd1be3b1
x-ms-traffictypediagnostic: AM7PR01MB6867:
x-microsoft-antispam-prvs: <AM7PR01MB68676357B8D160A66FE5CECDD6719@AM7PR01MB6867.eurprd01.prod.exchangelabs.com>
x-ms-oob-tlc-oobclassifiers: OLM:8273;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: qX7j6f+/479Ufdy4NUjQ7BjgbVBp28wP5fooTyBj4iGK4BcRekxHIcHO6U31mAFq0SB6Bdmkgy52OvanxnDmxwfcgox5M1zhTjvPJllPjso3TYNsjwZVeZ3DeUUNIrgs3AQZ1wcFXTKPTLntUqK9MT6UVm5K7m9BNpJKaqymDT5KJlaFXHq79FZuar8GpqLindNVOg+0Fblv34+whW7Ed73QApdggKAf8OfTmWTMYp+V1LJNQrL3cQuCtMc+N3ddxrDgFTubNeQl41x9swSYXRsbNmuWdtwvmBRBUZqO6WLnCQQ1wHLIx9/EvvhjckoDZgCem9ULGR6MQcYvpkFHM8siVjzMFTUOeCbUodGHwXVI2fEd4py4ClQtbQjWVfiKoCFhV66huo4RZet+2nXkwmQrbDC4koy4CAK0AMVCaunI+WxIl0OiP8tqpaSbqvJjPoybWDyVvnF/+g0v7sDf9Pn0ihVQBa9O/027cvhuJkvd011Ls85Gcti6n1yxzdCKjIHRoxd1j+HLmvoZ1FPCQzxc8OD3o9kevhBeYCJDzlKm5YWGbb2ghRy5fNFAGqab+6lhESaHFwez0oTu8LTGnRl44SYyyJKHT1Ccee5Vahg=
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AM6PR01MB4278.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(346002)(376002)(396003)(136003)(39850400004)(8936002)(53546011)(6506007)(8676002)(66476007)(76116006)(64756008)(52536014)(5660300002)(7696005)(66446008)(33656002)(66556008)(9326002)(26005)(186003)(55016002)(9686003)(2906002)(786003)(71200400001)(86362001)(6916009)(478600001)(66946007)(38100700002)(316002)(91956017)(83380400001)(4326008); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?N7SCuZH/jQ7GjFqUlQMvMBl07xd5PjZh0OHYB2O5ZE3MywkgJKSpM8De?= =?Windows-1252?Q?XApcb93KKatgDi9uJtuzeuCmobG1CMXhZdI6Fy0UCOVeDrZFcX7Rj2R8?= =?Windows-1252?Q?2ULQhqcDs20WUqCggBp6peC4P72x8AkbOlHdcmrRGgahYAZruYuLxX1p?= =?Windows-1252?Q?+UR0kOljdMvPLdZoNLwbyi4XwscI0KNXjegaqHA8BCdvs5JHRy5Puy/j?= =?Windows-1252?Q?4id7GTIsLCnCPMrkhVEhgs2kLSEexv5+Oo21XbDRiZZ3qvaV2ci/+Dnv?= =?Windows-1252?Q?d0LM1xwsdQyJjuCXathAcL0fEuBay12f9305Al+/7Vs77gsyXl756/Yg?= =?Windows-1252?Q?TnoV02KTFq7EgU6axd0EYiuglI/XEWd6o4lA+vUK4VV1oeX7vhnKMttZ?= =?Windows-1252?Q?EXQfL5rKkHay7W0MqKTllFjQ0HvAYMClcR9imzEmKJhk5cFupYyBEFbr?= =?Windows-1252?Q?zPQy/aD0NyruO1qs0J/T7VbzFMbUjVR3ibZa6XlJh+Sm0uOPgXPwpd/p?= =?Windows-1252?Q?nsPS/YBF4AllyL+3UuN3o8JTbUli/MyfWZ/mI0Mlm+uV/hQ1Z3Dg/afm?= =?Windows-1252?Q?ESO99UGuHGyFMf3hqXxeESHZYqG14wm/pRDy19Erui5uEyell758GNtv?= =?Windows-1252?Q?Ek+6R8P1lbjgC1OEwOHeYy+neNQUcaIJuvpxmdAo3KRcNhe0NwMEkCNH?= =?Windows-1252?Q?3K9mJbDECO6e2lTmJZITmLUf/DIonQC/XoJcrN1+kJrhWELkp+HnI/od?= =?Windows-1252?Q?hcKJ24xTFTGBT3ERKwCmYROGNNrSxhIlZg85hgwrJQS3ABzML2HrO0Ea?= =?Windows-1252?Q?yF3XcsFsI1zh2sGLGszEB7MyYAGy0rZ+ZVhCYbihMOZc/kEiBUlzWyzT?= =?Windows-1252?Q?X4Lb+fLwiAksGWq8lUkRI74U9ytH7ANZ/en5DWqkNFjEYI6RI7amxsUv?= =?Windows-1252?Q?I4uak0nox40bAum5SFyHwD3P4gPvzPI6YDuNshuzfHHfCf0gIyahQDZo?= =?Windows-1252?Q?doRjTPmM2qjMVhXBYgATMmnG0ajNTj+MEVShoS5dQkuxE8oh11KEQ9JG?= =?Windows-1252?Q?LZKgFU/zN+K/TI6w+E2cma/H+smZ6MKqpDDaJy1MqY6iCcRiImIMib9V?= =?Windows-1252?Q?51n/HOejkNUX++DG2/+Jx9UGZZyTx692om2EqU5ZtdSQ0zd8hMVkshRa?= =?Windows-1252?Q?W+pUgpsMhqH/iNDuDxrbsri1nJTJJvcVabitLF8x5AU10o0D7KsIf9wl?= =?Windows-1252?Q?UAcSVJlGQ95dmq9E6hVc+J0ufKmhF8M+gw7DV5zLiFhZmV/fNkp0tuKo?= =?Windows-1252?Q?04kGijL190cEkTs9gf5uW1XoUP85TwentFNBSa+NkgVhn7/SYQdnWKyo?= =?Windows-1252?Q?sef1jCZG3qhVG742E4+6BrQYGkObZLUUT5PIG4z/0EZFpYiL+PQVPWCS?= =?Windows-1252?Q?75Ybc8eDKrOs8S1/L0saiw=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_AM6PR01MB42783039E9763256D157973AD6719AM6PR01MB4278eurp_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: AM6PR01MB4278.eurprd01.prod.exchangelabs.com
X-MS-Exchange-CrossTenant-Network-Message-Id: acdeed43-7605-4f9b-f1fa-08d8fd1be3b1
X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Apr 2021 18:59:09.6081 (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: V1FYc9MEnzKPDPpSrPBL2uCjvu/Sc8iZ5IdUJvtGTBm5hhqgSIWqJ1lI1PwDwDzdhsRWVeVi+aY9SLguPclqYs5JtyfGW/4yZlv1Rsw6paY=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM7PR01MB6867
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/jalabhX74jnUwCs6AiHilTIRR74>
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: Sun, 11 Apr 2021 18:59:18 -0000

Hi Mike,

Thanks for your comment. I think we can have a more meaningful discussion on this if CPace and OPAQUE were concretely defined in the DSA/Schnorr or other MODP groups. Both protocols assume a special hash function of hashing a password to an non-identity element (base generator) in a designated prime-order group in constant time. So far, they depend on the hash-to-curve draft to realize that function, which leaves it undefined for DSA/Schorr or other MODP groups. As we can see from the example of SPEKE and Dragonfly, doing that in an MODP group is also a non-trivial task. I think this is certainly possible to avoid or minimize the effect of small subgroups in MODP, e.g., SPEKE, which does this mapping but at the cost of very expensive exponentiations because of the use of a safe prime and very long exponents. However, I don’t want to speculate how CPace/OPAQUE will want to do this until they are actually defined in an MODP setting.

Cheers,
Feng

From: Mike Hamburg <mike@shiftleft.org>
Date: Sunday, 11 April 2021 at 15:59
To: Hao, Feng <Feng.Hao@warwick.ac.uk>
Cc: CFRG <cfrg@irtf.org>rg>, Hugo Krawczyk <hugo@ee.technion.ac.il>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve


> On Apr 11, 2021, at 11:19 AM, Mike Hamburg <mike@shiftleft.org> wrote:
> Or, to pull the analysis back to the full group G: the probability of landing in the small subgroup doesn’t depend on its absolute size q.  It depends on its size relative to G, which is q/(pq) = 1/p, i.e. it depends only on the size of the large group.

Sorry for the spam: “large group” should read “large prime-order subgroup”. — Mike