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

From: Dan Brown <[email-masked]>
Date: Tue, 1 Aug 2017 21:22:10 +0000

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 went back and worked out some more details about this similarity (just some basic elliptic curve math).

To prepare, note that there exists a field element i in GF(8^91+5) with i^2=-1.

Putting x=iu and y=(-i/2)^(1/2)v defines a map to curve with equation v^2=u^3-u.  I believe (99% sure) that this map is an isomorphism (of GF(8^91+5)-rational points).  This equation has the same form as Miller's proposed equation y^2 = x^3 - ax, with a=1.

However, Miller does suggest that value a should not be a perfect square, which rules out a=1 above.  

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

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

So, the special curve 2y^2=x^3+x is isomorphic to a curve with an even more compact representation: y^2=x^3-x.  

Despite the more compact equation, the original form 2y^2=x^3+x is slightly preferable because it is already in the convenient Montgomery form, so I plan to use the original in the ID.   (But if somebody knows how to do the Montgomery ladder math equally as efficient on a Miller curve y^2=x^3-x, then I'm all ears :)

Best regards,

Dan

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Dan Brown
Sent: Tuesday, May 16, 2017 1:36 PM
To: [email-masked]
Subject: [Cfrg] ECC mod 8^91+5

Hi all,

I'm considering writing an I-D on doing ECC over the field of size
   8^91+5    (=2^273+5),
because it:
- is written in just 6 symbols (=low Kolmogorov complexity, heuristically minimizing threat of NOBUS-trapdoor),
- has easy and fast inversion, Legendre symbols, and square roots,
- has efficient arithmetic using at most five 64-bit words (use base 2^55),
- is at least 2^(256-epsilon),
- is (probably) prime, so not an extension field (has no subfields for descent-type attacks on ECDLP).
Other fields can improve on some of these properties, but might worsen the others.

For ECC with this field, I am also considering the special curve
   2y^2=x^3+x,
because it:
- is written in just 10 symbols (similar gains to 6-symbol field),
- has Montgomery form (and easily converts to Weierstrass),
- has efficient endomorphism (so it is a GLV curve),
- is similar to curves already suggested by Miller in 1985 (well-aged),
- is similar to sect256k1 already used in bitcoin (incentivized),
- has an small enough cofactor 72 (over field size 8^91+5),
- avoids the main ECDLP attacks: Pohlig-Hellman, Menezes-Okamoto-Vanstone, etc.,
- is similar to the special curves of Koblitz-Menezes [ia.cr/2008/390, Sec 11.1, Example 5] resisting a speculative attack.
The motivation for this special curve largely matches the motivation for the special field.

The curve's risks are at least:
- CM (endomorphism) makes it potentially weak (after 32 years of being safe) (note exactly opposing Koblitz-Menezes rationale),
- its small coefficients are weak for some unpublished reason (continuing trend of weak small-coefficients, y^2=x^3 (singular), supersingular, etc. being weak),
- weak twist order (so, it requires a static ECDH Montgomery ladder to use public key validation),
- weak Cheon resistance (but this is an attack with many queries, much computation, and faulty or no KDF).
- den Boer or Maurer-Wolf reductions are not tight as possible, so perhaps it has a big gap between DHP and DLP Other curves (over this field) can reduce these risks, but may also lose some of the benefits.

Overall, E(GF(8^91+5)):2y^2=x^3+x might offer competitive efficiency with fairly reasonable security (for 128-bit symmetric keys). It is only an incremental change over other standard ECC curves, not anything too radical.  

I'd be happy to hear what CFRG thinks, or if the CFRG would welcome such an I-D as a CFRG work item.  I hope to have this topic presented briefly at an upcoming CFRG meeting.

Best regards,

Dan Brown

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Thomas Garcia <[email-masked]>
Date: Wed, 2 Aug 2017 08:52:05 +0100

Hi Dan,
The transformation you proposed (x->iu, y->(-i/2)^(1/2)v) does indeed
define an isomorphism between the curve (2y^2=x^3+x) and the curve
(v^2=u^3-u), modulo p=8^91+5. As this transformation is defined over GF(p),
it preserves the group of points modulo p.

Thomas G.

On Tue, Aug 1, 2017 at 10:22 PM, Dan Brown <[email-masked]> wrote:

> 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.
>
> Putting x=iu and y=(-i/2)^(1/2)v defines a map to curve with equation
> v^2=u^3-u.  I believe (99% sure) that this map is an isomorphism (of
> GF(8^91+5)-rational points).  This equation has the same form as Miller's
> proposed equation y^2 = x^3 - ax, with a=1.
>
> 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)).
>
> 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).
>
> Despite the more compact equation, the original form 2y^2=x^3+x is
> slightly preferable because it is already in the convenient Montgomery
> form, so I plan to use the original in the ID.   (But if somebody knows how
> to do the Montgomery ladder math equally as efficient on a Miller curve
> y^2=x^3-x, then I'm all ears :)
>
> Best regards,
>
> Dan
>
> - is similar to the special curves of Koblitz-Menezes [ia.cr/2008/390,
> Sec 11.1, Example 5] resisting a speculative attack.
> - CM (endomorphism) makes it potentially weak (after 32 years of being
> safe) (note exactly opposing Koblitz-Menezes rationale),
> - its small coefficients are weak for some unpublished reason (continuing
> trend of weak small-coefficients, y^2=x^3 (singular), supersingular, etc.
> being weak),
> - den Boer or Maurer-Wolf reductions are not tight as possible, so perhaps
> it has a big gap between DHP and DLP Other curves (over this field) can
> reduce these risks, but may also lose some of the benefits.
>
> Overall, E(GF(8^91+5)):2y^2=x^3+x might offer competitive efficiency with
> fairly reasonable security (for 128-bit symmetric keys). It is only an
> incremental change over other standard ECC curves, not anything too radical.
>
> I'd be happy to hear what CFRG thinks, or if the CFRG would welcome such
> an I-D as a CFRG work item.  I hope to have this topic presented briefly at
> an upcoming CFRG meeting.
>
> Best regards,
>
> Dan Brown
>
>
>
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 2 Aug 2017 11:12:37 +0300

On Tue, Aug 01, 2017 at 09:22:10PM +0000, Dan Brown wrote:
> 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

---

From: Dan Brown <[email-masked]>
Date: Wed, 2 Aug 2017 14:11:35 +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 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:[email-masked]] On Behalf Of Ilari Liusvaara
Sent: Wednesday, August 2, 2017 4:13 AM
To: Dan Brown <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] ECC mod 8^91+5

