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

From: Armando Faz <[email-masked]>
Date: Fri, 9 Apr 2021 12:23:58 -0700

> That?s certainly a convenient solution. However, a proper one would be to preclude small subgroup points by design. The real problem here is to ensure mapping to points in the ?correct? group on an elliptic curve, not just any point. The current draft doesn?t solve that real problem (yet). I don?t think this is impossible to solve, but it needs some more efforts.
>
> Cheers,
> Feng

Let me just clarify that the hash to curve functions described in the
draft is a composition of
 H(x) := clear-cofactor( map-to-point ( hash-to-field (x)))

This hash function always gives you an element in the prime-order
subgroup of the curve E(Fp)[q]. That means that it can return either
 - a point of order q, or
 - the identity point.

No low-order points are returned, so the concern that you have raised
is not a problem, and it is already solved by the clear-cofactor
function.

The probabilities of getting in the identity were already described in
previous emails. And the fact that H returns the identity point is not
a failure nor a lack of completeness.

OTOH, the calling protocol could need some specific property about the
points produced by H. For example, ensuring points are different from
the identity. That being said, the protocol is who is in charge of
banning those points.

The concern is akin to the generation of keys. For example, calling a
PRGN(seed) to get a key K. Of course, the key generation procedure
must ban the case of K=0. However, nothing is wrong with the PRNG
returning K=0 (with low probability).

I could recommend adding a couple of lines in the Security
Recommendation section about it, but definitely it is not a problem.

-- 
Armando Faz
Cloudflare Inc.

---

From: Loup Vaillant-David <[email-masked]>
Date: Fri, 09 Apr 2021 21:54:44 +0200

> must ban the case of K=0. […]

That is far from obvious to me. Banning a key just reduces the search
space. Should we ban 0 because the attacker is more likely to test it
first? Then what about 1? Or 37? Or 2^256 - 1? Any published number? In
my opinion, the best solution is a uniform RNG. If we really want to
maximise unpredictability, we must not ban any number. Not even zero.

At least in the case of elliptic curves, one may argue that we should
ban the identity point because its properties are observably different
from all other points. Not just the bit pattern, but the fact that it
has order 1. (And even then I'd be cautious.)

Loup.

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 20:34:58 +0000

As explained in my first email on this subject, we can remove clear-cofactor from discussion here as it doesn’t do any help to resolve the issue: it simply changes a low-order point to an identity point. The fundamental question about the small subgroup remains.

As explained earlier to Scott, it’s not a simple case of checking the identity and banning it. If you get a low-order point or an identity point (after clear-co-factor) from hash to curve, you can’t accept it nor reject it (the fact of reject instantly allows offline dictionary attacks)

I think this is a completely different case. If it’s an AES key, you should of course generate the key at random without pruning.  If it’s for a public key and the key needs to satisfy certain conditions, you need to check if such conditions are fulfilled and if not re-generate it. The issue here is that if the mapped point doesn’t fulfil a property (say falling in a small subgroup), you cannot re-generate it, as doing so will allow trivial side-channel attacks.