Subject: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations

From: Björn Haase <[email-masked]>
Date: Thu, 17 Oct 2019 09:46:27 +0000

Dear Riad,

I think that it’s best to continue our private discussion on the list.

> Riad Wahby wrote:
>
>I agree with you that the generic description in Section 6.5.2 of
>the 04 draft is similar to what's in the patent. I was
>thinking of the version for p = 3 mod 4 that's described in Appx.
>D.2 (which is based on WB19, and can be generalized to other p.)
>
>- Compute x1 = X1(t), x2 = X2(t), and g(x1) in the usual way
>- Compute tmp = g(x1) ^ ((p + 1) / 4)
>- If tmp**2 == g(x1), return (x1, tmp)
>- Else return (x2, t^3 * tmp)
>
>In other words, there's no explicit square test or sqrt(g(x2))
>computation. Instead, we compute a value that's either the sqrt
>of x1 or close to the sqrt of x2, and choose the correct one by
>computing a square and checking for equality.

Yes. This seems very reasonable. When re-reading the claim 13 of US 8.718.276 B2 (copied below), I see three points, where a significant difference will be generated when using D.2 from WB19.
1.)	If we only use the X coordinate, we are safely out of the scope of the patent.
2.)	If the case distinction is not based on a square test for f(X1) but based on another condition.
3.)	If there is no square-root calculation taking f(X2) or f(X1) as input.
In addition as fourth distinction to the patent, the sign of the y-coordinate will also be changed depending on the parameter t. This is not what is claimed in the patent. All of these differences are significant in my opinion.

With this approach for curves with p = 3 mod 4, with the method of D.2 I conclude that we are safely out of the scope of the patent.
The algorithm from appendix D.2 of your paper for p = 3 mod 4 is also more efficient than the claimed method.
Also for p != 3 mod 4  (e.g. P-384) when using generic simplified SWU we have differences between the patent and draft 04, but it’s still somewhat similar. We probably might be better off with avoid simplified SWU for P-384.

In any case choosing “-1” as non -square value must be avoided due to US 8,712,038 B2.

All of this together might mean that for choosing the mapping algorithm for a curve while safely keeping out of the patent scope, we might need a decision tree and could not use a “one-size-fits-it-all” approach:

-	If Edwards or Montgomery curve: Use Elligator2
-	If p mod 4 == 3: Use accelerated SWU based on D.2 of WB19
-	Otherwise for short Weierstrass with p mod 4 != 3, use generic SWU
-	… special treatement of paring-friendly-curves ...

In order to avoid problems on the protocol-level, we should probably not recommend using P-384 in conjunction with protocols requiring mappings.

Regarding the PAKE protocol candidates, in my opinion a safe approach might be the following to avoid the patent pitfalls:
-	In OPRF constructions as used for salt blinding, specify use of an x-coordinate-only Diffie-Hellman algorithm on all curves.
This keeps “OPAQUE”, “B-SPEKE” and “strong AuCPace” safely out of the scope.
-	Don’t specify cipher-suites using P-384 for PAKE algorithms requiring mapping algorithms but recommend only Edwards/Montgomery curves or Short-Weierstrass curves with p = 3 mod 4, such as BrainPool, P-256 and P-521.
-	If possible, specify the protocols only for x-coordinate-only variants of EC Diffie-Hellman (applies to SPEKE, CPace, AuCPace). (Doing so also will restrict possible invalid-curve attacks to the quadratic twists and possibly allow for faster point verification.)

