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

From: [email-masked]
Date: Mon, 08 Jul 2019 16:32:52 -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-04.txt
	Pages           : 60
	Date            : 2019-07-08

Abstract:
   This document specifies a number of algorithms that may be used to
   encode or hash 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-04
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-04

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

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: Dan Harkins <[email-masked]>
Date: Tue, 16 Jul 2019 02:25:50 -0700

Hello,

   This draft seems like a departure from the direction -03 was going,
which is unfortunate.

   Version -03 had several methods of hashing whose preconditions made them
appropriate for certain curves. Importantly, though, it had SWU which will
work with basically any Weierstrass curve. Now it seems the focus is on 
highly
optimized and curve-specific methods and ciphersuites which fix the curve
and hash algorithm. SWU is now optimized to work only on certain 
pairing-friendly
curves.

   Would it be possible to add back the -03 SWU as a generic template that
can be instantiated with a curve and a hash function? That was how I was
planning on using this soon-to-be RFC.

   And a comment on -04. The Simple SWU method now has a check whether u=0
to prevent divide-by-zero. In the event it is, the algorithm outputs
B/(Z * A) as x. Doesn't this leak information? If I, as a passive observer,
notice x = B/(Z * A) then I know that hash_to_curve(m) returned 0. I know
the probability of u=0 is astronomically small but if the possibility is
going to be addressed why not reduce the output of the hash modulo (p-2)
and then add 2 to always place 1 < u < p?

   regards,

   Dan.

On 7/8/19 4:32 PM, [email-masked] wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Björn Haase <[email-masked]>
Date: Tue, 16 Jul 2019 13:16:53 +0000

Hi to all,

One of the clear advantages of using the less-efficient "plain" SWU method with the three calculations of the Legendre symbol as defined in section

"5.3.2.  Shallue-Woestijne-Ulas Method"

of the older draft -03 is that we keep safely away from the patents. Yes, its less efficient, but frankly speaking, in my opinion people really concerned about efficiency should use Montgomery or (twisted) Edwards curves anyway (and use Elligator2) and likely for most real-world-protocols the mapping will be not the bottleneck but rather the scalar multiplications.

This might be a reason to stick with plain SWU or at least include plain SWU as an option in the RFC.

Björn.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

-----Ursprüngliche Nachricht-----
Von: Cfrg <[email-masked]> Im Auftrag von Dan Harkins
Gesendet: Dienstag, 16. Juli 2019 11:26
An: [email-masked]
Betreff: Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt

   Hello,

   regards,

   Dan.

On 7/8/19 4:32 PM, [email-masked] wrote:
> https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-irtf-cfrg-hash-to-curve%2F&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7Cae3fd8bde95d49afaef008d709cfa996%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C636988659817711977&amp;sdata=DTtAtT0Ec2pyscnrisBC7dJkkgcNqGSe6pl8IrTHfP8%3D&amp;reserved=0
>
> https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Ftools.ietf.org%2Fhtml%2Fdraft-irtf-cfrg-hash-to-curve-04&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7Cae3fd8bde95d49afaef008d709cfa996%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C636988659817711977&amp;sdata=UdjS%2BluBqR%2F6%2FFSTRaevzruWEU8xqWVcGZBZ5PDX4lI%3D&amp;reserved=0
> https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Fdraft-irtf-cfrg-hash-to-curve-04&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7Cae3fd8bde95d49afaef008d709cfa996%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C636988659817711977&amp;sdata=LCWM4Q8iXV3phnMTTMg0E9HuVgR%2BHHZCvI9lg4I8ILU%3D&amp;reserved=0
>
> https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Frfcdiff%3Furl2%3Ddraft-irtf-cfrg-hash-to-curve-04&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7Cae3fd8bde95d49afaef008d709cfa996%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C636988659817721981&amp;sdata=CR%2F43lACEBS0g8uW7GNEL7H4aZHQxqnmeEWD%2Ft8bRmk%3D&amp;reserved=0
>
>
> https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7Cae3fd8bde95d49afaef008d709cfa996%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C636988659817721981&amp;sdata=1PEi9s085HZljfmE1Tl%2Bam7h5h7BldmYEXy%2FOmbQN3s%3D&amp;reserved=0

