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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sun, 11 April 2021 10: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 4B97E3A36EC for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 03:37:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 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, 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 8Wk1MjepNTSu for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 03:37:08 -0700 (PDT)
Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2048.outbound.protection.outlook.com [40.107.21.48]) (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 47BC93A36EB for <cfrg@irtf.org>; Sun, 11 Apr 2021 03:37:07 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Es9pzeWMRzK5P/PAziANt+9OOyWQ9miMdpnX7gtXVQ2mmIdy+tj7HGGYm1n7G29fCfT/Uzp/AmVgQVtm2ncY/3GlWTfe2zRM7LaN6CqyqHSg30IvFlv2hPLCcEIgSpSCEyqQcB/SWNMY2lj2+YgL6RdBvysyRkkW8ayfoRH+QUAgipOHnhWkddhUYpoCb5gcwl969t8LsM4qegxfBwLX7U9i3jh98Nd+ZjVNTZ7klcIBes077MIQ4GpqiQVUkp//9XqIuFZKIwsezvgv/fWxVK1A37xA00yibgbw0dl+PYtpDwKOjjlgnEO+VEXdbMGmhiGXvLum514k0p80qbpl5Q==
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=SvuyncLf/UNExT96ZXMig1U9IHBnv8toAx01NRP63+c=; b=PYiuxd4ohVlFdnMSfnwtqE+4dKdBiLZQ2oG5Kd0XD3Salxl6J5SOoh48w/Nhx9BLxAshuPxRsrpgHedo+24uJfpN0h98Oo2bLo49pzlSRKLzWMYHEJYF1xqWV/XeytDaL7tHCE+JRwNB1eA1BDals6P9cvtLzY1GjWSx9w/NXR2LabqcgesvqSUeAWP3ajVC7TohFac++bsrgIAEOsE17KHMNALBdVuSeL29mpHsA2JZKPGE8sxnOCI/ag8SxhnzbhXfN9EJvaRWWoVqshPjvcxxQDI85LVx6mUz6+cU8GcrdOna2NiWRR2Yof1gqEu9/foymZ4eY8YARFn/wney4w==
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 AM6PR0102MB3047.eurprd01.prod.exchangelabs.com (2603:10a6:209:10::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.16; Sun, 11 Apr 2021 10:37:05 +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 10:36:59 +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: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsrj2AgAANMx6AACTDAIAAhZzVgAB3mgCAACW5gIAAKQYugACNaACAAE7ZDw==
Date: Sun, 11 Apr 2021 10:36:58 +0000
Message-ID: <AM6PR01MB427851BEC3094FB01902DA1DD6719@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>
In-Reply-To: <CADi0yUP-Q-bjmDn-RpiVkns4c8ruK97SidFycg1cPVPJvdFB4w@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: ba13cbdd-7e18-4649-2404-08d8fcd5bc4f
x-ms-traffictypediagnostic: AM6PR0102MB3047:
x-microsoft-antispam-prvs: <AM6PR0102MB3047534923A86E967816FEDDD6719@AM6PR0102MB3047.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: p6Gys5/wlHra0VnRsQ/2vTMuC/w9j/oApRpG/Tvr4LssnifzwhTEWBJ9gUs9tyNCYpKkgbQqUF86Kk7FvTQsw343+Nc/z++YtORMj1tgxnGnUV53Wh95k5sax422EtJx9iMwk6+PPedxRVUWzMvecF0A2OKXtnVjPOQ5zgxPv1XJObfzJGmvYQAwL+e9bcGWJDhzMb//QiPuGwEfrJbOZ9AVNGN9JD4z2zfkbJ0q2Sw6r+iUr0EKUd2w1NKdEsaHujICqyEmeGI2Wd7e2nrX5pwSzezZTeiQZRBVEOutTQv2SYB7UmG4WVC0Hz1vepnxRUfA+XE55sFOaV+mML1Pi5dV4PW5tsCR2T7IcJ+VDQuL4BWEaSQ91BLYwvIqBv5HQxh/YKBTwOplyWxwtzD6gN7zTmdMtypFhDIkEJHFadUCJgXL2WJGZvMbeO69drcGzBwb4e32LD24Dr/q9o76uEzTK+GnBBH1JTazJtYiTpESkVVU0/2Gj3iO14D7958YYKMAIfi4ryDv3pjld9rgC9SIJ3mBR/UmTKQK2Jw0tfipzUX2Xm6ACCMVcFj31F656MVYF+A8k8mNzaTh3ERTaZnQOzXhrU038M9mGRChI3gz6eR81j74tOqQMA9IR6QE9RQJjFB1MdB+K34ySbMJoBUt2osYNJqytgJeLXqwsKPDCMZaSeC6ttHGk5AWUsx+
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)(366004)(376002)(346002)(136003)(39860400002)(396003)(478600001)(91956017)(6506007)(66446008)(8936002)(76116006)(66556008)(8676002)(66946007)(64756008)(316002)(52536014)(83380400001)(7696005)(33656002)(66476007)(786003)(5660300002)(966005)(6916009)(55016002)(71200400001)(186003)(9686003)(26005)(38100700002)(166002)(86362001)(2906002)(4326008); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?Aric+RpXpNKdB46k51EscrhcADu7La1Q/6wCuMntFF2V9rT41YiuxjBi?= =?Windows-1252?Q?83x64PTPJhx6zWqSlpwWGz8IzJpxoPMj5hAuc+B7CuycX32EsBeEmy/z?= =?Windows-1252?Q?1n/wc2PIfylym+rDlj8fOEpJkqH924a670xwoLyE5DJXzSjMBUQWj/U4?= =?Windows-1252?Q?QH+3jqrl+mOOl81H6V5o8KX9wyg92MwhVxSMT0bCfDwCa/3VpKpqKHE+?= =?Windows-1252?Q?nXaC0FH5zIq7M5x73dZS7dyo3/0p8eL1ncxGSTl0i4s9LROyb0MfqAdW?= =?Windows-1252?Q?rRTheoHx3hcmLV2N29TH9OBbqm2in7tNSv6bSeknjxmjnyA9q1JsUzK2?= =?Windows-1252?Q?1TefSdPk3TwvMN5NM5R0AVknSZRT5V7dPmkkG6O5v+61H9/TPDbpd3tO?= =?Windows-1252?Q?l2G468R9t4Z0aqnsQ+wATnAJgKQICDjdVlycS3GWvbCXNsCNkjey9/vh?= =?Windows-1252?Q?7mnE9ykaZPdMZhb7FIXRH4AlKuAAzkR/pkGlW2Sd2uadcmt11+D9YahV?= =?Windows-1252?Q?J3A4kpRTzxZkGWBqp17o9AFnKSkulOS1CsJblDKk6M2yCGoDfpID5bQT?= =?Windows-1252?Q?dr0Tw4zA6thM1u58lOmgM4Ef/+s7EH2O9n1KPAEzjOqfrLsgHbXd+3XZ?= =?Windows-1252?Q?SppnVLKlckO0+kgoOARsSi6a6o1gGoV9/KXn2AAMVerqOOmwG2hG26C9?= =?Windows-1252?Q?kGNbzUbErz4TyELk8s9QkNxmuhRW0nUuA11S+t8T2x/KbGsqaegUMB2Q?= =?Windows-1252?Q?VbwsaFag7Qdwr2EGRbgWx2nRnFoDK+Ak9r5biWMZsiOqKLVosxI8OGkZ?= =?Windows-1252?Q?XeX4eeinVRmY0WbtSYerWiFKWRwPfZE9Sd0lAOz4aXuM8eRZaiALL8qL?= =?Windows-1252?Q?3/Mw0OZakI+kTiEuZa70WGy6XoKzdEHqamoBfhuEnLyuQyEMxzYevW92?= =?Windows-1252?Q?sOcaBQfneejoBGcbpAwFWEpwMnWoLzjFWrW5lmrZYvV18PePSe7/FKvj?= =?Windows-1252?Q?pGaaEmNRCKcufD9b+7XEF3fy/kmT+/uJyJRGqd4TNN1O3kAOYGW2W9HC?= =?Windows-1252?Q?Zy4P0vlTc6vVOTK2blqNOKdVEhHwsSgvLZ79b10AN2poBfwjtdtAjUoO?= =?Windows-1252?Q?aS6fL3CIADNf1LnVlkASwbOHJrhlD5JtBZAYUj92xv4OiVRjALIoGOCF?= =?Windows-1252?Q?WHwmGYnoFkkTtFRblB2CuuXE1PVt/rFCeDl8inbfM8J2QjPl7vnwiovH?= =?Windows-1252?Q?yasxMh50ishUyDn4r3RcoWz/U+N677ZYw0IaEfsYYmm5Q6z3hu1ybYR9?= =?Windows-1252?Q?S+Ty+I1d0WoeKBBvjhpTk2+Wo6KSDl0erB3hYX4ZvK7R5J7p20PAdCB0?= =?Windows-1252?Q?6lwsguobAF5ETaBVjP1A81cKY36krfWcgRi7zPZ9xaK5/PMhuLdHLXzY?= =?Windows-1252?Q?5ibZtXv8YSja/+axCJemdg=3D=3D?=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_AM6PR01MB427851BEC3094FB01902DA1DD6719AM6PR01MB4278eurp_"
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: ba13cbdd-7e18-4649-2404-08d8fcd5bc4f
X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Apr 2021 10:36:58.8133 (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: 0x682V0nzbZ1b5ELyXQWI5ZGblkJ+iBdMlabJh4m6wFuEvdWMwvHaEB0alIK6Hmc9eiAzLbJXCbQZfoXKb2dnmx1TbXjODtusuPrem+33rQ=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR0102MB3047
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/8vJqs0fxWd3wTZSCwXnCXZfLYPI>
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: Sun, 11 Apr 2021 10:37:13 -0000

  *   I don't see any timing attack here. We are talking about a user that chooses a password that is mapped to the identity (let's call such a password magic) and is asked to choose a new one. Only non-magic passwords are allowed. All the attacker learned is that the user initially chose  a magic  password that was rejected and then chose a regular non-magic password. It knows nothing about the user's accepted password.

Once the map-to-curve output falls into a small subgroup, it’s a non-recoverable failure mode as the password is inevitably disclosed to a passive attacker by the side-channel. Now the user has to choose a new password. This is the same as CPace (using the hash-to-curve draft). The new password is of course fine. But the scenario might re-cur when the user tries to change passwords.

  *   Of course, this is a purely fictional discussion since the probability to have a magic password in a dictionary of 2^128 passwords (as rich as an AES-128 random key) is 2^{-128}  (for curves of size 2^256).

As I clarified before, I don’t claim this is a practical attack. So far this is mostly a thought experiment, which I hope can help better understand the PAKE system when you have the real hash-to-curve function included.

What this though experiment shows is an idiosyncrasy in the system. It seems the small subgroup confinement issue hasn’t been considered in CPace and OPAQUE. This is understandable given that both protocols have been assuming hash-to-curve as an idealized function. Fortunately, for the curve settings considered in the hash-to-curve draft, the size of the small subgroups is so small that the practical effect is negligible. But the effect can be dramatically different when CPace and OPAQUE are implemented in a different group where the size of the small subgroup is not small, e.g., DSA, Schnoor.

We know that both CPace and OPAQUE have been rigorously analysed to be provably secure in a strong universally composable model. That’s all good, but what exactly does this mean? The proof makes assumptions, which typically include certain hard math problems. What the above though experiment shows that for both protocols, the assumptions also include implementation choices, in particular, the size of the small subgroup must be small. This constrains the protocols to specific group settings, and not generally applicable to other group setting as one might have expected.

The idiosyncrasy itself is not a problem (depending on how you view it). In the history of PAKE development, there are lots of examples that certain aspects of a PAKE system are idiosyncratic but can do negligible harm when you choose very specific implementation settings.

As an example, in 1996, Jaspan described an idiosyncrasy in DH-EKE [1]. The possibility that the password-encrypted item may be decrypted to a value > p gives an oracle for a passive attacker to exclude certain passwords. Of course, one can argue we can mitigate the effect of this issue by carefully choosing the group parameters: namely, choosing a safe prime that is as close to the power of 2 as possible. Thus you can mitigate the effect of the leakage as low as you want, say below <2^{-128}. The theoretical leakage is still there, but the practical effect is negligible. This is fine, but it does mean one has to very carefully choose which specific group setting to implement the protocol, and the same protocol can be trivially insecure in other groups.

SRP is another example. In 2010, I analyzed SRP-6. I didn’t find practical attacks, but found an idiosyncrasy in the system [2]. The mixing up of operations in different groups including small sub-groups gives a possibility that an online attacker may guess more than one password. This is not any practical attack and the effect on the practical security of SRP-6 is negligible. However, this idiosyncrasy shows that it’s simply impossible to prove the online dictionary attack resistance for SRP-6 (namely, limiting to one guess per execution). Indeed, no one has proved that property for SRP-6.

There are other examples, but I won’t go on here.

In summary, with the current hash-to-curve functions defined in the draft, the practical effect of a small subgroup confinement is negligible for OPAQUE and CPace. I was hoping we could remove this effect (never mind how small it might be) so the security claims in CPace/OPAQUE can be cleaner and the hash-to-curve draft can be more useful, but if people think that can’t be done or is a waste of time, that’s OK! In that case, one might need to explicitly state the assumptions (not just math problems, but also specific implementation choices) and be very careful in applying the provable security claim to different group settings.

[1] Jaspan, “Dual-workfactor Encrypted Key Exchange: Efficiently Preventing Password Chaining and Dictionary Attacks”, 1996.

[2] Hao, "On Small Subgroup Non-Confinement Attacks," 2010. https://www.dcs.warwick.ac.uk/~fenghao/files/Analysis_of_SRP_final.pdf

Cheers,
Feng