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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sat, 10 April 2021 20:37 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 4AC1F3A1A9E for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 13:37: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 D8aqZory22QV for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 13:37:24 -0700 (PDT)
Received: from EUR03-DB5-obe.outbound.protection.outlook.com (mail-eopbgr40086.outbound.protection.outlook.com [40.107.4.86]) (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 87DF83A1A9C for <cfrg@irtf.org>; Sat, 10 Apr 2021 13:37:23 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Rrqwuycb8wSSpsQ0AXpxzS5rS6QWOOyVaLG4ax3RgGo7c1ZVOsjQbrhb4yHoOOTGdRhE7XgbeXDZ6vyYAV5ltII3ZTqvuBN33IatZ8lpUwulgveAtngQf+c9zar1JJmeBfizpVlf0HuUxGFM+V3fZ+94SqDMRC5bc4OC73C1AVokVrfl/xcBLUiN2NBfdyErV/4DqzDA2x7sHM7pkuosre/TPoDwMjTKOLaEXFIoctB/9ufKZnNs2gilb3XFD2LvURrNIeFxUjYlY0ycX4gYD35sZ8TsHSBOcnQqgNH69a8iwnT5YuB2SJ9zRqb3Cgtj/bfQECle1u52n9lCxDL/gg==
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=nqPcMNxxn2NmdYlDwg3A6A28tBVTYLG/0wmBPNjj2Vk=; b=G7TK4olEnseygatY2RViifthI2pMLzgYUMNFY8ISmmAe0oYxQsEPvLO7vpDVpImv5nb0GcUM3z0Tf+xJsBBaXhNm0jLPgB1phHJdKMWmeC+65mIhix+H+SEdEd43LM6ccVqqQZmlLRI1wLRbglX2QRkK5SGuaccIjgkKKxbZ37nRVT72HBPAq4YfPk4ZqPdJi6InEt8YMhvECrtj4jFC+PgQvInTB8EpOinU5P10DCgtSUh98Ykdh0Rv+aXohO2TWx3QdYmeM0H8X9oODMd7CFvBI9JoqHn0L0ggFJSpzlh88aMP4F7F7D8A11z5gkt+ep6TXTfDz/G/lwwE6+CepA==
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 VI1PR01MB6317.eurprd01.prod.exchangelabs.com (2603:10a6:800:155::24) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.16; Sat, 10 Apr 2021 20:37:20 +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 20:37:16 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Hugo Krawczyk <hugo@ee.technion.ac.il>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsrj2AgAANMx6AACTDAIAAhZzVgAB3mgCAACW5gIAAKQYu
Date: Sat, 10 Apr 2021 20:37:15 +0000
Message-ID: <VI1SPR01MB0357253A9BA2C2544D6B3F51D6729@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>, <CADi0yUNo7o07qM2Qw8yd_eVw_-cM-9wNy3CrLw_Pif79oD_+Og@mail.gmail.com>
In-Reply-To: <CADi0yUNo7o07qM2Qw8yd_eVw_-cM-9wNy3CrLw_Pif79oD_+Og@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: ee.technion.ac.il; dkim=none (message not signed) header.d=none;ee.technion.ac.il; 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: 198d0dec-5a74-46bd-76ab-08d8fc606dad
x-ms-traffictypediagnostic: VI1PR01MB6317:
x-microsoft-antispam-prvs: <VI1PR01MB6317A7B58176708D9A4E5D7AD6729@VI1PR01MB6317.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: b99ZyN1woCo8OHsZGS5hF2YUJ7CAewZnqLFIBOJ7Alv9Kxh0nVoiaefaTm7zT1NIY0OKtOzTBt+bEqO8qkYaeNO3Dq1ZVufXZ9PyBbq16nY+Lyy69C357n2817M63OjVQ9Nf79AlO1rGwkD7SoFlABFjqWwc+QzzOabLM1qYzvV2i0TZ6xGGNri/pYWQQSuW9VwLvbIqnYgrC+VUYWq/G8TJ2Prlqjbrqd3pZjXFVHexPIhbGPMsYJmHM5yv4mcOCyyHC5ZsfUjuvxHb5ACRWmkbhjXLqv8VbxM53Ja8C3w1c1F5CU/bJLM1lqwvWhTcjpvx0hj8pY9gXbdMRk5XMKLe0HoxcL+Vh2zObwsjAGSzq1Z5SQMorS8Q27uzkqeKo1Ta1SRIPKM3aBslSIzbwQKOwK6axEfGroW//OTcBeA6EV2lWdy7CWSXZkAYW0yEAavynmAxND9ejwQjwwkWUz0xS1tPpaMkktyhD5YTXAcSWMRynNjiVICq5XaHGfhYZUyKJRmr+MOtGDKW6pwqFKYIAUS24VEVS58TcRrcXA8U6f/MmO8UJOThx1WlAamAlkq2mYtIxiVITgqgJ9llClcPxecIPHX6nsjgCYFNuJw=
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)(39850400004)(346002)(376002)(136003)(366004)(396003)(5660300002)(8676002)(316002)(6916009)(8936002)(9326002)(4326008)(786003)(33656002)(7696005)(38100700002)(186003)(76116006)(55016002)(83380400001)(66946007)(2906002)(91956017)(52536014)(6506007)(71200400001)(66574015)(66476007)(66446008)(9686003)(26005)(86362001)(478600001)(64756008)(66556008); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?opMI9XQymXAI7QX6NO6wnI+vby8cgM+bAhUMFD0LXGv0ef6V3sdkY4EN?= =?Windows-1252?Q?RCrQRgRB9Q6Uu7CgyV1BmJMUkkCTvrkh6Km6Ze2j+vg308RLPgR5JqF6?= =?Windows-1252?Q?UJGYvrKHeRWlkQXJAFPr3+ttvKWov/M4mqtBJoPV3iMPRcVWn8x6oTE/?= =?Windows-1252?Q?8rsXcXpX3Fm04HbGEfF18t0YyjOurKFqc0TuUWl5cHddP71CrsNVfG/f?= =?Windows-1252?Q?dgQUn2IkrFBx7wKHOLptOMNQgnXt85GndjXwAMCPAaUfeKQgl+WK47Gm?= =?Windows-1252?Q?GovUnDN53ZlHwMeJUghddlgirBfSb3oXQ0D0Ql5cZSQWxoejrey5KMAV?= =?Windows-1252?Q?a9VsuZ5ez/A8WgoHD77uQ9GTo/D3P772nKoyvaSPjOczTa1h+isALomi?= =?Windows-1252?Q?RSLDjBQ5PurAha8lWa+MYe/+41vlTecUiJbsAFrmuHPLfkoOyxz0IUD9?= =?Windows-1252?Q?Y0HnHtY5LF6bdLxpiy/kOlknpme9M/FtTv2jUTk3Lk0gactw5QocvX04?= =?Windows-1252?Q?srMBwwKzn5bct+SwlHyvPzBwCatwwku2wZMuR9T1CxxRCe8JQ/6JBPle?= =?Windows-1252?Q?hLFFh6aAP1V09C27DJpoqA9d5A8b5jDDcszvPssRykIt8+655fLp7q1f?= =?Windows-1252?Q?Qd6BJd8ETbKBEbK5xEoqdzUcVztgvMq/GF8NetRaRcG2j2/t7DmECMkg?= =?Windows-1252?Q?huFoOc59HJ9xUAndcXWCXM6tAYgGPw7Ye/vZkGytWnIdj7eHLDKXBxG4?= =?Windows-1252?Q?H7bN+xGeBtcx6tgJ4q0+VT1FbvAt22nxcbpirh9OPThWVcwp+VtzpbZ5?= =?Windows-1252?Q?JL9PyTPbXA6uCf7ZimR+1OPHi7sjsZvDCDd4Riyt/4R+lpDmyu/8nc98?= =?Windows-1252?Q?ME9bv95us6CxtleY75pl34uC9ZRbh/RX5mW13xKcGbh8UYQvwjWYF1yj?= =?Windows-1252?Q?VrzMWHg1yNO86D8Gd1XKGarsidAiCheg9FtEHu8GQxCCWgrR2FqDXgtK?= =?Windows-1252?Q?s4h0nKH9dnVQ5wWM9UbmUU5MRTK/Qy7YgbJNYyXSeq6UskMvBhQCoBhF?= =?Windows-1252?Q?ZFQY2qoFdIexLoBvUOHGT8DZbxv4XTLk+E9SMQUX9PDNdsYJvq/TDMlr?= =?Windows-1252?Q?tecR3YE32+Zh8/slnA8vgECuOpketn+9RFHGJxGkLQ7WPPX3T1ZpPFIZ?= =?Windows-1252?Q?JHU/FO8PW0WRDQm/5g4F0UOtO5t0suLjQuYbbUppvbq2fsXPFOHdDd8g?= =?Windows-1252?Q?tmj6vFwlbb3wZz6agpxST57CKIWJElmwM5pykKG1TtkpTQ7CrlyZNpIe?= =?Windows-1252?Q?zREqIxjInl/AuBP7uPkjPGrbikQKw0tatFIzeHF0+JA2ori6rNOSt+tq?= =?Windows-1252?Q?HA3fR7Q66L7ZgYRGX3EJfg3dQmO9IQMsDaeMOnPjsds3HilhnQG5m9c8?= =?Windows-1252?Q?Q7q+CDhGf8zu/ClRE5ZKXA=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB0357253A9BA2C2544D6B3F51D6729VI1SPR01MB0357eu_"
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: 198d0dec-5a74-46bd-76ab-08d8fc606dad
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Apr 2021 20:37:15.9769 (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: ooSCVvkY2vQXUBHcS8AaYAyQfkITyjFgEU0Z0+kv9VwwnaQZmi+h0/4zpXhZDvOfh75GItjw3TmclvLRGrJ2H9bYBV9o84as4nQT2YYrHhs=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB6317
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/UB0JkpySBmekZ3wVkxS4IhDtm_A>
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 20:37:27 -0000

Hi Hugo,



  *   If I understand correctly, you are saying that in the case of password protocols, the unlikely event of (a correctly designed, correctly implemented) hash-to-curve mapping some value to the identity has irrecoverable consequences that are specific to the PAKE setting.

  *   I wanted to comment that in the case of OPAQUE, you could check during password registration that a user's password maps to the identity and ask to choose a new password (we are used to websites rejecting some passwords). However, when that happens, the website should immediately (*) sound an alarm to be heard across the universe. You would have found a preimage of the identity under a RO-modeled hash function. Either you are observing an event with probability, say, 2^{-256}, or you are observing a hugely more probable event: Someone broke the one-wayness of the hash function. STOP USING IT IMMEDIATELY FOR ANY PURPOSE.

As you know, hash-to-curve has three components: hash_to_field, map_to_curve and clear_co_factor. For the sake of discussion, let’s remove clear_to_factor as it has been a source of confusion, and this removal doesn’t affect our analysis in any way. Also for generality, let’s assume the small subgroup size is L. The value L depends on the group setting. In MODP, L is large, but in EC, it’s usually small, but that’s the implementation detail.

OPAQUE has a registration phase. In your paper, you assume registration is done securely but without details. Therefore, I have to fill in the details below according to my understanding (apologies if I got anything wrong, but in that case, do correct me!)

Unlike CPace and other balanced protocols which may use an out-of-band channel (visual, sound etc) to distribute a low-entropy secret, OPAQUE has to do the registration over a network since it involves exchanging data of long strings (k, Ps, c). However, in a typical PAKE context, there is no pre-existing secure channel. A natural solution would be to do the registration over SSL/TLS (which introduces a PKI which is what PAKE aims to avoid). But a PKI is needed only for a registration phase, so let’s assume registration is done over SSL/TLS.

The scenario we consider is what happens if the output of map_to_curve falls into a small subgroup. The user has to reject it and choose another password, but the timing side channel gives away the exact oracle to a passive attacker to do an offline dictionary attack. Note that the attacker doesn’t need to read the content in SSL/TLS, but just observes the communication time. He can exclude passwords that don’t fall into the small subgroup.

So the registration phase doesn’t help you. Even if it’s done over a secure SSL/TLS channel, it’s sufficient if the attacker can observe the timing delay in the communication.

Therefore, the best one can do is to hope map-to-curve never falls into a small subgroup. But in that case, wouldn’t it better to preclude small subgroup points from map-to-curve by design?