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

["Hao, Feng" <[e-mail]>]

Hi all,

I just read through the latest version of the hash-to-curve ID (v10) and have a question.

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.

If the mapping function gives a small subgroup point, you cannot re-run the function to generate another point, as that will defeat the constant time principle. But obviously, a small subgroup point (or an identity point after the co-factor clearing) can’t be used safely for any protocol. It seems we have a failure mode which is “non-recoverable”.

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 doesn’t match what is actually provided by the current hash-to-curve ID.

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

Cheers,
Feng