Subject: [Cfrg] Safecurves draft redux

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jan 2014 06:42:25 -0800

Dear all,
The email thread about the draft exploded and I had a lot of points to
respond to all over the place.

First off, I am including explicit formulas in the draft. It costs
nothing, and people seem to want it. I'm also explaining the benefits
of Montgomery form for x-coordinate only ECDH. I'll upload it as soon
as I'm happy with some editing I need to do.

The naming issue is fine: we can say "the safecurve Mxxx has been
found to be unsafe" without risk of being misunderstood. If there is
consensus that we should call the IANA registry something else, say
"Chicago curves", I'm not opposed to it.

But as for efficiency, pontification about what is fast and what isn't
will always be behind the drive of implementors to accelerate
everything. What seems like an awkward limb placement can be fixed by
some clever use of fractional radix arithmetic.

Lastly, just because a protocol suggests a form to go on the wire does
not mean that the calculations an implementation does need to resemble
it. Robert Ransom has made this point, and I agree with it. Good
standards specify observed behavior, not how it is attained.

As a metacomment: we shouldn't let our desire for "The Idiots Guide to
ECC" in RFC form get in the way of standardizing these curves. I don't
think our job is done with putting these curve formulas in an RFC, but
it does substantially help anyone who wants to use these curves in
another IETF protocol.

Sincerely,
Watson Ladd

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 9 Jan 2014 07:37:27 -0800

On Jan 9, 2014, at 6:42 AM, Watson Ladd <[email-masked]> wrote:

> found to be unsafe" without risk of being misunderstood.

Not at all. Having "safecurve Mxxx" be found unsafe will make many people think that all the other curves are unsafe.

The IETF has a long history of naming coming back to bite us in the butt. Please strongly consider getting rid of the "safecurve" name and just using the actual names that Dan an Tanja use.

--Paul Hoffman

---

From: Robert Ransom <[email-masked]>
Date: Thu, 9 Jan 2014 07:41:16 -0800

> some clever use of fractional radix arithmetic.

There is a limit to how much ‘fractional-radix arithmetic’ can help.
2^255 - k has a nice regular (vectorizable) pattern of 10 limbs ([26,
25]*5); no other pattern works as well.  2^414 - k can be split into
18 or 9 equal-size limbs, or a vectorizable pattern of 16 or 8 limbs.
None of the other curves' coordinate fields (with the possible
exception of M-221) have both a good arrangement of limbs and a
sufficiently small k to postpone carrying after multiplication until
after modular reduction.

> it. Robert Ransom has made this point, and I agree with it.

And I also made the exact opposite point: twist security is only
useful because implementations will be free to use Montgomery's ladder
formulas.

> Good

Good standards specify *both* the intended observable behaviour *and*
how to attain it.  The whole point of SafeCurves is to assist in
*implementing* ECC both safely and efficiently.

> it does substantially help anyone who wants to use these curves in

Shoveling this pile of curve equations into an I-D or RFC accomplishes
nothing.  What matters is specifying how to use curves of this class
in protocols, and that requires not only specifying point formats and
curve-operation formulas, but choosing the right set of point formats
to support in each case, and documenting how to assemble the primitive
curve operations into the exact procedures that the protocol requires.
 It's a matter of systems engineering, not mathematics or cryptography
alone.

Robert Ransom

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 09 Jan 2014 21:35:48 +0000

> found to be unsafe" without risk of being misunderstood.

I have to say, on reflection I'm definitely leaning more towards
calling the group of curves/IANA registry something else myself.

"SafeCurves" is the set of criteria and verifiable vetting process by
which djb and Tanja are trying to define safe curves to use: fair
enough, keep the reference under that name, they picked it.

