Subject: [Cfrg] Curve selection revisited

From: Benjamin Black <[email-masked]>
Date: Thu, 24 Jul 2014 22:10:18 -0700

Inspired by some comments from other and in hopes of returning to a more
productive debate rather than the pointed back and forth, of which I am
absolutely guilty, I'm suggesting a few constraints. These are not priority
ordered and none of them deal with the math, instead focusing on process
and practice.

1) As we are discussing this in the context of TLS, the performance of
various kx options must be evaluated for ECDHE as typically deployed. ECDH
is neither common nor recommended in the TLS BCP draft. In addition, I hope
there will be discussion of benchmarking methodology, with the
understanding the ultimate choice is for the CFRG chairs.

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.

3) The timeframe for a decision constrains the scope of this process. If a
decision is desired within a few months, then it is difficult to include
options beyond new curves. If a decision can take a year, new algorithms
could be considered. Given the importance, impact, and contentiousness of
new algorithms, I believe it would be difficult to complete a thorough,
careful algorithm and curve selection process in a short amount of time.

4) The precise set of security levels needed should be specified in advance
(whether by TLS or CFRG) and curve recommendations delivered together for
all levels. A stated goal is to use these curves in new drafts, and it
minimizes work to specify all security levels for a proposal in the same
draft. This is strictly a practical matter recognizing the chairs and area
directors have limited bandwidth and implementors can get everything done
in a single go.

5) Selections must efficiently support TLS 1.2. Adoption of new curves, and
potentially new algorithms, can't be gated on completion and widespread
deployment of TLS 1.3.

6) Drop-in replacement for the NIST curves is _not_ a requirement in this
process.

7) I don't think the chairs are signing up for a full-on, NIST-style
selection competition and we should aim to keep things are lightweight as
possible while still achieving the required level of rigor. I hope they
will address this point soon.

Ben

---

From: Yoav Nir <[email-masked]>
Date: Fri, 25 Jul 2014 10:18:09 -0400

On Jul 25, 2014, at 1:10 AM, Benjamin Black <[email-masked]> wrote:

> Inspired by some comments from other and in hopes of returning to a more productive debate rather than the pointed back and forth, of which I am absolutely guilty, I'm suggesting a few constraints. These are not priority ordered and none of them deal with the math, instead focusing on process and practice.
> 
> 1) As we are discussing this in the context of TLS, the performance of various kx options must be evaluated for ECDHE as typically deployed. ECDH is neither common nor recommended in the TLS BCP draft. In addition, I hope there will be discussion of benchmarking methodology, with the understanding the ultimate choice is for the CFRG chairs.

The ultimate choice is with the group, with the chairs refereeing. We are also interested in digital signatures, not only key agreement. I agree that we need a benchmark methodology, but before that, we need to agree on selection criteria. There’s no point in testing if the results don’t point you towards a choice. The obvious criterion is speed of operation (for generate, derive, sign, and verify) on one or more platforms (probably need more than one). Another criterion could be memory requirements for the operation (matters for small platforms, but also limits scalability of large servers). Yet another criterion that isn’t measured in a benchmark is complexity, although I don’t think the candidate curves differ on this.

> 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 think “production-quality” should be simply the kind of code that a vendor or open source project might “ship”. This is not necessarily the fastest. For example, if Microsoft ships this curve in Windows (or Google in Chrome for Windows), they are going to need the code to run on any platform that Windows runs on, from Atom to the latest i7. If the latest i7 has some instructions that make the implementation faster, they are faced with the choice of including multiple implementations, tailored to different chips, or coding for the lowest common denominator. In practice, they will only include multiple implementations if the performance difference is noticeable (no idea what their threshold would be, but for me it would need to be at least 50% before I recommended including multiple implementations). 

So optimizing code for the target processor does not necessarily yield “production quality” code. That said, I don’t really know how we could control for that.

> 3) The timeframe for a decision constrains the scope of this process. If a decision is desired within a few months, then it is difficult to include options beyond new curves. If a decision can take a year, new algorithms could be considered. Given the importance, impact, and contentiousness of new algorithms, I believe it would be difficult to complete a thorough, careful algorithm and curve selection process in a short amount of time.

There’s also the question of (lack of) resources. NIST or the NSA can assign six cryptographers to spend the next year examining curves and algorithms. We are all volunteers, so if we get someone with the cryptographic chops to take several hours from his or her busy schedule to examine and comment on a proposal, or if we get someone with the programming chops to spend a few days implementing and benchmarking, we should consider ourselves lucky.

> 4) The precise set of security levels needed should be specified in advance (whether by TLS or CFRG) and curve recommendations delivered together for all levels. A stated goal is to use these curves in new drafts, and it minimizes work to specify all security levels for a proposal in the same draft. This is strictly a practical matter recognizing the chairs and area directors have limited bandwidth and implementors can get everything done in a single go.

Agree.

> 5) Selections must efficiently support TLS 1.2. Adoption of new curves, and potentially new algorithms, can't be gated on completion and widespread deployment of TLS 1.3.

Agree. It shouldn’t be gated on TLS at all. The same curves will probably be adopted by whoever else uses ECDHE and elliptic curve signatures. So whatever choice is made here will affect IKE, SSH, certificate authorities. There is nothing special about TLS.

> 6) Drop-in replacement for the NIST curves is _not_ a requirement in this process.

Totally agree.

> 7) I don't think the chairs are signing up for a full-on, NIST-style selection competition and we should aim to keep things are lightweight as possible while still achieving the required level of rigor. I hope they will address this point soon.

Agree.

Yoav

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 25 Jul 2014 14:48:29 +0000

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" <[email-masked]> wrote:

>absolutely guilty, I'm suggesting a few constraints. These are not
>priority ordered and none of them
> deal with the math, instead focusing on process and practice.
>
>
>various kx options must be evaluated for ECDHE as typically deployed.
>ECDH is neither common nor recommended in the TLS BCP draft. In addition,
>I hope there will be discussion of benchmarking
> methodology, with the understanding the ultimate choice is for the CFRG
>chairs.

Some detail on benchmarking methods will indeed be helpful.

My perspective, from having talked to a number of vendors this week, is
that speed (one measure of performance) is important, but being the
fastest is not if the performance difference is x%. Here x is a variable
that ranges somewhere between 5 and 50 depending on which vendor you talk
to.

>
>
>2) Performance must be measured using "production-quality"
>implementations. By this I mean implementations which employ the sort of
>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).

>
>3) The timeframe for a decision constrains the scope of this process. If
>a decision is desired within a few months, then it is difficult to
>include options beyond new curves. If a decision can take a year, new
>algorithms could be considered. Given the
> importance, impact, and contentiousness of new algorithms, I believe it
>would be difficult to complete a thorough, careful algorithm and curve
>selection process in a short amount of time.
>

Yes, I agree. 

Our process is not going to be perfect. We don't have the resources of
NIST/NSA/your favourite agency here. This is not the AES or SHA-3
competition. Yet we can draw on many years of ECC experience and expertise
of people on the list (and off it).

I had a strong steer this week from the TLS WG chairs and other people
active in the TLS WG that ECDHE and EC-DSA are the target algorithms for
us to think about when selecting curves. In other words, it's about new
curves for existing algorithms, not new curves AND new algorithms. That
does not preclude the introduction of new algorithms via CFRG over a
longer timescale, but it's not part of our current work.

>
>4) The precise set of security levels needed should be specified in
>advance (whether by TLS or CFRG) and curve recommendations delivered
>together for all levels. A stated goal is to use these curves in new
>drafts, and it minimizes work to specify all security
> levels for a proposal in the same draft. This is strictly a practical
>matter recognizing the chairs and area directors have limited bandwidth
>and implementors can get everything done in a single go.
>

This is not a point of contention. We've been asked by the TLS WG to
produce curves at the 128-bit and 256-bit levels, with a 192-bit option if
we wish. 

There is some wiggle room here - for example, a suitable curve with small
co-factor defined over a prime with 383 bits would be acceptable as
meeting the 192-bit level, etc.

>
>5) Selections must efficiently support TLS 1.2. Adoption of new curves,
>and potentially new algorithms, can't be gated on completion and
>widespread deployment of TLS 1.3.

I don't see TLS 1.3 as being an issue. We can safely assume it is going to
be using the same basic algorithms as TLS 1.2 ECC.

>6) Drop-in replacement for the NIST curves is _not_ a requirement in this

