Subject: Re: [Cfrg] Safecurves draft

From: Dan Brown <[email-masked]>
Date: Thu, 9 Jan 2014 03:11:45 +0000

I don't object to these curves.

Still, could we please call these curves something more specific and neutral than just "safe"?

Aren't many other curves safe so far as we know?

For example, take the Brainpool curves, use a Montgomery (Brier-Joye?) ladder, and an extra careful implementation, and do ECDHE, with some other kind of safe auth. Is that not safe?

Indeed, what about the NIST curves?

Implying them to be unsafe in the sense of a weak DLP implies a hypotheses that mildly reduces the conventional notion of security for all ECC.

Anyway, I debated all this already with Bernstein over at the TLS list, with virtually no  agreement confirmed. For now, I'll try to focus on the naming issue.

Is it that "safe" means something less than "secure" in the conventional sense above? And safe is the best that can be hoped for in ECC, and maybe all PKC? That's just too strong to say.

To be constructive, I suggest a name: "minimal - coefficient Montgomery" curves. Implicit in this name is that minimality is subject avoiding known DLP attacks, though the Monty should tip one of the crypto app. The short name could be "mini Monty".

From: Watson Ladd
Sent: Wednesday, January 8, 2014 12:11 PM
To: [email-masked]
Subject: [Cfrg] Safecurves draft

Dear all,
draft-ladd-safecurves contains the Safecurves with orders
2^255+\epsilon and higher.
I forgot to update the TOC, but that shouldn't stop the substantive
conversation.

Does anyone object to these curves being approved for IETF standard
body use/typos/general nastiness?
Sincerely,
Watson Ladd
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg
---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Adam Back <[email-masked]>
Date: Thu, 9 Jan 2014 10:47:31 +0100

Erm I guess Bernstein, Lange et al already got  to name the curves because
they *generated them*?

You could certainly put a descriptive sub-heading in an RFC.

They are actually significantly better designed in their security,
performance, and demonstrable non-cooked status and several other highly
implementation security related factors.  They are actually scientifically
better curves on multiple factors and they have made strong arguments to
prove it.  Safe is in fact a reasonable name.  Clearly its partly marketing,
but so what I dont see how a third party can go rename
*their* curves.

Adam

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 09 Jan 2014 13:15:30 +0100

> I don't object to these curves.

I also support the draft. Diversity in available EC parameters is important as a safeguard to potential future
improvements in cryptoanalysis. And I acknowledge that certain applications may require particular efficient ECC
implementations for which the Brainpool curves may not be eligible.

> Indeed, what about the NIST curves?

I share Dan's concerns with the naming as "safe curves". Not only is this name misleading w.r.t the potential security /
safety of other curves (well, for the NIST curves we simply don't know), but it may also turn out to be extremely
unfortunate in the (unlikely) event that the "safe curves" become vulnerable to a new (currently unforeseen) attack. In
this case, the name "safe curve" will turn out to be fatally misleading.

Johannes

---

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

Adam Back <[email-masked]>:

Clearly its partly marketing,
> but so what I dont see how a third party can go rename

Well, of course you *can*; the question is whether you *should*.  (For
example, NIST P-192 is also known as secp192r1 in Certicom's SECG
specification, and ANSI X9.62 calls it prime192v1.)

That said, http://safecurves.cr.yp.to/ doesn't appear to use "SafeCurves"
as part of the name of *curves*, but rather for selection criteria.  The
curves meeting all current criteria have names such as "Curve25519" or
"M-221", and the latter name isn't Dan's or Tanja's (because the curve is
from other researchers): if you want to include a "namespace indicator"
along with the curve name from the literature, it's not clear that all of
these should be bundled under the same prefix.

