Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

rsw@jfet.org Fri, 09 April 2021 20:59 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 6CC353A1137 for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 13:59:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.419
X-Spam-Level:
X-Spam-Status: No, score=-1.419 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, 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 eIzbR82gcknq for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 13:59:30 -0700 (PDT)
Received: from mail-qt1-f181.google.com (mail-qt1-f181.google.com [209.85.160.181]) (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 F03DC3A1115 for <cfrg@irtf.org>; Fri, 9 Apr 2021 13:59:29 -0700 (PDT)
Received: by mail-qt1-f181.google.com with SMTP id u8so5245746qtq.12 for <cfrg@irtf.org>; Fri, 09 Apr 2021 13:59:29 -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:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=526zzS2EuPwnlGa/3Dd/ViVLKwZqsSL4Quq01Bi8/xM=; b=NQWPH0zxK0YEOM0dA9HVQVBw9X3x2hlkDFHwC4ZsQtK5haozv6RDofNKkyBjBQPhXX KWXHlS0QGKhn9aq8baIRAUJi6lYl6o6Sxp1XICJfoHDQGgpkk9ugtoRB3cEou0jSXwG1 8c1SFSAzbiRnhdoDafERqrwlexRNCNrYGmZd3YnrNPOzBc+DHKew+t1HOJk3xIUKLMGQ dGMNN3Ec7c13hBprpA165La/ARiJgvrqzAr5aM9DL1OD3q6SC0Fo1TuvO21Vaej/6vT7 qq6VJp9LYJzTnH3t+dZI+5YCZGGhByhn2InA7x1MnWzkTS0MRnFqjQtOcWdS01K0HvUi NHYw==
X-Gm-Message-State: AOAM532c5nFwo7uzl33GfuhgHngDBE8OKblGCk+QY0JcSpnCRPP8Rbo2 Ndx44O88tGq/WehtIvFCmK4+qESsoXI=
X-Google-Smtp-Source: ABdhPJxIjVuSYfrhq+VLJdsxB8JbrcJI+pHi4Qal9cxhPSmKNfsHwGIWBOEkMiqFeCOoZaAe7U9Xgg==
X-Received: by 2002:ac8:7fcc:: with SMTP id b12mr14181296qtk.343.1618001968612; Fri, 09 Apr 2021 13:59:28 -0700 (PDT)
Received: from localhost (mobile-166-177-56-20.mycingular.net. [166.177.56.20]) by smtp.gmail.com with ESMTPSA id h75sm2639059qke.80.2021.04.09.13.59.27 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 09 Apr 2021 13:59:28 -0700 (PDT)
Date: Fri, 9 Apr 2021 16:59:26 -0400
From: rsw@jfet.org
To: "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org>, CFRG <cfrg@irtf.org>
Message-ID: <20210409205926.le4vsrgbgwd5azv5@muon>
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <d0778523-5f5d-4327-b795-279918c1899c@www.fastmail.com> <CAMr0u6=PBX1W5zQFmpxKQ=ViUXN9QK00BREL4M0=2HOkaXaiZw@mail.gmail.com> <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <4590aaa512acf5a482c9890ebe48f1760e5831a5.camel@loup-vaillant.fr> <F9593D27-3244-470E-89BE-85215B2DC9E7@shiftleft.org> <VI1SPR01MB0357AE729116A79C8DF70516D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <VI1SPR01MB0357AE729116A79C8DF70516D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/5fy8c9YLJ6rwwn3lOCVw9W-wMzk>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
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: Fri, 09 Apr 2021 20:59:38 -0000

Hello Feng,

Thanks for bringing this up. It's good to discuss this so that we are
all on the same page. Below I'll give one low-level answer, and then
a higher-level one.

"Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org> wrote:
> For example, if a user already has an input value in F_p, does he
> still have to go through the hash_to_field step (which is complex
> on its own)?

The answer to this question is unquestionably yes---hash_to_field
must *always* be used before map_to_group in any construction that
purports to be a conforming hash-to-curve implementation.

The hash functions defined in the draft are very clearly defined
to require all steps. Skipping steps in a cryptographic construction
is generally a recipe for disaster, and this is no exception. The
hash-to-curve document does not make any security claims about
implementations that skip steps, nor (in my opinion) would it
be reasonable for CFRG to require that implementations that are
non-compliant somehow remain secure anyway (after all: what would
this even mean?).

Zooming out, the higher-level question seems to be: should the
hash-to-curve functions defined in the draft somehow be designed
never to return the identity point? The answer is no, they should
not be designed in that way---returning the identity point with
negligible probability is absolutely fine from a security point
of view, as Mike and others have already pointed out.

I will not rehash [ ack! no pun intended :) ] their arguments. Instead,
I'll ask an analogous question: should SHA-3 have been designed such
that the all-zeros string is never produced?

It seems clear that the answer here is no---and yet if we use SHA-3
in a Schnorr signature, we might very well worry that the all-zeros
string would break things rather badly! Indeed, if the verifier's
challenge (generated by hashing the prover's randomness and the
message) equals 0, the signer can "sign" for any public key. Even
worse, if the signer's initial randomness (which, in a deterministic
signature, is also generated by hashing) equals 0, the signature
reveals the signer's secret key!

In both of these cases, it seems pretty clear that the issue is not
in the hash function, but in the application's use of it. If one
is worried about SHA-3 returning zero in a Schnorr signature, perhaps
one adds a special check in the implementation (though I'd say this
is clearly unnecessary). Similarly, if one is worried about the
(negligible!) probability that hash-to-curve returns the identity
point, one would "fix" this in the calling application.

No such fix is necessary, however---again, for the reasons that Mike
and others have pointed out.

Regards,

-=rsw