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