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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sun, 11 April 2021 20:12 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 D36403A1C52 for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 13:12:58 -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 mYWio4sldx3U for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 13:12:55 -0700 (PDT)
Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-eopbgr50045.outbound.protection.outlook.com [40.107.5.45]) (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 3DA023A1C0B for <cfrg@irtf.org>; Sun, 11 Apr 2021 13:12:54 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=C4Ccm8m9jjyefqDi2vK7D95r0k3ICa3oG3ZNgWyZoazDyEKyHLgvexs4YCHtfap2CBZhrhrZto1XetHmpMFq0Zy1Sb6snTlU2/iqhb7l9BvdQvmB+8k8JzJm6mbpK7ryzNYIbXCU5JqN8+0CDwl9oOsRu4BdfY4ixqRNsO1XiQwykOJyelED9qtkhVP3vbOpiwKBa2UAOi8B8zKDlXwUiMpdZ8W3FLoZHGixAnU3c1W14RPaSxqiRZasdwEjn/VzC+viAFm3q72Yzv4U9s5/f3wNHQsPmyWXyuB8dhtO9S7TSMt6eBWyAIDvI3CJaSTrnBoHDDTbOCMA4HSkvKuQWg==
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=nTNWcb36TH+YDm73ogbfVJwjklQZUYwdhLvZXGJU0xE=; b=OxWYxoE/5fBbrP04UTZQGKCB3j1q06zQCLMl2N8G0ecG9Rqb8BiPntB8/nppGZ7SHBnIQj+1ch0CHlp/deeA8fWfSoyW0M0LDeFdPMbyMLVR3SSw536gAww4Cfe/Bf68IzXg9wip82qGI+fw/h50rCVvZX+Q68MV8Bj5U4eoUXs0Rg7fx4oZLWhH4fQzovtYlW4CpBVmqn9y4b7xuYIWa3XxSplNumuovAh/jU7tA944so4HBPKw5el4j+gKoxzZ6xtwvlJzRUt6HJJU6KIX7zpidZIVwmQWm16VMVRx+Sb3MkChUzE4M+jxGnvqKRNCdPeoQEelRhBp0tZHd0rwJA==
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 AM6PR01MB4278.eurprd01.prod.exchangelabs.com (2603:10a6:20b:23::18) by AS8PR01MB7334.eurprd01.prod.exchangelabs.com (2603:10a6:20b:23b::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.22; Sun, 11 Apr 2021 20:12:51 +0000
Received: from AM6PR01MB4278.eurprd01.prod.exchangelabs.com ([fe80::44c0:8247:69aa:bcd3]) by AM6PR01MB4278.eurprd01.prod.exchangelabs.com ([fe80::44c0:8247:69aa:bcd3%5]) with mapi id 15.20.4020.018; Sun, 11 Apr 2021 20:12:51 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Björn Haase <Bjoern.M.Haase@web.de>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: Closure (was Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve)
Thread-Index: AQHXLw8MzItWiBik906lCLqHFEKsuw==
Date: Sun, 11 Apr 2021 20:12:51 +0000
Message-ID: <AM6PR01MB4278F665DB4FB4E50DB27713D6719@AM6PR01MB4278.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> <CADi0yUNo7o07qM2Qw8yd_eVw_-cM-9wNy3CrLw_Pif79oD_+Og@mail.gmail.com> <VI1SPR01MB0357253A9BA2C2544D6B3F51D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <CADi0yUP-Q-bjmDn-RpiVkns4c8ruK97SidFycg1cPVPJvdFB4w@mail.gmail.com> <AM6PR01MB427851BEC3094FB01902DA1DD6719@AM6PR01MB4278.eurprd01.prod.exchangelabs.com>, <trinity-d2a9d991-f7cc-4510-a5da-5df48f4ae3b1-1618148306960@3c-app-webde-bap18>
In-Reply-To: <trinity-d2a9d991-f7cc-4510-a5da-5df48f4ae3b1-1618148306960@3c-app-webde-bap18>
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: 24a4b4fd-2cb0-40aa-f3f6-08d8fd262f6b
x-ms-traffictypediagnostic: AS8PR01MB7334:
x-microsoft-antispam-prvs: <AS8PR01MB73342188DFE83572A1699954D6719@AS8PR01MB7334.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: iruNZe+3jADHeqP03WegJfxaYna2WXk1lu4to7uMjH5GdyV1kQe23a/f9cxQEgqlHsP8Q54ooy0lnsheijXcpmLEEsQ+IEDJG+O/YgV5PTceh6ZoBGxlo3OsH6JW2cmvmn3IR9NGEfmmVXrdtCUJTv+/tm+88TmXV+33MRaZZMt6fWu+1FWdkm1Rk8yb3TfWjLevy/IDzxWEoYnyw060GntzcyJCfWxNjnD1xAt0yelDrMsXAG1StPVDo2gzO/xA51nt0H2/KNVB4ZNucDSEx36l1izqcflz6Ag/lflAFmtHNmebORzMx9INW/54j7gUNqZAF1sOxzbG+G9oW7GwgEXBsrVgb+FolcQgyaDlEmnIEkIqWXXE6YrshoHB47ElTaLBEpo3cp3saalCWqqn/ROe20cEVLoSo55JpiOLPUiD/P07b6pP5E80+BYZSC5WQuK+XJjpd3pwo5xqT4/ROaplDWVX0oMJ/INSNeoef9p/usuEXc/2vOt0mBK6I6C3X7skh5trnhsaqEhETE92ASHF252spFc2DTVa2ESw6dAqC2XJeMgUJTXv38wqDxUfpOO4KRiyWhU31AMFsItExsLJR6CZgwc+YmviZt7mKoo=
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AM6PR01MB4278.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(136003)(396003)(39850400004)(376002)(366004)(346002)(64756008)(66446008)(76116006)(66946007)(66476007)(66556008)(7696005)(5660300002)(91956017)(52536014)(83380400001)(8936002)(8676002)(55016002)(6506007)(6916009)(9686003)(478600001)(26005)(316002)(786003)(38100700002)(186003)(4326008)(86362001)(33656002)(2906002)(71200400001); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: Ipv/+evo7bdrXOAgCYjKIQ3i8zcJ9Byy2mdYAqPBlgR2nWeZclRQzBarkF1BsVdKXINvvkK1c466q2wU8Mjv6YRTphH3oSePFVq/m1sdAtg8XacpX3+Jflpk9ndDDqdUcSdBgdFwpWuNnNMFmzrJt28gEIi8U54iVYy+Y5Ze5A1Y2sxewSUTzWxiI4GsOeEAqrQRZqFHsX/9lVtW0bhTw3wEwko43dETquuuoU8c54KgXkblt9Zlz68mFl4k8h1oQeiWYj9/MUbVtNgkC2fHW46lEv5Gxy1Gws5ROcqTB/K61HSJbsvDpykbE1o0Vo9o2ICqCKfnfXk7cK1x5VTB9WqobRFKuvlely1LcvG4munIR3etxcKPyB80bcEWGwNk47A2KeHFJPU0FXVF0BZnNNMEUUCZPNM6fwvan7m2hZISHOiWD/aQY4yWJdzoz4hL1dBaBm4lpxMJGw2oddoZ8EfDpif04qCXv6cRgZBOU4XroXw4VpfXRoP/DxlqKxH231wwjq6L+pAwo37lYrzG6kesmFQgAoQHf/KQkeUpI+wGbjVZCPwYEHXY9KxtiaHXrAz5GOet1G4ZxXNdyZ5jenJ7rDhklSbHgwGaxPxJe8LRUikchtm0bAYVYfkGPeVpODRauimM54Fq6IylRSXtFlC+4yRePrW3H9HEknUQgQ3APlq61kQez75cgG6JCeAVBznl3dhLALg2sb/GL+0Mm+y4cA9KG1lXccUEUxlEGBGBDgXz5Spm3ED/NhoOSISfrWlPzNdSYL3H9lZKkxp8y+AvKziIi6LQfaoTixq413Ga3cq9zBMjpr04YQmQsHYDfJ5Gm4i7ahMfoYP6SVXYqSbFQ/D6DCtcQYnD9IjULZb3bwiwtQ4z6TZSQGo4ff47mpNjhpTAZgUK+ZpiAh+aHriX31o/FL7wYekzl8QIYmBw5sj72WOMjy8lw9MtKvlUxfSe3LFl/tQr3N5PWJUO47OTKRsSIOcw02H9nDB7SloggwGN8vHwDIEmnjnRm4suTlVLtSA29w6Y2J55TtIdrxjDczW8jnpCMt9cQmWI2z01R+Y5umxQgCkOrqpbYJt1v6bP22UpgswzZ/bLZ8D/+p6QQ0TZV3MLx44ZWohS04K/chCwKVhk8FYZFiX0G45ztMVF1PSsWrMeza7d5qC4KE15EKPbCy7lawjcSp/FQHe89bD7CL/mzjP2j2Jsl5zqefJutnPifhenW9y1eEf0g2B4DB/h/HNKsdrl5cP17ksUcVUO6YDLBH13PRHRZwSEegT++aUr87o40ZbT2olL/vVQpgy1uyy8BwLUa7p0xS8WKp3V1HpHyPBfV8NqAekQLvSf92RfaL03cOXkr0cpUQ==
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_AM6PR01MB4278F665DB4FB4E50DB27713D6719AM6PR01MB4278eurp_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: AM6PR01MB4278.eurprd01.prod.exchangelabs.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 24a4b4fd-2cb0-40aa-f3f6-08d8fd262f6b
X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Apr 2021 20:12:51.8574 (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: 3x8wVkB5HpEaLiBR8j4x4YbkOWeC4/uWEMQZxJFHxH2r3YwXB0f7CLOZg2rvEBp/lYSJhekuVqKRYBj0uGQshXqhZ+fVcDIZH+rWkr9eoQc=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR01MB7334
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/PdoDZ-bZr8GupwB3bOOL9CjAVgQ>
Subject: [CFRG] Closure (was Re: 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: Sun, 11 Apr 2021 20:12:59 -0000

 Hi Bjorn,


  *   I think that structuring the discussion along the lines of the existing security analysis papers might help avoiding emotional discussion and might help to get things further in a more constructive way.


  *   So far after reading all comments explicitly including yours I conclude that there happens to be consensus in that there is actually 1) neither a security problem with the current draft specifications for hash2curve nor 2) for OPAQUE and CPace regarding identity- and low-order points produced by the various maps, encode2curve constructions and hash2curve constructions as presented in the hash2curve draft.

Thanks for your email. I actually don’t feel there is emotion in the discussions and there shouldn’t be. All of the arguments are technical, which I greatly appreciate. My goal is to clarify technical facts, not to debate opinions. People may have different opinions about facts; that’s totally fine and should be respected.

I hope the following gives a factual summary of this discussion to close this topic.


  *   I raised that the clear-co-factor step in the hash-to-curve draft doesn’t really address the small subgroup issue (thanks to Rene for confirming this). It only hides the issue under the carpet of “identity”. Therefore, there is a need to explicitly discuss what will happen if map-to-curve falls into a small subgroup.
  *   We discussed and established that when map-to-curve falls into a small subgroup, the user password in CPace/OPAQUE will be subject to offline dictionary attacks because of the timing side channel (the attack will work even if the user rejects/aborts).
  *   We established that with a correct implementation of hash-to-curve, the probability of falling into a small subgroup is L/q where L is the size of the small subgroup and q is the prime order of the subgroup. For the curves considered in the hash-to-curve draft, the probability is negligible, so there is no real concern for practical security.
  *   I asked for clarification on whether the small subgroup points can be removed from map-to-curve by design. The replies from the hash-to-curve authors indicated no: because 1) too much hassle; 2) not worth it for the negligible probability. I think the rationale is clear.
  *   Thus, the way forward as suggested by Russ and Stanislav is not to change the draft, but to add a note in security consideration to discuss the issues raised in the discussion, which may include 1) informing the reader that map-to-curve might return small subgroup points but at a negligible probability in the normal case; 2) making it very clear that the implementation of hash-to-curve must include all steps, in particular, skipping hash_to_field will cause serious security failure due to small subgroup attacks; 3) be careful with function creep, in particular, it must not be possible for the attacker to influence the input at map-to-curve; in that case, small subgroup attacks will again work trivially. I agree with Russ and Stanislav that adding a note is a good way forward.
  *   I learned from Loup and rsw (thanks!) that it is not that easy to remove small subgroup points with the current hash-to-curve design. This is very useful feedback which informs me and others as well an interesting research problem for future work. So far great work has been done on map-to-curve, but very little on removing the small subgroup points (the clearing the co-factor trick doesn’t really solve this issue).

Overall, this seems a constructive discussion to me. I thank all again for the replies and comments. I know some of my questions may look silly or not to your taste, but thanks for your patience and for bearing with me.

Cheers,
Feng