Return-Path:
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 ; 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 ;
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 ; 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
To: Dan Brown , Ilari Liusvaara
CC: "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:
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
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-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 i=
n 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)}=3D{(1:1),(-1:1)}, which yields (X5:Z5)=3D(0:0) an EXC=
EPTION. This seems to be only exception (25% sure), but is in line with Il=
ari'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 poi=
nt 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) j=
ust using it anyway, and safely leaking just a few bits of information abou=
t the private key. =20
-----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
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 h=
appen to know off-hand a reference to the theorem you cited, then please le=
t 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 "notatio=
n" for low-order points. (My only guess (1% sure) is that "notation" coul=
d 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 impl=
ied assertion that "a complete curve has low-order point" a theorem? (I ha=
d mistakenly thought complete formulas for NIST had been found, albeit slow=
er - maybe they were only unified, so my understanding of what "complete" m=
eans 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 with=
out 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 pr=
oblematic?
-----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
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,
>=20
> A minor addition to this topic.
>=20
> In my first email on this topic, and in my recent IETF 99=20
> presentation, I mentioned that the proposed special curve 2y^2=3Dx^3+x=20
> was similar to curves proposed in Miller's 1985 paper introducing of=20
> ECC.
>=20
> I believe (50% sure) that Miller made this non-square a recommendation=20
> merely to help keep the group cofactor down (by ensuring a unique=20
> 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.
=20
And sets of complete Montgomery and complete Edwards curves are very closel=
y related, so this is probably not complete either as Edwards curve.
> By contrast 2y^2=3Dx^3+x, has a subgroup of order 8. (With points O,=20
> (0,0), (i,0), (-i,0), (1,1), (1,-1), (-1,i), (-1,-i).) A subgroup of=20
> order 4 (or 8) is nowadays considered (arguably) an advantage, because=20
> of various Edwards curves (but I am only 10% sure, since I haven't=20
> looked at this in a while, please correct me this is wrong).
It also seemingly has subgroup of order 9, which is considerably more probl=
ematic than subgroup of order 8.
There are some more exotic ECC algorithms that just can't deal with cofacto=
r bigger than 1, but I think the worst problems that are attributed to cofa=
ctor >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 implemen=
ting 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