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

[Russ Housley <[e-mail]>]

> On Mon, Apr 14, 2014 at 7:48 AM, Russ Housley <[e-mail]> wrote:
>> 
>>> 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
>> 
>> 
>> 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.
> 
> 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


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