Re: [Cfrg] Curve selection revisited

[Watson Ladd <[e-mail]>]

On Fri, Jul 25, 2014 at 8:30 AM, David Jacobson
<[e-mail]> wrote:
> On 7/25/14 7:48 AM, Paterson, Kenny wrote:
>>
>> Ben
>>
>> Thanks for this helpful message. I've responded in-line below,
>> representing the chairs and based on what I've heard on the list and at
>> the IETF meeting this week. People on the list should still feel free, of
>> course, to argue for other points of view.
>>
>> On 25/07/2014 01:10, "Benjamin Black" <[e-mail]> wrote:
>>
>> [snip]
>>
>>>
>>> 2) Performance must be measured using "production-quality"
>>> implementations. By this I mean implementations which employ the sort of
>>> techniques/optimizations appropriate for large scale deployment. This is
>>> specifically intended to exclude discussion of
>>> how simple or fast an implementation _could_ be, in favor of what they
>>> actually are in practice. However, the goal is to select curves which
>>> strike the best balance between various requirements, not simply the
>>> fastest.
>>>
>> I don't think it's very easy to be concrete about what
>> "production-quality" means. I tend to agree with Yoav's comments here
>> (http://www.ietf.org/mail-archive/web/cfrg/current/msg04735.html).
>
>
> I believe that we need to decide what to do about side channel leakage
> resistance.  Performance needs to be measured with the defenses deployed.
> Of course, the problem is that nobody knows what defenses should be deployed
> and when we have reached "good enough". One common defense is no branches on
> secret data.  Almost certainly we would want the benchmarks to be coded this
> way.  But if the threat model includes malicious processes that share a
> cache with the crypto process, then it is  good practice to code so that the
> stream of memory addresses accessed does not depend on secret data.    And
> then there are various blinding techniques with widely varying costs.
>
> This issue is more important if different curves/protocols have different
> sensitivities to leakage or require different leakage mitigations.  I don't
> know whether this is the case.

So I'd like to explain a bit about how implementations work, and why
performance will not help us decide between Curve25519 in twisted
Edwards form and the NUMS curve of similar size in twisted Edwards
form.

The first question is how to do the field arithmetic. All the primes
being considered are of the form 2^s-c, so either one of saturated
arithmetic
or unsaturated will work. Unsaturated is more portable: C cannot
access the carry flag. It offers more freedom in radix, and lets carry
chains be vectorized. Karatsuba can be used or not, which depends on
the saturated/unsaturated choice. But the exact values of s and c
don't matter as much.

The second question and third question what coordinates and what
addition formulas to use when, and what algorithm to use. All twisted
Edwards curves expose the same possibilities here: large precomputed
tables with mixed coordinate addition vs. smaller tables for variable
base, or a conversion to some other isogenous curve for variable base
exponentiation.

If we are willing to use Montgomery form (which the TLS WG initially
had strong support for in Curve25519) 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. But to be clear, a fast implementation for one prime and
curve of a certain size and shape will likely be adaptable to a
different curve
over a similar prime with the same shape.

Performance data will not distinguish between s=255 and s=256. It will
inform the decision of whether Ed448 is too big for an intermediate
curve, or if the speed disadvantage over whatever curve has size 384
is so minor as to make the extra strength effectively free, and
likewise the question of s=512 vs. s=521. But this is also a messier
question: how many options do we need and what do people want them to
be?

Sincerely,
Watson Ladd

>
>    --David Jacobson
>
>
>
>
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



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