Subject: [TLS] Why Edwards? (was Re: TLS process thread)

From: Watson Ladd <[email-masked]>
Date: Mon, 14 Apr 2014 07:32:46 -0700

On Sun, Apr 13, 2014 at 11:24 PM, Dan Harkins <[email-masked]> wrote:
>
> On Sun, April 13, 2014 10:44 pm, Watson Ladd wrote:
>> That's going to be a pretty big change from RFC 5246. Trying to keep
>> the textual changes minimal probably a lost cause at this point, and
>> will hurt, rather than help clarity. This is before we try to reduce
>> round-trips, eliminate unused ciphersuites, introduce the Edwards
>> curves (necessary for security because people do not write perfect
>> code, even when they should), and ensure that what we write matches
>> what we prove (because as I'm sure you know from my opposition to
>> Dragonfly, I do not support mechanisms that are not shown to be secure
>> from well picked assumptions)
>
>   Really? And Edwards curves will necessarily result in perfect code?
> Certainly not as a result of draft-ladd-safecurves! So what assures
> perfection in Edwards curves implementations then?

Nothing: you can always do something stupid that leaks information.
But on a Weierstrass curve, to add two points you have to
0: Be assured they are on the curve
1: Check that both are not the identity
2: Check they are not the same (and if so double them instead)
3: Check they are not inverses of each other
4: Add them

Doing this without branching is hard. Furthermore, to avoid leaking
information about the top bit of your exponent, you need to either
massage the exponent representation or do dummy calculations, along
with tracking when to start doing the real calculations.

I've written constant time P256 code. It wasn't easy, and there is one
particular exponent that will not get handled correctly (namely the
group order, which is fine because I'm doing ECDH with random secret
keys, and signature verification runs in not constant time). RFC 6090
gets this completely wrong.

By contrast on Edwards curves, there are no cases to consider: there
is only a formula that holds true for all cases. There can be no curve
checks: via compression we ensure that all considered points are on
the curve. There are no side channels at this level if you use a
masked table load, as there are no branches. It's significantly easier
to write the code and reason about it: naive double and add will work.

The same holds true for Montgomery curves, which is why the Curve25519
has attracted a lot of interest.

Of course, you could always suggest text to be added to
draft-ladd-safecurves or write one yourself on implementation of these
curves if you are dissatisfied with it. You could always write your
own draft if you had an alternative approach to presenting them.

Sincerely,
Watson Ladd

>   Dan.

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

---

From: Russ Housley <[email-masked]>
Date: Mon, 14 Apr 2014 10:48:13 -0400

> own draft if you had an alternative approach to presenting them.

Watson:

One thing that I like about the Weierstrass form is that we already have a lot of code that uses it.

Unfortunately, the NIST Prime Curves do not transform onto Edwards for because they are co-factor 1, and Edwards curves are co-factoer 4.  There are many people that will want FIPS 140 certification of their implementations, so we need to find a way to accommodate the NIST Prime Curves even if they are not the default curve.

Russ

---

From: Watson Ladd <[email-masked]>
Date: Mon, 14 Apr 2014 08:03:41 -0700

> Unfortunately, the NIST Prime Curves do not transform onto Edwards for because they are co-factor 1, and Edwards curves are co-factoer 4. There are many people that will want FIPS 140 certification…

I'm not suggesting we throw out short Weierstrass. I'm saying that
Edwards curves need to be a viable alternative for people who don't
want the extra complexity and lower performance of short Weierstrass.
But yes, the low round trip handshake does have its own requirement on
a few commonly supported curves or else the initial offering will be
rejected unnecessarily.

Having separate curve specific implementations is necessary anyway for
optimal performance as the primes are different and the performance
characteristics of fields change as you increase the size. Kasper's
P224 and AGL's P256 use different radices. Embedded implementations
can pick one curve and stick with it, and use generic bignums (with
some care to avoid timing issues).

