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

Filippo Valsorda <filippo@ml.filippo.io> Wed, 21 July 2021 21:18 UTC

Return-Path: <filippo@ml.filippo.io>
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 8AEE73A2AAC for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 14:18:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=filippo.io header.b=tEPA1syy; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=pylYKo/u
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 79HNGzLiig4f for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 14:17:55 -0700 (PDT)
Received: from wout3-smtp.messagingengine.com (wout3-smtp.messagingengine.com [64.147.123.19]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9CBF83A2ABB for <cfrg@irtf.org>; Wed, 21 Jul 2021 14:17:55 -0700 (PDT)
Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.west.internal (Postfix) with ESMTP id 07518320076F; Wed, 21 Jul 2021 17:17:53 -0400 (EDT)
Received: from imap1 ([10.202.2.51]) by compute2.internal (MEProxy); Wed, 21 Jul 2021 17:17:54 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:in-reply-to:references:date:from:to:cc :subject:content-type; s=fm1; bh=G440xjuJrcwBQ/1IVQ842muiMHjSBKc tRpw+CIDOg/A=; b=tEPA1syyTKddLEO7fNEtcNy+2Ni/rOL750/B+DSH5xPLTgc 3Gm9AwAEQHAl0HkSB/HTM9pwNXks4U0iaGmqBI5Z3fb1b9AtEUCVDgQg//7wY3I6 226SZTxjrZ9E87KfZhREIxpZY4/3sil3XqPQpKNirTf05dg+8v692fScEecStMeZ 83EAwbEvwir0cI+c9NxZh55ku/Lct4Z3AJ4Y6jOoOhfevQ6tHviZ2JzjvaT/8cor XmThfInx6/YZRP/1qbGx7C/rvpVUKgfBXXZx5uah18Wv7RtvbcVBNqLqYaI3cBX0 U/xrFazEhI0MpH8EdIqQI5clS4Hx6uYEhZuj2dQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=G440xj uJrcwBQ/1IVQ842muiMHjSBKctRpw+CIDOg/A=; b=pylYKo/uBBXFXrykv1kub9 8UE9WgFU3o2eB7hDHU/3jgjUnOfMGlzVsUt1RVFUDxa+PpZwx1zRoyKz0ndaMDSw YclltBuGhTw0tFCl/ygO9hZCVVED2vbeGZB0OcWa/ErhqIfgaAs/9Bvqn/XvBBvj hvbsaqfTdXjAbGJit1pX6NcF6vN7140SPKtPFEG3O4BlDGupc9b/aiUqt36+uzc7 zspmfG8Hefsayae3ACRfT94fkXvu3wxqRMFbgGK1DMPB/+4KXEqJ3J+KGo1Wb4np Ppq5VLrPLKtjZQqGXYMAxW61I46rnOwtyQ2EMygKgHpsb+H+AUdcRpUotbg8NL4g ==
X-ME-Sender: <xms:AY_4YN0UgE3EAuhPywlkjk0LD_irOZzYq8ORZrJhjIpJDM2nUgrdvg> <xme:AY_4YEGM-TtJmO4T8w_omUub2SH7vxRStABCMSacZ1EAzhMJdKSXucbqCfwEzpLaM khE5gd5YwJCdafREA>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvtddrfeeggddugedtucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucgoufhushhpvggtthffohhmrghinhculdegledmne cujfgurhepofgfggfkjghffffhvffutgesrgdtreerreerjeenucfhrhhomhepfdfhihhl ihhpphhoucggrghlshhorhgurgdfuceofhhilhhiphhpohesmhhlrdhfihhlihhpphhord hioheqnecuggftrfgrthhtvghrnhepvdeiffeileelvdfgtdetffffgfdtgeeuteekvdff ffejgedvffethefguddtffehnecuffhomhgrihhnpehgihhtrdhiohdpfhhilhhiphhpoh drihhonecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhep fhhilhhiphhpohesmhhlrdhfihhlihhpphhordhioh
X-ME-Proxy: <xmx:AY_4YN51j15l_mv2s91V8JCGPkyyO2lubxw8dQIwB02Dn43SUMGm_Q> <xmx:AY_4YK0Phpg4W9d2RhSDcGBg7K6FG7DUSelJs8GCLYeuipIqea3U4A> <xmx:AY_4YAHf6RhjWAiu4PLz7-lO2A3UCiJWFcittHxZdcb3VJP4bIXjkQ> <xmx:AY_4YDymcM0Nmn7P-3n2yv32wCQUtu-EC60AzYU6ifWlawGGkgDGzA>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 137BC130114A; Wed, 21 Jul 2021 17:17:53 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.5.0-alpha0-539-g8589ead45b-fm-20210721.001-g8589ead4
Mime-Version: 1.0
Message-Id: <9f3ac29d-c176-4440-8a2d-bd1546e39980@www.fastmail.com>
In-Reply-To: <20210721191123.i3f33p3qvkwxlbtl@kaon.local>
References: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com> <20210721191123.i3f33p3qvkwxlbtl@kaon.local>
Date: Wed, 21 Jul 2021 23:17:32 +0200
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: "Riad S. Wahby" <rsw@jfet.org>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary=02797b77d1e3470dadbc83d5c72abb0d
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/hbyaPPHIlMtOWmOhjkzDNMxd4CQ>
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 21:18:02 -0000

2021-07-21 21:11 GMT+02:00 Riad S. Wahby <rsw@jfet.org>:
> Hello Filippo,
> 
> Thanks for your thoughts on this! Answers and comments below.

Hi Riad! Replies inline.

> Filippo Valsorda <filippo@ml.filippo.io> wrote:
> > simply reducing 255 random bits will have a chance of bias of less
> > than 2⁻²⁵⁰, well within the security bounds of the curve.
> 
> As you say, for the case of p = 2^255-19 one gets a nearly unbiased
> result when reducing a 256-bit integer mod p. So you're right: it's
> safe in this specific case to use 256 (or even 255) bits.
> 
> But (as you know) in general it is not safe to reduce ceil(log2(p))
> bits mod p, since this can give significant bias for general p. The
> goal in the draft is to specify a hash-to-field method that is safe
> for any p without requiring any parameter except the security level
> in bits, k, and which gives bias roughly 2^-k. Adding parameters is
> dangerous in the sense that incorrectly choosing parameters gives a
> hash-to-field function that looks OK but is subtly broken.
> 
> So there's a tension here. On the one hand, we might say that it is
> not good to require a wide modular reduction; on the other hand, we
> might say that it is not good to open the door to subtle brokenness
> in the suite specs (especially when there is a strong temptation to
> introduce that brokenness for the sake of performance!).

Agreed there's a general tension here.

I think it helps to think in terms of abstractions. 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?

If the former, then maybe your hands are tied, but I also question whether this is trying to be too general. If the latter I feel like you could outright special-case p = 2^255-19 and I don't see how that could lead to mistakes.

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, and instead would take advantage of the ability to target specific curves individually to lead to better tailored algorithms.

> In my mind the second is the much more convincing argument, because
> every EC-relevant field library that I'm aware of implements a wide
> reduction already, inside the multiplication routine (which gives a
> p^2-size intermediate result).
> 
> So this
> 
> > Curve25519 implementations will all have to implement and expose
> > a new field operation (like https://git.io/JlU6L) which will be only
> > used for h2c, meaning it will not be well tested or maintained,
> > or h2c implementations will have to roll their own, probably
> > in variable time.
> 
> isn't really true. If one exposes the ceil(log2(p^2)) bit reduction
> that's already implemented for multiplication, then there's no need
> for extra code, and maybe even no need for extra tests.

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

Both libsodium and filippo.io/edwards25519 have ex-novo code for this draft specifically.

> I know this isn't a perfect answer, and I'm sure that some folks do
> not agree that it's better than the alternative (namely, adding the
> extra parameter to hash-to-field and asking folks to figure out for
> themselves the "safe" number of bits). But I would rather bet on J.
> Arthur Random Programmer to de-dup their code than to grok a subtle
> specification issue that could have potentially disastrous security
> consequences.
> 
> Would it partially allay your concerns if the hash-to-field section
> explicitly pointed out that it's possible to use the multiplication
> routine (or, well, half of it) for the wide modular reduction?
> 
> Thanks as always for your thoughts! and best regards,
> 
> -=rsw
>