On Tue, Aug 01, 2017 at 09:22:10PM +0000, Dan Brown wrote:
> 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.
> 
> 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

---

From: Dan Brown <[email-masked]>
Date: Wed, 2 Aug 2017 14:54:47 +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:[email-masked]] On Behalf Of Dan Brown
Sent: Wednesday, August 2, 2017 10:12 AM
To: Ilari Liusvaara <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] ECC mod 8^91+5

Hi Ilari,

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Ilari Liusvaara
Sent: Wednesday, August 2, 2017 4:13 AM
To: Dan Brown <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] ECC mod 8^91+5

 

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 2 Aug 2017 18:17:19 +0300

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Aug 2017 15:24:30 -0000

> that folded Montgomery ladder always works assumes that there is

The theorem in the Curve25519 paper assumed a unique point of order 2,
but this turned out to be unnecessary. See Theorem 4.5 in

   https://cr.yp.to/papers.html#montladder

and in particular the proofs of the underlying DBL and DADD theorems via
the Edwards addition law. The paper also gives proofs from the
historical Weierstrass perspective.

The completeness issue is more problematic outside the ladder context:

   * The fast complete Edwards formulas don't apply to this curve: the
     curve doesn't have a unique point of order 2.

   * The fast complete Hessian formulas also don't apply to this curve:
     the curve doesn't have a unique point of order 3.

   * The formulas from https://cr.yp.to/talks/2009.07.17/slides.pdf and
     https://eprint.iacr.org/2015/1060 do apply but don't meet the
     SafeCurves requirements of speed and simplicity ("implementations
     of scalar multiplication for the same curve cannot be much faster"
     and "reasonably fast implementations of scalar multiplication for
     the same curve cannot be much more concise"), so implementors are
     pressured to use incomplete formulas instead.

---Dan

---

From: Samuel Neves <[email-masked]>
Date: Wed, 2 Aug 2017 16:30:25 +0100

On Wed, Aug 2, 2017 at 3:11 PM, Dan Brown <[email-masked]> wrote:
> (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.)

These formulas do exist, cf. [1] or [2], but they require curves of
_odd_ order, which is not the case here.

[1] https://doi.org/10.1006/jnth.1995.1088
[2] https://eprint.iacr.org/2015/1060

Best regards,
Samuel Neves

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Aug 2017 16:00:15 -0000

> _odd_ order, which is not the case here.

The complete formulas from https://cr.yp.to/talks/2009.07.17/slides.pdf 
don't require odd order.

Fundamentally, incomplete implementations---and complete implementations
with timing leaks from branches between different incomplete formulas---
are not the result of complete formulas failing to exist. They are the
result of complete formulas failing to compete with the simplicity and
speed of incomplete formulas. This tension is what's nicely resolved by
Montgomery curves for DH, and by complete Edwards curves for more
general applications.

---Dan

---

From: Dan Brown <[email-masked]>
Date: Wed, 2 Aug 2017 16:04:42 +0000

Hi Dan,

Thanks so much for clarifying this!  

Sorry to all in CFRG that I am not up to speed on ECC implementation security and efficiency.

Just to be clear: this proposed special curve 2y^2=x^3+x (over GF(8^91+5)) is not intended to meet all SafeCurves requirements (as I remember them).  In particular and especially, (a) it is not twist-secure, and (b) it has a special feature of an efficient (complex) endomorphism.

Best regards,

Dan

Dumb question (on efficiency): For plain old Diffie--Hellman, is it right that Edwards form (8M per op) is only better than Montgomery (9M per bit) if a large window is used (to reduce ops/bit to something close to 1)?  If so, is this deemed simpler?  I guess where I'm going with this, is that Edwards form is very exciting from a research perspective, but maybe (0.000001% sure) it is not ready and ideal for engineering.  Again, I'm probably just totally missing something.

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of D. J. Bernstein
Sent: Wednesday, August 2, 2017 11:25 AM
To: [email-masked]
Subject: Re: [Cfrg] ECC mod 8^91+5

> that folded Montgomery ladder always works assumes that there is 

The theorem in the Curve25519 paper assumed a unique point of order 2, but this turned out to be unnecessary. See Theorem 4.5 in

and in particular the proofs of the underlying DBL and DADD theorems via the Edwards addition law. The paper also gives proofs from the historical Weierstrass perspective.

---Dan