Subject: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-08.txt

From: [email-masked]
Date: Mon, 01 Jun 2020 16:17:48 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : Hashing to Elliptic Curves
        Authors         : Armando Faz-Hernandez
                          Sam Scott
                          Nick Sullivan
                          Riad S. Wahby
                          Christopher A. Wood
	Filename        : draft-irtf-cfrg-hash-to-curve-08.txt
	Pages           : 156
	Date            : 2020-06-01

Abstract:
   This document specifies a number of algorithms for encoding or
   hashing an arbitrary string to a point on an elliptic curve.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-08
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-08

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-hash-to-curve-08

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 01 Jun 2020 16:31:36 -0700

This update carries a number of important changes, including, though not limited to:

- Domain separation mitigations for expand_message_xmd (as part of hash-to-field).
- Mapping function fixes and clarifications. Elligator 2 alignment is one such update.
- An overall reduction in suites. There is now one recommended RO and NU suite per target curve.
- Expanded test vectors, including those for expand_message. 
- Much improved security considerations text, particularly around domain separation guarantees.
- Alignment with the VRF specification [1].

We believe the document is now ready for RGLC, and would appreciate reviews and feedback to help get it across the finish line.

Thanks!
Chris

[1] https://github.com/fcelda/nsec5-draft/pull/35

On Mon, Jun 1, 2020, at 4:17 PM, [email-masked] wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Michael Scott <[email-masked]>
Date: Wed, 3 Jun 2020 14:04:51 +0100

Hello Chris,

I have a few remarks about this. The changes I noted were a minor change to
ELL2, some sensible updating to the Domain Separation Tag formats, and that
the SVDW method seems to now be deprecated (or at least not recommended)
for curves with AB=0 in favour of the isogeny map based method.

I was puzzled that the suite for edwards25519 uses SHA-512, whereas surely
SHA-256 would be a better fit?

On a very mundane issue, in section 8.1 hash-to-field should be
hash_to_field.

My major concern is about the Isogeny map vs SVDW issue. It is not clear to
me that suitable isogeny mappings can be found for all potential
pairing-friendly curves of interest. Indeed for the well-known BN254 curve,
and adapting the sage script from https://eprint.iacr.org/2019/403, I was
unable to find any isogeny map of degree less than 64 for the G2 group. And
for another BLS12 curve I could find no isogeny of degree less than 100 for
G1 (although one of degree 3 existed for G2). The method already seems
unwieldy with its multiple constants, compared with SVDW.

It would be a useful exercise to provide isogeny maps for all of the
pairing-friendly curves under active consideration for standardisation by
CFRG, to confirm the general applicability of the method. It seems to me
that the isogeny map method may have been rather lucky with BLS12-381 !

Personally, I would support SVDW being reinstated as an equally recommended
alternative option.

Mike

On Tue, Jun 2, 2020 at 12:32 AM Christopher Wood <[email-masked]>
wrote:

> We believe the document is now ready for RGLC, and would appreciate
> reviews and feedback to help get it across the finish line.
>
> Thanks!
> Chris
>

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 3 Jun 2020 11:00:44 -0700

Hello Mike,

Thanks as always for your careful feedback!

> for curves with AB=0 in favour of the isogeny map based method.

I copmletely understand how the recent changes give this impression,
but I hope I can reassure you that this was not the intent.

We removed a few suites in response to feedback asking that we pare
down to one recommended suite per curve. For BLS12-381 we kept the
SSWU+isogeny map because it's the one that is being widely deployed
for BLS signatures over this curve.

> SHA-256 would be a better fit?

We went with SHA-512 for {curve,edwards}25519 by analogy to Ed25519.
It's certainly true that SHA-256 is the better fit security-wise, but
anecdotally it appears that SHA-512 and *25519 are frequently deployed
in tandem, which seemed to make this a slightly more convenient choice
for implementors. (As one data point, the VRF authors preferred to use
SHA-512 for similar reasons.)

> that the isogeny map method may have been rather lucky with BLS12-381 !

This is a great point---seems like it makes sense to define suites
for all of these curves, either in h2c or in an appendix of the
pairing-friendly curves draft. (And certainly SvdW seems like the
clear winner for some of these!)

Best regards,

-=rsw

---