_______________________________________________
Cfrg mailing list
[email-masked]
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7Cae3fd8bde95d49afaef008d709cfa996%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C636988659817721981&amp;sdata=1PEi9s085HZljfmE1Tl%2Bam7h5h7BldmYEXy%2FOmbQN3s%3D&amp;reserved=0

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 16 Jul 2019 13:30:43 +0000

I am with Dan and Björn. Please add plain SWU back.

Regards,
Uri

Sent from my iPhone

> On Jul 16, 2019, at 09:18, Björn Haase <[email-masked]> wrote:
> 
> Hi to all,
>

---

From: Björn Haase <[email-masked]>
Date: Tue, 16 Jul 2019 13:36:37 +0000

... and another bad news might be the following: I fear that

P384-SHA512-ICART-NU

might be covered by the patent family of FR0950189 (including US8666066B2) ☹. 

Yours,

Björn.

Dr. Björn Haase 

Disclaimer: 

-----Ursprüngliche Nachricht-----
Von: Blumenthal, Uri - 0553 - MITLL <[email-masked]> 
Gesendet: Dienstag, 16. Juli 2019 15:31
An: Björn Haase <[email-masked]>
Cc: Dan Harkins <[email-masked]>; [email-masked]
Betreff: Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt

Regards,
Uri

Sent from my iPhone

---

From: "Riad S. Wahby" <[email-masked]>
Date: Tue, 16 Jul 2019 10:58:13 -0700

Hello Dan, Bjoern, Uri,

Thanks for this feedback.

Regarding patent issues, I think it's safe to say that the current draft
does not fully comprehend the IPR landscape (nor do I). I'm hopeful that
we will start to address this in the near future---certainly by the next
draft's release---and that could very well change the draft's content.

In the meantime, my answers below ignore potential IPR entanglements.

Dan Harkins wrote:
> work with basically any Weierstrass curve. Now it seems the focus is on highly
> pairing-friendly curves.

The goal is certainly still to give maps and corresponding preconditions
to cover effectively all curves. To that end, everything in Section 6 is
(intended to be) generic. (It's true that we give optimized curve-specific
methods in the appendix, but so far just three of them.) If the above
isn't clear from the text, then the text is buggy, and I apologize.
I've taken a note to make this clearer.

With regard to the SWU map given in 5.3.2 of -03, it's not quite correct
that it works with any Weierstrass curve. Specifically, it requires that
the j-invariant not be 0 or 1728, i.e., y^2 = x^3 + ax + b for ab != 0.
The Simplified SWU map in 5.3.3 of -03 further restricts p = 3 mod 4.

Note, however, that the Simplified SWU map in 6.5.2 of -04 removes the
restriction on p---in other words, it covers exactly the curves that SWU
does. Moreover, it's considerably cheaper: for curves over "reasonable"
base fields Simplified SWU can be implemented with one exponentiation,
whereas SWU takes more (3 exponentiations for a constant-time impl).
This is why we removed SWU: it's strictly dominated by Simplified SWU.

(Here, "reasonable" means "p - 1 is not divisible by some very large
power of 2," which makes life unpleasant no matter which map you use
because square rooting gets awkward.)

Your point that we should generalize the description of the Shallue--
van de Woestijne method is spot on, since this method really does cover
effectively any curve (in particular, it does not restrict j-invariant
the way SWU and Simplified SWU do). The issue is just that we haven't
yet written a nice, general presentation. This, too, should land before
the next iteration, I hope.

To be clear: I don't have any objections to including SWU if there's
a good reason. But given that Simplified SWU is always a better choice,
it's not clear to me why the draft would recommend using SWU. (Again,
this ignores IPR issues, which could end up being a very good reason
to include it!)

Does this address your concern, or have I misunderstood or otherwise
missed a key detail?

> and then add 2 to always place 1 < u < p?

Handling the exception does not leak (more) information. The reason
is that the mapping is invertible on any point in its image---so you
can always extract a field element u by looking at the output of the
map, whether or not the input was one of the exceptional cases.

