[CFRG] hash_to_field requires implementing a new 25519 field op

Filippo Valsorda <filippo@ml.filippo.io> Wed, 21 July 2021 17:09 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 7B4D43A1F53 for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 10:09:54 -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_H3=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=am8oDyh/; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=mN090TdY
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 WcIUBLC0rMZA for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 10:09:49 -0700 (PDT)
Received: from out4-smtp.messagingengine.com (out4-smtp.messagingengine.com [66.111.4.28]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 272CE3A1F55 for <cfrg@irtf.org>; Wed, 21 Jul 2021 10:09:48 -0700 (PDT)
Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id 0E6F05C01DC for <cfrg@irtf.org>; Wed, 21 Jul 2021 13:09:48 -0400 (EDT)
Received: from imap1 ([10.202.2.51]) by compute2.internal (MEProxy); Wed, 21 Jul 2021 13:09:48 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:date:from:to:subject:content-type; s= fm1; bh=nMrMexCKj88PGtatjOSydzfJjnkKCAhpd8ZfkUcwz58=; b=am8oDyh/ wMw0JjaA5iCZ9DC4jVy6u58KXBPO9BiMOkvTz+IIgPl1ARFO1MBZ5hu+DASqsrVq /WONB6IpElCFygX/vFMzyaawn6k9DTtOmCvw98Myz1GLQ9uoIyS4EjFUU/PFgNib qewJs6xR5Cje/Q4ibr/WrR1OxaH1fxX3ACzZenQDwUphQnUXSV7MGrFyp11PvGp3 hkQLi/w+9qfJKaGAPGDsV4r2/HcmrSYZltNleRCO9faJM4U1CdoLeeTIgGPvk3Ih J9VWohIGotGDE0e5K/dSTpkgEAxAMaaBV/7VCAmOKdA265ohH+PgXVozDfR3GB1Y MVOs5wYDjP4ouQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:message-id :mime-version:subject:to:x-me-proxy:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm3; bh=nMrMexCKj88PGtatjOSydzfJjnkKC Ahpd8ZfkUcwz58=; b=mN090TdYjLk8KGKQXsSzznssfBLaxEnufVxsEC7DXGTvv nV7q5BiXsEYuHmzWOL5JJ8V0yxQzmHTM3t17PLQe7pggkpHcDE+3XIqAdjdmWijI o39HyFuqzjd4pY2zz+HslVgCl7CONTYrpFvNvZw09BJ6cOSAC0zXlgpqqxT8gRE6 5Py3WSf8vY9Xv6tRSQL86nyy7SlsVbh1U6PLM9CecPMUE6O7jttpBP5BvwXRh2Ly 3TSfQiT71h2v5GpDHJ894Ob1cZjHqpJN50F6t3C5AR6MazxFNrwEHyOwJw+hN63g 9486A+FwQCPYa6rRjVIbGi6ZZQ8i9DILVU4nXv1cw==
X-ME-Sender: <xms:21T4YP4IbEa0L81Mg7ovrjN79l1_83lfGdvmCEJslrsKcaFA5CUKRw> <xme:21T4YE4kMuLVO28bJTZS1hnht1SzTfh68qgxUnhbHsSF8jak1xxI0DzH0cFubab_n bZa-axEPWp3iI8ILg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvtddrfeeggdeljecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecuogfuuhhsphgvtghtffhomhgrihhnucdlgeelmdenuc fjughrpefofgggkfffhffvufgtsegrtderreerreejnecuhfhrohhmpedfhfhilhhiphhp ohcugggrlhhsohhruggrfdcuoehfihhlihhpphhosehmlhdrfhhilhhiphhpohdrihhoqe enucggtffrrghtthgvrhhnpeejhefhfeffteeileejjeetgeeuleejhfekgedvfeffueef leeutdelveejtdejhfenucffohhmrghinhepghhithhhuhgsrdgtohhmpdhgihhtrdhioh enucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehfihhl ihhpphhosehmlhdrfhhilhhiphhpohdrihho
X-ME-Proxy: <xmx:21T4YGfhP29y1XEYigb0gy8CqXKmINBhPRi4mEsT_PPkUeIjdMBLJA> <xmx:21T4YALvjCTPGQtnCM6k8Yy9YrsbT_VOvTVtaR2sqWgFWs7EEDedyQ> <xmx:21T4YDJU2XwZVyeqYnSxoHWonwRHWWao8JOIKSgxGGSlivM70S9hqw> <xmx:3FT4YIVVicjbjkBc9pl_SWlz7HkOypwtP7Axw72C4KIceEnRxHZa-w>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 6BC62130114A; Wed, 21 Jul 2021 13:09:47 -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: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com>
Date: Wed, 21 Jul 2021 19:09:22 +0200
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary=78dbbc79392f47eda1a283f2dac68a9e
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/arUhkyLfixlgp0RrCayJx9QAnEk>
Subject: [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 17:09:55 -0000

Yawning Angel noticed that the current hash-to-curve draft requires implementing a new 25519 base field operation: wide reduction from 384-bit (or larger) inputs for hash_to_field. https://github.com/FiloSottile/edwards25519/issues/17

This is unfortunate, because most Curve25519 implementations probably don't already provide it, since simply reducing 255 random bits will have a chance of bias of less than 2⁻²⁵⁰, well within the security bounds of the curve.

There are two ways this can go: 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.

Why is a 384-bit integer reduced in hash_to_field for Curve25519 instead of the regular 255 bits?