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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Fri, 09 April 2021 20:35 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 B0FBD3A0E8A for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 13:35:05 -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_BLOCKED=0.001, 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 zay84aCP5Ixw for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 13:35:03 -0700 (PDT)
Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2049.outbound.protection.outlook.com [40.107.21.49]) (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 9E0FD3A0E6A for <cfrg@irtf.org>; Fri, 9 Apr 2021 13:35:02 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=MUq0tfargAVx5vTXYpvL/xiYcNBwMACE6bA9Dnq0UDpLIqpnL2oZTrf75KEtaX7mGcnELIDuMlvcBdKXBHqMx5grJOblh9/WFXKiB3DNOKsUyZ+Gmjy6YTqWlmz2O0IYwAAxwbJiUDgdBuNge1BmQTsR42actBk/fVtkGgY7oVwjM5vgy3uvCY0U43Owm0d0jLnUCqFMop5cBElLFAVXOAlqNCUemyIZud0kUz2P3eaS5kYqRq1FJsnzzXpgOoAqydD6CdHOIQmijPMidC+2wdvoG4qimYxazzShjDLstdOumP053xTCdy/qZTue0mpH0mLwIAzAIMHxsrI2T8ouww==
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=A7S1EbnVuw6GjmZ4Ba3LAc875JLZxmT/kU0x1DaafHQ=; b=Ml9BAa066svP8+/9ahfzJjrQdznqOaFY7tCrRB984nsCucG7QTV6UmQOfw+47UYvIh01tqFIY+uvyya0sCFLKa4TJPHUu/9/Hq9A+xUiCMxtqm4A81ilrLOYBEAiX6ynAVKWuAUc4UXHQ5czjJ4ymh9qq+zF3cF2Lmq6T8Es8Ef5zBJyQKufYqwwOODaUlHpvkDxia0tH7R8WeEkxlFT7B01PA1Cybh0bNjOI1GJN0C58DS+8e3ItIxzdkqK49Zt4iDAI0SM1ltsVxcfQuTOm9yI6ASll9MocmilcDbSxBGZZM0h3v6F+ahi57ctnj2kZqDzZqDpP3+EuYUs20SGpg==
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 VI1PR01MB4287.eurprd01.prod.exchangelabs.com (2603:10a6:803:6a::23) 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 20:34:59 +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:34:59 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Armando Faz <armfazh@cloudflare.com>
CC: IRTF CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLXXsOQWx3kzbXU+OBAJxxr7n/6qsnfU/
Date: Fri, 9 Apr 2021 20:34:58 +0000
Message-ID: <VI1SPR01MB03571410D41E89739684BCCAD6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
References: <CABZxKYmf2F0MV=aSa3ZrGbW3OuEzbsjMJ3ubCfPK+3Zg-Bkohw@mail.gmail.com>
In-Reply-To: <CABZxKYmf2F0MV=aSa3ZrGbW3OuEzbsjMJ3ubCfPK+3Zg-Bkohw@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: cloudflare.com; dkim=none (message not signed) header.d=none;cloudflare.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: 38d3b483-fad2-4ad5-168b-08d8fb96f1af
x-ms-traffictypediagnostic: VI1PR01MB4287:
x-microsoft-antispam-prvs: <VI1PR01MB42871AB501AFF6C44BEF0EB9D6739@VI1PR01MB4287.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: 7PqUOQ5rSF+0xhoMhTAJY/TIqxW5I3sY6xtL5jaWcvG/nbIeXccsKq7NdZcktpp2JwfmaA1xrmh4oqc9D7M0U6JQJakE++8k90wav19ak/yRa1nSPLMk1R56FNfxjmn4aYTZ5OtyIM+ZDmwb2bQ0EdTyxK48NNXpsGJ7CR73OWCIg3qME5UiGCfIWDLSX59Icp5JBtMJipS4bcpAiHT79cS+GA1Xckb7p0qS7+FMf+1SHb975tM5e5rqmLXUpK6xTXYzXXaAKgb+YUXqnIBxIY6x0KMTMDbbzGXw4XPfMJ3Q8IFFJEnlLA635wIHJCKEJJ+fVZKg/RH27RrJZQbKvEZdW4u6YaQKZghqbpcU3nPY7RWLe6uwMA42MZrna5jKpo5b0qkHHQ+R7XllDBeXdS5bRsUlavbg0Sr3So8uC4B0OekVoT5iHowIcucvcutRn5NLtelPEwqRux4xxQvtN5X7wu7OXUfQw3ZiyX3/oESeiS6G6+s/wx3A5gWssKeJ+r1j66aZJN1x0Mad2XV1kwkQBU6zPaMMZ9Iz/W4p1B+S/SWrvmgb2YkmDXrW54y6Rm9AIW3gVPgCN9CW1PvmivVDt5sciOeEjQ5dQAlYMWnanbhfNK01dDEVAoxkEZyqeE4Zapo9+/bjG5/s5wqLSE5yuKgH+Fx8UvH/abDZp84=
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)(39850400004)(396003)(346002)(366004)(376002)(86362001)(316002)(52536014)(26005)(38100700001)(786003)(91956017)(71200400001)(55016002)(2906002)(5660300002)(6916009)(9686003)(66446008)(66476007)(64756008)(6506007)(66556008)(186003)(66946007)(33656002)(8936002)(83380400001)(76116006)(478600001)(7696005)(8676002)(4326008); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?vF+eJGnhyr8+btAYMhQPJBEKhaCNaKAQlwbBNVM2wBksRiXj5YZTB8oZ?= =?Windows-1252?Q?yhG+0Ig8B5r8fFhClQ2URZfrvOAwwbvA0ulWqGt5e4JUfIVM7cP7jq9P?= =?Windows-1252?Q?ozgKN0cZLk9adGgke7kTzEoyFdXp8LVXDQoEx7Tcw55wIzN860Cx2Ksc?= =?Windows-1252?Q?drV7e5rGySsFYUIpfhHjt0QVNv27e3+11IVcS/+PUH1sVNnk164Xpc5m?= =?Windows-1252?Q?N9lKchuCl37b4DsRwK5lxTS655vCL2NlLl8JYO3CdRm2PndJ1y71hxSl?= =?Windows-1252?Q?vxWaJM6hzCdsVMimvNbt6KS7ldbs8bSzkvOUN9iVsp1ZUR8dlezFl+Jk?= =?Windows-1252?Q?NBtEiIHn/T+Z8rm8YOeaLdQmqNgcq96cycLpJnt1In98ev1EoNP7WFyU?= =?Windows-1252?Q?UfBrIdr8TJWxFIV218xVVuQ+Ry5fQwsFagf5DUl7URiwY2KzWGw7GbDL?= =?Windows-1252?Q?Ja1AU3Jj0byqsV+zXk4Dzs7WbkxizeXOY0HIhs0/nt18hUxVcBW6LLDd?= =?Windows-1252?Q?T4ro636Q5DFpbFn9ZXidlJxdaPFQTm6Wv0NoqUZCohPUSg1/jAgyI9nE?= =?Windows-1252?Q?b3VT+XwrT+joObhGn2ZosQMyrysbmtSpHQSGAgpuBaPiX6zfYu7sqJoJ?= =?Windows-1252?Q?zhPQP3Or6d/jlQyUDWmzsC8uEOMhRHWZV2qoCK8CWenRbe1tRyMgkmef?= =?Windows-1252?Q?n7Owq05Uf12+vtNcKA4QNtf7ZAc3ocwuExxL9xb797Lt3YdrDge/V4SU?= =?Windows-1252?Q?h5RcuLy+R+bkHj3IXZRTmbbnZCwO/5QdFfMOc9v+xTHZKvP/lc+ijnGy?= =?Windows-1252?Q?BURZ1wM9ficSz5c23ATxcCvyRtpty7+g8dVpzBV0+1DZjFNqOALVWzRR?= =?Windows-1252?Q?hhawSPDU+DRHj01l3KIl8nzss5pSicqMF2OFAVN8FN2qznU15bdrGAt3?= =?Windows-1252?Q?ztycHNQgyzkZTIglr1mw8L0hYb3Q3BnnpOwW/N0QHKaTkeFixAu8qW4u?= =?Windows-1252?Q?X6L+ToYOfqVcCQfDvzt0/viYWmSf4/v2gmgCcDqMyj5zYT1wUrGsDCJt?= =?Windows-1252?Q?a7b9oUSCzT+dVM411pUJokd/oqA23HHfRW6ZHlM+8HzjoJyfgPoPHRrq?= =?Windows-1252?Q?llGoAHbyFqIOMOKNeM0m1VpPQf1Td5BEocaNxARjg1kKuMLAGpOu5Sjs?= =?Windows-1252?Q?OjuaBHKnQIH4NhY8LgOdcI0nCayXT/HTAfOMfJqiT0or4jdPPngmy9gF?= =?Windows-1252?Q?GRg5PZ1EMu/n5h/Rbsb6CDMmJtdsOaxQCSXmWUhsxQyC2K5dNkP6Qd/2?= =?Windows-1252?Q?1e0dyxtR80dKns/46EE4YRGjkJixctocHO5SFcJr1wzYlXCgCp/VJfRI?= =?Windows-1252?Q?kwS1JYHxdFiwCVzw6pyRVyxIsByBTaLlP39K7CE7WT6If5hJMTODizI4?= =?Windows-1252?Q?KfsvWzA00FwVA0rrO4/ZOQ=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB03571410D41E89739684BCCAD6739VI1SPR01MB0357eu_"
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: 38d3b483-fad2-4ad5-168b-08d8fb96f1af
X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Apr 2021 20:34:58.9985 (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: nCmJ/l/fbfjYmj+uPy+KzOga1EL6VmYN8fkJP6TSHQlP8xkZf3ScHjR6815OZr3TD0UWJkYm7+6eoJloNSFhlPRx/aAFIgCeKlgdWY1AAyM=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB4287
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/qHLtgBwDLixexOgtDAL8CDShRr4>
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:35:06 -0000

> Let me just clarify that the hash to curve functions described in the
draft is a composition of
 H(x) := clear-cofactor( map-to-point ( hash-to-field (x)))

> This hash function always gives you an element in the prime-order
subgroup of the curve E(Fp)[q]. That means that it can return either
 - a point of order q, or
 - the identity point.

> No low-order points are returned, so the concern that you have raised
is not a problem, and it is already solved by the clear-cofactor
function.

As explained in my first email on this subject, we can remove clear-cofactor from discussion here as it doesn’t do any help to resolve the issue: it simply changes a low-order point to an identity point. The fundamental question about the small subgroup remains.

> OTOH, the calling protocol could need some specific property about the
points produced by H. For example, ensuring points are different from
the identity. That being said, the protocol is who is in charge of
banning those points.

As explained earlier to Scott, it’s not a simple case of checking the identity and banning it. If you get a low-order point or an identity point (after clear-co-factor) from hash to curve, you can’t accept it nor reject it (the fact of reject instantly allows offline dictionary attacks)

> The concern is akin to the generation of keys. For example, calling a
PRGN(seed) to get a key K. Of course, the key generation procedure
must ban the case of K=0. However, nothing is wrong with the PRNG
returning K=0 (with low probability).

I think this is a completely different case. If it’s an AES key, you should of course generate the key at random without pruning.  If it’s for a public key and the key needs to satisfy certain conditions, you need to check if such conditions are fulfilled and if not re-generate it. The issue here is that if the mapped point doesn’t fulfil a property (say falling in a small subgroup), you cannot re-generate it, as doing so will allow trivial side-channel attacks.