Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt
"Riad S. Wahby" <rsw@jfet.org> Tue, 16 July 2019 17:58 UTC
Return-Path: <rswatjfet.org@gmail.com>
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 453D6120C20 for <cfrg@ietfa.amsl.com>; Tue, 16 Jul 2019 10:58:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.56
X-Spam-Level:
X-Spam-Status: No, score=-1.56 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.091, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no 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 VTBAR7QnysMB for <cfrg@ietfa.amsl.com>; Tue, 16 Jul 2019 10:58:24 -0700 (PDT)
Received: from mail-pg1-f173.google.com (mail-pg1-f173.google.com [209.85.215.173]) (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 26A1B120C21 for <cfrg@irtf.org>; Tue, 16 Jul 2019 10:58:17 -0700 (PDT)
Received: by mail-pg1-f173.google.com with SMTP id q4so9808235pgj.8 for <cfrg@irtf.org>; Tue, 16 Jul 2019 10:58:17 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=7zPRTZqrIeJo+g7V6yZZ0AGk0p0nKMT+8trjkAwSoSo=; b=gzHH+0i7Yd/IBi4Yk0b+5tPFzqnHKcAVVoWQV6i5/bDdEe0kzqLBf4A0De6aGrpB/+ LlzT7LS0Thno/KCWMFU8xvlmIDURff9kmxQrbPjGRsIzCjziSgsLh42petn46Tp3swtP mmUfiOHx2TA6X4obImKLRWrN+zY8D4JyokPwyp2Dh2xMGyIpvAx+GPiXXm5sSfGtFNXg 863C0NLqRAU4ej0W8qdVHuUB20dJxIyVCNmfpaABdKDI+Za46Gcs7iOeWaKpJrYs8Y92 qpKFDyCTNn0TDNuYH2DH80sFi7etqQ5LGOInCVpLtMpBFvMP9Z/ecVHk1Nf+HatbUh2b Ceow==
X-Gm-Message-State: APjAAAVOgCGaQRqqp8C0l+p49OttshPzhsMj7YfI77r1khM/zQEr0Nk+ 3pHQ8YqCVMTC2CsXDVcshHTYxPa1
X-Google-Smtp-Source: APXvYqyWjeRPaWM0eM2+0SlAwgm3WqzOQsGvbmxG4/c8iCiaCuBUQokVOPRzfVra/sTxgZ+pR1hXPg==
X-Received: by 2002:a65:51c1:: with SMTP id i1mr14186769pgq.417.1563299896192; Tue, 16 Jul 2019 10:58:16 -0700 (PDT)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id o11sm39550467pfh.114.2019.07.16.10.58.14 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 16 Jul 2019 10:58:15 -0700 (PDT)
Date: Tue, 16 Jul 2019 10:58:13 -0700
From: "Riad S. Wahby" <rsw@jfet.org>
To: cfrg@irtf.org
Cc: dharkins@lounge.org, uri@ll.mit.edu, bjoern.haase@endress.com
Message-ID: <20190716175813.7vmllagxqeianual@positron.jfet.org>
References: <156262877252.887.17736027249172849204@ietfa.amsl.com> <ed63dbe8-4a7e-8c0d-ffe2-90cc99bb9a6e@lounge.org> <VI1PR0501MB22557A164EED31B2C17EB44983CE0@VI1PR0501MB2255.eurprd05.prod.outlook.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <VI1PR0501MB22557A164EED31B2C17EB44983CE0@VI1PR0501MB2255.eurprd05.prod.outlook.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/SWWXAbX7lh9an8KDqY_tGlgAjIc>
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 18:49:22 -0000
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