Subject: [Cfrg] Chopping out curves

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 13:40:37 -0800

Dear all,
Trevor Perrin suggests that we only put in Curve25519/T25519 and
E383/M382 so implementors can focus on 4 curves ala Suite B. Are there
any protocols in which larger curves would be useful? Anything we
might be missing with this decision?

This doesn't really affect the rest of the text at all, and I will
hold off until I hear what other people have to say about this.
Sincerely,
Watson Ladd

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 16 Jan 2014 13:50:12 -0800

> might be missing with this decision?

I didn't quite suggest that.

I do feel there should be fewer curves.  Perhaps only curve25519 and
(either Curve3617 or Ed448-Goldilocks).

It takes a great deal of effort to do high-speed, const-time
implementations of a different curve, so we should not diffuse that
effort across too many choices.

Note that Suite B only has 2 curves (P-256 and P-384).

Trevor

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 16 Jan 2014 13:53:51 -0800

> Note that Suite B only has 2 curves (P-256 and P-384).

Yeah, I was going to protest: instead of using one stronger Montgomery curve and one Edwards, maybe we should use a Montgomery curve and a birationally equivalent (or at least isogenous) Edwards curve, or vice-versa.

— Mike

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 16 Jan 2014 14:07:49 -0800 (PST)

> Note that Suite B only has 2 curves (P-256 and P-384).

  I think this is a good idea. Too much choice can lead to confusion
and lack of interoperability. When the brainpool curves were added
we pared it down from 14 (including twisted variants) to 4.

  Suite B has 2 curves because it defines two security levels. We can
define more security levels if needed but we should probably only
have 1 Chicago curve at each level.

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 14:36:24 -0800

> have 1 Chicago curve at each level.

So the question is which. I think curve25519 and Ed448-Goldilocks make
sense, together with an
isogenous curve for signatures since Montgomery curves are a bit odd
from that perspective. Does anyone see a need
for more security levels then that/are these choices terrible for
reasons we haven't appreciated?

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 16 Jan 2014 14:53:42 -0800

Hey Watson,

Let’s maybe let this sit for a couple of days before declaring the matter settled.  I mean, as the author of Goldilocks, I’d love to see it become the one stronger curve that gets adopted.  But Trevor proposed chopping curves literally one hour ago, and Goldilocks has been on Safecurves for less than a week and isn’t even completely implemented.  I don’t want it to be railroaded into being the one curve in a new RFC, even if just for a couple git revisions.

Defense for why it’s a good curve, though:
* Cofactor 4 is minimal for Edwards.  It could just as easily be a Montgomery curve; Ed vs Mont was mostly an arbitrary choice.
* 448 is a round number (although this can hurt us in point encoding, depending on the options)
* 448 is about the largest bitsize which can fit into a 16-limb reduced-radix multiplier on a 32-bit arch without carry problems.
* 2^448-2^224-1 is Karatsuba multiplier friendly.
* Solinas primes are fast.  Field mul comparable to about 2 muls over 2^255-19 on Intel.

Downsides:
* If you don’t like “special” primes, then you surely won’t like a Solinas trinomial prime.
* If the point encoding is as spec’d, it’s one bit too long.

Cheers,
— Mike

On Jan 16, 2014, at 2:36 PM, Watson Ladd <[email-masked]> wrote:

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

---

From: Adam Back <[email-masked]>
Date: Fri, 17 Jan 2014 02:14:14 +0100

Woulnt it make more sense to use two safe curve curves as they seem to be
what people are using and better tested/reviewed (re goldilocks).

Adam

---

From: Adam Back <[email-masked]>
Date: Fri, 17 Jan 2014 03:36:29 +0100

Uh I meant the Curve25519 and Curve3617.  Sorry about that (again conflating
safe curves and the Bernstein/Lange curves by the same authors.)

Adam

---

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 18:47:19 -0800

> safe curves and the Bernstein/Lange curves by the same authors.)

It would, but Curve25519 is a Montgomery curve and so we want an
Edwards curve for easy signatures.
T25519 should be the same curve, in a different form (if I didn't
screw up my basepoint choice, which I probably did. This weekend I
will do
a good computer search). Curve3617 has a nice Montgomery curve we
should describe for safe ECDH.

