Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt
"Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu> Tue, 16 July 2019 20:34 UTC
Return-Path: <prvs=2100813249=uri@ll.mit.edu>
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 8DD4A12006A for <cfrg@ietfa.amsl.com>; Tue, 16 Jul 2019 13:34:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.195
X-Spam-Level:
X-Spam-Status: No, score=-4.195 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_QP_LONG_LINE=0.001, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 rFstDsnQiCIz for <cfrg@ietfa.amsl.com>; Tue, 16 Jul 2019 13:34:02 -0700 (PDT)
Received: from llmx2.ll.mit.edu (LLMX2.LL.MIT.EDU [129.55.12.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 597D9120041 for <cfrg@irtf.org>; Tue, 16 Jul 2019 13:34:02 -0700 (PDT)
Received: from LLE2K16-MBX03.mitll.ad.local (LLE2K16-MBX03.mitll.ad.local) by llmx2.ll.mit.edu (unknown) with ESMTPS id x6GKY0dr034564; Tue, 16 Jul 2019 16:34:00 -0400
From: "Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu>
To: "Riad S. Wahby" <rsw@jfet.org>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt
Thread-Index: AQHVNeYRr2CXgYSNOECJQSvSRVmNrabNSCsAgABAjoCAAE6bgP//6HKA
Date: Tue, 16 Jul 2019 20:33:57 +0000
Message-ID: <25B1BA25-C3DA-4203-B0BF-A90145BCE468@ll.mit.edu>
References: <156262877252.887.17736027249172849204@ietfa.amsl.com> <ed63dbe8-4a7e-8c0d-ffe2-90cc99bb9a6e@lounge.org> <VI1PR0501MB22557A164EED31B2C17EB44983CE0@VI1PR0501MB2255.eurprd05.prod.outlook.com> <20190716175813.7vmllagxqeianual@positron.jfet.org>
In-Reply-To: <20190716175813.7vmllagxqeianual@positron.jfet.org>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.19.0.190512
x-originating-ip: [172.25.1.10]
Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg="sha256"; boundary="B_3646139635_1014036513"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-07-16_05:, , signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1810050000 definitions=main-1907160250
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JiJhc9gC7ktTps3oH3RGHk2B1rU>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt
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: Tue, 16 Jul 2019 20:34:05 -0000
> ...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 > 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? 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" <rsw@jfet.org> wrote: 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: > 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. 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? Dan Harkins wrote: > 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? 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
- [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-… internet-drafts
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Dan Harkins
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Björn Haase
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Björn Haase
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Riad S. Wahby
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Riad S. Wahby
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Björn Haase
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Rene Struik
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Armando Faz
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Björn Haase
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Riad S. Wahby
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Dan Harkins
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Björn Haase
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-cu… Riad S. Wahby