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

[[e-mail]]

Hello Feng,

Thanks for bringing this up. It's good to discuss this so that we are
all on the same page. Below I'll give one low-level answer, and then
a higher-level one.

"Hao, Feng" <Feng.Hao=[e-mail]> wrote:
> For example, if a user already has an input value in F_p, does he
> still have to go through the hash_to_field step (which is complex
> on its own)?

The answer to this question is unquestionably yes---hash_to_field
must *always* be used before map_to_group in any construction that
purports to be a conforming hash-to-curve implementation.

The hash functions defined in the draft are very clearly defined
to require all steps. Skipping steps in a cryptographic construction
is generally a recipe for disaster, and this is no exception. The
hash-to-curve document does not make any security claims about
implementations that skip steps, nor (in my opinion) would it
be reasonable for CFRG to require that implementations that are
non-compliant somehow remain secure anyway (after all: what would
this even mean?).

Zooming out, the higher-level question seems to be: should the
hash-to-curve functions defined in the draft somehow be designed
never to return the identity point? The answer is no, they should
not be designed in that way---returning the identity point with
negligible probability is absolutely fine from a security point
of view, as Mike and others have already pointed out.

I will not rehash [ ack! no pun intended :) ] their arguments. Instead,
I'll ask an analogous question: should SHA-3 have been designed such
that the all-zeros string is never produced?

It seems clear that the answer here is no---and yet if we use SHA-3
in a Schnorr signature, we might very well worry that the all-zeros
string would break things rather badly! Indeed, if the verifier's
challenge (generated by hashing the prover's randomness and the
message) equals 0, the signer can "sign" for any public key. Even
worse, if the signer's initial randomness (which, in a deterministic
signature, is also generated by hashing) equals 0, the signature
reveals the signer's secret key!

In both of these cases, it seems pretty clear that the issue is not
in the hash function, but in the application's use of it. If one
is worried about SHA-3 returning zero in a Schnorr signature, perhaps
one adds a special check in the implementation (though I'd say this
is clearly unnecessary). Similarly, if one is worried about the
(negligible!) probability that hash-to-curve returns the identity
point, one would "fix" this in the calling application.

No such fix is necessary, however---again, for the reasons that Mike
and others have pointed out.

Regards,

-=rsw