Re: [Cfrg] Curve selection revisited

[Robert Ransom <[e-mail]>]

On 7/26/14, Watson Ladd <[e-mail]> wrote:
> <choping irrelevent stuff>
>
>>
>> “Easy” does not mean “low-cost”.  Adding support for Edwards-form
>> input points to a Montgomery-ladder implementation is easy, but has a
>> high performance cost (1I per scalarmult).  Adding support for
>> Montgomery-form input points to an implementation which operates on
>> Edwards form is easy, and has much smaller performance cost.
>
> By "easy" I meant that as the field arithmetic is already done, which
> is the vast
> bulk of the difficulty, the additional code is smaller. Adding the
> Montgomery ladder
> as a routine on top of the arithmetic is not hard: it's 10 function
> calls and a loop more or less.

As I said, “easy” has nothing to do with “low-cost”.


>>> (there is an additional question of small parameters: a Montgomery
>>> curve with small
>>> parameter is birationally equivalent to a twisted Edwards curve of
>>> small parameter, but
>>> the converse is not (obviously) true. Most generated curves seem to be
>>> in Edwards form
>>> however.)
>>
>> Curve25519 chose (A+2)/4 to be a small integer because Edwards curves
>> had not been published yet.  All new curves should be chosen to have
>> Edwards d be a small integer, because that makes the Edwards-form
>> unified addition formulas faster at no cost to the Montgomery ladder
>> on the isomorphic Montgomery curve.  (I've mentioned this to CFRG
>> before; I wish more people had listened to me.)
>
> Doesn't A become a ratio of small integers rather than a small integer?
> Although
> this is still pretty fast.

A is irrelevant.  (A+2)/4, which is actually used in the formulas,
becomes the reciprocal of a small integer rather than a small integer,
which does not harm the performance of the Montgomery-ladder formulas.
(See
e.g. <http://www.ietf.org/mail-archive/web/cfrg/current/msg04077.html>.
You were part of that discussion; I'm a bit surprised that you've
forgotten this.)


>>>>> one caches ephemeral DH
>>>>> parameters so the cost of fixed-base exponentiation is amortized
>>>>> across connections. OpenSSL does this anyway, and this affects
>>>>> technique
>>>>> slightly.
>>>>
>>>> This is good for performance even if you use a table to optimize
>>>> fixed-base scalar multiplications.
>>>
>>> Very true: the NUMS performance results are thus dead wrong in ECDHE
>>> costs,
>>> which are two variable-base multiplications plus a very amortized
>>> fixed-base multiplication, not
>>> the fixed+variable base they used.
>>
>> I don't see anything wrong with what MSR states as the cost of ECDHE
>> -- they're consistent across the implementations, and not reusing
>> ephemeral keys is the simplest implementation strategy.  (If they did
>> change their figures to take key reuse into account, though, the cost
>> would be only one variable-base scalar multiplication, not two.)
>
> The numbers are right, but the conclusions are thus wrong since a
> common optimization
> is neglected. In particular, the absence of Montgomery form from the
> proposal is based on
> performance measures including a fixed based exponentiation.

Remember that MSR used a ‘hybrid’ implementation for ECDHE, which
performed the fixed-base multiplication in Edwards form and the
variable-base multiplication in Montgomery form.  They would have
drawn the same conclusions if they had looked only at their
variable-base multiplication performance figures, because they report
that their Montgomery-ladder implementation is slower than their
Edwards-form variable-base scalar multiplication implementation on
every curve they considered.

However, MSR's performance numbers may be wrong: they used an
unnecessarily long scalar for the Montgomery ladder (and threw away
twist security in the process), because they believed the (false)
conventional wisdom that the Montgomery ladder must start with the
most significant non-zero bit of the scalar.  They need to redo their
Montgomery-ladder implementation and publish corrected performance
figures before we can trust their algorithm recommendations on any
curve.


My bigger problem with MSR is that they seem to view Curve25519, and
the community of cryptography experts and users which made it the
de-facto standard for fast ECDH(E) in groups of near-256-bit order, as
their enemy.  It's not just that they showed up with their pile of
curves just in time to ask the TLS WG to not issue the protocol
numbers that people who want to use Curve25519 would need in order to
use it in TLS; they're also having to rediscover things that anyone
who has tried to optimize Montgomery and/or Edwards curves should know
by now (or worse, not rediscovering them).  If their goal is to find
the fastest ECC curves and algorithms, they're hurting themselves by
not listening to the people who have investigated these curves for
months or years already.


Robert Ransom