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

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Sun, 11 April 2021 12:46 UTC

Return-Path: <smyshsv@gmail.com>
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 F0DDE3A09BD for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 05:46:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.096
X-Spam-Level:
X-Spam-Status: No, score=-2.096 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 5AJs89NM837w for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 05:45:56 -0700 (PDT)
Received: from mail-ed1-x52c.google.com (mail-ed1-x52c.google.com [IPv6:2a00:1450:4864:20::52c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 240B93A0BD9 for <cfrg@irtf.org>; Sun, 11 Apr 2021 05:45:43 -0700 (PDT)
Received: by mail-ed1-x52c.google.com with SMTP id m3so11759926edv.5 for <cfrg@irtf.org>; Sun, 11 Apr 2021 05:45:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=FJv+veK+/lhHOwtJbyOArMmUeBbhPQzqVPNv3gx6ohI=; b=c+g3o/0gJA30zsUPfrVDD5RXxDebB6/DTYuch6YOZNhhEvBoruYe83tfvcZY+C+WWQ sN1OgioPieZsycu4b11Mo9AWkLE0WUufSHgDe01Pcl77IVUI97CBop6wF7kPaKW49DUX mnOGSwh0hrMNSSWQMHIvqByasbLSdAaqBIVtScQWsQw9jZHw9jPBGVylI4Ualf0s079L 6kWRTCm0b/iIg/hfT85bbAXH0utq2CTq3HRVp0is+mqJkkNIV1qqxBR1O9GiVjWxEkgN +1NGTCqF+aWT/27XTw/X+xYJq/dTzrUVNxqzro7I18Cqj7SotkL4TBYkoIof151mB0AW Ub+w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=FJv+veK+/lhHOwtJbyOArMmUeBbhPQzqVPNv3gx6ohI=; b=FOvJMG9roVzorzvLVFvy2STJ5hx7VxGjRq4Lfbru5mMezAoBff1VLthMN6NatYnQ1C kto7rxDCC0ukkJJKTOwvgHkpqsGjw8yudfGb9r302JY6dbR0paFCvI80k5H3eFeruQHb as53Pwml4piks2MSWEicc06lVFQ7i/HhOPyYpm5t/67vu5YrHrJD21+4kDYUluOg1hzk XxOYnr6mMogd2wXR6wE9UNXAokwH5XH5w7b1BfakcHfscViBaWpEP/dubR1sNvrmmGFy Rj3iDIo9IHj3Lzp6s294UovnT5734fTjt5tkvxRTWqGUKhqBaBibcDTKHlYSAA78UBk1 sTHw==
X-Gm-Message-State: AOAM5338gX62BmuWTG6VgDzGZ0UVnxbIbZqV0KgO5we1QobFjCr81/0Q qVgUP79HPES2kB9n7wN0nWpJQwOkGt8BzdUK3jc=
X-Google-Smtp-Source: ABdhPJx1+qhbtjfYcVgYn5iyVgS8ZSX5Dr5iW8WXzL4cJIvYJVaD1H+6OaXzU9LELuRqm47Q44PGoBR5kwyIex/EQEI=
X-Received: by 2002:a05:6402:882:: with SMTP id e2mr25263423edy.358.1618145140711; Sun, 11 Apr 2021 05:45:40 -0700 (PDT)
MIME-Version: 1.0
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>
In-Reply-To: <AM6PR01MB427851BEC3094FB01902DA1DD6719@AM6PR01MB4278.eurprd01.prod.exchangelabs.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Sun, 11 Apr 2021 15:45:29 +0300
Message-ID: <CAMr0u6muVn0qNwD8Dv+N+SACS8DUefhzc1Z4CYtt30VPAP63-A@mail.gmail.com>
To: "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org>, Russ Housley <housley@vigilsec.com>
Cc: CFRG <cfrg@irtf.org>, Hugo Krawczyk <hugo@ee.technion.ac.il>
Content-Type: multipart/alternative; boundary="0000000000004ea64c05bfb1c653"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ScJFeDae9FrAO7tuAsNPQ0YHSX0>
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 12:46:02 -0000

Hi all,

With my chair’s hat off, I completely agree with Russ Housley: adding some
comments about the issue and recommendations for implementors to the
Security Considerations section seems to be a good solution here.

Regards,
Stanislav

Вс, 11 апр. 2021 г. в 13:37, Hao, Feng <Feng.Hao=
40warwick.ac.uk@dmarc.ietf.org>gt;:

>
>    - 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
>
>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>