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

[Hugo Krawczyk <[e-mail]>]

Feng, you say:

> On the other hand, from the perspective of a higher layer protocol (say
CPace, OPAQUE and PAK), it’s simply impossible to handle the exception. As
soon as map-to-curve hits the small subgroup, the password in a PAKE system
will be compromised. Therefore, the above warning is self-defeating and not
meaningful.

If I understand correctly, you are saying that in the case of password
protocols, the unlikely event of (a correctly designed, correctly
implemented) hash-to-curve mapping some value to the identity has
irrecoverable consequences that are specific to the PAKE setting.

I wanted to comment that in the case of OPAQUE, you could check during
password registration that a user's password maps to the identity and ask
to choose a new password (we are used to websites rejecting some
passwords). However, when that happens, the website should immediately (*)
sound an alarm to be heard across the universe. You would have found a
preimage of the identity under a RO-modeled hash function. Either you are
observing an event with probability, say, 2^{-256}, or you are observing a
hugely more probable event: Someone broke the one-wayness of the hash
function. STOP USING IT IMMEDIATELY FOR ANY PURPOSE.

(The same alarm should go off if it just happens in a run of any other
protocol.)

(*) Of course, you should first check that you really have a preimage of
the identity under the hash - the most probable event to produce such a
result is an implementation error.

Hugo

PS: When you have an analysis that assumes a uniform distribution and then
decide to deviate from it as a way to "enhance" the design, you may be
introducing subtle weaknesses. An historic example (irrelevant to the cases
we are discussing here but illustrating the principle) is Enigma's
avoidance  of encrypting letters to themselves - something Turing was fast
to exploit
https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties

On Sat, Apr 10, 2021 at 11:13 AM <[e-mail]> wrote:

> 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
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>