Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt

"Riad S. Wahby" <rsw@jfet.org> Tue, 23 July 2019 20:25 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 9F6DD120967 for <cfrg@ietfa.amsl.com>; Tue, 23 Jul 2019 13:25:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.557
X-Spam-Level:
X-Spam-Status: No, score=-1.557 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_H3=0.001, RCVD_IN_MSPIKE_WL=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 Y6CPSD1yftxb for <cfrg@ietfa.amsl.com>; Tue, 23 Jul 2019 13:25:34 -0700 (PDT)
Received: from mail-pl1-f195.google.com (mail-pl1-f195.google.com [209.85.214.195]) (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 ED84E120962 for <cfrg@irtf.org>; Tue, 23 Jul 2019 13:25:33 -0700 (PDT)
Received: by mail-pl1-f195.google.com with SMTP id t14so21013199plr.11 for <cfrg@irtf.org>; Tue, 23 Jul 2019 13:25:33 -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=m0xrqi+X2N6VVkJjCFQE1usPvr4FwbhJ88mirkOiK5k=; b=jw6+hx96891Z08wyX+9yOxJT6Q8shUQs86Ut2rYHipkLMR+hcdj6NTxNS5elYgtob5 +hqtb2Si7a+ldzZF59DkRJgjqv015L7yHue7QuKrqibLxsX8t3znxx0Gx9LKWfE9j6z1 ve4dLHheRhImYMIR9QRq38FcbVEmpENpVZB/nxRTwvGJZ6LeLD7BgZwtId8PenkXlNM/ KkI89E4MmfmYsggD0NFApyTmeZLLJ3Y1SbELv5xNPLASveeXq31++PXgQzw41uoX/tgU OhAXp2be+VCvhkGx00VUfXJpqFY4L2lOpPLVwlSz3oocrlAwEFkwoOgj1idRIsll3VxT 9how==
X-Gm-Message-State: APjAAAWN9aHJBpTlr/S960HlHMAp2T0l26aFsK4ZhDvPwiwqkwJtZiAJ h+Va2tmSETe6r87cKwz3heRpsa4R
X-Google-Smtp-Source: APXvYqyaVuhimjoDZg6YCNTqdAZ6NAAyIHNF62gQ3letTGCfZEKhIepR1lgO1foRT+oebge2wUjVLQ==
X-Received: by 2002:a17:902:ac87:: with SMTP id h7mr85064481plr.36.1563913533499; Tue, 23 Jul 2019 13:25:33 -0700 (PDT)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id t96sm39401186pjb.1.2019.07.23.13.25.31 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 23 Jul 2019 13:25:32 -0700 (PDT)
Date: Tue, 23 Jul 2019 13:25:30 -0700
From: "Riad S. Wahby" <rsw@jfet.org>
To: Dan Harkins <dharkins@lounge.org>
Cc: cfrg@irtf.org
Message-ID: <20190723202530.vu6ko3fqyi6j222t@positron.jfet.org>
References: <46863a4d-e193-1697-058d-2c14106c317e@web.de> <84012971-70cd-da2d-55b7-944635c92b65@web.de> <F5C22BE6-7E24-43E8-B023-A5FF0A5EA960@jfet.org> <789acfa6-3084-abf5-d265-1b61dfd9f6bc@lounge.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <789acfa6-3084-abf5-d265-1b61dfd9f6bc@lounge.org>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/E6E6XGT_aMDahT9bptfTiaB55So>
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, 23 Jul 2019 20:25:36 -0000

Hello Dan,

Thanks (again!) for helping us make the draft better.

Dan Harkins wrote:
>   My original request to add back SWU was so I could have 1 method that worked
> for the majority of curves that can be instantiated with a particular curve
> and a particular hash function. I thought the trend from -03 to -04 was for
> ciphersuite-style methods where if you're using curve foo you do one kind of
> hash to curve with one particular hash algorith and if you're using curve bar
> you use a different hash to curve method with a different hash algorithm. From
> a programming point of view the latter is sub-optimal as I have to implement
> a whole slew of hash to curve methods if I want to support a slew of curves
> (where slew > 3).

It's true that Suites in -04 is revised and somewhat expanded from
-03, but the intent of this section remains the same: offering an
easy way to choose an efficient hash function for common curves.
In other words, Suites are suggested, not required.

    (Aside: This is more pragmatic than anything else: even if Suites
    were "required," implementors would find reasons to ignore them.
    So the document may as well reflect the reality that some will
    treat suites as a suggestion---if only as a warning to others!)

If your preference is to specify a single method for all ciphersuites
in a higher-level protocol, that is totally reasonable. On the other
hand, since maps do not interoperate, if a standard specifies Elligator
for one curve and Simplified SWU for another, there's little choice
but to implement both. (Fortunately, those two maps cover the lion's
share of curves.)

    (Corollary to the prior "aside": It seems reasonable to assume that
    some standards will specify only the fastest maps for the curve(s)
    they select---so unfortunately it's not obvious how we'll avoid having
    to implement more than one hash-to-curve method in practice. As an
    extreme example, even if we said every curve MUST use the same method,
    one assumes that would be summarily---I daresay lustily---ignored!)

>   If the Simplified SWU of -04 also applies to all the curves that SWU does
> then that complaint goes away. One issue with the Simplified SWU of -04,
> though,
> is that I need the parameter Z for the curve so I either need to derive a Z
> for every curve my code is going to support and store it (perhaps along with
> the rest of the domain parameter set) or I derive it on the fly which sounds
> like more looping which I want to avoid.

I agree it would be nicer if we could dispense with Z. As a small
silver lining, Z is essentially always a signed 8-bit integer, so
storing it is cheap. (As you say, deriving on the fly seems ugly.)

One thing we probably should do is provide (pseudo)code that outputs
Z as specified for each map. I've taken a note on this.

By the way, one of the reasons for the addition of per-curve Zs is
that we're trying to systematically handle exceptional cases, and Z
is a knob that we can turn for most maps.

>   So I still have a slight preference for the long-form SWU from -03 to
> return in -05. Having ciphersuites for people who prefer that sort of thing
> is fine but just don't make that the only way to go. Patents are, of course,
> show stoppers.

Fully understood and agreed. We will clarify that Suites are (intended
as) conveniences, not straightjackets :)

As far as a one-size-fits-all method, probably the best choice is
Shallue and van de Woestijne (ANTS 06), which works for *any* curve
over large prime fields (including j-invariants 0 and 1728). The
current description of Shallue and van de Woestijne (Section 6.9.1
of -04) isn't fully general, but this is something we will address
in the near future (I have something mostly worked out on paper).

By the way, it turns out there's another pretty strong (in my opinion)
reason to avoid resurrecting plain SWU: its interface doesn't match
the other mapping functions'. In particular, it takes a pair of field
elements as input, rather than one like other maps. In principle
this is a minor thing, and indeed it's totally surmountable if
necessary. But it risks unclarity and forces expenditure of effort
on a map that offers few clear advantages when compared to Simplified
SWU or Shallue and van de Woestijne:

- compared to Simplified SWU (as described in -04), SWU supports the same
  curves but runs much more slowly; and

- compared to Shallue and van de Woestijne, SWU supports fewer curves
  and has essentially identical performance.

So I'm still holding out hope that we can avoid bringing Plain SWU back.
But---of course---we will do what's necessary to make the draft useful.

Thanks again (again!) for the feedback!

-=rsw