Adding Edwards curves to a Weierstrass implementation can be as small
as writing a new add and double function, each of about 20 indirect
calls, if the implementation was highly generic in the first place. If
not, you have to recode and rename more functions.

Sincerely,
Watson Ladd

---

From: Russ Housley <[email-masked]>
Date: Mon, 14 Apr 2014 11:49:26 -0400

Watson:

As you say, code optimization is a curve-specific activity.  Some people have spent a fair amount of time to make the modular reduction very efficient for the NIST Prime curves.  If these primes are used in other contexts, then we can continue to use these efficient routines.  Are there other places we can leverage existing efficient code?

Russ

---

From: Adam Langley <[email-masked]>
Date: Mon, 14 Apr 2014 12:11:16 -0700

On Mon, Apr 14, 2014 at 8:49 AM, Russ Housley <[email-masked]> wrote:
> Some people have spent a fair amount of time to make the modular reduction very efficient for the NIST Prime curves.  If these primes are used in other contexts, then we can continue to use these efficient routines.  Are there other places we can leverage existing efficient code?

The generalised-Mersenne forms of the NIST P-curve primes has, I
believe, turned out to be a mistake with the benefit of hindsight.

More modern curves tend to use near-Mersenne primes which are faster
and easier to optimise for. I wouldn't suggest that anyone aim to use
NIST P-curve primes because of the existing code base.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Nico Williams <[email-masked]>
Date: Mon, 14 Apr 2014 23:27:11 -0500

FWIW, I believe the matter is very clear now: Weierstrass curves out,
Edwards curves in.  For all the reasons Watson gave, and, really, for
all the reasons that DJB has given.

DJB is so convincing on this subject that the burden of proof is on
anyone opposing the switch to Edwards curves.

That we have NIST curves code lying around is not a sufficient
argument: it will either not be constant time or its performance will
not be anywhere near as good as implementations of comparable Edwards
curves.  The first consideration (no side channels) is unarguably a
hard requirement; the second (good performance) is close enough to a
hard requirement that it might as well be.

Nico
--

---

From: Russ Housley <[email-masked]>
Date: Tue, 15 Apr 2014 09:12:50 -0400

> hard requirement that it might as well be.

Nico:

If your last paragraph is a response to the postings that I made yesterday, then you are over simplifying my points.

I am not arguing against the adoption of Edwards curves.  However, I am saying that there are many that will need FIPS 140 certification, and we need to accommodate that community as well.  This will be important in the way that the curve being used is negotiated.

Russ

---

From: Nico Williams <[email-masked]>
Date: Tue, 15 Apr 2014 10:35:47 -0500

> If your last paragraph is a response to the postings that I made yesterday, then you are over simplifying my points.

It was in response to your post (I should have responded separately,
but I also wanted to respond to that generally and in the same place
in which I supported Watson's comments).

> I am not arguing against the adoption of Edwards curves.  However, I am saying that there are many that will need FIPS 140 certification, and we need to accommodate that community as well.  This wi…

FIPS-140 may be in for some modernization.

Nico
--

---

From: Russ Housley <[email-masked]>
Date: Tue, 15 Apr 2014 11:41:58 -0400

> FIPS-140 may be in for some modernization.

Of course.  It has continued to evolve since it was created, and we cannot expect it to happen on our timeline.  Therefore, we should be give a transition plan to those that need one.  I think that means a way to support the current curves as well as those that we select for the future.

We need a negotiation mechanism regardless.

Russ

---

From: Nico Williams <[email-masked]>
Date: Tue, 15 Apr 2014 10:44:26 -0500

> Of course.  It has continued to evolve since it was created, and we cannot expect it to happen on our timeline.  Therefore, we should be give a transition plan to those that need one.  I think that…

Of course.  NIST curves might need to be RECOMMENDED for interop, but
Edwards curves should be REQUIRED to implement because they are the
future.

> We need a negotiation mechanism regardless.

No argument from me here!  I'm all for algorithm agility.

Nico
--