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

Dan Brown <danibrown@blackberry.com> Wed, 02 August 2017 14:54 UTC

Return-Path: <danibrown@blackberry.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 BAE59132118 for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 07:54:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Level:
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 lB9aKR4BDNUs for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 07:54:51 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id ED2FA1319B4 for <cfrg@irtf.org>; Wed, 2 Aug 2017 07:54:50 -0700 (PDT)
Received: from xct108cnc.rim.net ([10.65.161.208]) by mhs210cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 02 Aug 2017 10:54:48 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT108CNC.rim.net ([fe80::8dc1:9551:6ed8:c618%17]) with mapi id 14.03.0319.002; Wed, 2 Aug 2017 10:54:48 -0400
From: Dan Brown <danibrown@blackberry.com>
To: Dan Brown <danibrown@blackberry.com>, Ilari Liusvaara <ilariliusvaara@welho.com>
CC: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] ECC mod 8^91+5
Thread-Index: AdLNjx77PpyZT1/ZSIWijHcZu9CKCQ9d+upAACBlnYAAA5l8wAABnPiQ
Date: Wed, 2 Aug 2017 14:54:47 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501B799D5@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net> <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net> <20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII> <810C31990B57ED40B2062BA10D43FBF501B79953@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B79953@XMB116CNC.rim.net>
Accept-Language: en-US, en-CA
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/q4fZMDvYWTQQ-6t_6erKyO5ObEE>
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 14:54:54 -0000

Based on Ilari's advice, I sought and found some exceptions (on the curve in question, or perhaps even any prime-field curve with 3 points of order 2) to the preferred differential addition formula:
https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#diffadd-mdadd-1987-m
Put {(X2:Z2),(X3:Z3)}={(1:1),(-1:1)}, which yields (X5:Z5)=(0:0) an EXCEPTION.  This seems to be only exception (25% sure), but is in line with Ilari's claim about exceptions.  (Also, I couldn't find any exceptions in the preferred doubling formula (25% sure).)
I'm not sure how exploitable this exception would be, however, so maybe I'm still missing something.  The two points have order 4, but differ by a point of order 2, so (X1:Z1) would have (10% sure) to be (0:1) or (i:1) or (-i:1).  This could be stopped by checking (X1:Z1) -- or perhaps (0.1% sure) just using it anyway, and safely leaking just a few bits of information about the private key.  


-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Dan Brown
Sent: Wednesday, August 2, 2017 10:12 AM
To: Ilari Liusvaara <ilariliusvaara@welho.com>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] ECC mod 8^91+5

Hi Ilari,

Thank you very much for taking a look at these important details: I've been focusing on other aspects.

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).

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.)

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?

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Ilari Liusvaara
Sent: Wednesday, August 2, 2017 4:13 AM
To: Dan Brown <danibrown@blackberry.com>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] ECC mod 8^91+5

On Tue, Aug 01, 2017 at 09:22:10PM +0000, Dan Brown wrote:
> Hi CFRG,
> 
> A minor addition to this topic.
> 
> In my first email on this topic, and in my recent IETF 99 
> presentation, I mentioned that the proposed special curve 2y^2=x^3+x 
> was similar to curves proposed in Miller's 1985 paper introducing of 
> ECC.
> 
> I believe (50% sure) that Miller made this non-square a recommendation 
> merely to help keep the group cofactor down (by ensuring a unique 
> point of order 2, namely (0,0)).

Unfortunately there is another related problem: The theorem that says that folded Montgomery ladder always works assumes that there is unique point of order 2.

So if using curve with multiple points of order 2, there may be exceptional cases. And getting those cases wrong might be exploitable.

And handling those cases without timing sidechannels might be very nasty to implement.
 
And sets of complete Montgomery and complete Edwards curves are very closely related, so this is probably not complete either as Edwards curve.

> By contrast 2y^2=x^3+x, has a subgroup of order 8.  (With points O, 
> (0,0), (i,0), (-i,0), (1,1), (1,-1), (-1,i), (-1,-i).)  A subgroup  of 
> order 4 (or 8) is nowadays considered (arguably) an advantage, because 
> of various Edwards curves (but I am only 10% sure, since I haven't 
> looked at this in a while, please correct me this is wrong).

It also seemingly has subgroup of order 9, which is considerably more problematic than subgroup of order 8.

There are some more exotic ECC algorithms that just can't deal with cofactor bigger than 1, but I think the worst problems that are attributed to cofactor >1 are actually caused by having a notation for low-order points. And any complete curve has at least one such point.

And then, not having notations for low-order points is annoying in implementing algorithms...


-Ilari

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg