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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Fri, 09 April 2021 22: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 4F8513A145C for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 15:25:33 -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=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 ePxkFMrPGeYK for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 15:25:28 -0700 (PDT)
Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60083.outbound.protection.outlook.com [40.107.6.83]) (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 353DD3A1458 for <cfrg@irtf.org>; Fri, 9 Apr 2021 15:25:27 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=oR1uTyoo6Ctwmu5+0SuVRITWm7DlLngS1L7iFvDvUr2S+pB/vhyZQrlKKhx49Od0rkNocnybMV7jvpyPB8EFk0+cbg6wkoieGTuUsXyKGiTqTJFNlUz0dVR5X48Yamx0Vpt5//qsDeBPEOoO+baFHQ6LwmZsxvFDe5yPWynIz1OCm8SkHO+3RSv70pkVHN9IJUFAqmIfYqgYL1NjBQeqmbmGHWiSdkwSsq8jsEUuetBjqCA+Wt7nBdwInOf/tFADZhfTvgK1VDtgoK6KLFWCz3oHjxYzq3mZTyKuV8tCV63mf0tmAgk3YaPUqWQeqAI5xLNplSfbtq9XPsB0ORfRvQ==
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=SiDtOWcHlTW19IlqxIlSYU1vm30bqJT0y7MVkZo/IGY=; b=X7Ao9ugi8U0n6NUm8++Kr/GWdSu+pdM22In16zHsDTMs33mjPMuocQrjY+YIc9Y2n/gL1M19wBLOfeF5Z9bDbP0O9t2VQKvAW5KQKEDqxY+DAyCP6KIPuHoMOaR6o4SGlkfv9de4weWbF+l+bClc3WAsyw8g6FsEdAsiX4YnxQkL/Nl5RGmAMDP40KjbKaQgwSbidyrvj7C7qIW1Eb+lAW2Na1xbOkJZnKTulUBrz4yWmYmqkO1YgeXZSrXnuhFg16D8Rh8QXZ7bFHcaxQqeruHERO7PkTnnTl7SfSFi748QI5TJZYKxADlHUPV9BHJ2SHcIrBXd3oKQ9beMiYJ4aA==
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 VI1PR0102MB2637.eurprd01.prod.exchangelabs.com (2603:10a6:802:f::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3999.32; Fri, 9 Apr 2021 22:25:24 +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 22:25:23 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: =?Windows-1252?Q?Bj=F6rn_Haase?= <Bjoern.M.Haase@web.de>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsrj2AgAANMx4=
Date: Fri, 9 Apr 2021 22:25:23 +0000
Message-ID: <VI1SPR01MB035772443E4DA3206E4CD4D3D6739@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>, <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03>
In-Reply-To: <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: web.de; dkim=none (message not signed) header.d=none;web.de; 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: fc272988-f835-4802-7ec0-08d8fba65e50
x-ms-traffictypediagnostic: VI1PR0102MB2637:
x-microsoft-antispam-prvs: <VI1PR0102MB2637F815411EECF1D6E21FF4D6739@VI1PR0102MB2637.eurprd01.prod.exchangelabs.com>
x-ms-oob-tlc-oobclassifiers: OLM:9508;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: 4/+fLByGs/cJ5xNcuN8hgYVZ9g0m+91Uga7P+kyZ5KBLcBOz/H1GKibALeqm3YeuhTFPOEr1/SgEBXV+VgUgfwc6MKzNC3vjec5HNWv55i4F6HSLivTm0N3jlghtFekFH42vtLQSj0lzqSK8gGl0KsBDkt90M16hzdEYW4Zni75DQLbdr+t48Wncij6+SqG+QxYKG8C7vX/LS8g2K2/P6gvahyqZUa1xGSwdH9rRTg3lLGDPJS23awODcEl+5ArV9CLtsTWxIKEd5jal97bGC7dONla8j+54Jtkf3koMJQa7WTtVjRUR4LezDzADmtgnvjxPQ7SPWiMPysM2n/4LgwSrMQcWEjxaam5BC74skJZrpCH5whaZWDIIjVkVOVxXKjez8lqZQP37gkLm4MW6VP0aU6VHGOIhou7qa1MyGv3TIgILIzQJIeLrBxtzPVX6kgnC9pRJTPyjDd5gTVlezg+yb99ngPWFYG0pNBcFXRFSvjmawuIBd5ol7MeePB9hxjBAf3up06XKGa9Nrv7GvsHUZYX/nhsmjhfcSrzy0zoemtD4xso3dTe5ZWxMgfwOrlvGfM8w7MRVo1jl90lGma55k5oQXS9KuwYsl3Rk/e/YzDvEt1/kArUjbUhKoOIhzTu24oCC2obiOdqNdQ+N3aliAD4mINPbRQ4CQyA+9yMtKyzPjZRyPUtCnj9z4/0Gw2qMr5vPZEZKJc5xzwORdXAC2gh0/hNr2okT7qU5k49MOVbCrnVIBeMADo5LS+Ur
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)(346002)(39850400004)(396003)(366004)(376002)(136003)(66556008)(5660300002)(26005)(71200400001)(38100700001)(52536014)(66476007)(66446008)(64756008)(83380400001)(66946007)(6916009)(478600001)(8676002)(7696005)(66574015)(186003)(91956017)(76116006)(9686003)(6506007)(2906002)(86362001)(316002)(33656002)(4326008)(966005)(786003)(8936002)(55016002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?aXXQa9hqIywBpmk0Rtgxo7fcXurEwI0WiNjdAJLhTP7sjb0a9ejoatUC?= =?Windows-1252?Q?Jtz9DeYezjSxLnnJ97DFe8K/96xYb5Zskw3LT9drUQcaDlV/41RmFv6P?= =?Windows-1252?Q?eQLSjTnI9mpef/F7QmY4cIh6+th8iRf9xc0r43dmT5k5GYQ7FhykWJK+?= =?Windows-1252?Q?wwXtv1jhKcx2JvvGwjhQDrMX6MJVximDkXTjzKXcR4EgjvchtsNYyoZD?= =?Windows-1252?Q?iUFe/7s5JPMvtNrWl3SofVVREKY+t7mS3IZlcDiLAa8AFhDhM32fBJso?= =?Windows-1252?Q?7ThaAJ/irUnh7S/H4OjgdaOJk3TmP9Bb+IMmtttbOqii9mNdRQZM0CCZ?= =?Windows-1252?Q?xIGLUQpvzMulQX2vm0Y9S85Z9IDPhKm0azqna678/4+34xxHyteRkbnS?= =?Windows-1252?Q?oPfxkElLlI9aMy1xlzWXK2ujSIldYP6urOVBkDyTeiIRB92rRA99H6IU?= =?Windows-1252?Q?20T4dOGnzhWEi6MEOULhHQCYlyQw79MLvnbX2W6k22VooZ16+ruEyhRU?= =?Windows-1252?Q?5cEwFGRiSAm/RdRf1+P04YRP+6evTFOXCW7BF9eFz3qg0Zl0cZOli07a?= =?Windows-1252?Q?yYoYYqZVKa1PJZ53seROJMNGiPUCB/tyEXy6W75pz3RUM8ynprd+oSH+?= =?Windows-1252?Q?dIpVWYJ4hkhIkjbWhQrdo76LdsD+c9EoC2HJZdQgNnkqpcUlzqwN1Ay0?= =?Windows-1252?Q?48a6E9baKkel2nCXWztXyPDq2cXHGUoB9B5faTchAGfwQZvO6JokYHqX?= =?Windows-1252?Q?iCt4g3KfOYuwyFGdJWxu18n1Rn5rXz33vn6XL8p4sKJq+KXBrLn+6liG?= =?Windows-1252?Q?WaRzOeIq4aeuf7GyA/CrgBB5Q4E8fQ2koDTeNTBiqYIYc2kcqBx9ksiO?= =?Windows-1252?Q?KZIu+aOigoZ59BpXWxwGBH8vtQr5Ku2/TCIPO3s+OQQTkkwiOGGhnKOn?= =?Windows-1252?Q?bKfT7mXvj7A9xz6DLn7BVRo2GNRbJJIGpO1Lnsc21OxcKr51kqH0sPdP?= =?Windows-1252?Q?jMvcSPsh+7kp081aCCj6AwPhJp/21B3J/Q32gXwsAXLkgn7OVQvg4j7V?= =?Windows-1252?Q?apwGl0KU66Jmn8W9JMmIj72lrO1vH2EBPIrF5gbPgeyizg4LBXZfHq36?= =?Windows-1252?Q?W+9iT7L6ZZJbp6MIGc27RpYwkJJzcmmfgsPqpeSKZPelB1xPc0morG5G?= =?Windows-1252?Q?LSCdw806fNZYHYm/7ib665WGpVpVUNlqm+AZQK5ErkPuJlEM1/TAQODV?= =?Windows-1252?Q?5W1DnhQBOel4wCecotIctirL1wm/S3wwB+2EYKhbB6QqZeWOxDabF6U4?= =?Windows-1252?Q?Et6q7ncKwW2rHfS1kmUZObtKOKFobdGfiv1iwGjBqRHtCRo6D9feq3uQ?= =?Windows-1252?Q?9sEpdBC1TBwh804pwA7oEG2CQtIvlkIYe5lZ9JMuRqHIt3CcItWhWVCe?= =?Windows-1252?Q?SJA/rsnvY9/x+aZWFA62EA=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB035772443E4DA3206E4CD4D3D6739VI1SPR01MB0357eu_"
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: fc272988-f835-4802-7ec0-08d8fba65e50
X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Apr 2021 22:25:23.6932 (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: 7n7QoLH1rGTEEe+IL9mibMMWx3PPtbr4whrcp/dENCpDoaAhvObzda4n2360r0AfGmtBIIoyDZaVMLzykn9Hq+ve8GOWUQp957wTItdBUCs=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0102MB2637
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/-F4299ocu6DuPGX4TIcLdldni-E>
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 22:25:33 -0000

Dear Björn,

> for CPace this has been considered in https://eprint.iacr.org/2021/114.pdf in the context of the proof for theorem 3.6 (and  correspondingly theorem 6.1, "Security of CPace with Map2Point") and become part of the (negligible) loss due to  the increased collision probability for the hash H_1.

It's good to see this has been considered in your new paper. In your theorem 3.6, I wonder if the proof covers the cyclic groups in general or the specific groups on elliptic curves. As you may know, small subgroup confinement is a common issue for both MODP and EC groups. The practical effect for the former is far more severe than the latter since the size is larger, but the theoretical principle of the small subgroup confinement applies the same for both settings.


  *   I don't identify the need of considering this aspect in the hash2curve level, but I agree that this should be covered by the security analysis of protocols that use the maps.

So far hash2curve and CPace/OPQUE have been developed separately with the former being largely assumed as an idealized function. I think now is a good time to look at the integration of the two in a system context. With the current hash2curve draft, as long as map-to-curve returns a low-order point, the user’s password will be inevitably broken by offline dictionary attacks based on the side-channel information. There is nothing the protocol can do (rejecting the point gives away the exact side-channel information needed for offline dictionary attacks). However, one can argue that the chance of this “really bad event” happening is L/q where L is the size of the small sub-group. It’s too small to be of any concern over common elliptic curves, and we hope that never happens. I think this is a perfectly sensible argument from a practical point of view. From a theoretical point of view, the argument is not appealing or neat. Hence, my question is why the small subgroup points can’t be precluded from the map-to-curve function?