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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sat, 10 April 2021 19:40 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 74F093A18EA for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 12:40:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, 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 jUJ-wppOw1QR for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 12:40:14 -0700 (PDT)
Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60085.outbound.protection.outlook.com [40.107.6.85]) (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 06A243A18E7 for <cfrg@irtf.org>; Sat, 10 Apr 2021 12:40:13 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=XFf8bMPuFu/2+RBn6MYG2mYqxtLSjC8Vq6O6SkPxoPyCr2MLgteOilS+KsTNuvt2hyZENIePbbHis6thcL4IwF3J1XLj6ey8HE2SwfrWp/sXu+V9kmC03iJlKp/w2bLMPctfh7PqAol1wHwJVD4ja1wr0EdQ/atlwt4WDq1XyS94r0GaW77jKAaXUpFI5q0W0BSn05RUC8xKuwC8sarkPl6IGuIL//0TqxqlKtGYV3L29+FaWLCkN9CEqy3zeckxuilbI57yWDYiXd/YvzFIKIqnScnwznFTby1dmr7a+7qoFjnUZ9O9B4ty+mTYgTzQPek0Niwn0MTt2Sua89/ISQ==
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=9BZVOIhTVzW0Njvch9XiD7LXD6V5KCwu9bOtRyjmdUY=; b=g7+WRej9L48QVzp1PTrzrgB5TVU5MsDvRGFh8SWuB3fZgOi/aK3Tjs7SAOxx9eNyRQIywtnKbDgvIKMgbZq6TNgxP5KbeEY+mnm+Qfw/1me4qNEqCK02HCV2gb2Y4vf/am7cQcZCyPmpxS3VYq+85jkWrJi9Y0mwT3kcmvOxO89cgYfDPVF1C9iheWy7zKB0Bq0SDzJKDmi6OZ4hiAH68sh/g7+jaNl79gmDjWOKNvCEUn/GYDOIf/afQmSoIMflqEkkN4kAOjqzM/NsFxIbJCVO8BCUyNNyRPHtWTXszWAvxa3nKfzNLDXKCkFGe9g7lbHPOKMsAxPxvt9puc1+tw==
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 VI1PR01MB4799.eurprd01.prod.exchangelabs.com (2603:10a6:803:98::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.18; Sat, 10 Apr 2021 19:40:07 +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; Sat, 10 Apr 2021 19:40:07 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: "rsw@cs.stanford.edu" <rsw@cs.stanford.edu>, CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsrj2AgAANMx6AACTDAIAAhZzVgAB3mgCAAEY9Pg==
Date: Sat, 10 Apr 2021 19:40:07 +0000
Message-ID: <VI1SPR01MB0357E173308FA953D4B3D1A4D6729@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> <VI1SPR01MB035772443E4DA3206E4CD4D3D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <7944D4F1-81F8-44FC-95D1-45D47733B385@shiftleft.org> <VI1SPR01MB03574E592790FD59C1ACEB84D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>, <20210410151254.7ze5pt4lpvblhk3f@muon>
In-Reply-To: <20210410151254.7ze5pt4lpvblhk3f@muon>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: cs.stanford.edu; dkim=none (message not signed) header.d=none;cs.stanford.edu; 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: d8240a1c-2d89-4629-0dc1-08d8fc58724b
x-ms-traffictypediagnostic: VI1PR01MB4799:
x-microsoft-antispam-prvs: <VI1PR01MB479982F6B1E69CB2E944A74FD6729@VI1PR01MB4799.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: NOUFxfXTkdO3rL8ptVntFgePO8e3GG7z9Wjpp2j7hU7gfNqzNTWogyK5K9JSSwj9f678HNQKa6g47l6KWQTxO9sS4UzorDyVXhRZBg0fOVWXIgAeTXGJebjpIvXTKy+pdi3Lw2XWoMOIkXX2IGjGGoyBhNxmh/0YMgsF3GTg0SCul5USmbrowqiD2ZMyIL5D3jiF0jFFWn+gS6LNwSvxfU5FXq8XbfNLxEqzYd7/2ooq2pLDhDWNtofooO9ygPxzbn85uBxuGCfhk0OXDZkIiktSy3OQPHK5MSQy9TDH4dg8RFwkdZ1TEGegRXuoJ68fV5P1g6XNdoNolGw/navV+oxXYPve+vvti1oVUf8z4SSAo54aIylL8clo5jwO21goiLY5dERwZ/yMDt90Qv8S2mJcA8oUkanwNFurSf6u10tvI/dSP8uuEzW7akzwXE8xw9Ghh0jux57xOWqDcsZdYIzNYQo69u3rffogwXuwLlfKaqwsYsTajQrdvtBerXfodYJHKmBxODmC/b2+fxkZIqL8NuLsU22wNZxXvD9ymOEmLo01lTUwwL/ABsKjnLYcXfqcNKsqAdVntEEdTlq2Khw8a+RspMG8ak5QyKvjba4=
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)(376002)(366004)(136003)(346002)(396003)(39850400004)(66446008)(71200400001)(91956017)(64756008)(53546011)(66476007)(478600001)(8936002)(83380400001)(66946007)(76116006)(6506007)(86362001)(186003)(26005)(55016002)(786003)(66556008)(8676002)(110136005)(2906002)(7696005)(316002)(5660300002)(52536014)(9686003)(33656002)(38100700002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?CD8s/SgRLKM+ZUKbINmDxWO8C2HmKpX8ia8qp6HPQ74NbRCT7MB5xnDr?= =?Windows-1252?Q?u+GlfrIvuRnHowxAmBvOC+cW8T/wB/OrL4E5Z6NNT2r+VBXYOsJjUrQ1?= =?Windows-1252?Q?j8lQcnMrej6/PzNlSSVRN/KDVclWRgzfKcFYW86NJipZr4cWTKmoxwiM?= =?Windows-1252?Q?qbUoo0I0DHTpaPO2wlXZzmyI2c9TL5NS780EZczzRL2AWpHM4dL05EMN?= =?Windows-1252?Q?sXRQqrpPxOGRj57/YEUot23Ze2L52z4tXE5q1vqJzKNSU0cFtlrYLQVk?= =?Windows-1252?Q?8jf1CHk9b1kwB+W2Tyi3P6Xh83+/jwjaqG+lEnaZKwq7sSb+7R2VEaSc?= =?Windows-1252?Q?3hgbGAPbAAGN5hjERG5IUxsv8/Z9g1+YYpfnbPq0q/j1DfPrVNgnq95D?= =?Windows-1252?Q?BBpunewYZtyHIq95yf4VRc+CLbritMrcm6+UsL7gZW2NTt7ceoo/ho7c?= =?Windows-1252?Q?nNB3IVV00IvImSAdO5LYov2FJc3oWaiO8GIdctvpHs/nnzUOqujHiaqM?= =?Windows-1252?Q?PC0iJigajY0BI/PUtBPiJ+HXMARcfhtKecMWG4AdpeGrj9nHeMV3Q1WP?= =?Windows-1252?Q?ppSqEOy1Vpx+KkJBxgGDf3FKBkWV8ne7884yNQLVdyfI5QcGL1VexCCZ?= =?Windows-1252?Q?RbpRrDaZixjaecZVbiaVBMvZoLBp0XpdKC4NyBFmqgWoFpKG0cqAr3z/?= =?Windows-1252?Q?F0lo6+1f0R5xIwCY5VoPqKhJLxxM+wHKs5MylxA2UJjyz6y7UTmcSo0M?= =?Windows-1252?Q?jW7GTUDEbDR5NOolkjNasXvR1JWqpSQdP1yreIm1Q4blyiYIX9PTTDTR?= =?Windows-1252?Q?OTvGZwWxtYaFb8rC9MtzJPzWnH53orzyeMwoZdsk/8E7k6Zg7E9MtRn7?= =?Windows-1252?Q?JzICa3M3Xc4Cwa+AktBXP8CfM2a5Qk7NHnIo2llH8CGVJRbnnpIEChvw?= =?Windows-1252?Q?9PkEwFgPsjB1pTo0lgXvEnk6DbDAPYcCeSqgQ36b0Q54OXylJaSD5dev?= =?Windows-1252?Q?Fnvs7HPhwEm4YcpmStZfHvJg6V1OpNNc40/iZKodCkmi3zU6Quijl8h6?= =?Windows-1252?Q?+QyrwS4W1fRhoPsKHlxmIMiGjP6Z2yFlWFo5AKxICJg4JXDLL+HuoGhS?= =?Windows-1252?Q?Yx0fY8z1DfnoF6xw3/OIvjNNe+x6D9HgexhWtavTg5lAleMtcmlSDkUj?= =?Windows-1252?Q?axq8KcX2HoKMnQcJdsZAEE7jGlm5ACzmRAOYFjjrcSBQxgQ14mWfMAuH?= =?Windows-1252?Q?/Lr2uTBs7y9PSevLmqD5VTzqRbITWL2TybB4/GZZXnYOSVxMQ5t2CxhX?= =?Windows-1252?Q?jTiuI9oXFERzOPUUED6GG5zguxOfMRyjhpmmWEHtcI6YyKdItfh5tHX8?= =?Windows-1252?Q?txdrMXngc4Z938TT3IrxxVnKm0NsWTR/3jQ5g3zEBR8N5yI+Y6J6ysdF?= =?Windows-1252?Q?L56Ndpl2C+DYJSeB+KwSng=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB0357E173308FA953D4B3D1A4D6729VI1SPR01MB0357eu_"
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: d8240a1c-2d89-4629-0dc1-08d8fc58724b
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Apr 2021 19:40:07.6718 (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: 17UmbfsHRReN9RevQrhdr8JcDQmM8mrgQwG3my2qhR8XfacmQ457qg89PNqZ93mVPZ08s/aTUpx4xtgTLgLGi5FLhX5b+xYQHI5LozyquUY=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB4799
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/WDM-m8BkJ_s3S33LtR7-69QRCjg>
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: Sat, 10 Apr 2021 19:40:20 -0000

Hi rsw,

That current map-to-curve functions don’t preclude low-order points is a known fact, and acknowledged by the authors in their papers. This is also clear from the hash-to-curve draft.

What people have tried (so far) to address this issue is by using the clearing-the-co-factor trick. But as explained, this trick doesn’t do any help to address the small subgroup issue in the use case of PAKE. Here, we are talking about a theoretical flaw not a practical attack. The practical effect of this flaw varies according to the underlying groups – if it were in MODP, the effect will be very severe, but the effect has been vastly reduced on elliptic curve due to the size of the small subgroup being small. Ideally, these effects should be removed by design. The security of a protocol shouldn’t depend so much on the choices of the underlying groups.

Cheers,
Feng

From: rsw@cs.stanford.edu <rsw@cs.stanford.edu>
Date: Saturday, 10 April 2021 at 16:13
To: Hao, Feng <Feng.Hao@warwick.ac.uk>uk>, CFRG <cfrg@irtf.org>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Hello Feng,

"Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org> wrote:
> Rsw also gave a similar example of having all zeros for the hash.
> Let me clarify that we are not – and shouldn’t be - concerned with
> any of such cases since the values are uniformly distributed within
> their respective range.

Right. And the argument is precisely the same for hash-to-curve!

Let me be perfectly clear: the property that hash_to_curve gives
is that the output is a uniformly* distributed point in the (big)
prime-order subgroup of the target elliptic curve.

At the risk of seeming didactic (in which case, apologies): the
identity element is indeed an element of the target group G.

Put another way: fix a generator g of group G of prime order q. Then,
hash_to_curve returns g^r in G, for r sampled uniformly* at random
in 0 <= r < q. Under the assumption that discrete log is hard in G,
hash_to_curve does not reveal r. Under the preimage and collision
resistance of the underlying hash function, one cannot choose any
particular r or find two inputs that hash to the same r.

I hope this helps clarify the security properties, and why focus
on low-order points at intermediate steps of the computation is not
relevant to the security of hash_to_curve as specified.

* uniformly except for some statistical distance less than 2^-100.

Regards,

-=rsw