I agree. At Toronto, the common view amongst people I talked to was that
"Weierstrass-only" form curves (i.e. curves of prime order) is not a
*hard* requirement.

The benefits of switching to other curve forms (speed, simplicity of
side-channel protection) may well outweigh the benefits of sticking with
W-only forms (code re-use, familiarity for developers, no co-factor to
worry about).

>will address this point soon.

I'm not sure in what way you'd like the chairs to address this point. I
hope it was clear from the initial announcement
(http://www.ietf.org/mail-archive/web/cfrg/current/msg04655.html) that
we're running a lightweight process lasting a couple of months.

That has not changed.

Best regards,

Kenny

---

From: David Jacobson <[email-masked]>
Date: Fri, 25 Jul 2014 08:30:35 -0700

On 7/25/14 7:48 AM, Paterson, Kenny wrote:
> [snip]

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.

    --David Jacobson

---

From: Watson Ladd <[email-masked]>
Date: Fri, 25 Jul 2014 18:04:05 -0700

On Fri, Jul 25, 2014 at 8:30 AM, David Jacobson
<[email-masked]> wrote:
> 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
> [email-masked]
> 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

---

From: Robert Ransom <[email-masked]>
Date: Fri, 25 Jul 2014 19:25:54 -0700

> the saturated/unsaturated choice. But the exact values of s and c

The exact value of c determines whether a portable or vectorized
implementation can delay carries until after reduction.  For example,
after curve25519-donna performs a multiply or squaring, each of 19
64-bit limbs has absolute value less than 14*2^54.  When
freduce_degree reduces a field element to 10 limbs without carrying,
the result has absolute value less than (c+1)*14*2^54 = 280*2^54, or a
bit more than 2^62.  In the Microsoft field 2^255 - 765, or even 2^256
- 189, this would not be possible.

Carries between limbs can be performed more efficiently than in
curve25519-donna -- curve25519-donna goes to extra effort to keep
limbs signed.  In the Montgomery ladder, this optimization does not
add any extra carry steps, because the Montgomery-ladder formulas
never perform more than two add/subtract operations between a
multiply/square operation.  With Edwards-curve operations, this
optimization may require an additional carry step in the doubling
formula.

The exact value of s determines whether carries can be vectorized
within a coordinate-field element.  For example, 2^251 - 9 can be
represented using one 26-bit limb (in the least significant position)
and 9 25-bit limbs, but this interferes with the vectorization
strategy described in the neoncrypto paper (by Dr. Bernstein et al.).
Since c=9 is so small, this can be worked around by representing
coordinates modulo 2^252 - 18 instead, but this trick is rarely
possible without running into the bound on c.

> base, or a conversion to some other isogenous curve for variable base

Affine Montgomery-form points can be unpacked to and packed from
projective (optionally twisted) Edwards-form points at a trivial extra
cost over unpacking from or packing to a compressed affine
Edwards-form point.  Variable-base scalar-multiplication operations
which use Edwards form internally are not slowed significantly by
having a projective rather than affine input (if any operations rely
on their input being affine, they must occur during table setup), and
they are not slowed at all if they double and/or apply isogenies to
clear the cofactor group before operating on an ‘incomplete’ curve
(e.g. a=-1 in a field in which -1 is a non-square).

As you should know, fixed-base scalar-multiplication operations which
use Edwards form internally are not slowed at all by producing
Montgomery-form output.

Affine Edwards-form points cannot be unpacked to affine
Montgomery-form points for use with the Montgomery ladder without an
extra inversion at the beginning of a scalar multiplication, and using
a projective input in the Montgomery ladder is always slower than
inversion by coordinate exponentiation.

Since the Montgomery ladder remains the simplest implementation
strategy, and the performance benefit to more complex implementations
from using an Edwards-form point format is small at most, I still see
no reason to use an Edwards-form point format.

> had strong support for in Curve25519)

Has the TLS WG changed its support for using the widely implemented,
de-facto standard point format for Curve25519?  If so, when was this
decision made?

> one caches ephemeral DH
> slightly.

This is good for performance even if you use a table to optimize
fixed-base scalar multiplications.

> But to be clear, a fast implementation for one prime and

This is simply not true.  Curve operations can often be reused, and
some other utility routines can easily be modularized in a way that
supports other coordinate fields with similar properties (e.g.
q=3mod4), but primes which make portable or vectorized coordinate
operation implementations efficient are too rare for there to be any
pairs of ‘similar prime’s.

> Performance data will not distinguish between s=255 and s=256.

It will distinguish between Curve25519 and the Microsoft curves in the
implementations (either portable, open-source C, or heavily-optimized
machine code) which are actually used.

Robert Ransom

---

From: Watson Ladd <[email-masked]>
Date: Fri, 25 Jul 2014 20:40:40 -0700

Thanks for the much more detailed analysis: I'll have to revise my opinion.
> possible without running into the bound on c.

True: since square roots in F_p with p=5(8) are easy, one of the rationals
for the NUMS curves is just wrong, and we can live with smaller c.
> (e.g. a=-1 in a field in which -1 is a non-square).

I think I follow all the way up to the last phrase: the incompleteness
means some
additions might blow up, complicating the analysis, and I think a=-1
only gives the twist
if -1 is a nonsquare. Otherwise it is a curve isogenous to the
original one, under a 1-isogeny.
I've not thought about it that much.

> no reason to use an Edwards-form point format.

Signatures: the y-encoding strategies I've seen are too clever by
half, so keys for
ECIES and signatures look very different. There is no security issue
with reuse and
there are papers to that effect, or so I'm told.
That said adding Edwards support or Montgomery support to an implementation
of the other partner in the isogenous pair is easy: we can live with
two point formats.

(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.)
> de-facto standard point format for Curve25519?  If so, when was this

Quite true: perhaps the leadership would like to explain why
"curve25519 has no security
issues" was insufficient for the adoption of curve25519 in TLS for
ECDHE, given substantial
implementor support and existing drafts.

> 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.

> pairs of ‘similar prime’s.

I think within 10% or 5% is likely. Certainly not outside 50%.
> machine code) which are actually used.

Well, absent hard numbers I'm not sure we can say how much it distinguishes.
> Robert Ransom

Sincerely,
Watson ladd

---

From: Robert Ransom <[email-masked]>
Date: Fri, 25 Jul 2014 22:40:50 -0700

> optimization may require an additional carry step in the doubling

Er.  The ‘optimization’ I'm referring to is carrying in such a way
that the resulting limb values are always non-negative, in three
operations (shift, add, and bitwise and) rather than the seven (four
shifts, two adds, one subtract) needed to chop an extra bit off the
absolute value of each limb, and possibly producing negative limbs.

Dr. Bernstein wrote up his own explanation of how the performance of
unsaturated-limb arithmetic depends strongly on the exact values of s
and c on the curves list; see
<https://moderncrypto.org/mail-archive/curves/2014/000237.html>.  The
Curve41417 paper gives a more extensive treatment of how its
coordinate field allows even more optimization.

Robert Ransom

---

From: Robert Ransom <[email-masked]>
Date: Fri, 25 Jul 2014 22:42:45 -0700

> if -1 is a nonsquare.

I'm not talking about using the twist.  I'm talking about mapping from
the ‘complete’ Edwards/Montgomery curve which the specification states
and simple implementations use to an ‘incomplete’ curve (i.e. a
(twisted) Edwards curve with non-affine points defined over the base
field), by whatever means (isomorphism or isogeny), on which the
unified addition formula has exceptional cases for inputs with even
order.  When this is a useful thing to do -- i.e. when the curve is
defined over a field in which -1 is a non-square, and thus (twisted)
Edwards curves with a=-1 are always incomplete -- there is almost
always more than one suitable curve to map to.  For example, Mike
Hamburg suggests in <https://eprint.iacr.org/2014/027.pdf> a 4-isogeny
from Ed(1,d) to Ed(-1,d-1); when d is a non-square, there is also an
isomorphism from Ed(1,d) to Ed(-1,-1/d).

My point is that most implementation strategies which want to *use* an
incomplete Edwards curve start with operations which (a) modify the
original input point such that it is guaranteed to have odd order, and
(b) produce a non-affine result, which all further operations use as
their input.  Because of (b), using a Montgomery-form input point
format in such an implementation has almost no performance cost (only
a few multiplies).

