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 759B512008A
for ; Wed, 2 Aug 2017 07:11:41 -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 zQaQLv-CKoip for ;
Wed, 2 Aug 2017 07:11:40 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89])
(using TLSv1.2 with cipher RC4-SHA (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id C7A1E126C83
for ; Wed, 2 Aug 2017 07:11:39 -0700 (PDT)
Received: from smtp-pop.rim.net (HELO XCT103CNC.rim.net) ([10.65.161.203])
by mhs215cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA;
02 Aug 2017 10:11:37 -0400
Received: from XCT116CNC.rim.net (10.65.161.216) by XCT103CNC.rim.net
(10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.319.2; Wed, 2 Aug
2017 10:11:37 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by
XCT116CNC.rim.net ([::1]) with mapi id 14.03.0319.002; Wed, 2 Aug 2017
10:11:36 -0400
From: Dan Brown
To: Ilari Liusvaara
CC: "cfrg@irtf.org"
Thread-Topic: [Cfrg] ECC mod 8^91+5
Thread-Index: AdLNjx77PpyZT1/ZSIWijHcZu9CKCQ9d+upAACBlnYAAA5l8wA==
Date: Wed, 2 Aug 2017 14:11:35 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501B79953@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net>
<810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
<20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII>
In-Reply-To: <20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII>
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:11:41 -0000
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