As Bodo points out, it's _not_ really a collective name for the curves
that made it through that process. (Although it's tempting to use it
as one, there really isn't one.) As Jon and Paul and Johannes Merkle
and others have pointed out, if we did name the registry/RFC that,
we're risk looking a bit naïve (and dangerously misleading) at least
in a decade, or two, or whenever, when QC eventually bears fruit or
something similar happens.

If “SafeCurves” risks being confusing, we need another name. …I have
no idea. They're next-generation elliptic curves (NGEC?), now that
we've found better curve forms than short Weierstrass, but I think
"Next-Generation" always sounds a bit silly when it's the current one,
or especially when it's the previous one. We may just as well use a
catchy, arbitrary name… “Ellipsis”, maybe?

As far as the names of the individual curves: while a systematic
naming scheme is tempting, which is why I raised it, counterbalancing
that are that people are actually using these curves _right now_ in
the wild: adding new names for them might just serve to confuse
everyone. Not everyone's waiting for our informational RFC, after all:
people need fast strong crypto badly right now, the routines are
already available, and they're getting used. All we're really doing,
perhaps, is documenting it consistently as a starting point for their
adoption in internet standard protocols like TLS, DNSSEC, IPsec, PKIX
and so on.

So maybe just stick with the names their respective creators gave them
(dropping the caps and dashes as I suggested so command lines and
config files don't hate us forever): curve1174, curve25519, curve3617,
e511, m521, …

On 09/01/2014 09:27, Manuel Pégourié-Gonnard wrote:
> While at it, we should also document the requirements for private 
> keys, which are different from the way they are usually chosen for 
> short Weierstrass curves.

Good call.

On 09/01/2014 20:01, Paul Lambert wrote:
>> [draft doesn't specify encoding]
> Wrong answer — we need interoperability of public key 
> representation Since a key may be used in multiple applications.

As above, given they're already in-the-wild, and we're just
documenting them, I'm inclined to just say, use the representation
specified in the papers already in the wild, and implemented in the
software already in the wild. Done. Time for tea.

I note [draft-josefsson-tls-curve25519-02] goes with big-endian
instead of little-endian, essentially because TLS usually uses
big-endian for bignums. I'm probably going to go and comment against
that decision, because the paper and every implementation already out
there uses little-endian: in a sense, that decision's been made for us
(and big-endian lost the commonness fight some time ago)?

- -- 
/akr

---

From: Paul Lambert <[email-masked]>
Date: Thu, 9 Jan 2014 14:10:26 -0800

Hi Alyssa,

> that made it through that process. (Although it's tempting to use it as
> one, there really isn't one.) As Jon and Paul and Johannes Merkle and
> others have pointed out, if we did name the registry/RFC that, we're
> risk looking a bit naïve (and dangerously misleading) at least in a
> decade, or two, or whenever, when QC eventually bears fruit or
> If “SafeCurves” risks being confusing, we need another name. …I have no
> idea. They're next-generation elliptic curves (NGEC?), now that we've
> found better curve forms than short Weierstrass, but I think "Next-
> Generation" always sounds a bit silly when it's the current one, or
> especially when it's the previous one. We may just as well use a

Good points.
Perhaps if we look at the full collection of curves as a curve catalog,
we are simply adding two more classes of curves.

There would be some value in comparing the attributes of all curves if
we treat them as a full set versus old and new.

It also happens that the new curves are using Edwards and Montgomery
equations.  For an RFC for just these new curves we could just refer 
To these terms - "Edwards and Montgomery Curves for Elliptic Curve Cryptography"
or something similar ...

> As far as the names of the individual curves: while a systematic naming
> scheme is tempting, which is why I raised it, counterbalancing that are
> that people are actually using these curves _right now_ in the wild:
> adding new names for them might just serve to confuse everyone. Not
> everyone's waiting for our informational RFC, after all:
This need not be an issue if the new names are clearly distinguishable 
and mapped to the old names.  For example: 'secp256r1' is identical to
the later 'nistP521'

I suggest that we reuse a similar nomenclature.  It would make the new curves
look like equals in notation, provide a consistent nomenclature,
And the postfix 'r1', 'r2' notation is handy for new parameters or generator
points in the same curve/field.

Proposal:
 - first four characters define the curve type/equation/math/etc
 - next 3 or more numbers are the field size
 - next characters carry an 'r' followed by a revision indication

curve3617 -> edwp414r1

> > Wrong answer — we need interoperability of public key representation
> > Since a key may be used in multiple applications.
> 
> As above, given they're already in-the-wild, and we're just documenting
> them, I'm inclined to just say, use the representation specified in the
> papers already in the wild, and implemented in the software already in
> the wild. Done. Time for tea.
Better answer ... but the representation needs to be documented.

Paul
> 
> I note [draft-josefsson-tls-curve25519-02] goes with big-endian instead
> of little-endian, essentially because TLS usually uses big-endian for
> bignums. I'm probably going to go and comment against that decision,
> because the paper and every implementation already out there uses
> little-endian: in a sense, that decision's been made for us (and big-
> endian lost the commonness fight some time ago)?
> 
> - --
> /akr
> -----BEGIN PGP SIGNATURE-----
> 
> iQIcBAEBCgAGBQJSzxYzAAoJEOyEjtkWi2t6HfUP/iS0t44KYkNVJIooNhTOztZr
> 9SBPHXX7DSKzWyV5ZOZ4GtMJsPsRW74tyPZT1VniHG9ZQijdQVa59Kyadse0UKwM
> chv6Qq2atUq553VKNL7XGQdMjmPSRKuNjgPajynl7Aq096zp+2KZkObfHM/fJqAo
> l9BHym/ieTzZUJYt1n4AEPz3awEN0EYHZeQ4ABz+zHCguoRYO15UPbWWgWYz16An
> qXrr4Bsxs8cyioIDnVbnSWDrmfcMe2wAu/0flxgdBJMrrE5/vKmVCl2c16nBtyVx
> Ox41WcnY5ltj56x4a+q8ko7oSxjRlyV1PsUft+8PLYlpIzMFqE6WOAbd1Igvz+XM
> 3wPXKuSnMS6yKXryJh+ju1y+v1SERmOdRnxu5Mbu3HqoYbEmMW265AMqxTn/bDPK
> dKIzgXN+z6t3t6xeA04C3TN/wTKpMJeUL+zau+HFti4Yd5bfIy7YpfGc7moiUC4K
> RcPxBHS56ebYPNKEi9FncRDUts8OgT8nFsiUt+0MjN+Wz9vdgG5KB9tsDGhTBGnR
> tG2OYKU0FfIMnICfIoM4Goa0Vs3N8a11Scii0v6QCfABaGDH3f2Zc1AEbCYei1yT
> sByseeFB6SaSesOkOxWx1dTa4pI9LXmRYXPhhjkcKq8eF0zJNMsKb3a6NsCMZLwC
> cbtmmLqAzgIAassFudKN
> =Avz3
> -----END PGP SIGNATURE-----
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jan 2014 14:25:45 -0800

> To these terms - "Edwards and Montgomery Curves for Elliptic Curve Cryptography"

RTFD: It is titled simply "Additional Curves for IETF Protocols" and
has been since the beginning.
Safecurves is simply part of the filename with minimal semantic
import. I changed the registry name
in version 01.

Anyway, I'll upload a third revision sometime that addresses some of
the more substantive issues that have been
raised, such as a desire for canonical representations.

A lot of the issues that have been raised are readily resolvable with
additional drafts, should they be necessary, such
as a systemic catalog of all curves. If this really is the worst
problem you have with the draft, I think we're done.

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

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 9 Jan 2014 23:43:52 +0100

>  - next characters carry an 'r' followed by a revision indication

"r1" in SECG curves indicates that it's "random" curve number 1 (as opposed
to "k1", which would be a Koblitz curve).  Of course the new names don't
have to look anything like SECG curve names, but if they do, that very
different meaning for a very similar postfix could end up causing some
confusion.  So I think you might want to adjust the proposal to
give curve3617 a name of the form "...p414ed1" instead.

Bodo

---

From: Paul Lambert <[email-masked]>
Date: Thu, 9 Jan 2014 17:52:45 -0800

Hi Bodo,

>"r1" in SECG curves indicates that it's "random" curve number 1 (as opposed to "k1", which would
>be a Koblitz curve).

Thanks ... my mistake..  putting the 'type' and changing the 'r' meaning in the front was confusing

>Of course the new names don't have to look anything like SECG curve names,
Yes ...
>but if they do, that very different meaning for a very similar postfix could end up causing some
>confusion.  So I think you might want to adjust the proposal to give curve3617 a name of the
>form "...p414ed1" instead.

Much better.

I assume ... needs filling as origin of name space. Since we're on this list it could be:
   'cfrgp414ed1'
or just
  'p414ed1' or 'fp414ed1'

So far, a curve ontology -
  'r' -> Short Weierstrass (current usage always has a = p-3)
  'k' -> Koblitz (subclass of Short Weierstrass with optional optimizations)
  'ed' -> Edwards
I assume we need:
  'mo' -> Montgomery
   Others??

Brainpool curves specifically call out 't' for twisted versions of their random
Curves that are 'r' curves.  The twists have a=p-3 ... confusing when
comparing to SEC/NIST. The provenance of the numbers
seems less important the clearly identifying the curve type and applicable
math routines.

Paul

From: Bodo Moeller [mailto:[email-masked]]
Sent: Thursday, January 09, 2014 2:44 PM
To: Paul Lambert
Cc: [email-masked]
Subject: Re: [Cfrg] Safecurves draft

Paul Lambert <[email-masked]<mailto:[email-masked]>>:

Proposal:

curve3617 -> edwp414r1

"r1" in SECG curves indicates that it's "random" curve number 1 (as opposed to "k1", which would be a Koblitz curve).  Of course the new names don't have to look anything like SECG curve names, but if they do, that very different meaning for a very similar postfix could end up causing some confusion.  So I think you might want to adjust the proposal to give curve3617 a name of the form "...p414ed1" instead.

Bodo