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

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

Hi rsw,

That current map-to-curve functions don’t preclude low-order points is a known fact, and acknowledged by the authors in their papers. This is also clear from the hash-to-curve draft.

What people have tried (so far) to address this issue is by using the clearing-the-co-factor trick. But as explained, this trick doesn’t do any help to address the small subgroup issue in the use case of PAKE. Here, we are talking about a theoretical flaw not a practical attack. The practical effect of this flaw varies according to the underlying groups – if it were in MODP, the effect will be very severe, but the effect has been vastly reduced on elliptic curve due to the size of the small subgroup being small. Ideally, these effects should be removed by design. The security of a protocol shouldn’t depend so much on the choices of the underlying groups.

Cheers,
Feng

From: [e-mail] <[e-mail]>
Date: Saturday, 10 April 2021 at 16:13
To: Hao, Feng <[e-mail]>, CFRG <[e-mail]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Hello Feng,

"Hao, Feng" <Feng.Hao=[e-mail]> wrote:
> Rsw also gave a similar example of having all zeros for the hash.
> Let me clarify that we are not – and shouldn’t be - concerned with
> any of such cases since the values are uniformly distributed within
> their respective range.

Right. And the argument is precisely the same for hash-to-curve!

Let me be perfectly clear: the property that hash_to_curve gives
is that the output is a uniformly* distributed point in the (big)
prime-order subgroup of the target elliptic curve.

At the risk of seeming didactic (in which case, apologies): the
identity element is indeed an element of the target group G.

Put another way: fix a generator g of group G of prime order q. Then,
hash_to_curve returns g^r in G, for r sampled uniformly* at random
in 0 <= r < q. Under the assumption that discrete log is hard in G,
hash_to_curve does not reveal r. Under the preimage and collision
resistance of the underlying hash function, one cannot choose any
particular r or find two inputs that hash to the same r.

I hope this helps clarify the security properties, and why focus
on low-order points at intermediate steps of the computation is not
relevant to the security of hash_to_curve as specified.

* uniformly except for some statistical distance less than 2^-100.

Regards,

-=rsw