Dr. Bernstein's Curve3617 implementation (he now wants to call it
Curve41417) operates on a complete Edwards curve; its implementation
strategy is more complex than the Montgomery ladder, and slightly less
complex than one using an incomplete curve.  As a consequence, it
benefits more than the fastest implementation strategy from having an
affine Edwards-form input point: it saves an additional 7M in the
process of constructing a 15-element table.  I don't think this
benefit to exactly one sub-optimal implementation strategy justifies
the cost to the simplest implementation strategy (the Montgomery
ladder).

> Otherwise it is a curve isogenous to the

The proper term for a ‘1-isogeny’ is “isomorphism”.  Otherwise, people
will think that “isogeny” is just the term used for an isomorphism
between elliptic curves, rather than a very different type of map.

> ECIES and signatures look very different.

What do you mean by this?

> There is no security issue
> with reuse and

“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.

> the converse is not (obviously) true. Most generated curves seem to be

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.)

> 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.)

Robert Ransom

---

From: Watson Ladd <[email-masked]>
Date: Sat, 26 Jul 2014 10:59:29 -0700

<choping irrelevent stuff>

> 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.
> 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.

> 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.

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 26 Jul 2014 14:42:11 -0700

> possible without running into the bound on c.

The main argument for p = 2^255-19 v.s. p = 1^256-189 is that the C=19 
is smaller than C=189 and this helps to "manage" the carries.

Let's assume that an F(p) integer is represented as n limbs (words).

256 bit Montgomery curve will have on the order of (5 mul + 4 squares) 
and about the same number F(p) additions per one scalar bit.

Therefore, we can talk about one unreduced F(p) multiplication + F(p) 
reduction (where C plays its role) + F(p) addition. With this in mind 
the contribution of C can be estimated within this group.

F(p) multiplications (counting squares here as well) dominate the 
performance of EC operations:
* the result of the multiplication is 2*n limbs and the complexity of 
this operation is n^2 limb multiplications and O(n^2) additions.
* the 2*n limbs must be reduced (mod p) to n limbs immediately after 
multiplication
* there is on average ~1 addition/subtraction of n limbs per each 
multiplication due to EC formula

Each multiplication needs degree reduction and settling of accumulated 
carries before the next multiplication. One can only postpone settling 
of carries while he does additions (prior to the next multiplciation).

We have about n^2 limb additions, plus n limb additions due to EC 
formular, plus we must perform n additions of the form <some_limb>*C 
(for modp reduction).

Assuming n=10 limbs, the entire contribution of n <some_limb>*C is bound 
by ~10% of all the additions.

We are not talking about C=0, however, but rather about |C|=4 bits v.s. 
|C| = 8 bits difference.

A rough estimate here is 5% penalty.

One reason why I think this is a good estimate is that there may be a 
benefit of more fine-tuned control of carries. The highest accumulation 
of the carries happens in the inner limbs of the 2*n integer (imagine 
paper-and-pencil multiplication of two n-limb numbers: the stack is the 
highest in the middle). Therefore, if we have the need to control 
overflow within, say, multiplication, perhaps it's possible to 
accomplish this within a subset of n limbs.

( BTW, I don't see a clear argument why can't any F(p) be vectorized 
(some more efficiently than others). The vectorization using x86 SSE2 is 
known to speeds up RSA operations for generic F(p)s. )

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 27 Jul 2014 08:22:16 +0300

On Fri, Jul 25, 2014 at 07:25:54PM -0700, Robert Ransom wrote:
> Edwards-form point. 

Do you mean Montgomery_x-only, or that (Montgomery_x, Edwards_x_sign)
representation?

If the latter, it is not at all obvious how to get both in just
one inversion (either can obviously be gotten in just one inversion,
as can full edwards affine form).

Also, looks like the representation hits special case if Edwards-x is
0 (both points map into Montgomery_x=0, and sign bit needs to tell
apart Edwards_y values, instead of Edwards_x values as usual).

So yes, easy conversion to Montgomery form is useful for DH, but
is it useful for when the other side will do things like additions?

> Variable-base scalar-multiplication operations

At least some protocols that do seem to cope with h>1 (as in having
checks for low-order points and no direct coupling between subgroups)
don't clear cofactors in points sent by the peer, but proceed to
directly calculate with those.

-Ilari

---

From: Robert Ransom <[email-masked]>
Date: Sun, 27 Jul 2014 11:02:34 -0700

> calls and a loop more or less.

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

> 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.)

> 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

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 10:58:14 -0400

The whole world is NOT TLS.  For example I am working in IEEE 1609 which 
is Vehicle-to-vehicle safety communications and their need is for signed 
data objects that are quickly generated and verified (you have ~100ms 
from the braking event to all the cars being able to act on that 
information).  I also work in IEEE 802.15.4 highly constrained devices 
(some much smaller than what many IETF groups accept as their lower limit).

8 bit processors are the norm, and NO, Dr. Moore is NOT going to change 
that.  Lower energy demand is much higher on the design plan than faster 
processing.  Also whatever is done will be running on fielded devices 
for the next 10 - 20 years.  Hardware acceleration is acceptable, but 
that could make in-field corrections impossible. Over-the-air firmware 
updates may also be impossible (802.15.4k is 40kb/s) or only done in the 
dealership (yes!  another recall!).

So getting on to my thoughts of curve selection requirements for the 
world of small:

1) Low over-the-air demands.  Every BIT counts.  We have to live with 32 
bytes; but 64 bytes may be too much.  Oh, IEEE 1609.2 has its own 
'certificate' and signature format as even the standard asn.1 is too 
wasteful of the very limited channel.  This applies also in 802.15.4 
where adding another MAC frame might mean that the whole thing fails 
because now it is more likely that one frame got lost.

2) Easy/size of implementation.  There has been lots of chatter here 
about how NIST p256 can be implemented wrongly.  Here it is of greater 
concern, as it might require a physical swap-out to correct an 
implementation error.  Manufacturers look at the cost of a programmer to 
save 5K code cheaper than that extra 5K footprint.  So little code and 
easy to code.  This world is extremely price sensitive.

3) Performance on an 8 bit  processor.  Performance is measured in time 
and energy.  In-vehicle devices tend to have a ready source of electrons 
(except for tire gauges!), but some devices have limited battery (your 
front door lock) or NO battery (MEMEs energy harvesters on bridge stress 
sensors).  So low energy is as important as quickly done.  Here 10% 
faster IS 10% faster; and it could make a life-or-death difference. (In 
Positive Train Control, the automatics MUST take over if the human can 
no longer respond in time and bullet trains can take 7Km to stop safely)

4) preserving ECDSA and ECDHE.  This is what is currently in use, and in 
some cases written into regulations (urgh), so we have to still keep 
them working.  But if something 'new' and provably good makes a big 
difference in one of the previous needs I suspect there will be an 
attentive audience.

I have tried to keep things general so as not too much to limit 
choices.  I never claimed to be a crytographer or to have the math 
skills to evaluate the various contenders.  Others working in this area 
might have their own reading on the needs of constrained 
devices/communications.

But please just don't solve this for TLS on octo-core 64-bit systems.

On 07/25/2014 01:10 AM, Benjamin Black wrote:
> Inspired by some comments from other and in hopes of returning to a 
> more productive debate rather than the pointed back and forth, of 
> which I am absolutely guilty, I'm suggesting a few constraints. These 
> are not priority ordered and none of them deal with the math, instead 
> focusing on process and practice.
>
> ECDH is neither common nor recommended in the TLS BCP draft. In 
> addition, I hope there will be discussion of benchmarking methodology, 
> with the understanding the ultimate choice is for the CFRG chairs.
>
> 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.
>
> 3) The timeframe for a decision constrains the scope of this process. 
> If a decision is desired within a few months, then it is difficult to 
> algorithms could be considered. Given the importance, impact, and 
> contentiousness of new algorithms, I believe it would be difficult to 
> complete a thorough, careful algorithm and curve selection process in 
> a short amount of time.
>
> drafts, and it minimizes work to specify all security levels for a 
> proposal in the same draft. This is strictly a practical matter 
> recognizing the chairs and area directors have limited bandwidth and 
> implementors can get everything done in a single go.
>
> 5) Selections must efficiently support TLS 1.2. Adoption of new 
> curves, and potentially new algorithms, can't be gated on completion 
> and widespread deployment of TLS 1.3.
>
> selection competition and we should aim to keep things are lightweight 
> as possible while still achieving the required level of rigor. I hope 
> they will address this point soon.

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 28 Jul 2014 10:05:23 -0700

