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

[Mike Hamburg <[e-mail]>]

Hi Feng,

> On Apr 10, 2021, at 4:20 PM, Hao, Feng <[e-mail]> wrote:
> 
> hash_to_curve is (epsilon-close to) uniformly distributed within its range, which is the prime-order group of points on the curve, which is also the range specified by these schemes in the literature.
> Please kindly note that I explicitly refer to map_to_curve, which can return low-order points.

Ah, sorry, I thought we were still talking about hash_to_curve.

> No, not PAK.  PAK uses the hash output as an additive blinding factor, so it ideally wants the value to be uniform in the group, non uniform among non-identity elements.  Of course, removing the identity won’t harm it, since again, that’s a negligible change.
> Please See Figure 1 on p. 11 in [1]. PAK uses the result from H1 as a base generator before being raised to the power of r. The follows the same idea as SPEKE.

I was insufficiently precise.  I’d forgotten that PAK refers to several PAKE algorithms; I was thinking of some of the elliptic curve versions, such as PAK-EC from "More efficient password-authenticated key exchange" by Philip MacKenzie, CT-RSA 2001.  I re-proposed a variant of this protocol, not knowing that it had been done before, as "SPAKE2: Elligator Edition”.  This design is slightly slower than SPEKE, but it has a simpler security analysis than SPEKE.  It sends something very roughly of the form aG + hash_to_curve(password), so you want hash_to_curve to be uniform.  Security follows by a very simple argument (compared to most other PAKEs) under ROM + strong DH.

> No, it’s pretty much the exact opposite of that.
> DDH is usually written as distinguishing (G, aG, bG, abG) from (G, aG, bG, cG) where g is a generator and (a,b,c) are uniformly random mod the group order.  See eg http://theory.stanford.edu/~dabo/papers/DDH.pdf <http://theory.stanford.edu/~dabo/papers/DDH.pdf> (which uses exponential notation but is otherwise the same), though variants (such as c != ab) are sometimes used instead.  Here aG, bG and cG can be the identity.  In this formulation, G cannot be the identity: it’s defined as a generator.  But if it were the identity then the two distributions would be identical — they would each be 4 copies of the identity — so DDH would still hold.
> Sorry, that can’t be right. if you want uniform distribution of values in Gq, the items in DDH can’t be identity elements.

The DDH assumption is that those two distributions are hard to distinguish, not that they’re uniform.  And it is indeed hard to distinguish (Id, Id, Id, Id) from (Id, Id, Id, Id).

> They should have the prime order q. Please see the explicit definition of Decision Diffie-Hellman (Problem 6.4 in Section 6.7.3) In Stinson’s book [2].

I don’t have this book.  Is Stinson's definition different from Boneh’s?

Even if you ask for it to be hard to distinguish (G, aG, bG, abG) from (random, random, random, random), this is still hard if G is a uniformly random element of the group, because with overwhelming probability G will not actually be the identity.
> If you’re using my library, libdecaf, then you can use decaf_point_eq and decaf_point_cond_sel to remove the identity in constant time.  Similar functions are likely available in other libraries.
> That’s interesting. Why not integrate it into the hash-to-curve draft?

Because, as I have been arguing, it’s not necessary and is only negligibly useful.  I guess it could be a note or security consideration?

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

But as I have already explained, clearing the cofactor isn’t to get rid of low-order points.  It would be required even if the hash cannot return low-order points.  The problem also isn’t more severe for Fp* groups, so long as there is a large prime-order subgroup (and if not, the scheme is insecure anyway, because discrete log is easy).

Regards,
— Mike