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

Armando Faz <armfazh@cloudflare.com> Fri, 09 April 2021 19:24 UTC

Return-Path: <armfazh@cloudflare.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 4AECC3A2BCF for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 12:24:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
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 sTTgw1xWEy0j for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 12:24:24 -0700 (PDT)
Received: from mail-lj1-x22b.google.com (mail-lj1-x22b.google.com [IPv6:2a00:1450:4864:20::22b]) (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 D19603A2BDB for <cfrg@irtf.org>; Fri, 9 Apr 2021 12:24:16 -0700 (PDT)
Received: by mail-lj1-x22b.google.com with SMTP id u10so7726870lju.7 for <cfrg@irtf.org>; Fri, 09 Apr 2021 12:24:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:from:date:message-id:subject:to:cc :content-transfer-encoding; bh=rV7CH+9r8RugxfWfgkaiZyD+nNJ/oH/UphFfDWi3D34=; b=NNZgK+poCqpD24Kaoj6Q7a/KwUOVfhgJbljnbiZbX3cUySqgz0nDVUU7BMJahpf7IS RDk/qTRaEUBLfTt5cF+8n2gEPRfTEBQHgsFwaaTcwY4UE4HYNRM4Do3pwWdUla2K9Zr2 LKEbYEoKJFZLfzVYNWTPfbz/WwCDauVSyuFpE=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc :content-transfer-encoding; bh=rV7CH+9r8RugxfWfgkaiZyD+nNJ/oH/UphFfDWi3D34=; b=qSya9EGexHYg3vmB6cIWLYTuFnQhpwyIEJ8BzJd/Etbtu3aGTFGJe6tX6X08VOCxAs 3zRc1WJVMohS8cxobNiPD9ukKTK36c5W3KPr9MqLGHPgwJvaGHGnvgFEpJZD5EcWSABi iOiC6a9mzSWvmShqCXBrOfYqZIuAyCIoa2+hf7BbZLn8E+1/KQQAGdaKRDWJVcWikNOG j+SuPGvkwb7eV1WfeCIJLv/dsPnImQIWybbcSprIOdJc+sEiOkfYfVe53ZU1tS23evRw A4yb9aS+YyNQwM06XqvJBxB8KgFsZlEo5uXDJhjeKQR45EEzNqT0Xw4TqIEtxHFN3ijP A7/g==
X-Gm-Message-State: AOAM5308bzdH/ptLrIOfD63WjXPejkSKi8cJcUnEZlsvw4doAYnFmBhh 6sycJgMPp8Q5IsbSWiVZcrs6kZyuWKnd2eMP4O7Guw==
X-Google-Smtp-Source: ABdhPJz5X/8VcVj6OPlONn43sB215Q7A+d822ff+7R/utglD+H8GbwfLhljubGTGK+izlfN5KA0LZPxPs6vv5Ld+MgI=
X-Received: by 2002:a2e:b44f:: with SMTP id o15mr10577195ljm.19.1617996249561; Fri, 09 Apr 2021 12:24:09 -0700 (PDT)
MIME-Version: 1.0
From: Armando Faz <armfazh@cloudflare.com>
Date: Fri, 9 Apr 2021 12:23:58 -0700
Message-ID: <CABZxKYmf2F0MV=aSa3ZrGbW3OuEzbsjMJ3ubCfPK+3Zg-Bkohw@mail.gmail.com>
To: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
Cc: IRTF CFRG <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/0zT5HkmebRJ5p4dQnlgcuFfZJBk>
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 19:24:29 -0000

> That?s certainly a convenient solution. However, a proper one would be to preclude small subgroup points by design. The real problem here is to ensure mapping to points in the ?correct? group on an elliptic curve, not just any point. The current draft doesn?t solve that real problem (yet). I don?t think this is impossible to solve, but it needs some more efforts.
>
> Cheers,
> Feng

Let me just clarify that the hash to curve functions described in the
draft is a composition of
 H(x) := clear-cofactor( map-to-point ( hash-to-field (x)))

This hash function always gives you an element in the prime-order
subgroup of the curve E(Fp)[q]. That means that it can return either
 - a point of order q, or
 - the identity point.

No low-order points are returned, so the concern that you have raised
is not a problem, and it is already solved by the clear-cofactor
function.

The probabilities of getting in the identity were already described in
previous emails. And the fact that H returns the identity point is not
a failure nor a lack of completeness.

OTOH, the calling protocol could need some specific property about the
points produced by H. For example, ensuring points are different from
the identity. That being said, the protocol is who is in charge of
banning those points.

The concern is akin to the generation of keys. For example, calling a
PRGN(seed) to get a key K. Of course, the key generation procedure
must ban the case of K=0. However, nothing is wrong with the PRNG
returning K=0 (with low probability).

I could recommend adding a couple of lines in the Security
Recommendation section about it, but definitely it is not a problem.

-- 
Armando Faz
Cloudflare Inc.