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

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

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id F0DDE3A09BD for <>; Sun, 11 Apr 2021 05:46:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.096
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 5AJs89NM837w for <>; Sun, 11 Apr 2021 05:45:56 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::52c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 240B93A0BD9 for <>; Sun, 11 Apr 2021 05:45:43 -0700 (PDT)
Received: by with SMTP id m3so11759926edv.5 for <>; Sun, 11 Apr 2021 05:45:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; 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: <> <> <> <> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <> <> <> <20210410151254.7ze5pt4lpvblhk3f@muon> <> <> <> <>
In-Reply-To: <>
From: "Stanislav V. Smyshlyaev" <>
Date: Sun, 11 Apr 2021 15:45:29 +0300
Message-ID: <>
To: "Hao, Feng" <>, Russ Housley <>
Cc: CFRG <>, Hugo Krawczyk <>
Content-Type: multipart/alternative; boundary="0000000000004ea64c05bfb1c653"
Archived-At: <>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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.


Вс, 11 апр. 2021 г. в 13:37, Hao, Feng <Feng.Hao=>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.
> Cheers,
> Feng
> _______________________________________________
> CFRG mailing list