From: Marek Jankowski <[email-masked]>
Date: Thu, 11 Jun 2020 15:08:23 +0200

Hi Chris,
I think this is a great draft - it explains very well hashing to curves,
which is vital for many new applications that I hope to see coming, mainly
those using pairings.
The section about domain separation is very important and I'm glad to see
it explained explicitly and thoroughly.
Here are a few suggestions, most of them minor:
a. I think Table 1 (Sec. 2.1) could be better formatted, using less line
breaks. Please consider redistributing the widths of the columns.
b. The second paragraph in 2.2.1 can be simplified: it suffices to say it
needs not be bijective/surjective/injective. Also I'm not entirely sure
it's best practice to use the term 'invertible' for just _efficiently_
reversible functions.
c. I think a better formulation in the first paragraph in 2.2.5 is
something like "...assuming the attacker accesses RO only through the
protocol, viz. the RO is not used elsewhere."
d. The word 'encode' (Sec. 3) implies that its output can be decoded.
Perhaps there's a better word for noninvertible maps.
e. Domain separation (Sec. 3.1): I believe that if needed for backwards
compatibility, it is not a disaster if we omit the version number from the
Tag. Maybe it is worth a "NOT RECOMMENDED".
f. It says that expand_message MUST NOT use rejection sampling (5.3.4). To
the best of my understanding, rejection sampling is to be avoided for the
sole purpose of mitigating side channel attacks; this is defined (Sec. 4)
as a SHOULD, so I believe this SHOULD should (no pun intended :-) propagate
there.
g. Do we really want to approve as many curves as in [Table 2, Sec. 8]? We
are standardizing something new here, so we can allow ourselves to stick to
just the best curves. In my opinion Curve25519 is in every way superior to
the NIST curve of the same strength, so the latter can be omitted.
Again, I am very supportive of the draft and will be happy to further help
in the process.

Cheers,
Marek

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 15 Jun 2020 12:14:01 -0700

Hi Marek,

Thanks for the feedback! Please see inline below.

On Thu, Jun 11, 2020, at 6:08 AM, Marek Jankowski wrote:
> Hi Chris,
> I think this is a great draft - it explains very well hashing to 
> curves, which is vital for many new applications that I hope to see 
> coming, mainly those using pairings.
> The section about domain separation is very important and I'm glad to 
> see it explained explicitly and thoroughly.
> a. I think Table 1 (Sec. 2.1) could be better formatted, using less 
> line breaks. Please consider redistributing the widths of the columns.

I'll see if we can clean this up:

   https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/279

> b. The second paragraph in 2.2.1 can be simplified: it suffices to say 
> it needs not be bijective/surjective/injective. Also I'm not entirely 
> sure it's best practice to use the term 'invertible' for just 
> _efficiently_ reversible functions.

This seems to be the term used in literature. Would you prefer it say, "efficiently reversible" instead of "invertible"?

> Perhaps there's a better word for noninvertible maps.

I'm less certain about this one, as encode is a fundamental concept in the document. I think the text in 2.2.2. makes it clear that some encodings may be invertible, so I'm not sure this is an issue. (I recognize that view may not be universal. :-))

What word would you recommend instead?

> compatibility, it is not a disaster if we omit the version number from 
> the Tag. Maybe it is worth a "NOT RECOMMENDED".

That's a good point worth considering:

   https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/280

> f. It says that expand_message MUST NOT use rejection sampling (5.3.4). 
> To the best of my understanding, rejection sampling is to be avoided 
> for the sole purpose of mitigating side channel attacks; this is 
> defined (Sec. 4) as a SHOULD, so I believe this SHOULD should (no pun 
> intended :-) propagate there.

Great catch. This is an inconsistency:

   https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/281

> g. Do we really want to approve as many curves as in [Table 2, Sec. 8]? 
> We are standardizing something new here, so we can allow ourselves to 
> stick to just the best curves. In my opinion Curve25519 is in every way 
> superior to the NIST curve of the same strength, so the latter can be 
> omitted.

We want this document to be maximally useful to implementers who may have a need for NIST curves. Omitting them seems like it would defeat the purpose of the document. So, I'm strongly inclined to keep them. 

> Again, I am very supportive of the draft and will be happy to further 
> help in the process.

And we appreciate your help and input -- thanks again!

Best,
Chris