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

[Mike Hamburg <[e-mail]>]

> On Apr 9, 2021, at 11:45 AM, Loup Vaillant-David <[e-mail]> wrote:
> 
> 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.

Yeah, the usual answer is: if an event happens with negligible probability,
and an adversary can’t cause it to happen more often, and it only breaks
one thing, then it doesn’t affect security.  Any reasonable adversarial
strategy has some chance to break the protocol anyway (e.g. just guess
someone’s private key), and this unlikely event doesn’t significantly
contribute to that chance.  I haven’t checked the details for CPace and
OPAQUE, but for cases I’ve looked at it’s been fine.

Of course, implementations will not be fully compliant with the spec
unless they can properly handle the identity point.  They would have to
do another analysis to see whether this sort of non-compliance is itself
a security issue, but the answer would probably again be: not unless
an adversary can cause it to happen.

Cheers,
— Mike