(This is the reason we need to be careful when specifing the hash
function from messages to field elements u: roughly speaking, it's
this hash function that makes inversion of the whole hash-to-curve
operation infeasible, makes it collision resistant, etc.)

Also, it's not quite true that the check is for u == 0; this is one bad
case, but there may be others. So while the method you suggest could
work for some curves, unfortunately it doesn't generalize. (From a
practical perspective, it would also be painful for implementors if
we required reductions mod integers other than p.)

Regards,

-=rsw

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 16 Jul 2019 20:33:57 +0000

>    ...Simplified SWU map in 6.5.2 of -04 removes the
>    does. Moreover, it's considerably cheaper

I think IPR could be quite sufficient as a reason to use SWU rather than Simplified SWU. But not being a patent lawyer, I cannot evaluate how bad that problem is.

Is there any problem with including both SWU and S-SWU?

On 7/16/19, 1:59 PM, "Riad S. Wahby" <[email-masked]> wrote:

    Hello Dan, Bjoern, Uri,

    

    

    

    

    
    
    Regards,
    
    -=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Tue, 16 Jul 2019 14:05:45 -0700

"Blumenthal, Uri - 0553 - MITLL" <[email-masked]> wrote:
> I think IPR could be quite sufficient as a reason to use SWU rather
> than Simplified SWU. But not being a patent lawyer, I cannot evaluate
> how bad that problem is.

Same here on both counts.

I'm inclined to err on the side of including IPR workarounds, which
is unfortunate because...

> Is there any problem with including both SWU and S-SWU?

...if we lived in a universe without IPR concerns, my opinion would be
that only Simplified SWU should be included. The reason is, including
any given algorithm is (at least tacitly) endorsing its use, and as
far as I can see there is no *technical* justification for endorsing
SWU over Simplified SWU.

-=rsw

---

From: "Björn Haase" <[email-masked]>
Date: Tue, 16 Jul 2019 23:39:55 +0200

Dear Riad,

>....if we lived in a universe without IPR concerns, my opinion would be
>that only Simplified SWU should be included. 
Yes. I agree with you here.

>The reason is, including

We'll have to struggle with the following situation: If we have too many options, we might face an incompatibility nightmare and complexity. And all complexity is bad for security because at least one of the options might have an exploitable implementation pitfall.

On the other hand dealing with licensing issues or even disputes at courts is extremely painful. Also a mere IPR conflict risk might motivate people use the second-best option security-wise or even scare away people from a helpful and more secure technology.

In my opinion dealing with this type of topic is something specific for an organization such as IETF or CFRG, in contrast to pure research work.

I have made quite some effort on analysis of possible IPR issues for hash2curve. Concluding my analysis today gives the following result:

- I believe Icart's mapping for curves with p mod 3 = 1 is covered by the morpho patent. For a product of my employer, I'd would not recommend using this approach without purchasing a license.
- I believe that simplified SWU in the form of the current draft is not covered by the claims in the patents that I have read so far. I would recommend using simplified SWU in products of my employer, however only after having arranged for an assessment by an experienced patent attorney and an assessment of *all* national applications or patents. Sometimes the claims differ significantly and there might be the risk of divisional applications with new claims in some countries, once the standard comes out.
- I believe that plain SWU is not covered by patents. For the plain SWU algorithm, I would recommend my employer to use the algorithm without the need of further analysis.

Summing up the only IPR issue in the current draft is Icart's mapping for P384. I have filed an official IPR notice for this aspect.

I believe that SWU and simplified SWU are not covered and I did not file an official IPR notice. Still when working on the draft, I'd like to suggest that the Icart and Icart/Coron patents regarding optimizations for plain SWU should carefully be kept in mind.

I further believe that apart of the two patents from Icart and the one from Icart/Coron no further patents might be around.

Yours Björn,

P.S.: Sorry for bothering you with these painful topics. Still I believe that getting a clear common picture on the IPR situation for hash2curve will be important pre-requisite for establishment of consensus regarding protocols for OPRF and PAKE.