You’re going to need a hardware accelerator for some of these small things.  Eg for v2v safety, the real ask has to be “fast and small and easy in hardware”.  The best solution to this is binary curves, though they are considered slightly edgy right now.

But yeah, 8-bit processor performance is important too.

Cheers,
— Mike

On Jul 28, 2014, at 7:58 AM, Robert Moskowitz <[email-masked]> wrote:

> The whole world is NOT TLS.  For example I am working in IEEE 1609 which is Vehicle-to-vehicle safety communications and their need is for signed data objects that are quickly generated and verified (you have ~100ms from the braking event to all the cars being able to act on that information).  I also work in IEEE 802.15.4 highly constrained devices (some much smaller than what many IETF groups accept as their lower limit).
> 
> 8 bit processors are the norm, and NO, Dr. Moore is NOT going to change that.  Lower energy demand is much higher on the design plan than faster processing.  Also whatever is done will be running on fielded devices for the next 10 - 20 years.  Hardware acceleration is acceptable, but that could make in-field corrections impossible. Over-the-air firmware updates may also be impossible (802.15.4k is 40kb/s) or only done in the dealership (yes!  another recall!).
> 
> So getting on to my thoughts of curve selection requirements for the world of small:
> 
> 1) Low over-the-air demands.  Every BIT counts.  We have to live with 32 bytes; but 64 bytes may be too much.  Oh, IEEE 1609.2 has its own 'certificate' and signature format as even the standard asn.1 is too wasteful of the very limited channel.  This applies also in 802.15.4 where adding another MAC frame might mean that the whole thing fails because now it is more likely that one frame got lost.
> 
> 2) Easy/size of implementation.  There has been lots of chatter here about how NIST p256 can be implemented wrongly.  Here it is of greater concern, as it might require a physical swap-out to correct an implementation error.  Manufacturers look at the cost of a programmer to save 5K code cheaper than that extra 5K footprint.  So little code and easy to code.  This world is extremely price sensitive.
> 
> 3) Performance on an 8 bit  processor.  Performance is measured in time and energy.  In-vehicle devices tend to have a ready source of electrons (except for tire gauges!), but some devices have limited battery (your front door lock) or NO battery (MEMEs energy harvesters on bridge stress sensors).  So low energy is as important as quickly done.  Here 10% faster IS 10% faster; and it could make a life-or-death difference. (In Positive Train Control, the automatics MUST take over if the human can no longer respond in time and bullet trains can take 7Km to stop safely)
> 
> 4) preserving ECDSA and ECDHE.  This is what is currently in use, and in some cases written into regulations (urgh), so we have to still keep them working.  But if something 'new' and provably good makes a big difference in one of the previous needs I suspect there will be an attentive audience.
> 
> I have tried to keep things general so as not too much to limit choices.  I never claimed to be a crytographer or to have the math skills to evaluate the various contenders.  Others working in this area might have their own reading on the needs of constrained devices/communications.
>

---

From: Michael Jenkins <[email-masked]>
Date: Mon, 28 Jul 2014 13:17:24 -0400

Bob,

I'm really glad to hear someone saying the whole world isn't TLS, and
IOT/constrained environments seems to be getting a lot of air-time, which
is good too. But while I was reading your email, I kept thinking, where's
the big-I Internet in this? If this is a high-speed, low-power, limited
range communication, what's the need for an Internet protocol?

On Mon, Jul 28, 2014 at 10:58 AM, Robert Moskowitz <[email-masked]>
wrote:

> data objects that are quickly generated and verified (you have ~100ms from
> the braking event to all the cars being able to act on that information).
>  I also work in IEEE 802.15.4 highly constrained devices (some much smaller
> than what many IETF groups accept as their lower limit).
>
> processing.  Also whatever is done will be running on fielded devices for
> the next 10 - 20 years.  Hardware acceleration is acceptable, but that
> could make in-field corrections impossible. Over-the-air firmware updates
> may also be impossible (802.15.4k is 40kb/s) or only done in the dealership
> (yes!  another recall!).
>
> wasteful of the very limited channel.  This applies also in 802.15.4 where
> adding another MAC frame might mean that the whole thing fails because now
> it is more likely that one frame got lost.
>
> 2) Easy/size of implementation.  There has been lots of chatter here about
> how NIST p256 can be implemented wrongly.  Here it is of greater concern,
> as it might require a physical swap-out to correct an implementation error.
>  Manufacturers look at the cost of a programmer to save 5K code cheaper
> than that extra 5K footprint.  So little code and easy to code.  This world
> is extremely price sensitive.
>
> sensors).  So low energy is as important as quickly done.  Here 10% faster
> IS 10% faster; and it could make a life-or-death difference. (In Positive
> Train Control, the automatics MUST take over if the human can no longer
> respond in time and bullet trains can take 7Km to stop safely)
>
> some cases written into regulations (urgh), so we have to still keep them
> working.  But if something 'new' and provably good makes a big difference
> in one of the previous needs I suspect there will be an attentive audience.
>
> I have tried to keep things general so as not too much to limit choices.
>  I never claimed to be a crytographer or to have the math skills to
> evaluate the various contenders.  Others working in this area might have
> their own reading on the needs of constrained devices/communications.
>
>> a decision is desired within a few months, then it is difficult to include
>> drafts, and it minimizes work to specify all security levels for a proposal
>> in the same draft. This is strictly a practical matter recognizing the
>> chairs and area directors have limited bandwidth and implementors can get
>> everything done in a single go.
>>
>> and potentially new algorithms, can't be gated on completion and widespread
>> deployment of TLS 1.3.
>>

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 28 Jul 2014 10:57:10 -0700

Actually, one more thing: in constrained environments, you really want Schnorr instead of ECDSA.  That extra inversion mod r is a giant pain.  It’s slow and often doesn’t share code with anything.  Plus Schnorr can go down to 3/4 the size if necessary.

Cheers,
— Mike

---

From: Hannes Tschofenig <[email-masked]>
Date: Mon, 28 Jul 2014 19:58:11 +0200

Hi Mike, Hi Bob,

Saying that you need hardware acceleration because of performance, RAM
and ROM size supported by some boards running 8-bit microcontrollers is
a bit lying to ourselves. The hardware acceleration might in fact
involve a chip with 32-bit.

8-bit microcontrollers have been great for devices that are not
connected to the Internet. For example, many early Arduino boards have
used a 8-bit microcontroller and their RAM/ROM configuration does not
make the use of crypto feasible to any realistic extend.

Now, we are past that point and it turns out that you get a Bluetooth
Smart chip that happens to have (internally to the chip) an 80kb stack
just for the actual link layer. New Arduino boards also run on 32-bit
processors and so do most of the IoT gear that gets brought to market
these days.

Also, the cost of 32-bit microcontrollers is sufficiently low that it
makes no sense to focus development effort on a 8-bit microcontroller
anymore. Just think about the software development cost here as well
(and not only on the pure hardware cost). While the world is indeed cost
sensitive real product managers look beyond the pure hardware cost and
also take other factors into account. Of course, everything depends on
the volume.

32-bit processors can also be energy efficient as the widespread
deployment shows. It is also important to note that energy consumption
does not only depend on the processor - it is the result of the entire
system. So, just focusing on the processor makes it a bit difficult to
have a useful discussion about energy efficiency. Since the IETF does
not focus on products / entire systems  I fear it will be very difficult
to have a meaningful conversation about this topic.

Since we have these discussions regularly in ACE I am planning to
schedule a Webex conference call to have one of my co-worker (who works
on hardware many years already) to explain what the industry trends are.

Having said that I am happy to take the results that come out of this
group and let them run on ARM processors to see what the performance is.

Ciao
Hannes

PS: Regarding the ASN.1 format I am wondering whether the IEEE has done
some more detailed analysis of the over-the-wire and the software
implementation cost. This would be useful for us in the ACE working group.

