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

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

Dear Björn,

> for CPace this has been considered in https://eprint.iacr.org/2021/114.pdf in the context of the proof for theorem 3.6 (and  correspondingly theorem 6.1, "Security of CPace with Map2Point") and become part of the (negligible) loss due to  the increased collision probability for the hash H_1.

It's good to see this has been considered in your new paper. In your theorem 3.6, I wonder if the proof covers the cyclic groups in general or the specific groups on elliptic curves. As you may know, small subgroup confinement is a common issue for both MODP and EC groups. The practical effect for the former is far more severe than the latter since the size is larger, but the theoretical principle of the small subgroup confinement applies the same for both settings.


  *   I don't identify the need of considering this aspect in the hash2curve level, but I agree that this should be covered by the security analysis of protocols that use the maps.

So far hash2curve and CPace/OPQUE have been developed separately with the former being largely assumed as an idealized function. I think now is a good time to look at the integration of the two in a system context. With the current hash2curve draft, as long as map-to-curve returns a low-order point, the user’s password will be inevitably broken by offline dictionary attacks based on the side-channel information. There is nothing the protocol can do (rejecting the point gives away the exact side-channel information needed for offline dictionary attacks). However, one can argue that the chance of this “really bad event” happening is L/q where L is the size of the small sub-group. It’s too small to be of any concern over common elliptic curves, and we hope that never happens. I think this is a perfectly sensible argument from a practical point of view. From a theoretical point of view, the argument is not appealing or neat. Hence, my question is why the small subgroup points can’t be precluded from the map-to-curve function?