[Cfrg] comments requested on proposed hash-to-field changes in hash-to-curve draft

"Riad S. Wahby" <rsw@jfet.org> Sat, 15 February 2020 10:52 UTC

Return-Path: <rswatjfet.org@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 7805E120048 for <cfrg@ietfa.amsl.com>; Sat, 15 Feb 2020 02:52:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.42
X-Spam-Status: No, score=-1.42 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id JDLSgf_T1ini for <cfrg@ietfa.amsl.com>; Sat, 15 Feb 2020 02:52:10 -0800 (PST)
Received: from mail-pg1-f169.google.com (mail-pg1-f169.google.com []) (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 C56D3120047 for <cfrg@irtf.org>; Sat, 15 Feb 2020 02:52:08 -0800 (PST)
Received: by mail-pg1-f169.google.com with SMTP id g3so6348191pgs.11 for <cfrg@irtf.org>; Sat, 15 Feb 2020 02:52:08 -0800 (PST)
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:subject:message-id:mime-version :content-disposition:content-transfer-encoding; bh=+mx+krI38WzufDVckUA5/BeyawYiP7Uq9L3SYNcsjTU=; b=iXLV3VyeQ9+2aCGuRbogyy/+kmeoREyeqaBcT8ujs2usB5BcotvbKR0RBPE8aKz7LB D7D5iCp6sOQbfUNQqb/fUPrC422Ole/bZDCyqxt6WWG0qw3nXxBqVJMoqFckk5Smyeui 9VdjkuEHV+GeMj1Rs6JKlLP4O1XuYQrgbspSAQ0aIW/NHZe1+RTlGoYDsgS+sN+LfdsU l6XI+lUP8py1yXQz+gF+/MftBiaNNdza9/kHURr+Z5FPQ243ZhjiIVOdPx82rYtW076V 4CvfhIcCGuiYfKmZoMz6B7fJ2m2+25IsCILfdGTEYqFJoxXPRG2dV9lphJFjHRm9Ev3/ 8nLw==
X-Gm-Message-State: APjAAAUGV6ZGqepaZmUwBLZcF3O0a7ERDGiSnFu1h06Tmqi+0tFA+hUd h8B5BSgXgxJKz3j0zZfYagQrQ3I6luw=
X-Google-Smtp-Source: APXvYqw8dBizVNNFvapz7yk2lB5NC0yG+2AmTMayif48tNAoUh/oAf7qloSAu88s+2hAcYREMdPluQ==
X-Received: by 2002:a63:4763:: with SMTP id w35mr8328625pgk.113.1581763927818; Sat, 15 Feb 2020 02:52:07 -0800 (PST)
Received: from localhost ([]) by smtp.gmail.com with ESMTPSA id z5sm10024714pfq.3.2020. for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 15 Feb 2020 02:52:06 -0800 (PST)
Date: Sat, 15 Feb 2020 02:52:04 -0800
From: "Riad S. Wahby" <rsw@jfet.org>
To: cfrg@irtf.org
Message-ID: <20200215105204.jj6dzmghqeyidrgc@muon>
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/p9WiZJ3PTfa8sklgklOH12xvaB4>
Subject: [Cfrg] comments requested on proposed hash-to-field changes in hash-to-curve draft
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: Sat, 15 Feb 2020 10:52:11 -0000

Hello CFRG,

I'm writing to request feedback on some proposed changes to the
hash-to-curve draft that the hash-to-curve authors and others are
currently discussing. These changes regard the way that the input
octet-string is hashed into an element of the base field, which
is the first step in hashing to an elliptic curve.

We're discussing this issue and proposed changes on GitHub
(but of course I'd be grateful for feedback via email, too).

As a brief overview of the issues we're trying to address:

The current function (called hash-to-base in draft-05) uses HKDF
to produce a pseudorandom byte string. This choice was motivated,
among other reasons, by our desire to have an indifferentiability
proof for Merkle-Damgaard hash functions and to allow for easy
domain separation.

Unfortunately, the current design suffers from three issues:

- Björn Haase points out that hashing is often expensive for smart
cards and embedded systems, which means that there's a strong
motivation to avoid HKDF and other HMAC-based constructions.

- Relatedly, several people have asked us to specify a way of using
functions from the SHA-3 family. There are no security issues with
using SHA-3 underneath HKDF/HMAC, but it's not necessary to do so.

- Leo Reyzin points out that, because of the way we use HKDF, we only
get domain separation from other uses of HKDF---*not* from other
uses of the hash function underlying HKDF. The result is that domain
separation "escapes" hash-to-curve in a rather unpleasant way.

The GitHub issue I referenced above proposes a simpler design that
attempts to address these issues. We would appreciate your feedback!