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

[Loup Vaillant-David <[e-mail]>]

Hi,


> 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
chance.

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
representatives.

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.

Loup.