I certainly think "Curve25519" is sufficiently unique without a further
namespace prefix, to describe the curve as such in the cryptographic
context.  What we need to standardize is not just names for curves, but
also further details such as OIDs and clearly specified ways to encode
elements and keys -- names should denote that entire bundle, such that if
someone else encodes values for SafeCurves's Curve25519 differently, there
won't be confusion.  For example, note that the name "Curve25519" also
refers to a particular DH scheme *using* that curve, and "Ed25519" refers
to using the "EdDSA" scheme with an equivalent Edwards curve.  As far as
Safecurves is concerned, I don't think a distinction is made between the
two representations of the curve, but that distinction obviously is crucial
for interoperable implementations.  In that context, given that the name
"Curve25519" is already overloaded, and that we probably should make the
Edwards representation available for DH too (in addition to EdDSA), maybe
we *should* make up new name variants to avoid further possibilities for
confusion?

Bodo

---

From: Robert Ransom <[email-masked]>
Date: Thu, 9 Jan 2014 05:32:19 -0800

On 1/9/14, Bodo Moeller <[email-masked]> wrote:
> In that context, given that the name
> Edwards representation available for DH too (in addition to EdDSA),

No.  Montgomery-form variable-base single-scalar multiplication takes
5M+4S per scalar bit; Edwards-form doublings alone (in ‘extended
coordinates with a=-1’) are 4M+4S (or 3M+4S if the output will only be
used as input to another doubling).  There is no reason to use an
Edwards-form y coordinate in a Curve25519 point representation that
will be used for DH.  (But there's also no reason to use a
Montgomery-form y coordinate in a Curve25519 point representation;
even if the point will need to be compatible with use in ECDH, use the
Edwards-form x coordinate or its sign bit instead.)

(For some other curves over large (at least 8-limb) coordinate fields,
e.g. s=2170 over the Curve3617 coordinate field, the 3M+6S formulas
shown at <http://hyperelliptic.org/EFD/g1p/auto-edwards-yzsquared.html>
are faster, but Dr. Bernstein wouldn't consider those curves to be
‘safe’.  (The differential addition formulas on that page have an
exceptional case at Y1=0.))

Robert Ransom

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 9 Jan 2014 15:25:19 +0100

Robert Ransom <[email-masked]>:

> used as input to another doubling).

As pointed out by Section 6 in http://eprint.iacr.org/2007/286.pdf,
sliding-window multiplication using the Edwards form can be faster than
5M+4S per scalar bit for this curve (although that's probably no longer
true if you want a constant-time implementation -- while the non-sliding
window approach in Section 8 doesn't seem optimal because it's not making
use of signed windows, I don't think the extra savings are sufficient to
beat the Montgomery ladder).  More importantly, if you have a *fixed* base
(which is very relevant for ephemeral ECDH), with appropriate fixed
precomputation you won't need any double operations at all: so the total
time for one fixed-base single-scalar multiplication and one variable-base
signal-scalar multiplication as used in ECDH can be less than with the
Montgomery ladder, even if you want constant time with no secret-dependent
branches.  If you have severe space constraints, then an approach that
involves a few hundred precomputed points is not for you, but in many
typical scenarios this is not an issue at all.

So while the Montgomery-form Curve25519 certainly has its use, allowing
applications to negotiate a different form for ECDH would be beneficial.

Bodo

---

From: Robert Ransom <[email-masked]>
Date: Thu, 9 Jan 2014 06:34:13 -0800

> applications to negotiate a different form for ECDH would be beneficial.

Even if the party which generates a public key uses Edwards-form
points internally for that operation, whoever generates the key can
put it into Montgomery form for free before scaling, whereas whoever
receives it would need to perform an extra coordinate inversion in
order to convert from Edwards form to affine Montgomery form.  (Over
an implementation-friendly coordinate field, projective-base
Montgomery-form point multiplication is always slower than scaling
followed by affine-base Montgomery-form point multiplication.)

I really don't see any benefit to transmitting an Edwards-form point for ECDH.

Robert Ransom

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 9 Jan 2014 16:26:42 +0100

> order to convert from Edwards form to affine Montgomery form.

That's a good point.  As I've pointed out (or tried to point out, anyway),
the receiver might want to do the computations in Edwards form too, but
there's not that much to be gained from that, so it may not be worth the
extra complexity.

Bodo

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 9 Jan 2014 10:07:24 -0800

On Jan 9, 2014, at 7:26 AM, Bodo Moeller <[email-masked]> wrote:

> That's a good point.  As I've pointed out (or tried to point out, anyway), the receiver might want to do the computations in Edwards form too, but there's not that much to be gained from that, so it may not be worth the extra complexity.
> 
> Bodo

I agree.  The sender might well use Edwards internally -- it's about 3x faster -- but the point should be sent in Montgomery form.

I wonder, though, if the standard encoding of the spec should have the sign of the y-coordinate.  That way if we want to use the format for something other than ECDH -- signatures or PAKE or whatever -- we won't have to specify a new encoding.

An overly-complicated but cute solution is 1/sqrt(x) chosen with the same sign as y.  (x is always square if you're in the q-torsion; 1/x works just as well as x in the ladder; 1/x lets you encode the identity.)  But we probably don't actually want to spec that.  Maybe just a bit for sign(y)?

-- Mike

---

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jan 2014 10:10:54 -0800

On Thu, Jan 9, 2014 at 10:07 AM, Mike Hamburg <[email-masked]> wrote:
> I agree.  The sender might well use Edwards internally -- it's about 3x
> faster -- but the point should be sent in Montgomery form.
>
> I wonder, though, if the standard encoding of the spec should have the sign
> of the y-coordinate.  That way if we want to use the format for something
> other than ECDH -- signatures or PAKE or whatever -- we won't have to
> specify a new encoding.
>
> An overly-complicated but cute solution is 1/sqrt(x) chosen with the same
> sign as y.  (x is always square if you're in the q-torsion; 1/x works just
> as well as x in the ladder; 1/x lets you encode the identity.)  But we
> probably don't actually want to spec that.  Maybe just a bit for sign(y)?

This draft doesn't specify an encoding: it's up to whichever standard
uses this draft
to pick one.

Specifying an encoding of an x coordinate, or x coordinate plus sign
is easy enough.

You could upload a draft to specify it in more detail if you want.

I've uploaded a new version.

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

---

From: Jon Callas <[email-masked]>
Date: Thu, 9 Jan 2014 10:43:14 -0800

I concur that we shouldn't call it "safecurves" or anything like that. I think that definitely this needs to heed Paul Hoffman's advice on names coming back to bite us.

All crypto parameter sets have a lifespan where they're new and shiny, older and trusted, then kinda dodgy but accepted, and then outmoded or insecure. Each phase might be there for years or perhaps minutes. I've seen things go the entire lifecycle in an hour. We don't want the premature aging of one to tarnish the whole thing. Think about what you'd say when the Buzzfeed reporter calls you up for comment or background on their article "Ten Shocking Reasons Why SafeCurves are The Spawn of Satan" after a Eurocrypt paper has a new banana attack that shows a curve has ten fewer bits of security with 2^300 memory.

I also think there should be a quick set of names where we specify what's a Montgomery and what's Edwards. This is already needed and the reason why there's 25519 and Ed25519 in current parlance. If we *don't* do it here, then someone else will. It's too useful not to have it. 

You can have a table with common names and extended names and have the extended names have something simple like a suffix of M or E. It's easy to fit 25519 and Ed25519 into this as well.

	Jon

---

From: Paul Lambert <[email-masked]>
Date: Thu, 9 Jan 2014 11:56:12 -0800

+1 on a different name Š

Other comments:

1) Curve definitions really badly need clear parameterization.  Cutting
and pasting the referenced web site does provide all the right numbers,
but no context to implement. For the parameterization Š the curve math is
different so merging old and new in some fashion might make for
interesting comparison of the differences.

2) Is there any provenance on the generator selection for the curves?  I
hear critical comments on the NIST seeds, if we add new curves, should we
also document the process used for the selection of the Œarbitrary¹ values?

3) test vectors ..

Paul

On 1/9/14, 10:43 AM, "Jon Callas" <[email-masked]> wrote:

>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>I concur that we shouldn't call it "safecurves" or anything like that. I
>think that definitely this needs to heed Paul Hoffman's advice on names
>coming back to bite us.
>
>All crypto parameter sets have a lifespan where they're new and shiny,
>older and trusted, then kinda dodgy but accepted, and then outmoded or
>insecure. Each phase might be there for years or perhaps minutes. I've
>seen things go the entire lifecycle in an hour. We don't want the
>premature aging of one to tarnish the whole thing. Think about what you'd
>say when the Buzzfeed reporter calls you up for comment or background on
>their article "Ten Shocking Reasons Why SafeCurves are The Spawn of
>Satan" after a Eurocrypt paper has a new banana attack that shows a curve
>has ten fewer bits of security with 2^300 memory.
>
>I also think there should be a quick set of names where we specify what's
>a Montgomery and what's Edwards. This is already needed and the reason
>why there's 25519 and Ed25519 in current parlance. If we *don't* do it
>here, then someone else will. It's too useful not to have it.
>
>You can have a table with common names and extended names and have the
>extended names have something simple like a suffix of M or E. It's easy
>to fit 25519 and Ed25519 into this as well.
>
>	Jon
>
>
>
>
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: PGP Universal 3.2.0 (Build 1672)
>Charset: us-ascii
>
>wj8DBQFSzu3CsTedWZOD3gYRAvjQAJ9B7cbpze9iHhwEtb7V93IAuz2o3QCghrND
>YuOdLybBrq7s0mdSfKRcbK8=
>=uq7Y
>-----END PGP SIGNATURE-----

---

From: Paul Lambert <[email-masked]>
Date: Thu, 9 Jan 2014 12:01:15 -0800

>> faster -- but the point should be sent in Montgomery form.
Totally undefined in the draft.  Critical for interoperability.

>This draft doesn't specify an encoding: it's up to whichever standard
Wrong answer Š  we need interoperability of public key representation
Since a key may be used in multiple applications.

Paul

---

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jan 2014 12:46:08 -0800

> Totally undefined in the draft.  Critical for interoperability.

Whether or not Montgomery or Edwards form is used depends on what the protocol
is doing with the points. Montgomery form does not support addition,
but has advantages
in ECDH representations because it eliminates some validations without
point compression issues.

> Since a key may be used in multiple applications.

Most reasonable representations can be interconverted. However, there
are popular implementations
of these curves that make strange representation choices: a format
switch might not be popular if everyone
implementing a protocol wants to use NaCl.

Furthermore, some people (like me) want fixed length encodings sized
to cover the necessary range exactly, while
others like ASN.1 (for inexplicable reasons). The fewer choices we
make here, the faster this can get through. The new version explains
what
representations should do, while leaving it up to the end user
protocols to decide what makes sense.

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 9 Jan 2014 22:29:36 +0100

Watson Ladd <[email-masked]>:

> others like ASN.1 (for inexplicable reasons).

With ASN.1, you'd normally see a fixed-length OCTET STRING for this.  I
doubt that anyone seriously prefers variable-length encodings here.

> The fewer choices we
> make here, the faster this can get through.

What's gained, though?  The same decisions would have to be made, instead,
for each protocol that is going to use one of these curves.

Bodo

---

From: Robert Ransom <[email-masked]>
Date: Thu, 9 Jan 2014 18:42:57 -0800

> other than ECDH -- signatures or PAKE or whatever -- we won't have to

I've implemented some routines that generate and use Curve25519 keys
represented as the Montgomery-form x coordinate, with the high bit
used to transmit the sign bit of the Edwards-form x coordinate.

I would still recommend distinguishing the case where the party who
generated the key did not compute the sign bit from the case where
that party did compute the sign bit, and the sign bit was 0.  That
calls for two point formats (or three if anyone wants an uncompressed
point with the whole Edwards-form x coordinate).

Robert Ransom