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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Fri, 09 April 2021 16:18 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 0EF9B3A264F for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 09:18:45 -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 8ikKkqOH44ZS for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 09:18:41 -0700 (PDT)
Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-eopbgr70075.outbound.protection.outlook.com [40.107.7.75]) (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 0A0933A264D for <cfrg@irtf.org>; Fri, 9 Apr 2021 09:18:40 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=HjUB3XQPHCZH1VNPDeYvUyCFMQS3vKVTgn5k9CzDNi8WO2QM0SLUCfa7yEaCxShRg/jOjyqDCjCrK1b46GAIBLnpXdpzHqbZkp4phKLhozkqSvgB2fFyVwX7mVV5p7XV4t0AylrhA5E4sB61Qvod0a8lNl8YxRje8M90oDlEua5OL6ByEHYXQk+08BKH6RUVhKxhc9XUlj8wKtd+7Fu/iPTUHHUOElMeM8OnriNV4f8hMu0Q8wbNg3pN3X2yWS7Kfwuhe0jqScP7uQWYuJfj3wwI35Ih+nk8u4dyLTdRFNBmsIqdk0Sln3KWmXYOrc3qM4g3b8yZslhLPRx4GKLetA==
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=ZbeSvkyR0J94UPbaVOJUbft7DdG7yuj/FXGRU0IgcmM=; b=GlqHZYzADVENS1ConIDJcDGbjsyKoK5rMy33dK9j0ixtGv6u1P/fwJM+xNuiBlkZuIW1ud5iY6NxCAc5EZIYowXzSVsZ7gSdkpRX+DgGZg0xzqDfRp+xEgf2tca/tuve6JGcE/haxRTuEXVg+9nC/xHKxb2R3VOs2om1mEJJ3/xOr0B8BGWvFNlXIc329UQmpFg2ZjVuYZwNYKNwINQqObGxikPxO3xb2dGMwTUUdetvBQ9WbcP1tleVSGQ7TiQNFT8kCt0kFU17giiRPfvQTrK5kLdIWZMOVpIZP39z5WzObB9OXVKnFHfY1xUxSw6wPyJ0nR8EaTD7ujx2HyuHug==
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 VI1PR01MB5310.eurprd01.prod.exchangelabs.com (2603:10a6:803:d0::32) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3999.27; Fri, 9 Apr 2021 16:18:33 +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 16:18:33 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Mike Hamburg <mike@shiftleft.org>, Loup Vaillant-David <loup@loup-vaillant.fr>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsQ0gAgAADtICAAAg2lg==
Date: Fri, 9 Apr 2021 16:18:33 +0000
Message-ID: <VI1SPR01MB0357AE729116A79C8DF70516D6739@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> <4590aaa512acf5a482c9890ebe48f1760e5831a5.camel@loup-vaillant.fr>, <F9593D27-3244-470E-89BE-85215B2DC9E7@shiftleft.org>
In-Reply-To: <F9593D27-3244-470E-89BE-85215B2DC9E7@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: c2e28d26-305f-4220-2e4a-08d8fb731ef3
x-ms-traffictypediagnostic: VI1PR01MB5310:
x-microsoft-antispam-prvs: <VI1PR01MB5310AEB6723416CFE4B154A1D6739@VI1PR01MB5310.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: DKijBHZQGZYBxohDZpV9MJmkTCI0mvniC6BW1tUS+Cln2k9epTcHg6ETDuE/Ps+IMd/WZ0n3rxGEbHD1imkUuHLp3pFP7Ze0fUCqA2KuH9nffGTTWdfc8rcj7LKDXiR/y846ht5ihLmAKmHBYCS89MbqCmD6p8/YHseD4XO8jpnJZO5HKqB6gillPWzZb3HFwBvTUIAp1WpHFPeFjgLQngBfZ1VT3F0edmLm3PiKhzo6emmw4Bn6FTBqvWclx6yQRxkmrDSQrekfL3q8ro+5ciTSS8kJNF3Y0/uOw/DlMq8PqZndXJCg89mCimrVmnGPgcV+2tsR35MAJ1THvaMkJiwoTMOsiCNxUYrnTAaZm96VbCRfWWN2Pu+zeqBEix8huac0dC2igdcQvYYc9r6tEoIk3a3VetCrcrUXfMTw4m8dy4+0j+jXz9FoRw3g7cuSYMNc5fAeIzESrcHd77L5i1zven2wWi/v1qJdyYQ2VmBnY9IG/iHTyc/FDzq+rtCzvqEN+xP3uAvItntx/N9Gg7eC8eJsqVFSk6rn1sJdndvKIC7bcEd7he8QpKHF17NNTgoesGpE0HkkBwOlCa0w/PvkdT3Hx+2ggeYSy+X6BdlJbGFFEkrUwwzKorwUfYs4aLhxkCWUursfXimIIJwUlQFvJt9wJgXnUO3So8qcNbE=
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)(136003)(376002)(39860400002)(396003)(366004)(86362001)(52536014)(38100700001)(5660300002)(8936002)(186003)(83380400001)(316002)(7696005)(71200400001)(110136005)(4326008)(26005)(66556008)(9686003)(66446008)(66946007)(55016002)(786003)(33656002)(6506007)(76116006)(91956017)(64756008)(66476007)(2906002)(8676002)(478600001); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?BDFUnXEzpXLRkDypXjmCQ16s4EBv+pzlo8QuepPt1biJJ5KFkU645Gq7?= =?Windows-1252?Q?xDIr6+Kt7nBSUIsPLTRZd3H/BcNM+8FuybyZ1XpsDy+SWWaoUZcLN7zu?= =?Windows-1252?Q?+FwyGlPjTFBOxRfkzDCfE3sQy33rh6FAQYLzvLZD6A3W0oJIa987DWAR?= =?Windows-1252?Q?8fowElZGiASABuyuDGXftNwSbQZqN/zL5sffQbI6IcCcE2bp1SWrrTJc?= =?Windows-1252?Q?2poDaBlU/TQ/s4h+CVzToJ6LHwiti7gbCLQihvLi5e0lRYTcLqVm3Esw?= =?Windows-1252?Q?FyNEhfAh55H5QuxgV7j5hU5fyyCbjhWjzTjezoMHY08/2Y4vCD8klupJ?= =?Windows-1252?Q?HViAllOZiGZg7UtlOHE6Mjxm5rfcq58twtI2NFi6fGoKJ2AbzxEC6ylB?= =?Windows-1252?Q?GgVY7mGwSmHiTW026zfgHhYJ2u7ITS1jwnIs64Lql30q4oJ9ziLYg2nC?= =?Windows-1252?Q?IofeJRRQ0JDoxmPw6Z/GPTEGkncAL91RFo3q7SMAgpfC3amHoWFNtDgU?= =?Windows-1252?Q?H4Z1aJUbadQXK77QfnXWQjENOQwnSXJPTD5zewmaoIziiMIipghdvj/4?= =?Windows-1252?Q?NF68RLhBjjhviwM7HkwfOzsZ+yDw55wIYIhk+rE7q+bDOPyaNVKiRmGi?= =?Windows-1252?Q?2pacRfJbTa1CDX42y8Pf7nw26osAo5aUHfCGdeZ32YXSwv7zWal6wPQp?= =?Windows-1252?Q?btNIX23A3ZolLZi5ns0tgQvWEpeXWtNuC685Gxj8ZAu3PXS4OCHyS/DK?= =?Windows-1252?Q?4+nTd2JKBdcQr8TONrJUqP6Y7z69k6aE7hTK9woUrtTwjrHDoVsN/TSc?= =?Windows-1252?Q?CEZocakgTQZPRKXpuU6gMPU73qzohXLHSdnPldMjgmBo7TzAMD0+3PZv?= =?Windows-1252?Q?E5wtG64dmP3yttv5VPKXifjl/Txq/P2YnsJafmbaKsxRzeOlY00mQD7m?= =?Windows-1252?Q?EP6zAHSIkaqtQ47hK4D5yKFO1ffjsPEdPFcQFuXv4+VzKDgfw8amOabc?= =?Windows-1252?Q?C7hm99VoYO0NKKRJWpushezAXxqLIuBtZeKZB6/9F149EPsRpRS9JqxF?= =?Windows-1252?Q?GUVs8fOGgNUjbcpA5ulChgs7wdMFvfLI4Ph1GHeXmlkWP4/4RFXjPpey?= =?Windows-1252?Q?H3YLuSvejPb9y9bU2bPfags4pTMwaic0CpDJTAKsqMddQdXqTmwsQRrL?= =?Windows-1252?Q?DOnnrMW9Higu5Aj+RP3QBt8Qetlj3hzdUQXYgdOSfWI/zDMlSmXYd0tl?= =?Windows-1252?Q?ivLDsTjWIrT+becuyX3q9E9cqPnOKVm1YE/LA8uLeHEG+07lt0j5+Ksy?= =?Windows-1252?Q?6fbpIavn9XR3mAJVjeq5e0OsZDMhic9acLil+yolyJSNC22ibuQykEA9?= =?Windows-1252?Q?s+DTSisfDQybZPsQqZ5kUfoLJ8/vazCMF//ognhSaA6WnaoLlcgPM8h3?= =?Windows-1252?Q?Jjnb1CADwEc3s7KE2MvC5A=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB0357AE729116A79C8DF70516D6739VI1SPR01MB0357eu_"
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: c2e28d26-305f-4220-2e4a-08d8fb731ef3
X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Apr 2021 16:18:33.0600 (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: /1DhXleYtDJjF+FejdwHep52FFrJV04eZT0SPCAp9R6Nwog1UueilbDZk+o9vZBaXL5v/HXRfJmolRHlxX0hy+WUaBWw9rXETELXERwvZ10=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB5310
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/6hUfqSwBf1tUbbsxEMlxWTaZTuE>
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 16:18:45 -0000

Hi Loup and Mike,

Thanks for the comments. As your arguments have something in common, so I will reply together.

First, let me re-iterate my two main questions:


  1.  Do we agree we need an algorithm specification be “complete”, covering all usual and edge cases? In the current hash-to-curve draft, there is a failure mode that is non-recoverable. I’m concerned about this as I haven’t come across something like this before. My question is not on the probability, but the “completeness” of an algorithm specification.
  2.  If a protocol is provably secure under some assumption, do we agree the assumption should be “precise”? There is a clear discrepancy in what’s assumed in the CPace, OPAQUE and maybe other protocols and what’s actually provided by the concrete construction. Either should the assumption in the security proof be modified to fit the real construction, or the construction modified to fit the actual assumption in the proof.

Both of you mention that the probability of falling into a small subgroup in common elliptic curves is negligible, and hence should be ignored. However, we should be aware of the function creep once the map-to-curve functions are deployed at scale. For example, if a user already has an input value in F_p, does he still have to go through the hash_to_field step (which is complex on its own)? A conscious implementer will quite likely skip this step. But that will give more freedom to an attacker to engineer the input such that the output falls into a small subgroup. The negligible probability in your analysis will no longer hold. For a safe implementation, precluding small-group points should be built into the map-to-curve function itself (in constant time of course). I know that’s hard, but that’s exactly why the hash-to-curve function has remained so tricky to get right in PAKE since early 2000s.

Cheers,
Feng

> My opinion as an implementer is two fold:
>
> 1. Excluding low-order points is quite the hassle, and it's not
>   clear how I could do it in constant time.
> 2. We never generate those points to begin with.
>
> I don't want to deal with (1), which makes (2) very convenient for me.
> So I'll just justify (2), using Curve25519 as an example:
>
> - The order of the prime subgroup is a little over 2^252.
> - The cofactor is 8.
> - Therefore, Curve25519 has a little over 2^255 points.
> - Selecting a point at random will give a low-order point about
>  once every 2^252 trials. That means never.
>
> The security of a curve is basically the square root of its prime
> order. Here, 2^125 or so. Breaking it with standard brute force methods
> is incommensurately easier than stumbling upon a low-order point by
> chance.
>
> In security parlance, a probability of 1/2^255 isn't just "extremely
> small", it's "flat out impossible". I can therefore justify my laziness
> and chose not to check for that event.
>
> ---
>
> Note that generating a small-subgroup point *on purpose* will not work
> either: Curve25519 has 8 low-order points, and a maximum of 16
> representatives for those points (maybe a couple more if we allow
> representatives over 2^255 - 19). The inputs are hashed before we map
> the hash to the curve. So it's not enough to pick a matching
> representative, we need to pick a hash whose image is one of those
> representatives.
>
> To do this, we need to conduct a multi-preimage attack on a 2^255-bit
> hash, with 16 images. The difficulty of that attack is roughly 2^251.
> Again, this is impossible if the hash is secure.
>
> As a consequence, I cannot generate test vectors that account for this
> edge case even if I wanted to. Even if I wasn't lazy, accounting for
> low-order points means writing code I cannot trigger even if I want to
> —dead code. That will only harm security in practice.
>
>
>> 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 assumption is correct as far as I can tell: yes, in *theory*, we
> have a couple exceptions. In *practice*, those exceptions will never
> occur. The probabilities are low enough to be considered negligible.
>
>
>> Has this issue been considered? Apologies if I missed any discussion
>> on this before.
>
> Likely. I haven't followed past discussions though, so I cannot say.
>
> Loup.

Yeah, the usual answer is: if an event happens with negligible probability,
and an adversary can’t cause it to happen more often, and it only breaks
one thing, then it doesn’t affect security.  Any reasonable adversarial
strategy has some chance to break the protocol anyway (e.g. just guess
someone’s private key), and this unlikely event doesn’t significantly
contribute to that chance.  I haven’t checked the details for CPace and
OPAQUE, but for cases I’ve looked at it’s been fine.

Of course, implementations will not be fully compliant with the spec
unless they can properly handle the identity point.  They would have to
do another analysis to see whether this sort of non-compliance is itself
a security issue, but the answer would probably again be: not unless
an adversary can cause it to happen.

Cheers,
— Mike