Re: [Cfrg] ECC mod 8^91+5

Ilari Liusvaara <ilariliusvaara@welho.com> Wed, 02 August 2017 15:17 UTC

Return-Path: <ilariliusvaara@welho.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 01F9E12711B for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 08:17:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-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 IDqM7u0FlCmB for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 08:17:24 -0700 (PDT)
Received: from welho-filter4.welho.com (welho-filter4.welho.com [83.102.41.26]) by ietfa.amsl.com (Postfix) with ESMTP id 12B6D124207 for <cfrg@irtf.org>; Wed, 2 Aug 2017 08:17:23 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by welho-filter4.welho.com (Postfix) with ESMTP id 431B73EB1E; Wed, 2 Aug 2017 18:17:22 +0300 (EEST)
X-Virus-Scanned: Debian amavisd-new at pp.htv.fi
Received: from welho-smtp3.welho.com ([IPv6:::ffff:83.102.41.86]) by localhost (welho-filter4.welho.com [::ffff:83.102.41.26]) (amavisd-new, port 10024) with ESMTP id n79eGiFG0qQT; Wed, 2 Aug 2017 18:17:22 +0300 (EEST)
Received: from LK-Perkele-VII (87-92-19-27.bb.dnainternet.fi [87.92.19.27]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by welho-smtp3.welho.com (Postfix) with ESMTPSA id EB4822313; Wed, 2 Aug 2017 18:17:19 +0300 (EEST)
Date: Wed, 02 Aug 2017 18:17:19 +0300
From: Ilari Liusvaara <ilariliusvaara@welho.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Message-ID: <20170802151719.ebdnjxpqj443f4th@LK-Perkele-VII>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net> <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net> <20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII> <810C31990B57ED40B2062BA10D43FBF501B79953@XMB116CNC.rim.net>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B79953@XMB116CNC.rim.net>
User-Agent: NeoMutt/20170609 (1.8.3)
Sender: ilariliusvaara@welho.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/InBD-XecdjCwWRn2hrTr04UjbWk>
Subject: Re: [Cfrg] ECC mod 8^91+5
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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, 02 Aug 2017 15:17:26 -0000

On Wed, Aug 02, 2017 at 02:11:35PM +0000, Dan Brown wrote:
> Hi Ilari,
> 
> I did not know about the condition on uniqueness of a point of order
> 2.  So, I will try to better learn this important implementation
> issue.  If you happen to know off-hand a reference to the theorem
> you cited, then please let me know - but don't sweat it, I'll eventually
> find it (99% sure).

Safecurves says: "2006 Bernstein had shown a more limited form of
completeness for the Montgomery ladder on Montgomery curves y^2=x^3+Ax^2+x
with a unique point of order 2, i.e., with A^2-4 not a square.
Specifically, given X0(P) as input, the Montgomery ladder always produces
X0(nP) as output; here X0(P) means 0 if P=0, and otherwise the x-coordinate
of P. It is possible that ladders provide completeness for other curves,
but the analysis is not easy; the only literature is a second 2006 
Bernstein paper on this topic."

> I did not understand what you meant by the "worst problem" being a
> "notation" for low-order points.   (My only guess (1% sure) is that
> "notation" could be some kind of "exception"?)  Also, I'm assuming
> that "worst" is in some relative sense, since Curve25519 has low-order
> points.  Also, is your implied assertion that "a complete curve has
> low-order point" a theorem?  (I had mistakenly thought complete
> formulas for NIST had been found, albeit slower - maybe they were only
> unified, so my understanding of what "complete" means is off.)

If you can represent all points on the curve, you can also represent
the additive identity, which has order 1.

And being able to feed any low-order points (including point of order
1) into some ECC algorithms causes trouble.

E.g., if fed as key to Schnorr signature algorithm, the resulting
signatures have undesirable properties (which may be exploitable in
some applications that assume nonstandard properties from signatures).

> In my slides, I mentioned that the propose curve's cofactor (72)
> not being a power of 2 is problematic for easily generating signature
> ephemerals without bias. This has some known workarounds, but it is a
> serious issue.  Did you have something else in mind in saying that a
> subgroup of order 9 was problematic?

Well, the easiest way to generate signature ephremals on such groups
without bias is to include the factor of 9 into initial space.
This causes just some very minor slowdown.


Also, there is a fast check for low-order points on Edwards curves.
However, that check only works if cofactor is 4 or 8.




-Ilari