On 07/28/2014 07:05 PM, Michael Hamburg wrote:
> You’re going to need a hardware accelerator for some of these small
> things.  Eg for v2v safety, the real ask has to be “fast and small
> and easy in hardware”.  The best solution to this is binary curves,
> though they are considered slightly edgy right now.
> 
> Cheers, — Mike
>> The whole world is NOT TLS.  For example I am working in IEEE 1609
>> which is Vehicle-to-vehicle safety communications and their need is
>> for signed data objects that are quickly generated and verified
>> (you have ~100ms from the braking event to all the cars being able
>> to act on that information).  I also work in IEEE 802.15.4 highly
>> constrained devices (some much smaller than what many IETF groups
>> accept as their lower limit).
>> 
>> 8 bit processors are the norm, and NO, Dr. Moore is NOT going to
>> change that.  Lower energy demand is much higher on the design plan
>> than faster processing.  Also whatever is done will be running on
>> fielded devices for the next 10 - 20 years.  Hardware acceleration
>> is acceptable, but that could make in-field corrections impossible.
>> Over-the-air firmware updates may also be impossible (802.15.4k is
>> 40kb/s) or only done in the dealership (yes!  another recall!).
>> 
>> 1) Low over-the-air demands.  Every BIT counts.  We have to live
>> with 32 bytes; but 64 bytes may be too much.  Oh, IEEE 1609.2 has
>> its own 'certificate' and signature format as even the standard
>> asn.1 is too wasteful of the very limited channel.  This applies
>> also in 802.15.4 where adding another MAC frame might mean that the
>> whole thing fails because now it is more likely that one frame got
>> lost.
>> 
>> 2) Easy/size of implementation.  There has been lots of chatter
>> here about how NIST p256 can be implemented wrongly.  Here it is of
>> greater concern, as it might require a physical swap-out to correct
>> an implementation error.  Manufacturers look at the cost of a
>> programmer to save 5K code cheaper than that extra 5K footprint.
>> So little code and easy to code.  This world is extremely price
>> sensitive.
>> 
>> 3) Performance on an 8 bit  processor.  Performance is measured in
>> time and energy.  In-vehicle devices tend to have a ready source of
>> electrons (except for tire gauges!), but some devices have limited
>> battery (your front door lock) or NO battery (MEMEs energy
>> harvesters on bridge stress sensors).  So low energy is as
>> important as quickly done.  Here 10% faster IS 10% faster; and it
>> could make a life-or-death difference. (In Positive Train Control,
>> the automatics MUST take over if the human can no longer respond in
>> time and bullet trains can take 7Km to stop safely)
>> 
>> 4) preserving ECDSA and ECDHE.  This is what is currently in use,
>> and in some cases written into regulations (urgh), so we have to
>> still keep them working.  But if something 'new' and provably good
>> makes a big difference in one of the previous needs I suspect there
>> will be an attentive audience.
>> 
>> skills to evaluate the various contenders.  Others working in this
>> area might have their own reading on the needs of constrained
>> devices/communications.
>> 
>>> Inspired by some comments from other and in hopes of returning to
>>> a more productive debate rather than the pointed back and forth,
>>> of which I am absolutely guilty, I'm suggesting a few
>>> constraints. These are not priority ordered and none of them deal
>>> with the math, instead focusing on process and practice.
>>> 
>>> 1) As we are discussing this in the context of TLS, the
>>> performance of various kx options must be evaluated for ECDHE as
>>> typically deployed. ECDH is neither common nor recommended in the
>>> TLS BCP draft. In addition, I hope there will be discussion of
>>> benchmarking methodology, with the understanding the ultimate
>>> choice is for the CFRG chairs.
>>> 
>>> 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.
>>> 
>>> 3) The timeframe for a decision constrains the scope of this
>>> process. If a decision is desired within a few months, then it is
>>> difficult to include options beyond new curves. If a decision can
>>> take a year, new algorithms could be considered. Given the
>>> importance, impact, and contentiousness of new algorithms, I
>>> believe it would be difficult to complete a thorough, careful
>>> algorithm and curve selection process in a short amount of time.
>>> 
>>> 4) The precise set of security levels needed should be specified
>>> in advance (whether by TLS or CFRG) and curve recommendations
>>> delivered together for all levels. A stated goal is to use these
>>> curves in new drafts, and it minimizes work to specify all
>>> security levels for a proposal in the same draft. This is
>>> strictly a practical matter recognizing the chairs and area
>>> directors have limited bandwidth and implementors can get
>>> curves, and potentially new algorithms, can't be gated on
>>> completion and widespread deployment of TLS 1.3.
>>> 
>>> 7) I don't think the chairs are signing up for a full-on,
>>> NIST-style selection competition and we should aim to keep things
>>> are lightweight as possible while still achieving the required
>>> level of rigor. I hope they will address this point soon.
>> 
>> _______________________________________________ Cfrg mailing list 
>> [email-masked] http://www.irtf.org/mailman/listinfo/cfrg
> 
> _______________________________________________ Cfrg mailing list 
> [email-masked] http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Hannes Tschofenig <[email-masked]>
Date: Mon, 28 Jul 2014 20:12:16 +0200

Mike, do you have data that supports your remark?

Ciao
Hannes

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 14:12:56 -0400

On 07/28/2014 01:17 PM, Michael Jenkins wrote:
> IOT/constrained environments seems to be getting a lot of air-time, 
> which is good too. But while I was reading your email, I kept 
> thinking, where's the big-I Internet in this? If this is a high-speed, 
> low-power, limited range communication, what's the need for an 
> Internet protocol?

Some of it is NOT internet protocols.  IEEE 1609.4 WSMP is a MAC direct 
protocol.  In 1609, it is all about broadcast messages, as every car 
needs to receive it and there is NO time for any setup. Sign the 
message, get your channel allocation and send.  There is IP for some 
stuff, but most of that is V2R (roadside).  If we tackle a proper CANbus 
(now there is an interesting non-protocol) replacement, most of it will 
be a MAC message format.  And then there is SMS.  I can keep coming up 
with cases where there is no IP (IEEE 11073), or IP only occurs at the 
gateway (pacemaker (IEEE 802.15.6) to hospital).

The lack of an Internet layer, and maybe even a transport layer with 
only a message (session) layer or just MACsec, does not mean no 
security.  Security happens at many layers other than IP (IPsec) or 
Transport (TLS, DTLS, SRTP (or is that session)).

>
>
> On Mon, Jul 28, 2014 at 10:58 AM, Robert Moskowitz 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     which is Vehicle-to-vehicle safety communications and their need
>     is for signed data objects that are quickly generated and verified
>     change that.  Lower energy demand is much higher on the design
>     plan than faster processing.  Also whatever is done will be
>     running on fielded devices for the next 10 - 20 years.  Hardware
>     acceleration is acceptable, but that could make in-field
>     corrections impossible. Over-the-air firmware updates may also be
>     impossible (802.15.4k is 40kb/s) or only done in the dealership
>     (yes!  another recall!).
>
>     also in 802.15.4 where adding another MAC frame might mean that
>     the whole thing fails because now it is more likely that one frame
>     got lost.
>
>     here about how NIST p256 can be implemented wrongly.  Here it is
>     of greater concern, as it might require a physical swap-out to
>     correct an implementation error.  Manufacturers look at the cost
>     of a programmer to save 5K code cheaper than that extra 5K
>     footprint.  So little code and easy to code.  This world is
>     extremely price sensitive.
>
>     time and energy.  In-vehicle devices tend to have a ready source
>     of electrons (except for tire gauges!), but some devices have
>     limited battery (your front door lock) or NO battery (MEMEs energy
>     the automatics MUST take over if the human can no longer respond
>     in time and bullet trains can take 7Km to stop safely)
>
>     makes a big difference in one of the previous needs I suspect
>     there will be an attentive audience.
>
>         Inspired by some comments from other and in hopes of returning
>         to a more productive debate rather than the pointed back and
>         forth, of which I am absolutely guilty, I'm suggesting a few
>         constraints. These are not priority ordered and none of them
>         performance of various kx options must be evaluated for ECDHE
>         as typically deployed. ECDH is neither common nor recommended
>         in the TLS BCP draft. In addition, I hope there will be
>         discussion of benchmarking methodology, with the understanding
>         the ultimate choice is for the CFRG chairs.
>
>         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
>         process. If a decision is desired within a few months, then it
>         is difficult to include options beyond new curves. If a
>         decision can take a year, new algorithms could be considered.
>         Given the importance, impact, and contentiousness of new
>         algorithms, I believe it would be difficult to complete a
>         thorough, careful algorithm and curve selection process in a
>         short amount of time.
>
>         4) The precise set of security levels needed should be
>         specified in advance (whether by TLS or CFRG) and curve
>         recommendations delivered together for all levels. A stated
>         goal is to use these curves in new drafts, and it minimizes
>         work to specify all security levels for a proposal in the same
>         draft. This is strictly a practical matter recognizing the
>         chairs and area directors have limited bandwidth and
>         5) Selections must efficiently support TLS 1.2. Adoption of
>         new curves, and potentially new algorithms, can't be gated on
>         NIST-style selection competition and we should aim to keep
>         things are lightweight as possible while still achieving the
>         required level of rigor. I hope they will address this point soon.
>
>
>     [email-masked] <mailto:[email-masked]>

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 28 Jul 2014 19:52:05 +0100

