Subject: Re: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve

From: David Núñez <[email-masked]>
Date: Wed, 21 Mar 2018 10:57:06 +0100

Hi all,
I am too very interested in supporting this RFC, I think it’s very necessary. Apart from the good points raised by Jason in the previous mail, I have some comments for the Try-and-increment method in Appendix A. Although it is an appendix, I believe special care should be taken into this function too, since it’s very attractive due its simplicity and generality (of course, when timing attacks are not a concern).  

Comments:
- Current pseudocode relies on I2OSP failing to avoid looping forever when ctr > 256^4. Although this only happens with probability 2^-32, perhaps it should be an explicit condition for the loop. This should also be acknowledged in the introduction, since the size of this counter determines the probability of failure, as in the MapToGroup approach.
- Clarify the meaning of "2n-octet string” when introducing RS2ECP. Also, RS2ECP is not explicitly defined in RFC8032, but in https://tools.ietf.org/id/draft-goldbe-vrf-01.html#suites <https://tools.ietf.org/id/draft-goldbe-vrf-01.html#suites>. According to that, only when curve is Ed25519, RS2ECP is defined in Section 5.1.3 of [RFC8032].

Regards,
David

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 21 Mar 2018 08:24:20 -0700

If I've seen "rough consensus and running code" in this area, it's around a
couple of the options covered in this draft, namely this method:

On Wed, Mar 21, 2018 at 2:57 AM, David Núñez <[email-masked]> wrote:

> I have some comments for the Try-and-increment method in Appendix A.
> Although it is an appendix, I believe special care should be taken into
> this function too, since it’s very attractive due its simplicity and
> generality (of course, when timing attacks are not a concern).
>

...which some of us have lovingly dubbed "hash-and-pray"...

But also, Elligator2 as described in section 4.4 has appeared in a lot of
protocol designs and running software.

All that said, hashing to a curve seems like a very important primitive in
the design of many protocols and I definitely think this is an area the
group should address.

-- 
Tony Arcieri

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 21 Mar 2018 16:51:26 +0000

If I've seen "rough consensus and running code" in this area, it's around a couple of the options covered in this draft, namely this method:

I have some comments for the Try-and-increment method in Appendix A. Although it is an appendix, I believe special care should be taken into this function too, since it’s very attractive due its simplicity and generality (of course, when timing attacks are not a concern).

But also, Elligator2 as described in section 4.4 has appeared in a lot of protocol designs and running software.

All that said, hashing to a curve seems like a very important primitive in the design of many protocols and I definitely think this is an area the group should address.

+1

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:48:48 +0000

Hi David,

Please see inline below for comments.

On Wed, Mar 21, 2018 at 2:57 AM David Núñez <[email-masked]> wrote:

> Hi all,
> I am too very interested in supporting this RFC, I think it’s very
> necessary. Apart from the good points raised by Jason in the previous mail,

We can and probably should make this side channel more clear in the
appendix. The current text only hints at it.

>
> Comments:
> - Current pseudocode relies on I2OSP failing to avoid looping forever when
> ctr > 256^4. Although this only happens with probability 2^-32, perhaps it
> should be an explicit condition for the loop. This should also be
> acknowledged in the introduction, since the size of this counter determines
> the probability of failure, as in the MapToGroup approach.
>

Very good point. I filed:
https://github.com/chris-wood/draft-sullivan-cfrg-hash-to-curve/issues/13

> - Clarify the meaning of "2n-octet string” when introducing RS2ECP. Also,
> RS2ECP is not explicitly defined in RFC8032, but in
> https://tools.ietf.org/id/draft-goldbe-vrf-01.html#suites. According to
> that, only when curve is Ed25519, RS2ECP is defined in Section 5.1.3 of
> [RFC8032].
>

Another good point. I filed:
https://github.com/chris-wood/draft-sullivan-cfrg-hash-to-curve/issues/14

Thanks again for your feedback.

Best,
Chris