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

Hugo Krawczyk <> Sat, 10 April 2021 17:28 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 043113A161A for <>; Sat, 10 Apr 2021 10:28:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.399
X-Spam-Status: No, score=-1.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id AdrAK9kqSbHS for <>; Sat, 10 Apr 2021 10:28:24 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id ED0313A1619 for <>; Sat, 10 Apr 2021 10:28:23 -0700 (PDT)
Received: by with SMTP id a7so13543624eju.1 for <>; Sat, 10 Apr 2021 10:28:23 -0700 (PDT)
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=LxJrRGQURcmCIaSKFpXbzVSeriV9zQArVH/T6NmPf7M=; b=sOPQNx33Sa6xDjtbnjE4azVQohtbnn1UTCIOk6KitQWgZ+vQPlJQG/RNohigYeVXwh werxxnhJl0vPNvhnOEh7+mEduXLZef1y5a3firZFjir5+MF9ypTaw3VYNTVm5B2MTS3a Wm9QV/Tm9fUr2a7tdVJ8q0Z/RLebnc1eQC9eJt6vWgiIesCwOiJnAEb4PyHJxXPV9wy4 1z3MTtx39ZpodnWWVBW9+ULzPQ44dd1AOWu4eVsyPxGvCfyB3CZ6Nf3jVkkrREGwZtys vU4GbX7iRmf+5nrs1Y7W7AhjgXEzGoyCusTdV1eyqK7IOY5D4sn0yfxqEGMQO2kranZK GNIA==
X-Gm-Message-State: AOAM5304mJdKFZBcKR2666a+PNHz5aqRfqBlKSSf20TJ9cxY6pZIm4KX /ZKpR02F1jROyj/9A4dD8tdnA1KSHk+cfnCWTF0=
X-Google-Smtp-Source: ABdhPJxji3O4ap6sIhPgKqf2EP6RlcOlYH4z7cqAZKYDSRSegiL1d6rnDnBqjGraRX3YndDlakU+4zxjlGM/y/pYAnI=
X-Received: by 2002:a17:906:c0c1:: with SMTP id bn1mr20183212ejb.406.1618075701397; Sat, 10 Apr 2021 10:28:21 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <> <> <> <20210410151254.7ze5pt4lpvblhk3f@muon>
In-Reply-To: <20210410151254.7ze5pt4lpvblhk3f@muon>
From: Hugo Krawczyk <>
Date: Sat, 10 Apr 2021 13:27:55 -0400
Message-ID: <>
To: "Riad S. Wahby" <>
Cc: "Hao, Feng" <>, CFRG <>
Content-Type: multipart/alternative; boundary="00000000000066ce7e05bfa19b7d"
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: Sat, 10 Apr 2021 17:28:29 -0000

Feng, you say:

> On the other hand, from the perspective of a higher layer protocol (say
CPace, OPAQUE and PAK), it’s simply impossible to handle the exception. As
soon as map-to-curve hits the small subgroup, the password in a PAKE system
will be compromised. Therefore, the above warning is self-defeating and not

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

(The same alarm should go off if it just happens in a run of any other

(*) Of course, you should first check that you really have a preimage of
the identity under the hash - the most probable event to produce such a
result is an implementation error.


PS: When you have an analysis that assumes a uniform distribution and then
decide to deviate from it as a way to "enhance" the design, you may be
introducing subtle weaknesses. An historic example (irrelevant to the cases
we are discussing here but illustrating the principle) is Enigma's
avoidance  of encrypting letters to themselves - something Turing was fast
to exploit

On Sat, Apr 10, 2021 at 11:13 AM <> wrote:

> Hello Feng,
> "Hao, Feng" <> wrote:
> > Rsw also gave a similar example of having all zeros for the hash.
> > Let me clarify that we are not – and shouldn’t be - concerned with
> > any of such cases since the values are uniformly distributed within
> > their respective range.
> Right. And the argument is precisely the same for hash-to-curve!
> Let me be perfectly clear: the property that hash_to_curve gives
> is that the output is a uniformly* distributed point in the (big)
> prime-order subgroup of the target elliptic curve.
> At the risk of seeming didactic (in which case, apologies): the
> identity element is indeed an element of the target group G.
> Put another way: fix a generator g of group G of prime order q. Then,
> hash_to_curve returns g^r in G, for r sampled uniformly* at random
> in 0 <= r < q. Under the assumption that discrete log is hard in G,
> hash_to_curve does not reveal r. Under the preimage and collision
> resistance of the underlying hash function, one cannot choose any
> particular r or find two inputs that hash to the same r.
> I hope this helps clarify the security properties, and why focus
> on low-order points at intermediate steps of the computation is not
> relevant to the security of hash_to_curve as specified.
> * uniformly except for some statistical distance less than 2^-100.
> Regards,
> -=rsw
> _______________________________________________
> CFRG mailing list