Hi Bob,

> Transport (TLS, DTLS, SRTP (or is that session)).

I think it'll be interesting to see if the work done on new curves
here maps well or badly to lower layers. I do not think that's a
reason to hold up this work though - most lower layer ECC is afaik
done in h/w that is not amenable to change and for which I don't
know of any desire for change. If someone doing 1609 in h/w really
wanted some new curves that'd be interesting for sure, but again
I do not think we should hold up this work for that purpose. Given
the relative timing and differing modus operandi of the various
SDOs involved, trying to incorporate such requirements could easily
add 6 months or more of nothing but delay.

S.

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 28 Jul 2014 12:34:20 -0700

Which remark?

Schnorr signatures are well-known to scale down to 3/4 the size, because they do not rely on collision resistance of the hash function.  See for example, http://www.neven.org/papers/schnorr.pdf.

That you need a hardware accelerator for v2v: well, partly company-confidential reasons.  But back of the envelope, an Edwards Schnorr sig verify is likely to cost around 3000 field multiplies at the 256-bit level, give or take.  Maybe more if you’re memory-constrained.  Weierstrass is slower.  ECDSA is slower.  Each 256-bit field multiply, implemented naively, costs 1024 MACs on an 8-bit machine.  That’s 3 million MACs, and each one is going to cost multiple cycles because of load / store.  Call it 12 million cycles minimum, and you need a few milliseconds latency / inverse throughput tops.  Even a 16-bit micro isn’t enough, since you’re not running at a GHz.

That binary curves are smaller and faster in hardware: see any paper or spec sheet on them.  For example, http://www.ipcores.com/elliptic_curve_crypto_ip_core.htm

About inversion mod r, I’ve implemented it.  A Schnorr verification routine does not need any math mod r, except that it may want to compute or check reduction mod r for speed / malleability reasons.  Depending on the exact form of Schnorr, it may not even need to reserialize points (just to check equality), so it may not need an inversion routine.  If it uses point compression, it will need a square root routine mod p, which can be overloaded into inversion mod p for almost no cost.  If the implementation uses inversion mod p, exponentiation is usually fast enough to be better than extra code for EGCD.

An ECDSA verify needs to invert and multiply mod r.  The inversion can be EGCD, but you would not have needed EGCD otherwise; or it can be a powering ladder.  The powering ladder would take 6% of the time if multiplication mod r is as fast as mod p.  But r isn’t a special form prime, so actually it will take at least twice as long, at least 12%.  Also, the powering ladder will be a different subroutine from the one mod p for the inverse/square root, and r isn’t sparse/special so it’s a longer routine.

In hardware, you have to choose between implementing reasonably fast multiplication mod r and a powering ladder, or implementing EGCD.  Both of these add significant complexity, which is the hardware architect’s enemy.  If you’re using a binary curve, you could have verified with no integer math at all, but now you can’t.

In at least two implementations of “ECDSA”, I've had the signer tweak the signature by inverting s, since there isn’t any reason that the verifier should do it and it doesn’t even cost the signer anything.  Obviously this doesn’t change the security, but it breaks standard point formats.

Likewise Schnorr signing does not need an inversion routine mod r, just multiply and add/sub mod r.  The multiply is used only once, so it can be very slow.  But in ECDSA, an inversion is required.  It needs DPA protection, which will make it slower.  Signatures are in principle faster than verifies, taking perhaps under 1000 multiplies, so the powering ladder starts at about 20% if multiply mod r and mod p are the same, but actually it creeps up toward 35% because it’s not a special-form prime, and perhaps even more because of DPA protection.  Again EGCD is an option, and it’s not required otherwise, and now it has to be blinded for DPA protection as well.

All of this would be fine if ECDSA added security vs Schnorr.  In fact it adds nothing but complexity.

Cheers,
— Mike

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 15:36:26 -0400

> implementation cost. This would be useful for us in the ACE working group.

Actually, I mispoke a bit on this.  ASN.1 can be a syntax to describe 
data.  It is the BER that defines what is really in the object.  So 1609 
as developing a task to create an ASN.1 discription of their format and 
the specific BER to create it.  ETSI will be much happier once this is done.

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 15:41:45 -0400

> involve a chip with 32-bit.

It is nice to state this and your following items. Yet 8 bit devices are 
being shipped at a greater rate and beind designed in smaller 
footprints. These have network connections; not necessary IP. I am 
seeing new designs limited to 32K memory. I had one vendor just last 
fall state that was a stretch for them (MEMEs powered).

The thing I have learned about things on the internet is they come and 
will continue to come in all sorts of sizes and still be considered things.

And yes, specialized hardware might deviate from a nice clean 8 bit 
architecture. I saw one design that just addressed the large addition 
item. But everywhere else it was 8 bits.

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 15:44:37 -0400

> You’re going to need a hardware accelerator for some of these small things.  Eg for v2v safety, the real ask has to be “fast and small and easy in hardware”.  The best solution to this is binary cu…

I cannot parse 'edgy right now'.  Is there a technical definition of this?

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 16:05:14 -0400

> add 6 months or more of nothing but delay.

Well some in ETSI wanted the inclusion of Brainpool curves in 1609, but 
so far that has not gained any significant push.

I get your concern about timing, but If a tie-breaker is needed, 
consider these points.

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 28 Jul 2014 13:25:58 -0700

Binary curves less popular due to patent encumberment but also due to progress in cryptanalysis, though there is not a known break.  The Microsoft NUMS paper, for example, says:

“””
These curves are either defined over prime fields or binary extension fields; on the internet, however, the deployed elliptic curves are mostly defined over prime fields. This can be partially explained by the increasing skepticism towards the security of elliptic curves defined over binary extension fields (justified by recent progress on solving the discrete logarithm problem on such curves [citation]). Therefore, in this work, we only consider elliptic curves defined over prime fields.
“”"

The citation is to Faugère, Perret, Petit, Renault, "Improving the complexity of index calculus algorithms in elliptic curves over binary fields."

http://hal.inria.fr/docs/00/77/60/66/PDF/MAYA2-UPMCINRIA-aaec_1.0.pdf
slides at http://www.cs.bris.ac.uk/eurocrypt2012/Program/Mon/Renault.pdf

Their improved performance and small hardware footprint can make it worthwhile to implement binary curves anyway, but the trends are showing a preference for prime fields.

— Mike

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 28 Jul 2014 16:40:36 -0400

Thank you for this!

---

From: Paul Lambert <[email-masked]>
Date: Mon, 28 Jul 2014 17:33:29 -0700

Thank you for the details below.  One question on a comment you made:
> Depending on the exact form of Schnorr, .

So, what form of Schnorr signatures would you recommend?

Paul

From: Cfrg [mailto:[email-masked]] On Behalf Of Michael Hamburg
Sent: Monday, July 28, 2014 12:34 PM
To: Hannes Tschofenig
Cc: [email-masked]; Robert Moskowitz
Subject: Re: [Cfrg] Curve selection revisited

Which remark?

That you need a hardware accelerator for v2v: well, partly company-confidential reasons.  But back of the envelope, an Edwards Schnorr sig verify is likely to cost around 3000 field multiplies at the 256-bit level, give or take.  Maybe more if you're memory-constrained.  Weierstrass is slower.  ECDSA is slower.  Each 256-bit field multiply, implemented naively, costs 1024 MACs on an 8-bit machine.  That's 3 million MACs, and each one is going to cost multiple cycles because of load / store.  Call it 12 million cycles minimum, and you need a few milliseconds latency / inverse throughput tops.  Even a 16-bit micro isn't enough, since you're not running at a GHz.

About inversion mod r, I've implemented it.  A Schnorr verification routine does not need any math mod r, except that it may want to compute or check reduction mod r for speed / malleability reasons.  Depending on the exact form of Schnorr, it may not even need to reserialize points (just to check equality), so it may not need an inversion routine.  If it uses point compression, it will need a square root routine mod p, which can be overloaded into inversion mod p for almost no cost.  If the implementation uses inversion mod p, exponentiation is usually fast enough to be better than extra code for EGCD.

