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

Loup Vaillant-David <loup@loup-vaillant.fr> Fri, 09 April 2021 14:45 UTC

Return-Path: <loup@loup-vaillant.fr>
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 0B2893A2380 for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 07:45:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham 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 chKVrEvoPVmE for <cfrg@ietfa.amsl.com>; Fri, 9 Apr 2021 07:45:07 -0700 (PDT)
Received: from relay5-d.mail.gandi.net (relay5-d.mail.gandi.net [217.70.183.197]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6FFBA3A237B for <cfrg@irtf.org>; Fri, 9 Apr 2021 07:45:06 -0700 (PDT)
X-Originating-IP: 78.198.246.40
Received: from grey-fade (unknown [78.198.246.40]) (Authenticated sender: loup@loup-vaillant.fr) by relay5-d.mail.gandi.net (Postfix) with ESMTPSA id DE0521C0016; Fri, 9 Apr 2021 14:45:01 +0000 (UTC)
Message-ID: <4590aaa512acf5a482c9890ebe48f1760e5831a5.camel@loup-vaillant.fr>
From: Loup Vaillant-David <loup@loup-vaillant.fr>
To: "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org>, CFRG <cfrg@irtf.org>
Date: Fri, 09 Apr 2021 16:45:00 +0200
In-Reply-To: <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
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>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.28.5-0ubuntu0.18.04.2
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/T0DomQJDgHRl_yf1VITgl-I1atU>
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 14:45:10 -0000

Hi,


> The methods defined in the draft map field elements in F_p to points
> on elliptic curves. But the points include small subgroup (low-order) 
> points. What if the mapped point on the curve falls into a small
> subgroup? The clearing-the-co-factor step (section 7) does no help at
> all here as it only turns the small subgroup point to an identity
> point.
>  
> The chance of falling into a small subgroup is extremely small, but
> for the completeness of the algorithm specification and the analysis,
> it’s still necessary to explicitly specify what to do in this case.

My opinion as an implementer is two fold:

1. Excluding low-order points is quite the hassle, and it's not
   clear how I could do it in constant time.
2. We never generate those points to begin with.

I don't want to deal with (1), which makes (2) very convenient for me.
So I'll just justify (2), using Curve25519 as an example:

- The order of the prime subgroup is a little over 2^252.
- The cofactor is 8.
- Therefore, Curve25519 has a little over 2^255 points.
- Selecting a point at random will give a low-order point about
  once every 2^252 trials. That means never.

The security of a curve is basically the square root of its prime
order. Here, 2^125 or so. Breaking it with standard brute force methods
is incommensurately easier than stumbling upon a low-order point by
chance.

In security parlance, a probability of 1/2^255 isn't just "extremely
small", it's "flat out impossible". I can therefore justify my laziness
and chose not to check for that event.

---

Note that generating a small-subgroup point *on purpose* will not work
either: Curve25519 has 8 low-order points, and a maximum of 16
representatives for those points (maybe a couple more if we allow
representatives over 2^255 - 19). The inputs are hashed before we map
the hash to the curve. So it's not enough to pick a matching
representative, we need to pick a hash whose image is one of those
representatives.

To do this, we need to conduct a multi-preimage attack on a 2^255-bit
hash, with 16 images. The difficulty of that attack is roughly 2^251.
Again, this is impossible if the hash is secure.

As a consequence, I cannot generate test vectors that account for this
edge case even if I wanted to. Even if I wasn't lazy, accounting for
low-order points means writing code I cannot trigger even if I want to
—dead code. That will only harm security in practice.

 
> In CPace and OPAQUE, both protocols use the output of hash-to-curve
> as a base generator. The implicit assumption is that the returned
> value from hash-to-curve must be a non-identity point in a subgroup
> of the large prime order.

This assumption is correct as far as I can tell: yes, in *theory*, we
have a couple exceptions. In *practice*, those exceptions will never
occur. The probabilities are low enough to be considered negligible.

 
> Has this issue been considered? Apologies if I missed any discussion
> on this before.

Likely. I haven't followed past discussions though, so I cannot say.

Loup.