Here again for reference the claims of the Icart/Coron patent with highlighting (//  highlighted text //) for points that would make the difference:

13.) A method for obtaining, with an electronic component, a point P(X // ,Y //) on an elliptical curve satisfying the equation Y^2 = f(X) and starting from polynomials X_1(t), X_2(t), X_3(t) and U(t) satisfying the Skalba equality: f(X_1(t)) * f(X_2(t)) * f(X_3(t)) = U(t)^2
In the finite field F_q for any value of t, the method comprising choosing the polynomials that satisfy Skalba’s equality such that the value of X_3(t) for any value of t is such that f(X_3(t)) is never a squared term in F_q, the method further comprising:
(a)	Selecting a parameter t;
(b)	Calculating X_1=X_1(t) and X_2 = X_2(t);
(c)	// Determining if the term f(X_1) is a squared term in the finite field F_q, // 
// If  (c) is true, then: //
   (d1) // calculating the square root of the term f(X_1) , and //
   (d2) assigning point P with an abscissa equal to X_q  // and an ordinate equal to the square root of the term f(X_1) //
// If (c) is not true, then: //
   (d3)  // calculating the square root of the term f(X_2) , and // 
   (d4) assigning point P with an abscissa equal to X_q // and an ordinate equal to the square root of the term f(X_2) //

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.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Oct 2019 12:20:11 +0000

>    -	Don’t specify cipher-suites using P-384 for PAKE algorithms requiring mapping
>  algorithms but recommend only Edwards/Montgomery curves or Short-Weierstrass
>  curves with p = 3 mod 4, such as BrainPool, P-256 and P-521.

I have a problem with exclusion of P-384. Are there patent issues with mapping for P-384, and do you see a way to avoid them, but still use P-384?

Thanks!

---

From: Björn Haase <[email-masked]>
Date: Thu, 17 Oct 2019 12:58:52 +0000

Dear Uri,

The possible patent problem persists for curves with p = 1 mod 4.  I did believe P-384 to belong to this class.

I see now that among the NIST curves the case p mod 4 == 1 seems only to apply to P-224. I was confused by the fact that the draft 04 did suggest Icart's mapping for  p = 2 mod 3 for the case of P-384.

The approach for simplified SWU from Appendix D.2 from WD19 could only be taken for p = 3 mod 4. 
The general simplified SWU which works also for p = 1 mod 4 (without the approach D.2 from WD19) would be different but still quite close to the patented method.
Icart's special method for p = 2 mod 3 is also patented.

So the increased patent-collision risk seems only to apply to P-224 which should not be recommended anyway as having less than 128 bit security level.

Yours,

Björn.

Dr. Björn Haase 

Disclaimer: 

-----Ursprüngliche Nachricht-----
Von: Blumenthal, Uri - 0553 - MITLL <[email-masked]> 
Gesendet: Donnerstag, 17. Oktober 2019 14:20
An: Björn Haase <[email-masked]>; [email-masked]
Betreff: Re: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations

Thanks!

---

From: "Riad S. Wahby" <[email-masked]>
Date: Thu, 17 Oct 2019 06:26:34 -0700

Hi Bjorn,

Thank you for the detailed analysis. One small comment:

Björn Haase <[email-masked]> wrote:
> Also for p != 3 mod 4  (e.g. P-384) when using generic simplified
> SWU we have differences between the patent and draft 04, but it’s
> still somewhat similar. We probably might be better off with avoid
> simplified SWU for P-384.

I might be missing something, but I believe P-384 is over GF(p) for
    p = 2**384-2**128-2**96+2**32-1
which is congruent to 3 mod 4, so the same method should work.

For curves where p = 5 mod 8, a similar process works:

- Compute x1 = X1(t), x2 = X2(t), and g(x1) in the usual way
- Compute tmp = g(x1) ** ((p + 3) / 8) and tmp2 = tmp * sqrt(-1)
- If tmp ** 2 == g(x1), return (x1, tmp)
- If tmp2 ** 2 == g(x1), return (x1, tmp2)
- Let tmp = tmp * t ** 3 and tmp2 = tmp * sqrt(-1)
- If tmp ** 2 == g(x2), return (x2, tmp)
- Else return (x2, tmp2)

One can keep generalizing for p = 9 mod 16, 17 mod 32, etc. Eventually
it gets unwieldy, but most of the time one chooses a prime where p - 1
is divisible by only a small power of 2 to avoid this (and there exist
methods that handle ugly cases: http://cr.yp.to/papers.html#sqroot).

Regards,

-=rsw

---

From: "Björn Haase" <[email-masked]>
Date: Thu, 17 Oct 2019 15:57:32 +0200

>which is congruent to 3 mod 4, so the same method should work.

Yes. You are right. Got confused by seeing Icart's algorithm for p = 2 mod 3 recommended for P-384. (See my last mail to Uri)

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Oct 2019 19:41:25 +0000

Excellent, thanks! 

I'm glad to hear that P-384 is still "safe" for hash2curve.

On 10/17/19, 8:59 AM, "Björn Haase" <[email-masked]> wrote:

    Dear Uri,

    
    Yours,
    
    Björn.

    
    Dr. Björn Haase 

    

    

    Disclaimer: 

    
    -----Ursprüngliche Nachricht-----
    Von: Blumenthal, Uri - 0553 - MITLL <[email-masked]> 
    Gesendet: Donnerstag, 17. Oktober 2019 14:20
    An: Björn Haase <[email-masked]>; [email-masked]
    Betreff: Re: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations

    
    Thanks!

---

From: "Riad S. Wahby" <[email-masked]>
Date: Sun, 20 Oct 2019 14:46:03 -0700

Hi folks,

In thinking about this a bit more, I believe there is a relatively
easy way to totally avoid Claim 13 of US Patent 8718276, which may
otherwise present IPR issues for use of the Simplified SWU map.

Let y^2 = f(x) = x^3 + A * x + B be the target curve over field F.

The text of the claim is reproduced below. The important part here
is that the method requires choosing polynomials Xi(t), 0 < i < 4,
for which the following hold:

1. f(X1(t)) * f(X2(t)) * f(X3(t)) is square in F for all t in F.

2. f(X3(t)) is a nonsquare in F for all t in F.

We can instead choose polynomials Xi(t), 0 < i < 3, and Z in F, for
which the following hold:

1. Z is non-square in F.

2. f(X1(t)) * f(X2(t)) * Z is square in F for all t in F.

3. x^3 + A * x + B - Z is an irreducible polynomial in F.

This still gives a usable map. Crucially, though, there is no X3(t)
such that f(X3(t)) = Z for all (any!) t in F. This is because when
    x^3 + A * x + B - Z
is an irreducible polynomial in F, this implies that it has no roots
in F and thus that x^3 + A * x + B != Z for all x in F---so Z cannot
be written as f(X3(t)) for any polynomial X3(t), and Claim 13 is not
applicable (to my non-lawyerly eyes, anyhow).

By combining the above modified criteria with the requirement that
Z is not -1, we have a method that is covered by neither US8718276
nor US8712038, regardless of how the map is evaluated (again, from
my perspective as a non-lawyer).

One might also worry that no suitable Z exists for curves of interest.
So far I've checked the NIST curves, BLS12-381, and secp256k1 and have
found suitable Z's without trouble (so at least heuristically it seems
like we shouldn't have that problem). I have not thought about whether
there is an easy proof that Z likely exists for any curve, but that is
not entirely implausible.

Thoughts on the above would be very much appreciated!

-=rsw

---

From: "Björn Haase" <[email-masked]>
Date: Mon, 21 Oct 2019 08:39:13 +0200

Dear Riad,

I follow your arguments, but in my opinion that might be still somewhat critical. Seeing that the problem occurs only only the case "p = 1 mod 4" and this is not the case for all of the relevant curves in practice today, I'd not spend too much effort on this.

For myself, I have summarized the results of the patent pitfalls of mappings and the consequences for protocols that use mappings as:

- We should recommend standardized protocols particularly for curves with p = 3 mod 4. (=> no restriction in practice when considering today's popular curves!)

- The standards such as hash2curve should prescribe simplified SWU according to the Annex D.2 of WB19 on curves with p = 3 mod 4

- If we have the option, we should better be constructing protocols on top of "x-coordinate-only" algorithms instead of full coordinates if possible (e.g. in the OPRF draft). I.e. not only for Curve25519 where doing so would be straight-forward with using X25519 but also in the case of Short-Weierstrass and Ed448.

- We might be better still including "plain" SWU as an option for mapping in the hash2curve draft.

Yours,

Björn.

Gesendet: Sonntag, 20. Oktober 2019 um 23:46 Uhr

Von: "Riad S. Wahby" <[email-masked]>

An: "Björn Haase" <[email-masked]>

Cc: "[email-masked]" <[email-masked]>

Hi folks,

1. Z is non-square in F.

x^3 + A * x + B - Z

-=rsw

> (d4) assigning point P with an abscissa equal to X_q // and an ordinate equal to the square root of the term f(X_2) //

_______________________________________________

Cfrg mailing list

[email-masked]

https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Riad S. Wahby" <[email-masked]>
Date: Mon, 21 Oct 2019 08:55:35 -0700

Hello Bjorn,

As I pointed out off-list, and to be completely explicit: X3(t)=Z is
not a counter-argument to my prior message since Skalba's inequality
requires a polynomial X3(t) such that

    f(X1(t)) * f(X2(t)) * f(X3(t)) == U(t)^2

and the point of choosing Z as we have is that there does not exist
any polynomial X3(t) such that f(X3(t)) == Z.

>    - We might be better still including "plain" SWU as an option for mapping

As I've said in the past, there is no reason to ever use "plain" SWU.
The map of Shallue and van de Woestijne has exactly the same cost and
is strictly more general. (We will certainly include the S-vdW map.)

Regards,

-=rsw

---

From: Björn Haase <[email-masked]>
Date: Mon, 21 Oct 2019 19:57:21 +0200

Helly Riad,

yes I now agree with you. The point would also be that the modified
method does not at all refer to Skalba's equality. And in this case,
plain SWU is indeed something not to include in the hash2curve draft.

Also this would also avoid the annoying restriction for avoiding use of
the y-coordinate! I'll look more closely at it this weekend.

Yours,

Björn