An ECDSA verify needs to invert and multiply mod r.  The inversion can be EGCD, but you would not have needed EGCD otherwise; or it can be a powering ladder.  The powering ladder would take 6% of the time if multiplication mod r is as fast as mod p.  But r isn't a special form prime, so actually it will take at least twice as long, at least 12%.  Also, the powering ladder will be a different subroutine from the one mod p for the inverse/square root, and r isn't sparse/special so it's a longer routine.

In hardware, you have to choose between implementing reasonably fast multiplication mod r and a powering ladder, or implementing EGCD.  Both of these add significant complexity, which is the hardware architect's enemy.  If you're using a binary curve, you could have verified with no integer math at all, but now you can't.

In at least two implementations of "ECDSA", I've had the signer tweak the signature by inverting s, since there isn't any reason that the verifier should do it and it doesn't even cost the signer anything.  Obviously this doesn't change the security, but it breaks standard point formats.

Likewise Schnorr signing does not need an inversion routine mod r, just multiply and add/sub mod r.  The multiply is used only once, so it can be very slow.  But in ECDSA, an inversion is required.  It needs DPA protection, which will make it slower.  Signatures are in principle faster than verifies, taking perhaps under 1000 multiplies, so the powering ladder starts at about 20% if multiply mod r and mod p are the same, but actually it creeps up toward 35% because it's not a special-form prime, and perhaps even more because of DPA protection.  Again EGCD is an option, and it's not required otherwise, and now it has to be blinded for DPA protection as well.

Cheers,
- Mike

Ciao
Hannes

Actually, one more thing: in constrained environments, you really want Schnorr instead of ECDSA.  That extra inversion mod r is a giant pain.  It's slow and often doesn't share code with anything.  Plus Schnorr can go down to 3/4 the size if necessary.

Cheers,
- Mike

You're going to need a hardware accelerator for some of these small things.  Eg for v2v safety, the real ask has to be "fast and small and easy in hardware".  The best solution to this is binary curves, though they are considered slightly edgy right now.

Cheers,
- Mike

---

From: Paul Lambert <[email-masked]>
Date: Mon, 28 Jul 2014 18:18:00 -0700

]PS: Regarding the ASN.1 format I am wondering whether the IEEE has done
]some more detailed analysis of the over-the-wire and the software
]implementation cost. This would be useful for us in the ACE working
]group.
I know of one IEEE group that is working on raw representation of a point
for Curve25519.
In another - X.509/PKIX formats are proposed largely because they exist.

I'm partial to opaque non-ASN.1 myself.

Paul

]
]
]
]On 07/28/2014 07:05 PM, Michael Hamburg wrote:
]> You're going to need a hardware accelerator for some of these small
]> things.  Eg for v2v safety, the real ask has to be "fast and small and
]> easy in hardware".  The best solution to this is binary curves, though
]> they are considered slightly edgy right now.
]>
]> But yeah, 8-bit processor performance is important too.
]>
]> Cheers, - Mike
]>
]> On Jul 28, 2014, at 7:58 AM, Robert Moskowitz
]> <[email-masked]> wrote:
]>
]>> The whole world is NOT TLS.  For example I am working in IEEE 1609
]>> which is Vehicle-to-vehicle safety communications and their need is
]>> for signed data objects that are quickly generated and verified (you
]>> have ~100ms from the braking event to all the cars being able to act
]>> on that information).  I also work in IEEE 802.15.4 highly
]>> constrained devices (some much smaller than what many IETF groups
]>> accept as their lower limit).
]>>
]>> 8 bit processors are the norm, and NO, Dr. Moore is NOT going to
]>> change that.  Lower energy demand is much higher on the design plan
]>> than faster processing.  Also whatever is done will be running on
]>> fielded devices for the next 10 - 20 years.  Hardware acceleration is
]>> acceptable, but that could make in-field corrections impossible.
]>> Over-the-air firmware updates may also be impossible (802.15.4k is
]>> 40kb/s) or only done in the dealership (yes!  another recall!).
]>>
]>> So getting on to my thoughts of curve selection requirements for the
]>> world of small:
]>>
]>> 1) Low over-the-air demands.  Every BIT counts.  We have to live with
]>> 32 bytes; but 64 bytes may be too much.  Oh, IEEE 1609.2 has its own
]>> 'certificate' and signature format as even the standard
]>> asn.1 is too wasteful of the very limited channel.  This applies also
]>> in 802.15.4 where adding another MAC frame might mean that the whole
]>> thing fails because now it is more likely that one frame got lost.
]>>
]>> 2) Easy/size of implementation.  There has been lots of chatter here
]>> about how NIST p256 can be implemented wrongly.  Here it is of
]>> greater concern, as it might require a physical swap-out to correct
]>> an implementation error.  Manufacturers look at the cost of a
]>> programmer to save 5K code cheaper than that extra 5K footprint.
]>> So little code and easy to code.  This world is extremely price
]>> sensitive.
]>>
]>> 3) Performance on an 8 bit  processor.  Performance is measured in
]>> time and energy.  In-vehicle devices tend to have a ready source of
]>> electrons (except for tire gauges!), but some devices have limited
]>> battery (your front door lock) or NO battery (MEMEs energy harvesters
]>> on bridge stress sensors).  So low energy is as important as quickly
]>> done.  Here 10% faster IS 10% faster; and it could make a
]>> life-or-death difference. (In Positive Train Control, the automatics
]>> MUST take over if the human can no longer respond in time and bullet
]>> trains can take 7Km to stop safely)
]>>
]>> 4) preserving ECDSA and ECDHE.  This is what is currently in use, and
]>> in some cases written into regulations (urgh), so we have to still
]>> keep them working.  But if something 'new' and provably good makes a
]>> big difference in one of the previous needs I suspect there will be
]>> an attentive audience.
]>>
]>> I have tried to keep things general so as not too much to limit
]>> choices.  I never claimed to be a crytographer or to have the math
]>> skills to evaluate the various contenders.  Others working in this
]>> area might have their own reading on the needs of constrained
]>> devices/communications.
]>>
]>> But please just don't solve this for TLS on octo-core 64-bit systems.
]>>
]>>
]>> On 07/25/2014 01:10 AM, Benjamin Black wrote:
]>>> Inspired by some comments from other and in hopes of returning to a
]>>> more productive debate rather than the pointed back and forth, of
]>>> which I am absolutely guilty, I'm suggesting a few constraints.
]>>> These are not priority ordered and none of them deal with the math,
]>>> instead focusing on process and practice.
]>>>
]>>> 1) As we are discussing this in the context of TLS, the performance
]>>> of various kx options must be evaluated for ECDHE as typically
]>>> deployed. ECDH is neither common nor recommended in the TLS BCP
]>>> draft. In addition, I hope there will be discussion of benchmarking
]>>> methodology, with the understanding the ultimate choice is for the
]>>> CFRG chairs.
]>>>
]>>> 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.
]>>>
]>>> 3) The timeframe for a decision constrains the scope of this
]>>> process. If a decision is desired within a few months, then it is
]>>> difficult to include options beyond new curves. If a decision can
]>>> take a year, new algorithms could be considered. Given the
]>>> importance, impact, and contentiousness of new algorithms, I believe
]>>> it would be difficult to complete a thorough, careful algorithm and
]>>> curve selection process in a short amount of time.
]>>>
]>>> 4) The precise set of security levels needed should be specified in
]>>> advance (whether by TLS or CFRG) and curve recommendations delivered
]>>> together for all levels. A stated goal is to use these curves in new
]>>> drafts, and it minimizes work to specify all security levels for a
]>>> proposal in the same draft. This is strictly a practical matter
]>>> recognizing the chairs and area directors have limited bandwidth and
]>>> implementors can get everything done in a single go.
]>>>
]>>> 5) Selections must efficiently support TLS 1.2. Adoption of new
]>>> curves, and potentially new algorithms, can't be gated on completion
]>>> and widespread deployment of TLS 1.3.
]>>>
]>>> 6) Drop-in replacement for the NIST curves is _not_ a requirement in
]>>> this process.
]>>>
]>>> 7) I don't think the chairs are signing up for a full-on, NIST-style
]>>> selection competition and we should aim to keep things are
]>>> lightweight as possible while still achieving the required level of
]>>> rigor. I hope they will address this point soon.
]>>
]>> _______________________________________________ Cfrg mailing list
]>> [email-masked] http://www.irtf.org/mailman/listinfo/cfrg
]>
]> _______________________________________________ Cfrg mailing list
]> [email-masked] http://www.irtf.org/mailman/listinfo/cfrg
]>

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 28 Jul 2014 23:48:33 -0700

