Re: [CFRG] hash_to_field requires implementing a new 25519 field op

"Riad S. Wahby" <rsw@jfet.org> Wed, 21 July 2021 22:30 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 C352E3A2CE9 for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 15:30:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.646
X-Spam-Level:
X-Spam-Status: No, score=-1.646 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 5VRxJup_XzHN for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 15:30:17 -0700 (PDT)
Received: from mail-qt1-f169.google.com (mail-qt1-f169.google.com [209.85.160.169]) (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 D4BEA3A2CEA for <cfrg@irtf.org>; Wed, 21 Jul 2021 15:30:16 -0700 (PDT)
Received: by mail-qt1-f169.google.com with SMTP id g8so3015747qtj.1 for <cfrg@irtf.org>; Wed, 21 Jul 2021 15:30:16 -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=ILJqg/QxM+Ss1SDwbBRk3N1uQye3KzGsFpZ7N5JS9Lw=; b=IYse22jrIpASYLEoPk/BvEZBOzmjgtgs9izFALhe+bpjbf2RT3AMInYgqtsGJcxTWH WQcFMQQSS8OcO3kt2U/ezURKUYCOhg0ET5sS0/9daf+NaOZTftBzcE/Ae6+t5zvo70Cr LHRjIfr2rgCOGMUpxQNSj/sVgjKmmfvtgz51VsWL8IxWBmrG8gH0NP/3C1be/ZEmvslW QdXSUaC1ccbPp/ZVVqfu+FaBNo/OGWh3nU6nGqhWc7RJQSjFc7fe9TESpAV8gKzX6zGW yS0JwyaFDPzuv6cP6geuE3rcE8OOCEbrvWiXB2ayJ9b1NZfVkb2poZY3AZJElJO0Xi/U NUfA==
X-Gm-Message-State: AOAM530vxxVBAOP/GwCjupc+x3TQf/ax9rVXk0/TKNu2eNFyXuiENNm/ OH9h5JXAqP1ig/hJh+SW36KuXzC2NKk=
X-Google-Smtp-Source: ABdhPJxoOF5Y7XhGTOSttIes15ErSJobuhZUjVX/+6hm2qfu7Df3v/zICnJgiDdSOHf/QUijH0e+mw==
X-Received: by 2002:a05:622a:1805:: with SMTP id t5mr33560132qtc.340.1626906615354; Wed, 21 Jul 2021 15:30:15 -0700 (PDT)
Received: from localhost (mobile-166-170-21-67.mycingular.net. [166.170.21.67]) by smtp.gmail.com with ESMTPSA id m80sm9041990qke.98.2021.07.21.15.30.13 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 21 Jul 2021 15:30:14 -0700 (PDT)
Date: Wed, 21 Jul 2021 18:30:12 -0400
From: "Riad S. Wahby" <rsw@jfet.org>
To: Filippo Valsorda <filippo@ml.filippo.io>
Cc: cfrg@irtf.org
Message-ID: <20210721223012.sxinywkcwt4ztphx@kaon.local>
References: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com> <20210721191123.i3f33p3qvkwxlbtl@kaon.local> <9f3ac29d-c176-4440-8a2d-bd1546e39980@www.fastmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <9f3ac29d-c176-4440-8a2d-bd1546e39980@www.fastmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Y3t8q6wqFwqPqeVZoFfWW0n3zRc>
Subject: Re: [CFRG] hash_to_field requires implementing a new 25519 field op
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: Wed, 21 Jul 2021 22:30:22 -0000

Hey again Filippo,

Filippo Valsorda <filippo@ml.filippo.io> wrote:
> Is the h2c spec supposed to expose a safe, universal hash_to_field
> function, or is it just a component of higher-level functions? Are
> developers expected to swap in arbitrary curves into the spec,
> or are they supposed to use specific instantiations? Is an h2c
> library expected to work with all possible curves, or is h2c one
> of the features of a curve-specific library?

These are great questions. I don't have any particular opinion on the
third one, but with respect to the first two my opinion is that there
are really two separate roles here. One is a developer who implements
an existing suite. The other is an application designer, who needs to
hash to some curve in their application that we (the h2c authors) did
not anticipate. For the second role it should be easy to start with a
curve spec and end up with a secure hash-to-curve suite.

> Myself, I believe elliptic curves are not a safe abstraction (as
> opposed to prime order groups, as you might have expected ;-),
> which I believe should include a fixed-length-string-to-element
> map as part of the abstraction, solving the issue) so I wouldn't
> try to write something that generalizes over arbitrary elliptic curves

Totally agreed that elliptic curves have plenty of sharp edges! But I
am not convinced that hash-to-curve is the culprit here---mostly it's
protocols that are designed assuming "elliptic curve" == "prime-order
group," whereas h2c explicitly deals with composite order. And in any
case, I cannot stop anyone from using a composite-order group, but at
least h2c can help them get one tricky part right!

(Moreover, one of h2c's main users is pairing-friendly curves. Do any
nice composite-order abstractions exist for these? I do not know any.
But they *do* seem to be a moving target! which suggests that we have
to assume the suites in h2c won't suffice forever...)

> That's not true for unsaturated limbs like the popular 51-bit limb
> schedule used by most 64-bit implementations of Curve25519. Reduction
> in multiplication is carried out simultaneously with multiplication,
> and it yields double-wide _limbs_, which are carried very differently
> from a wide reduction. https://git.io/JlTG0

Surely there is nothing magic about unsaturated limbs! It's true that
the code you linked would need an "adapter" morally equivalent to the
code on lines 79--117; but after writing that adapter, lines 146--162
could be shared with the wide reduction routine.

So it is not true that we could get away without new tests, contra my
prior email's claim---mea culpa!---but certainly the adapter would be 
much simpler than either lines 79--117 or lines 146--162: split a 384
bit number into 8 * 51 bits with some shifts and masks; call addMul64
three times; continue at line 146. Is that 10 lines of code? 20?

I freely admit that this is just one point of view and that there are
good arguments in the other direction. And talk is cheap for me since
I don't have to maintain those 20 lines of code! :) But I don't think
those lines suffice to justify dramatically increasing the likelihood
that an application designer gets confused and specifies a broken h2c
suite for next year's shiny new elliptic curve...

Best regards,

-=rsw