I feel like I'm coming around to Robert Ransoms arguments about how to
pick curves.

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 17 Jan 2014 07:41:53 +0000

On 17/01/2014 02:36, Adam Back wrote:

> Uh I meant the Curve25519 and Curve3617.

We have three key sizes for AES, and three hash sizes with SHA-2 and
SHA-3 (and the candidates).

I propose:
• curve25519 (plus twist t25519)
• curve3617
• e521

That gives us three curves with strength roughly congruent to the 128,
192 and 256 key sizes, and about as good performance as we're going to
get for those levels.

curve25519 is likely to be used for high-performance ECDH; its twist
is likely to be used for high-performance encryption and signing.

curve3617 seems likely to be used for higher-assurance encryption and
signing (Silent Circle intends to use it, for one).

e521 is slower, but very conservative - maybe you'd want to use it for
very careful signatures or encryption; the prime field is of course a
well-known Mersenne prime people are already used to (thanks to
secp521r1), and it's so rigid, three people came up with the
parameters independently.

I wouldn't cry a river if we dropped e521 from that list.

Those are, I think, the two or three that applications are most likely
to actually want to use in practice.

Regarding the t25519 basepoint, the argument for using the ed25519
basepoint is that it's already out there and thus already rigid, but
yes, it is ugly.

If you do choose a new basepoint, Watson (and I can see the sense in
that), please rigidly document the choice criteria so the decision can
be independently verified and confirmed (minimal y, right?).

I haven't had my first cup of tea yet today, so I apologise if I'm
wrong, but I believe any new basepoint would need to go through the
SafeCurve verification tests again, because ℓ would change? - run it
yourself for sanity checking, and please post the source files on the
list so we can use Sage or something to verify it too, but please also
speak to Tanja and djb about that to get wider verification.

- -- 
/akr

---

From: David McGrew <[email-masked]>
Date: Fri, 17 Jan 2014 07:40:50 -0500

Hi Michael, and Watson,

> Let’s maybe let this sit for a couple of days before declaring the matter settled.  I mean, as the author of Goldilocks, I’d love to see it become the one stronger curve that gets adopted.  But Tre…

I agree that people need more time to understand and think about the 
issues.  Let me suggest an approach:

- add a placeholder section to the draft stating that "This draft 
identifies one curve at each important security level, in order to 
promote interoperability.   These curves will be described in a future 
version of this draft.  Feedback should be directed to the authors and 
to [email-masked]."

