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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Fri, 09 April 2021 13:44 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 E65E53A21A3 for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 06:44:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 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] 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 mt-6hJ__Kyzn for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 06:44:24 -0700 (PDT)
Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60047.outbound.protection.outlook.com [40.107.6.47]) (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 8AB233A2193 for <cfrg@irtf.org>; Fri, 9 Apr 2021 06:44:24 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ZSvLcgTgTIh31gtdF3qYTHnTwnZhYsue7jfUaq2gVQHCB2yXb3nDSrCMVjdg7MBMNIYwwV3DZZak0omPsoygDFEFU7ro/LIdSuSUhMxW8BczrJ00Sgi//kVFzsLgan5UugqaScy6mkak6vcvyiNq1+LCt1zOFnxzVma/h7aOTNvokhv7kyMnPKvGkjNrlGbQmlSLTfSI4a73yshMJgNIvPwnuqs7g+fUd4+MdnDdvHVcryVYjUCNPSTYql/d1fpQ1J5bttYjasm7Lzrwo6jowrDxSbRTG1i67dnaauP83zT6X/mI968pBBT/z/HkF6rW0C6Fe26ZGT7rmUEe3gO5dQ==
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=ULwbIlvsx8m6IUNsL37PVDsgCMpsE5u/oP4RvGoGPaI=; b=gcqQzhnVgMFuVakjNbhIEthXPA6iohc/RUTaEvaraMeJoAO7t8YPnVTQOf1aNtkUVwrelRHg5CEMELIz8VKy4/1arR2YTyikYm5DCImhJID9bwTKXdbkxWroLXBFYsHK8Vpx0LBdrK/znQW26bmb/ADIO6eWuGvwvgdBbDpbeURC5zPfhQRs0lOGyEHj5vhmu0v4RNOjSvmR1GRVayZ4X8+ySMv9a9ehX40m5quIPL+ngdo9YxkNmjngCs6i6QfGKqnl2yp6Jt+3EDbLEHnZSRgWygz0HVei+gveHhh4/ObYSumnWt1seH6K3uji0VzvQciAikiSUtXaVjzGFb3Aaw==
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 VI1PR01MB5200.eurprd01.prod.exchangelabs.com (2603:10a6:803:cd::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3999.29; Fri, 9 Apr 2021 13:44:22 +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 13:44:22 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: CFRG <cfrg@irtf.org>
Thread-Topic: Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsA==
Date: Fri, 9 Apr 2021 13:44:21 +0000
Message-ID: <VI1SPR01MB03573585C37B871D200ECC23D6739@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>
In-Reply-To: <CAMr0u6=PBX1W5zQFmpxKQ=ViUXN9QK00BREL4M0=2HOkaXaiZw@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: irtf.org; dkim=none (message not signed) header.d=none;irtf.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: 1fcf74d3-c89c-4f26-daca-08d8fb5d94d4
x-ms-traffictypediagnostic: VI1PR01MB5200:
x-microsoft-antispam-prvs: <VI1PR01MB5200D2C92F67AED8965A95A6D6739@VI1PR01MB5200.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: DSo5AzcHxm09abRn+91eWPQs0gozwb2YeS3rLJobhSkGOD4k7aapT9qZrLx334ASKwKFQp4dfkS0lWDEt8ggU7UE5MacT/FLNMlsdO4myaRFFtQuRwZY2HpqvcJ1kGj8gt3T6n+Lp7yVgtA5QK9375sGjoTXXcomVrw0T3vId9Bsow+8qgsBDyCMKzYWWqLL3ov96mg5QFA3isinrJLqqZrufd39Z3UJ3yw7Kko25QIZGSQf8Kv20htDlbFtEJK8OiMrkUxaylDrGNUSVW/laT89RLrC8k5GRK3S5qlQ7DpYWqUES402VsvU+JQp8RhwHZRGtLb9jeuyjRgiVqkXNBjRjqVfn5d8TmP9FjaFoBYK3BL7z6ssYiKjeanrNjYmprmrnwVfEF1cc7FuNF+v84ePDch/hh3tQYU57Ebk0aNLmUDhL4u7bbHrJ62MZb1l1mNlaOiddAE2JqFdronaqNeWzRUifBOViE2BF2Rt1qqyelUyFNB340wJ0iKisYBfMsrjpqNRaDxbkzupERPn0wwm9EPGK+knyY2Enn4eDTQ1as8r/smpvjbNeWo33FEkqmrgYI/SrUmEwWCiN+aStJMmfCWxPu0LcmhuPcqMzEUhDxnHsWQsa6GCFnnA7FrLyRSlzZn0p+0KqIg+wcgJVBzcSJ+q8jAd6/zI5RngrQ8=
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)(366004)(396003)(346002)(39860400002)(376002)(186003)(26005)(8676002)(8936002)(83380400001)(86362001)(786003)(316002)(52536014)(9686003)(7696005)(33656002)(71200400001)(5660300002)(478600001)(66476007)(66556008)(64756008)(66446008)(66946007)(6916009)(38100700001)(6506007)(55016002)(2906002)(76116006)(91956017); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?28Vbpvj0EUEavG74qBUCChmmoseWAam1AMW/7fauSFDcl09P1m7XAq2D?= =?Windows-1252?Q?NAvRBx7b54iico/M4dUQN3X6o2dxGjmCOxg7uTkF4TNZr13sbDvpTNmH?= =?Windows-1252?Q?ZUZpmwdP89Q6ZRLTbk4yzMSVtgGnVTevwD8d4kOQFYizb0Zzin+YSM5o?= =?Windows-1252?Q?ciEkiJWar+HurlqKlR6HA4rQGBG7wV2B8RlmUjsHNES1e1kxvqZJmZF+?= =?Windows-1252?Q?DP0sTsQ5q1BkTt48o6/Cbgy/yDoZQkFS5vr2uj7VawS7bxag4E6pJV+k?= =?Windows-1252?Q?5Zoy1XepCC30L+bMDqIU2kulZXLyJdS1I44YFuCSnPQB2Mr2aUcuBxnw?= =?Windows-1252?Q?qz++vDYRMdvX55MPv736aCoxvxOnSkR/v4DQZ9KvC+UbEKndJk+0GMqW?= =?Windows-1252?Q?Q8CxCjjZj8iX9Hsmq97h/Y+X3f+8oiesXDKL17YxbF/uCxwa5+4z+bzm?= =?Windows-1252?Q?nLH4g6Lj+9uEFkjKGsoMNTO7biPBmLh+xqI6PgsNU8g7yuDba212ry/2?= =?Windows-1252?Q?IHxV6mXT6Rq3Z5tHQg/vm8C/nYAYSpfk4eOil0ngH/xoF+R7MxI3Jsdg?= =?Windows-1252?Q?o+6yIqMhIZl2l5W5/lLBYMYWR/343x8USa6jakyKJO0fTHia6z7piqBc?= =?Windows-1252?Q?oUFNHnqnhFqXjj2Ypsy/d1c6FQ0YGQMXuufPuXb2lU5C3BlI1qUMey/H?= =?Windows-1252?Q?ivzs2hqC5ZfTacGGKEMxKY6zFxNB2bXT9TVUXyeMpg/umoaoawrOCuYt?= =?Windows-1252?Q?F2vvoSeSKW+wlxUx7OpunkZ50kaGk0OzT1uYaSEyNrHEEG81aQUqOL9T?= =?Windows-1252?Q?Kun7ultzqPCrJLHZre+dfb1x3dQahneGSIDw/AoCvJXv76KamfSx7eF6?= =?Windows-1252?Q?FApiWX/2o5mKF0BFzgLlt5TA/CTdm9bSuiGpcBp3rF6/qZwmukEcY8lp?= =?Windows-1252?Q?H9y2JnNk8vgWkGEhUfrDdnJPECFmXTFKxsTrgoZkRzaRhItPzuFTDKMx?= =?Windows-1252?Q?4mXC9DzDbUQJp5yARPYj4iDt2hMgzzBRLIQQJXqVHXyenpkJm5+dVucI?= =?Windows-1252?Q?/RKY3ea2/otMjhw9QXHlswRFMwCUYCgXInJNflueZ/GxEwqwkWzjY7Xo?= =?Windows-1252?Q?YvZwymFopr7uc/a9btsgoUDH3Ql346H0FVmZeQNrey6E62Rw3OvUcnw1?= =?Windows-1252?Q?IGjZsn51R1O8utrpUzZnFTzsIzRbrPZofQotfG1puv2wbkZ2f4mXdA10?= =?Windows-1252?Q?vXGGoEWhUw/axXlfmWNzDQ+DDpVN+lNZFY/YwTgjggvB2qbfOFF4/Het?= =?Windows-1252?Q?XyCfZny0ErM/OHhNndtsdG2XK4R+IxCz4E8RfvIK9yNvwbvU7ogOFa7k?= =?Windows-1252?Q?qJTvMhQBjswR/GmZLYr4aWH0Q8rzkQZPsy7EsYzYfWkPUquadKk5DaD6?= =?Windows-1252?Q?4DHEdbLwnHoEXcPOA8udCw=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB03573585C37B871D200ECC23D6739VI1SPR01MB0357eu_"
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: 1fcf74d3-c89c-4f26-daca-08d8fb5d94d4
X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Apr 2021 13:44:21.9833 (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: 1vukTeY03LkzFJmZ6kz+POa0f5qMdDvrotqqkEHdZlEIrBRqNrnuuIRzTDov742DuCN2Tk+/qngf0WRO00Jx4g+qIj7bYwZx9QW7APJw9kc=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB5200
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/vslUZygp8XPmoCOl28b2K5yjuiE>
Subject: [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 13:44:28 -0000

Hi all,

I just read through the latest version of the hash-to-curve ID (v10) and have a question.

The methods defined in the draft map field elements in F_p to points on elliptic curves. But the points include small subgroup (low-order) points. What if the mapped point on the curve falls into a small subgroup? The clearing-the-co-factor step (section 7) does no help at all here as it only turns the small subgroup point to an identity point.

The chance of falling into a small subgroup is extremely small, but for the completeness of the algorithm specification and the analysis, it’s still necessary to explicitly specify what to do in this case.

If the mapping function gives a small subgroup point, you cannot re-run the function to generate another point, as that will defeat the constant time principle. But obviously, a small subgroup point (or an identity point after the co-factor clearing) can’t be used safely for any protocol. It seems we have a failure mode which is “non-recoverable”.

In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator. The implicit assumption is that the returned value from hash-to-curve must be a non-identity point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

Has this issue been considered? Apologies if I missed any discussion on this before.

Cheers,
Feng