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

"Riad S. Wahby" <rsw@jfet.org> Wed, 21 July 2021 19:11 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 ABF853A25C3 for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 12:11:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.649
X-Spam-Level:
X-Spam-Status: No, score=-1.649 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_H2=-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 C2MJQ_dmBJl9 for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 12:11:27 -0700 (PDT)
Received: from mail-qv1-f50.google.com (mail-qv1-f50.google.com [209.85.219.50]) (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 057D63A25C0 for <cfrg@irtf.org>; Wed, 21 Jul 2021 12:11:26 -0700 (PDT)
Received: by mail-qv1-f50.google.com with SMTP id ck17so1457559qvb.9 for <cfrg@irtf.org>; Wed, 21 Jul 2021 12:11:26 -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:content-transfer-encoding :in-reply-to; bh=nhRDi/BNU5Xdw+8XCdBeMcX1h5GDsiWMyNk1lkSYHyw=; b=hI0NgrFQahc4Ql0verxmf5K/5pLNDgVgUE7k/vT7ZjNwpIT4Bl3vLdMwqOV8PoLJWf Ttb+nt4OU1VkHhHFE3zOGcgOzW5RgAuZJCDQkr70KNbqOdP2R/+51t1+DlHXyUqGDbqR uSIZwzcl08+Ebu1b8nFoT1zyhu3fPcnFFI8F1ORtJ2NmOe/ggHMk8Pqli4l3idco0L+L 94xva71HN+Q8Z2rSiFSmkKDnATGwmMiNtRyIPlmhMlegT2yZQOEKUJ2tAx28RVNY3TBL OAZEmtgSJjxHnuwSP3Qji3BcYOqjcOVJYoV/XIhlaQksmZcQePWZTTWz6VWObjKq63i6 pT8w==
X-Gm-Message-State: AOAM5301vruHJHflYxArC/Fxh9kP2fkIp53svlbkQGTk2fGoq8bx3NQ6 l6QVbedscC7N+xdIAp8EQjA=
X-Google-Smtp-Source: ABdhPJzNOqwIrNDjIWGgZjfcFNUG2St2PEFwlKtu5idpQGhr9J6p6aJ32/a4hCDnozG53jL385Cg3g==
X-Received: by 2002:ad4:4a03:: with SMTP id m3mr37539765qvz.33.1626894685456; Wed, 21 Jul 2021 12:11:25 -0700 (PDT)
Received: from localhost (mobile-166-170-21-67.mycingular.net. [166.170.21.67]) by smtp.gmail.com with ESMTPSA id v20sm9256301qto.89.2021.07.21.12.11.23 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 21 Jul 2021 12:11:24 -0700 (PDT)
Date: Wed, 21 Jul 2021 15:11:23 -0400
From: "Riad S. Wahby" <rsw@jfet.org>
To: Filippo Valsorda <filippo@ml.filippo.io>
Cc: cfrg@irtf.org
Message-ID: <20210721191123.i3f33p3qvkwxlbtl@kaon.local>
References: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Nn0a3hIcadMrINozzB2iGwPTGAw>
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 19:11:33 -0000

Hello Filippo,

Thanks for your thoughts on this! Answers and comments below.

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!).

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.

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