> So, what form of Schnorr signatures would you recommend?
Let x be the secret key, g^k the nonce, e = H(stuff) the challenge and s 
= k - xe the response.

If you want short signatures it has to be (e,s).  Otherwise, (g^k,s) is 
slightly faster and batchable.    The hash should be H(pubkey||g^k||m) 
to prevent collision attacks, because you can and there's little downside.

I don't think there's a good case for setting s = ke - x.  It may resist 
some power attacks more easily, but it increases the attack surface and 
prevents optimizations.

-- Mike

---

From: Robert Ransom <[email-masked]>
Date: Tue, 29 Jul 2014 04:14:15 -0700

> is smaller than C=189 and this helps to "manage" the carries.

Actually, the main argument for p = 2^255 - 19 is that Curve25519 is
the de-facto standard curve for high-performance ECC in a group of
near-256-bit order.  Part of the reason for that is that implementers
have, in practice, been able to rely on the small value of what you
denote as “C” for that field in optimizing their software, so no one
has felt a need to switch to a different field of that form for
performance reasons.

(Mike Hamburg introduced ‘special Montgomery primes’ and showed
evidence that they can provide better performance in some
implementations than the Curve25519 coordinate field in
<https://eprint.iacr.org/2012/309.pdf>, but that's a different form of
prime.)

> A rough estimate here is 5% penalty.

As Dr. Bernstein has pointed out, a larger value of C requires 3*n
carries instead of n carries (see
<https://moderncrypto.org/mail-archive/curves/2014/000237.html>), and
carries have high latency (see section 4, subsection ‘Reduction’ of
naclcrypto).

> accomplish this within a subset of n limbs.

So you expect greater implementation effort and complexity to reduce
the added cost, but not eliminate it?

> known to speeds up RSA operations for generic F(p)s. )

As I said, the vectorization strategy used in the neoncrypto paper is
incompatible with 251-bit moduli.  That strategy requires pairing
together limbs of the same size, so that a vectorized shift operation
can be used to carry out of both limbs at the same time.

In RSA, where (in your notation) C is necessarily huge, there is no
performance penalty from making C a few bits larger, so it's easy to
lengthen the modulus and make every limb the same size, so it's easy
to vectorize carries across any pair of limbs.  But that's not very
relevant to the primes used for fast ECC.

Do you see any benefit of p = 2^256 - 189 over p = 2^255 - 19 that you
believe offsets the costs of switching to a different coordinate
field?

Robert Ransom

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 30 Jul 2014 00:24:32 -0700

> has felt a need to switch to a different field of that form for

Yes, I accept it.

> the added cost, but not eliminate it?
I think it's fair to say that lower C will be faster if you only 
consider F(p) ( multiplies and squares; the additions/subtractions don't 
matter).

> relevant to the primes used for fast ECC.
That's correct. For RSA with SSE you do similar things you do here, but 
the reduction is generic and slow.

> believe offsets the costs of switching to a different coordinate

They are :
* aesthetics
* it happened that square root of  p = 2^255 - 19 requires 
multiplication by a sqrt(-1) in half the cases when decompression is 
involved.

Both are tolerable from aesthetics point of view IMO if we (effectively) 
standardize on p = 2^255 - 19. p = 2^255 - 19's slightly higher 
performance than 2^256 - 189 should balance *sqrt(-1) out.

( Compare this with 2^414-17, which won't be trivial to match with other 
algorithms. )

---

From: Robert Ransom <[email-masked]>
Date: Wed, 30 Jul 2014 02:36:12 -0700

> performance than 2^256 - 189 should balance *sqrt(-1) out.

What do you mean by “aesthetics”?  (My aesthetic sense may have been
warped by seeing how these fields are implemented -- 2^255-19 and
2^414-17 are quite pretty to me.)

As for the slightly more annoying square-root algorithm modulo
2^255-19, (a) that's *much* better than the P-224 field (already
IETF-approved as a TLS NamedCurve), and (b) that's better than having
a trade-off between using the a=-1 formulas (and saving 1M per scalar
limb in Edwards form) and having a complete formula available for
arbitrary points.  I think it's unfortunate that 2^414-17 is a 3mod4
field rather than a 5mod8 field.

> ( Compare this with 2^414-17, which won't be trivial to match with other

What do you mean by “match with other algorithms”?

If you're referring to ‘security level’:

* Stream-cipher keys are found by brute-force preimage search;
discrete logarithms in strong EC groups are computed by brute-force
collision search on the function m*P + n*Q.  The preimage-search
attack on a stream cipher can attack multiple target keys at the same
time at no extra cost, and its probability of finding any of the
target keys is linear in the number of operations performed.  The
discrete-logarithm attack targets a single key at a time (and cannot
find the first of multiple targets at reduced cost), and its
probability of finding the target key increases slower than linearly.
(See Dr. Bernstein's bruteforce paper for the engineering details of
preimage search, then see his ecc2k130 paper for the details of
discrete logarithms, though that paper targets a curve with
automorphisms.)  Thus, a curve group ‘at the n-bit security level’
should always be used with a stream cipher whose key is longer than n
bits.

* The only reason that people use AES keys shorter than 256 bits is
that NSA chose a cipher which uses more rounds (and is thus slower)
for longer keys.  If AES-256 ran at the same speed as AES-128,
everyone would rightly use 256-bit keys, regardless of the difficulty
of breaking the public-key algorithm used with it.

Robert Ransom

---

From: Robert Ransom <[email-masked]>
Date: Wed, 30 Jul 2014 02:41:08 -0700

On 7/30/14, Robert Ransom <[email-masked]> wrote:

> discrete logarithms,

Oops.  His paper that explains the discrete-logarithm algorithm is ecc2x.

Robert Ransom

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Jul 2014 15:47:52 -0400

> involve a chip with 32-bit.

Sorry, no, that does not help at all. The only way to reduce the
number of 8 bit processors would be to burn down the fabs.

The problem is that when the price on the 32 bit processor drops to
the price of the 8 bit, the 8 bit processor also drops in price. And
then it proliferates to another layer of devices. Which is why the
number of 6502 and Z80 processors has climbed exponentially since the
80s.

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 31 Jul 2014 09:43:10 -0400

> number of 8 bit processors would be to burn down the fabs.

And Bastille Day has come and gone.  We will have to wait another year  :)

---

From: Russ Housley <[email-masked]>
Date: Thu, 31 Jul 2014 12:56:43 -0400

We seem to have gone away from discussing requirements.  Can we get back to that?

I would like to see us use of the same curve for digital signature and key agreement.  This provides obvious modularity, and it seems to fit well with the security protocols that already have support for ECC.

Russ

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 31 Jul 2014 13:18:40 -0400

> I would like to see us use of the same curve for digital signature and key
> agreement.  This provides obvious modularity, and it seems to fit well with
> the security protocols that already have support for ECC.

I don't want this requirement because I'd like to use 25519 for DH-style key exchange, without having to give up whatever "standard" curves are being used for signature.  I find the "system" approach to Curve25519 appealing, and the efficiency -- where we might have 100's of hosts on a single IP address with their own PFS requirements -- compelling.

	/r$

--  
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: [email-masked] Twitter: RichSalz

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 31 Jul 2014 15:26:13 -0400

> I don't want this requirement because I'd like to use 25519 for DH-style key exchange, without having to give up whatever "standard" curves are being used for signature.  I find the "system" approa…

I don't see that there is a need for a WF128 digital signature scheme
that is backwards compatible.

For existing uses of Digital Signatures where I am currently using
RSA2048 I will switch to WF256 curves and those are the ones where
backwards compatibility matters. There isn't a security argument to
switch from RSA2048 to curve25519 and I don't see the performance
argument as being a good one for where we are already using crypto.

It does make sense to do digital signatures for a WF128 curve because
there may well be applications that a higher performance curve will
enable.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 31 Jul 2014 15:52:11 -0400

> There isn't a security argument to switch
> from RSA2048 to curve25519 and I don't see the performance argument as

I'm talking strictly about Curve25519 as a DH protocol.  I am not talking about Ed25519 as a signature mechanism. Sorry for any confusion, but this follows the documents and terminology used by djb.  So to me switching from RSA2K to Curve25519 is like switching from coffee to a bicycle.

	/r$