- in the draft, outline the pros and cons for each curve type (this 
could be as simple as Michael's text in this email)

- collect feedback from reviewers and implementers during the lifetime 
of the draft

- before RFC publication, choose the curves and fill in the section.   
Leave all the text about the curves that were chosen, and move the text 
about the other curves either to an appendix or to the rationale.   Edit 
the rationale section so that it explains why the particular curves were 
chosen as mandatory-to-implement, and why the others were not.

This approach would make sure that the draft gets a broad review, which 
is really important, and it allows us to postpone making choices that 
might limit the solution space that gets considered. Our goal should be 
to create a well-considered RFC that provides value for the broadest 
possible community.

regards,

David

> .

---

From: Adam Back <[email-masked]>
Date: Fri, 17 Jan 2014 13:41:59 +0100

I'm not sure if we should be going as far as generating new curves, or
significantly tweaking choices in the existing curves in incompatible ways
(eg new generators), I thought original idea was more to provide in RFC
format the best rigid/NUMs curves available that people are already starting
to use so they at least have a reference.

Generating new curves or significantly deviating from them or their exiting
parameter choices, creates our own NUMs risk, and a restart on the review
process, creates something that needs to have its own (maybe derivative)
name, and places CFRG in the biased editorial position of both generating &
selecting...

Adam

On Fri, Jan 17, 2014 at 07:41:53AM +0000, Alyssa Rowan wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA512
>
>-----BEGIN PGP SIGNATURE-----
>
>iQIcBAEBCgAGBQJS2N7AAAoJEOyEjtkWi2t6OaUQAIyZsJdPlguckuHKMY+UdCJN
>YEaRx4MXQ5BrBH2Z8HrMdrY+4mmNqogI23MzAUYjE5/TdKcQvfOYDtpW7D6ooKAx
>K+SFj553BmE6By4F3woZ/5bsRH3oifnFaT7g6OMRijGpkaN//AWIx8PdMU3LbrrB
>tXHG2ciEmlKr5rdve8EhA3c9dUZo3XE2qltiWplaK5kObskl+bpXibm0JmajMVzl
>DLi0b5lzh3l7JZVqL0gR1Nk/swd5PSXqgET2k7NhBfrP0+NbJ7niGYUFT1gVtxVz
>2Qg0aDusvlRTeFeVCxUiZV7oDQg1+JbaMxTUg6gAP6HuUCnuzy2A6D+0Dt9qajX2
>UvHezZawZhC8PL2XPIgjXhTVCiUCz6oexy1V2OCKFO+ZIGcvypIMT6N5WbVZVzIb
>G4YNv+IrUEFnfssfkueXr4huBat4gZ2HXArG4hWd/85EOvxbTng4tAkShSRJl5bS
>cYaej5Tlz5WC4evzZC+VvnHeyzVInPn9AFJdkKjQeuPgXaANeluI9SdpFW5hY3w4
>o6wmLDdnX2lxVeq8rY0pz0aXvxTm/IFpn7SlVs7RZU0upmuCzquKfAUgcjcaYaj0
>JkLPu8Iq/aSpfIF4foC7jNJn43yNN76rqpxUjXICQosbg3ybqZTzs+ppjB10SPOr
>n8JoVsmG08Boh8FpVHo2
>=8vwB
>-----END PGP SIGNATURE-----

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 17 Jan 2014 14:03:31 +0000

>name, and places CFRG in the biased editorial position of both
There are arguments in favour of both the existing or a new basepoint for t25519 (which is what I'll call the twisted Edwards representation of Curve25519 used in Ed25519, as I'm not sure it actually has a name of its own?).

Keeping the same basepoint for t25519:
• Preexisting
  - No confusion about where it came from
  - Routines already out there
  - We should perhaps focus on documenting what's in use
• Clear link to Curve25519; conversion?

Generating a new basepoint for t25519:
• Elegant; we can select minimum y that satisfies SafeCurves criteria
  - What advantage, really, would that give in implementation?
  - Is it worth any perceived benefit?
  - Absolute rigidity would be critical to avoid potential manipulation concerns
• Conversion... problematic
  - Is that actually a disadvantage?
  - Goes back to the "dual use key" question, I suppose...
• Reverification necessary, I think.
  - New basepoint → new prime order → new primality tests for SafeCurve script? (Damn. They're the expensive part.)
  - Independence: would have to ask Tanja & djb to double-check our results externally
  - Would probably cause extra delay

Anyone's clearly free to do so. Whether we *want* to do it is another question.

On balance I have to say, I think I prefer keeping the basepoint Ed25519 already uses for t25519, but it's not a strong preference. If we do change it, we do need to dot the i's and cross the t's, so to speak.

- --
/akr

---

From: Robert Ransom <[email-masked]>
Date: Fri, 17 Jan 2014 06:33:24 -0800

On 1/17/14, Alyssa Rowan <[email-masked]> wrote:

> There are arguments in favour of both the existing or a new basepoint for
> t25519 (which is what I'll call the twisted Edwards representation of
> Curve25519 used in Ed25519, as I'm not sure it actually has a name of its
> own?).

The curve specified as ‘T25519’ (a=121666, d=121665) in
draft-ladd-safecurves-03 is something that Watson Ladd made up.  The
Ed25519 signature scheme paper
(<http://ed25519.cr.yp.to/ed25519-20110926.pdf>) specifies the a=-1
form (a=-1, d=-121665/121666).

>   - Absolute rigidity would be critical to avoid potential manipulation

Watson Ladd actually chose a point with small Edwards-form x, not
small Edwards-form y.

There is no benefit to choosing a new basepoint, but there's also no
benefit to using ‘T25519’ instead of the (more efficient) form
specified for Ed25519.

As you point out, using a different basepoint does prevent use of keys
in different protocols, even when the protocols are designed to be
safe to use with the same key material, so that's a real (and
unnecessary) cost.

>   - New basepoint → new prime order → new primality tests for SafeCurve
> script? (Damn. They're the expensive part.)

‘T25519’ is isomorphic to Curve25519, so any non-identity group
element of odd order on T25519 generates the same group as the
standard basepoint of Curve25519 (and has the same order).

> On balance I have to say, I think I prefer keeping the basepoint Ed25519
> already uses for t25519, but it's not a strong preference. If we do change
> it, we do need to dot the i's and cross the t's, so to speak.

I have a strong preference for throwing out T25519 and using Ed25519
with its standard basepoint.

Robert Ransom

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Jan 2014 07:17:45 -0800

> form (a=-1, d=-121665/121666).

Actually the curve is from the 2009 Twisted Edwards paper of Lange and
Bernstein.
On reflection the a=-1, d=-121665/121666 form saves an an addition,
but the multiplication
is by a bigger number in the complete form. Anyway, I don't have
strong thoughts on the matter.
>>   - Absolute rigidity would be critical to avoid potential manipulation

All points in [q] have random self reducible DDH problem. The only

> with its standard basepoint.

I'll follow that preference, but ugh, the number in front of x^2y^2 is big.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 17 Jan 2014 19:12:37 +0100

> • curve25519 (plus twist t25519)
I second that (replacing t25519 with Ed25519 as discussed in the follow-ups).

Manuel.

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 17 Jan 2014 18:58:12 +0000

On 17/01/2014 14:33, Robert Ransom wrote:
> small Edwards-form y. […] ‘T25519’ is isomorphic to Curve25519, so 
> any non-identity group element of odd order on T25519 generates the
> same group as the standard basepoint of Curve25519 (and has the 
> same order).

Ah, thankyou. I missed that (and had mistakenly assumed he'd go for
small y to match the Edwards curves).

Clearly, I haven't had enough tea today!

On 17/01/2014 14:33, Robert Ransom wrote:
> There is no benefit to choosing a new basepoint, but there's also 
> no benefit to using ‘T25519’ instead of the (more efficient) form 
> specified for Ed25519.

On 17/01/2014 15:17, Watson Ladd wrote:
> On reflection the a=-1, d=-121665/121666 form saves an an
> addition, but the multiplication is by a bigger number in the
> complete form. Anyway, I don't have strong thoughts on the matter.

Well then, there's little or no benefit in specifying a new form when
we already have the Ed25519 parameters ready-made and people already
have routines working with it?

On 17/01/2014 14:33, Robert Ransom wrote:
>> I have a strong preference for throwing out T25519 and using 
>> Ed25519 with its standard basepoint.

> I'll follow that preference, but ugh, the number in front of

If it doesn't really have a performance impact in practice, it's no
big deal.

Ed25519 it seems to be, then. Though, that said, the name might be
confusing. Maybe we'd better call that form something else.

Perhaps: 'te25519', for Twisted Edwards (2^255)-19?

(Deliberately referring to the curve names in lower-case. Thinking
ahead to when people put these things on command-lines or config files
and argue about capitalisation; none of the other curves in IETF
protocols get capitals.)

• If we called it 't25519', people might confuse it with the one in the
  draft here.

• But if we call it 'Ed25519', people might confuse it with the whole
  Ed25519 signature scheme.

  (Sure it's used _in_ that signature scheme, although it seems likely
  to me at this stage that we might be heading more in the general
  direction of a cleaner, fresher version which works with te25519,
  curve3617 and e521, and quite possibly uses a new hash. Demand seems
  stronger for curve25519 ECDHE first, however.)

- -- 
/akr

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Jan 2014 11:01:19 -0800

> Perhaps: 'te25519', for Twisted Edwards (2^255)-19?

Okay. I'll follow the Ed25519 paper and call it te25519 and add the
paper as a reference.
Are rationals fine, or do people want me to write big numbers?
> • If we called it 't25519', people might confuse it with the one in the

it's an ID: names change.

> iQIcBAEBCgAGBQJS2X1EAAoJEOyEjtkWi2t6tR0QALl42L1yV84EFgckps6R2rOe
> 30UOcOWx1XZGnU/Kdwt0w7YP8SvUbAtX97RgVlcgWQbG9CyYldELJ/39lZw7uyFF
> iNyNmIGYvXdrlxpWTNMry0lB8SLjZts+RJX0/ZcDD0qguGnmsP+IHUH7Q80hsjJ0
> CB9rvVVfuuAmDU5pWWOWHt8hEVhX9jl7vRuF4Yb51ngqHrS/NpasK2qaZ88Gw4Fp
> ns/b8OzZNoChxkAHYBlGVrkuCq6O9d8gpRaoxkl0ujsndvsZlQ2ud0FhVg/FXcRs
> le6YCig5rEuEoS/XwGUc4Mb6Py2BRJZ4C0Ax6ZTP1pOzH8OhwKskuEeLe7SVvKGu
> WhC5hgGz/Sub1nKBI/mTZNwZrY5kjEzg21iZ1kIbpK37V59TwplLOJzu/aalXDbU
> Sq0U1aW73Y6p+KSQKsGpSfeUpmY/6e19emoUQRbZ9J1eER/o2vjPAJcCmv+zfugx
> uE2moiZoc1mfCV5E7wIxZvUrU5bPk4ARSzHxhw7o/higqc/PZbtosFKEqeRBOz1I
> paqlewTRs7tQTwoSx9mn3+dln47Kz2y18pBAUM7BitUyWghMoJRq6Mm6crKkGG2O
> f2ZAkmKDlpEuLix9/ENlmGDl2i9ZXH7tALnOeYZ/txlFtagpUBSdLWSBGo0erEwp
> Q0AWcvz2wr81lOwpPuBq
> =w0/6

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 17 Jan 2014 19:13:45 +0000

> Are rationals fine, or do people want me to write big numbers?

I'd vote for both.  Removes a possible source of implementation error
and provides the implementer with an easy check the values were entered
properly.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 17 Jan 2014 20:17:37 +0100

> Are rationals fine, or do people want me to write big numbers?

I'm sorry, but I'd prefer big numbers (or best, both). Of course it's more work
for you, but it's less for the readers. And since the document will hopefully be
read more often than it is written... :)

>>   Ed25519 signature scheme.
With all the respect I have for the great work done by Bernstein on this, I find
it unfortunate that the same name is used for a curve, a particular protocol
using this curve (and often even "the" implementation), causing some confusion.
I'll be really glad if the I{R,E}TF encourages more distinct names for curves
and protocols (and of course, many distinct interoperable implementations as usual).

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Jan 2014 11:23:30 -0800

> read more often than it is written... :)

Blegh. This is going to be one ugly looking equation. 4/5 and
-121665/121666 I can memorize.
Can't do the same with giant numbers. Okay, time to fire up PARI and
make the changes.

> using this curve (and often even "the" implementation), causing some confusion.

I'm not sure this is correct. Bernstein's implementation today is the
donna implementation,
and tweetnacl has tweetnacl implementation of cuve25519. It's no worse
than BLAS, where
ATLAS, gotoBLAS, netlib BLAS, and Intel all provide implementations of BLAS.

> and protocols (and of course, many distinct interoperable implementations as usual).

ECDH on curve XXXX seems to be what people do when disambiguation is required.

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 17 Jan 2014 14:05:39 -0800

By the way, folks, are any of these curves actually implemented (in C/C++, not python) besides the 25519 ones?

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 17 Jan 2014 23:31:36 +0100

> not python) besides the 25519 ones?
According to http://eprint.iacr.org/2013/647

    A proof-of-concept implementation of all these curves is available
    as part of the RELIC library [1]. Work on a production-quality
    implementation is ongoing.

    [1] D. F. Aranha and C. P. L. Gouvêa. RELIC is an Efficient LIbrary
    for Cryptography.

I have a "generic" implementation of Montgomery curves in PolarSSL that
currently offers only Curve25519 but the other curves in Montgomery
forms can be added easily. I also plan to implement curves in Edwards
form there some day (hopefully soon).

Manuel.

---

From: Jon Callas <[email-masked]>
Date: Tue, 21 Jan 2014 18:49:16 -0800

> safe curves and the Bernstein/Lange curves by the same authors.)

For what it's worth, I'm using Curve414-19 (fka Curve3617) and it would be nice to have it in standards. Not having it in standards isn't going to make me change.

	Jon