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

Loup Vaillant-David <> Fri, 09 April 2021 14:45 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0B2893A2380 for <>; Fri, 9 Apr 2021 07:45:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id chKVrEvoPVmE for <>; Fri, 9 Apr 2021 07:45:07 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 6FFBA3A237B for <>; Fri, 9 Apr 2021 07:45:06 -0700 (PDT)
Received: from grey-fade (unknown []) (Authenticated sender: by (Postfix) with ESMTPSA id DE0521C0016; Fri, 9 Apr 2021 14:45:01 +0000 (UTC)
Message-ID: <>
From: Loup Vaillant-David <>
To: "Hao, Feng" <>, CFRG <>
Date: Fri, 09 Apr 2021 16:45:00 +0200
In-Reply-To: <>
References: <> <> , <> <>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.28.5-0ubuntu0.18.04.2
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit
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: Fri, 09 Apr 2021 14:45:10 -0000


> The methods defined in the draft map field elements in F_p to points
> on elliptic curves. But the points include small subgroup (low-order) 
> points. What if the mapped point on the curve falls into a small
> subgroup? The clearing-the-co-factor step (section 7) does no help at
> all here as it only turns the small subgroup point to an identity
> point.
> The chance of falling into a small subgroup is extremely small, but
> for the completeness of the algorithm specification and the analysis,
> it’s still necessary to explicitly specify what to do in this case.

My opinion as an implementer is two fold:

1. Excluding low-order points is quite the hassle, and it's not
   clear how I could do it in constant time.
2. We never generate those points to begin with.

I don't want to deal with (1), which makes (2) very convenient for me.
So I'll just justify (2), using Curve25519 as an example:

- The order of the prime subgroup is a little over 2^252.
- The cofactor is 8.
- Therefore, Curve25519 has a little over 2^255 points.
- Selecting a point at random will give a low-order point about
  once every 2^252 trials. That means never.

The security of a curve is basically the square root of its prime
order. Here, 2^125 or so. Breaking it with standard brute force methods
is incommensurately easier than stumbling upon a low-order point by

In security parlance, a probability of 1/2^255 isn't just "extremely
small", it's "flat out impossible". I can therefore justify my laziness
and chose not to check for that event.


Note that generating a small-subgroup point *on purpose* will not work
either: Curve25519 has 8 low-order points, and a maximum of 16
representatives for those points (maybe a couple more if we allow
representatives over 2^255 - 19). The inputs are hashed before we map
the hash to the curve. So it's not enough to pick a matching
representative, we need to pick a hash whose image is one of those

To do this, we need to conduct a multi-preimage attack on a 2^255-bit
hash, with 16 images. The difficulty of that attack is roughly 2^251.
Again, this is impossible if the hash is secure.

As a consequence, I cannot generate test vectors that account for this
edge case even if I wanted to. Even if I wasn't lazy, accounting for
low-order points means writing code I cannot trigger even if I want to
—dead code. That will only harm security in practice.

> In CPace and OPAQUE, both protocols use the output of hash-to-curve
> as a base generator. The implicit assumption is that the returned
> value from hash-to-curve must be a non-identity point in a subgroup
> of the large prime order.

This assumption is correct as far as I can tell: yes, in *theory*, we
have a couple exceptions. In *practice*, those exceptions will never
occur. The probabilities are low enough to be considered negligible.

> Has this issue been considered? Apologies if I missed any discussion
> on this before.

Likely. I haven't followed past discussions though, so I cannot say.