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

"Björn Haase" <Bjoern.M.Haase@web.de> Mon, 21 October 2019 06:39 UTC

Return-Path: <Bjoern.M.Haase@web.de>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A065A120071 for <cfrg@ietfa.amsl.com>; Sun, 20 Oct 2019 23:39:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.597
X-Spam-Level:
X-Spam-Status: No, score=-2.597 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, LOTS_OF_MONEY=0.001, MIME_HTML_ONLY=0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=web.de
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OGGoZLZsnoeC for <cfrg@ietfa.amsl.com>; Sun, 20 Oct 2019 23:39:22 -0700 (PDT)
Received: from mout.web.de (mout.web.de [217.72.192.78]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CB444120052 for <cfrg@irtf.org>; Sun, 20 Oct 2019 23:39:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1571639953; bh=DWTc2xLXqC/dC/aFDu6uSkCJ18h7SUMbjynsWWfSqTw=; h=X-UI-Sender-Class:From:To:Cc:Subject:Date:In-Reply-To:References; b=JzYWOryk3Xvdz+EC5yHQCqLMqGl4EsdPnw0f0A+YTkXClInZYHbPsDY9VenLxju45 R+OBOlyXPmXkFxRUFrZIWZuwfK17CCoAPnDrvJ0yRrE2SDWtd9pVMYUM0YrWKN6vj5 rrDJKZBf5Z4D7Rt+BlOBCd/xhevIGJEBsSV+RLi8=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [93.240.145.106] ([93.240.145.106]) by web-mail.web.de (3c-app-webde-bap26.server.lan [172.19.172.26]) (via HTTP); Mon, 21 Oct 2019 08:39:13 +0200
MIME-Version: 1.0
Message-ID: <trinity-549479d5-9427-41ad-987b-e35871e9cfeb-1571639953515@3c-app-webde-bap26>
From: "\"Björn Haase\"" <Bjoern.M.Haase@web.de>
To: "Riad S. Wahby" <rsw@jfet.org>
Cc: "\"Björn Haase\"" <bjoern.haase@endress.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/html; charset="UTF-8"
Date: Mon, 21 Oct 2019 08:39:13 +0200
Importance: normal
Sensitivity: Normal
In-Reply-To: <20191020214602.veecj2ft2v6czjye@positron.jfet.org>
References: <5e1610c6-2038-31ce-6bb8-a6e18f40434d@web.de> <ac0ed5bf-cc4b-14e6-59c6-f24c7cb43f1a@web.de> <20191016202223.lbuavuery4yj6qib@positron.jfet.org> <trinity-77782fb3-2939-452c-85d8-95592c7829b8-1571301291317@3c-app-webde-bs25> <VI1PR0501MB22556D3FA849989AAFFFD1FA836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com> <VI1PR0501MB22555DA1CD400E64259EA39D836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com> <VI1PR0501MB2255C90CDB1AA88516A1CFDC836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com> <20191020214602.veecj2ft2v6czjye@positron.jfet.org>
X-UI-Message-Type: mail
X-Priority: 3
X-Provags-ID: V03:K1:uLvSASxB+09tfdek/NqEjjM68EWknkunQJsClFSjo1n5x6klIpdzR5mYbY7E/7ShSax0k NHZVQNPn9W9I1wuZREbRIOJ7bu1S1g8LqpCIbQzvpWCP2/yOrUg0C8uB+y1N9QbKbna7ttcNhsAY xoBOJbYzaThxbzk4ESb/aA7jmDbIe6ycvZAMQaUqcudePUpf7iGK9QLR5VfQ/LUO4X1q3EYxLBm4 0AgzFXQLcbpd7cdtXcJYiH25xcyN3BHS8tRRupuBwpNdbxYDh41Xy/rBQTk0jfj+6/D8zYuD5mdT Fs=
X-UI-Out-Filterresults: notjunk:1;V03:K0:MeUPKLsscC4=:PYDOTBWfbZuDba8Cmj/aBZ j/qQlJxZduyDWafBZgbeiWGeXbR5pgnkLjeG50AIIW3DjGnbsW97cDLpnSoh6S+4pyXZvyMzt UhI4Gr32ApzguFMDGk0PsqGIbr8lskHYdNPeZRHJxP1FpxTqY5CHbSErBjwG02ixIT90IgwwI uZgDygtScC7sAk16ZwT+7i+kQ09Te0k/0cCZy0OhYARSu8Y4b6IqEnWNwX1IiWyBSiGzwQD1E d+3UDX9FOuRTvQgaDeD+84AXjjdNKqNeOkrUWNsiMuNQanxxsrVplh3btLu82wC4CH2y/7tbn VALI7mfXGt4ZB7Wgu5DPRv4cmD6pcIoRfQFLhZSaDN6SUAcxGf7Ys2feSVwOJgdoRAJywRwnJ mvSoq/JpHbEj1wiazL27DQ6mt8T8+ERCk4XwGIrB6zBnjKBba4ZZEkdW9BnkOL9J+ux9lWlf0 rYsO5htHb7KyZOB7UdUTmIe9kEuHXh2POCql9DsXWo/oD0xgeA8qiFujAFZrntUc5zA20bles +yr9NhFsWTEvmSZDOptRhbiNb7Pp3MpewymwOyIx7XgF7gRdS5H84dLwtfgfJWzEiWDt22EgC IEURXUcLsdPOIG/GMuhHZdJRhszr+pXGh2T/mUXm7wfKn80Po9ekohAbBpQXDtQMrU0hC5Sjr GgNv0HufGbh6quySb3huXpjtCGMQgdNJp659i1TmwixA8xff/VOGjCvobrS5B6saFB0w=
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JwR3YyMCUPG7qdSEHxAjQ_He7-4>
Subject: Re: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 21 Oct 2019 06:39:25 -0000

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" <rsw@jfet.org>
An: "Björn Haase" <bjoern.haase@endress.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Betreff: Re: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations
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

Björn Haase <bjoern.haase@endress.com> wrote:
> 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) //

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg