Subject: [Cfrg] Fwd: Re: Safecurves draft

From: Alyssa Rowan <[email-masked]>
Date: Thu, 09 Jan 2014 08:12:36 +0000

On 08/01/2014 23:50, Watson Ladd wrote:

> I don't want to rename curves because that induces consistency 
> issues.

Entirely accepted: I raised it merely as a question. People are
already beginning to adopt these curves of their own volition, so
changing the names of them could be confusing, yes.

As other have raised, putting the ladders in the appendix would
definitely be a good idea, and we need to explain the criteria under
which they were designed, which is what makes them so useful.

And yes, we should definitely get some OIDs. (However you actually
_do_ that. I've no idea.)

On 09/01/2014 01:32, Paul Lambert wrote:

> Comment: -too terse

It's an early draft. There's some fleshing-out still to go.

> - no clear mapping of numbers to variables - no documentation of 
> Edwards point addition Which is different from durrent ECC drafts

See above. Agreed.

> - no indication of security concerns and need or lack of checking 
> public key values

Important advantages. We should cover this, I think.

> Here¹s how I¹d document curve parameters: […python…]

> PS - above parameters are directly executable Python code Why use 
> pseudo code when you can use real code :-)

Advantage: People can copy-and-paste it into their implementations.
Disadvantage: People will copy-and-paste it into their implementations.

I honestly don't know which practice is preferable.

Naïve Python implementations directly using the bignums rather than
the good addition ladders probably wouldn't be constant-time - would they?

On 09/01/2014 03:11, Dan Brown wrote:

> I don't object to these curves.

Cool.

> […several objections to the name ‘safe’, implying other curves 
> aren’t, raising the NIST curves…]

As the SafeCurves criteria clearly explains:

• Their design criteria are transparent, and rigid, with few
  opportunities for an attacker to secretly select cryptanalytically-
  useful choices¹.

• They support simple, fast, complete, constant-time single-coordinate
  single-scalar and multi-scalar multiplication techniques which work
  in every case.

• These can be implemented using relatively-simple (compared to short
  Weierstrass) ladders which are both constant-time, and extremely
  efficent.

• They have large complex-multiplication field discriminants; are safe
  against additive and multiplicative transfer; and have secure twists.

Compared to the curves we've got at the moment (most of which don't
even have clearly-explained design criteria, and the ones that do are
unfortunately inefficient), the choice of name seems entirely apt to me.

Besides, it's what they're already widely known and referenced as:
people are already in the process of implementing these. As above,
changing it probably wouldn't be helpful and would just confuse people.

___
1. Contrast, say, the NIST/SEC curves generated by Certicom, whose
   design criteria are what I can only describe as “opaque” —
   mysterious black-box values which SHA-1 hash out to “provably
   random” parameters, but which are not in fact random themselves:
   the design team minted those values via repeated iteration to
   deliberately and secretly ensure they would meet some set of
   criteria (and then even listed the prime order in decimal to
   disguise the structure).

  (Sources are under the impression that was actually a set of
   criteria to ensure the curves would be efficiently implemented via
   Certicom-patented methods, but unfortunately, cannot state for sure
   that the criteria didn't also include cryptanalytically-useful
   weaknesses, and of course, that's what people are worried about,
   given the news. They didn't actually _see_ any attempt to actually
   weaken the NIST curves, they can at least say that much — phew —
   but that's little help in positively assuring it didn't happen.)

   These have no such concern.

- -- 
/akr

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 09 Jan 2014 10:27:46 +0100

> changing the names of them could be confusing, yes.
About names, I'd really like the names to reflect the type of the curve
(Montgomery or Edwards). This is already the case for other curve families, by
the way. So, Mxxx and Exxx seem great to me. I'd even go so far as to rename
Curve25519 as M255, but I'm sure there are good reasons to disagree on this point.

While at it, I also think the document should define the curves for each type in
distinct sections. Overall, the goal is that it should be easy for other
document to define the of just the Montgomery (or just the Edwards) curves for
use in a protocol, and refer to the appropriate section of this draft.

> Important advantages. We should cover this, I think.
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.

> [...]
I think this kind of thing should go in the draft :)

> unfortunately inefficient), the choice of name seems entirely apt to me.
I tend to disagree on this point. Don't take me wrong, I think these curves are
a useful tool in making security better, for all of the reasons mentioned above.
However, they're not some kind of magic security pill either, and IMO it would
be bad for security to give this impression. This goes both sides:
- people shouldn't think any implementation of the "safe" Montgomery/Edwards
curves is automatically flawless;
- people shouldn't think the NIST/Brainpool curves are so impossibly hard to
implement right that they don't even try.

Take the points list on the frontpage of the safecurves site, for instance
(numbered by me for convenience).

1. Your implementation produces incorrect results for some rare curve points.
2. Your implementation leaks secret data when the input isn't a curve point.
3. Your implementation leaks secret data through branch timing.
4. Your implementation leaks secret data through cache timing.

Point 3 and 4 are entirely a property of the implementation, not of the curve.
Point 2 can (and must) be addressed by telling everyone to validate points. I
mean, the idea of validating inputs shouldn't be new to anyone implementing
crypto! About point 1, it probably depends on the reference used, but Hankerson
& al's "Guide to ECC", which looks like a classic to me, gives formulas that are
correct in all cases (but have data-dependant branches). Besides, this problem
can be completely avoided by using a well-chosen multiplication algorithm,
ensuring that the special cases will never be hit.

Overall, of course it's nice that issues 1 and 2 are completely annihilated by
Montgomery and Edwards curves, and to be fair point 4 is a bit easier to address
with these curves too. But I wouldn't go as far as to say that they are
inherently safer than the Brainpool curves. They are easier to implement
correctly, have excellent performance, and reduce the conflicts between security
and efficiency/ease of implementation, which is great. But I'm still a bit
uncomfortable with calling them "safe" and implying all other curves aren't.

Manuel.

PS: besides, there's a practical advantage in being more specific than "safe":
when/if someone comes with other curves which have arguably nicer
security/implementation properties, a neutral and specific term will remain
appropriate, while "safe" will sound odd. (It's like calling things "modern".)

---

From: Robert Ransom <[email-masked]>
Date: Thu, 9 Jan 2014 01:50:48 -0800

> Curve25519 as M255, but I'm sure there are good reasons to disagree on this

Remember that Curve25519's parameter is *not* minimal subject to the
constraint of twist security with minimal cofactors -- Dr. Bernstein
considered a slightly more subtle criterion regarding the group orders
too.  Keep that in mind if you try to establish a systematic name for
Curve25519.

> use in a protocol, and refer to the appropriate section of this draft.

I don't see the benefit of defining both a ‘safe’ Montgomery curve
(for the present definition of “safe”) and a ‘safe’ Edwards curve over
the same coordinate field -- every Edwards curve with minimal
parameter can be used efficiently with Montgomery's formulas.  (The
Montgomery-form parameter becomes the reciprocal of a small integer,
which can be handled as efficiently as a small integer itself.)

(For that matter, I would suggest replacing Curve25519 with the
twisted Edwards curve a=-1, d=121665 over the same field in any new
application or standard.)

I would also recommend highlighting the most efficient curves --
Curve25519 and Curve3617 have especially nice coordinate fields; even
2^521 - 1 is less convenient (the limb arrangement is less regular).

> Montgomery and Edwards curves,

Issue 2 is obviated by twist security for single-scalar multiplication
of a Montgomery-form x coordinate.  It remains relevant for any
application which operates on full points (whether transmitted
uncompressed or compressed).

> and to be fair point 4 is a bit easier to
> address
> with these curves too.

Why 4?  The benefit of complete addition formulas is that
implementations don't need to switch to a doubling routine when two
points are equal.  Nothing about SafeCurves makes constant-time table
lookups any easier.

