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

[Watson Ladd <[e-mail]>]

On Sun, Apr 13, 2014 at 11:24 PM, Dan Harkins <[e-mail]> 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