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