Robert Ransom

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 09 Jan 2014 11:21:48 +0100

> too.  Keep that in mind if you try to establish a systematic name for
I'm not sure it goes against my argument that the name should reflect the type
of the curve. Or did I miss something?

> application or standard.)
An interesting point.

> uncompressed or compressed).
Absolutely. There was a hidden assumption that only the x coordinate be used in
my statement. Actually, I think it reinforces my point that the curves aren't
"magically" safe regardless of the how they are implemented or used in a
protocol: indeed, the fact that no public key validation is needed depends not
only on the curve (twist security), but also on the protocol (x coordinate only).

> points are equal.  Nothing about SafeCurves makes constant-time table
Right, I was making an unstated assumption again, sorry for that. The assumption
was that other curves are more likely to use a larger table for performance,
while a Curve25519 implementation will generally use a ladder with no
precomputed table, so it will only have to safely swap two points, which is less
expensive than doing a constant-time lookup in a larger (say 16 or 32 points)
table. So it lessens the performance vs security conflict.

Manuel.

---

From: Robert Ransom <[email-masked]>
Date: Thu, 9 Jan 2014 08:38:00 -0800

On 1/9/14, Manuel Pégourié-Gonnard <[email-masked]> wrote:
>>> (Montgomery or Edwards). This is already the case for other curve
>>> families,
>>> by
>>> Curve25519 as M255, but I'm sure there are good reasons to disagree on
>>> this
>>> point.
>>

That's an argument against making curve names appear systematic (e.g.
“M255”) when they may not be.  (I particularly dislike the naming
schemes used in the various versions of 2013/647.)

I guess I have more of a problem with the idea that Montgomery and
Edwards are two different types of curves at all.  The important fact
to convey for a SafeCurve is which *part* of the curve one is talking
about:

* the Montgomery line (i.e. the subset of a curve over the quadratic
extension field whose Montgomery-form x coordinates are ‘rational’);
* the Edwards curve (i.e. the subgroup of a curve whose coordinates
are both ‘rational’); or
* the non-trivial quadratic twist of the Edwards curve (which I'm
pretty sure no one uses).

Curve25519 is a Montgomery line; Ed25519 is an Edwards curve which is
part of Curve25519.  Curve1174 and Curve3617 are Edwards curves.  (I
implemented Curve1174 for 64-bit processors, and called my
Montgomery-form routines “mont1174”, but don't treat that as
normative.)

All of this makes good nomenclature for the various curves and
subcurves and subgroups and subsets both more difficult and more
important to define properly.

> table. So it lessens the performance vs security conflict.

A Curve25519 (Montgomery-line ECDH) implementation will generally use
a ladder with no precomputed table because Montgomery's formulas are
so much faster that way.

An Ed25519 (Edwards curve, typically signature-related) implementation
will generally use either (a) the variable-time Bos-Coster algorithm
(for batch verification of signatures), (b) the potentially
constant-time Brauer and/or Straus algorithm (for constant-time
signature verification or weird protocols like Ace), or (c) fixed-base
single-scalar multiplication using a huge precomputed table (for key
generation, which had better be done in constant time).

Robert Ransom

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 10 Jan 2014 00:41:56 +0100

> schemes used in the various versions of 2013/647.)
Oh, yes, fair point. Sorry for missing it the first time.

> about: [...]
100% agreed.

> will generally use either [...]
> 
Right. Since I only implemented the Montgomery version so far, I've got the
nasty habit of thinking mainly about that form.

But, unless I'm mistaken, it seems to me we agree on the main point here: "no
data-dependant branches or memory access" is a property of the implementation,
not of the curves. (And I take back my comment that the curves from safecurves
make the "no data-dependant memory access" part easier.)

Manuel.

---

From: Robert Ransom <[email-masked]>
Date: Sat, 11 Jan 2014 08:10:41 -0800

> not of the curves.

Yes.

Robert Ransom