Subject: Re: [Cfrg] revised requirements for new curves

From: Adam Langley <[email-masked]>
Date: Tue, 9 Sep 2014 13:23:06 -0700

(I'm commenting with my Google hat on. I'm on vacation at the moment
and haven't circulated this around internally but I believe that this
reflects our position. Where I'm less sure I've used "I".)

> SE5. Required: each set of curve parameters should be generated by a
> well-defined procedure that allows only a limited and quantified amount of
> flexibility. If the selected procedure involves the choice of an initial
> seed, then the seed will be selected by multiple independent parties using
> a procedure having the property that no collusion of all but one or fewer
> of the parties can exert any control over the chosen seed. [RC]

Although flexibility should be eliminated where possible, we believe
that forgoing sensible optimisations because of a fear that someone
might know a magic attack on a subset of curves and might be guiding
the selection them that would be a mistake. We are not looking for a
replacement for P-256 because we seriously worry that the NSA
backdoored it. We're looking for a replacement because we think that
we can get something much faster and simpler.

Past a point, constraining the curve based on that fear isn't valuable to us.

> SE6. Required: the selected curves should provide levels of security that
> match to a good approximation 128-bit, 192-bit and 256-bit security
> levels, as these levels are currently commonly understood in the wider
> security community. [NC]

We don't want three curves. I'm not completely convinced that we even
want two, but two is plausible. For symmetric primitives, matching
powers of two makes sense because it fits well with software
implementation. For curves that motivation is much weaker.

Above the 120ish bit level one is no longer fighting stronger
attackers, but hedging against a breakthrough (but not too much of
one). Matching 192 or 256 bit security levels is a *misunderstanding*
in the wider community, and is thus of the lowest priority.

> IP2. Desired: securely, simply and efficiently implementable world-wide in
> a patent-free manner. [RC]

This is probably a requirement for us, unless the "royalty-free" was
legally strong, didn't include registration etc. I cannot specify
exactly what we would require in that case because it's not my area.

> IN2. Required: minimise work needed to generate suitable OBJECT
> IDENTIFIERs for Subject Public Key Information Fields, as defined in RFC
> 5480 (PKIX). [C]

I don't think that I understand what this means, or rather, I can't
imagine how a curve could fail it. By having a name so long that it
caused tooling problems perhaps?

> IN2. Desired: usable with minimal changes to existing IETF RFCs for CMS,
> SSH, IKE, IKEv2, Kerberos PKINIT. [RC]

The cost of making a change in these systems is largely fixed. I think
that trading off too much to make the change smaller is often a false
economy. If the thinking here was to try and reuse ECDSA with new
curves for reasons of easy of patching then I think that would be an
example of such a false economy.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 10 Sep 2014 10:15:19 +0000

Adam,

Thanks for interrupting your holiday to participate in this discussion.

>Past a point, constraining the curve based on that fear isn't valuable to

It's good to get Google's view on what is the main driver for this
activity.

>implementation. For curves that motivation is much weaker.

Should we infer, then, that Google would prefer at most a single curve at
each security level (rather than, say, two)?

>exactly what we would require in that case because it's not my area.

Noted.

>caused tooling problems perhaps?

William Whyte pointed out more or less the same thing. This was intended
more as a placeholder to remind us that we will have some PKIX work to do,
and as a contrast to the starting requirements (from David McGrew) which
looked more onerous (to me) at first. Some rewording of this requirement
would clearly be helpful.

>example of such a false economy.

Thanks for sharing this perspective. My feeling is that a bit more work is
needed (possibly by me, but maybe others already did it) to dig into these
RFCs and see what work would be implied with different levels of change to
curves and algorithms.

Enjoy the rest of your holiday,

Cheers

Kenny 

>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Adam Langley <[email-masked]>
Date: Wed, 10 Sep 2014 09:52:59 -0700

> each security level (rather than, say, two)?

I was suggesting that only one or two curves be approved in total.

Consider the current situation: in terms of having a good
implementation base, P-{256|384|521} are significantly above the rest.
Of those, P-256 is the workhorse. There is some use of P-384,
generally, from what I've seen, for long-lived ECDSA keys (with
dubious justification). P-521 is hugely less common than either of the
other two.

In order to get a performant, solidly constant-time implementation,
one needs, in practice, to hand craft the field operations for an
elliptic curve, which is quite a lot of work. That's been done for
P-256 in many cases, but much less so for P-384. (Since P-384 is
substantially used for ECDSA verification, constant-time is less of a
worry there.)

Diversity of curves dilutes the capacity for building, auditing and
verifying good implementations. Also, the precomputed tables for high
speed signing take too much space in some clients if there are several
of them, and then implementations need to support and test two build
modes: fast and small.

Many systems will never be able to drop support for P-256 and 384, so
these new curves can only add to the implementation burden. I think
that a single curve to replace P-256 can pay its way by being faster
and simpler. I'm much less sure about a second, and pretty confidently
against a third.

Cheers

AGL

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 14 Sep 2014 10:22:51 -0400

On Tue, Sep 9, 2014 at 4:23 PM, Adam Langley <[email-masked]> wrote:

> backdoored it.

Well maybe not. BUT one of the main advantages of moving to new curves
is that the deployment of ECC has been gradual and incremental and has
taken an enormous amount of time. And one of the main points to a flag
day is not just burning the old ones, it is getting everyone to buy
and hang the new.

>We're looking for a replacement because we think that

Case in point here, can anyone who has these facts at their disposal
tell us what sort of leverage random curves are believed to provide
over primes close to a power of 2.

The issue here is cryptographic leverage. I am prepared to do more
work to increase the work factor for the attacker. But should I pick
(say) a fast curve with 256 bits or a slower curve with 192 bits?

If the two curves give exactly the same work factor or take exactly as
long with different security, then the comparison is easy. But things
rarely turn out so simple, chances are that the fast but bigger curve
turns out to be a little bit slower and a bit more secure than the
smaller one... oops.

The basis for comparison is a little tricky...

If I am doing RSA 2048 then I an doing four times the work of RSA 1028
But if I am doing a symmetric cipher then 256 bits is more likely to
take about double 128

Oh and RSA 2048 does not give anywhere close to the square of the work
factor of RSA1024 (i.e. double the bits). In fact that is one of the
main reasons we have to look beyond RSA.

But if we plot the points on graphs of defender effort vs attacker
work factor and look at the curves we can probably see quite easily
what we are buying with the different approaches.

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 14 Sep 2014 15:59:01 -0700

> On Sep 14, 2014, at 7:22 AM, Phillip Hallam-Baker <[email-masked]> wrote:
> 

I hacked up some plots for ECDH (protected variable-base scalarmul) on Intel Sandy Bridge and Cortex A8, A9 platforms at

http://ed448goldilocks.sourceforge.net/comparison/ <http://ed448goldilocks.sourceforge.net/comparison/>

Lots of caveats follow!

It’s important to note that the curves aren’t all on equal footing here.  The measurements are from the NUMS paper, the Curve41417 paper, `openssl speed`, the Goldilocks bench utility (on SBR and Tegra 2); curve25519-donna (Curve25519 on Tegra2), SUPERCOP (Curve25519 on other platforms, Goldilocks on A8+NEON).  Of these, SUPERCOP and `openssl speed` almost certainly give less favorable numbers.

I haven’t fully implemented Ed480-Ridinghood.  The point in the graph is an estimate based on the field arithmetic being identical to Ed448-Goldilocks on 64-bit except for the shift amounts.  This is also why it doesn’t appear in the 32-bit numbers: it cannot use the same arithmetic on 32-bit platforms, but instead would take ~50% longer, which is why I didn’t propose it.

Curve25519, Curve41417, Goldilocks, and the MS “mont” curves are performing point (de)compression, but OpenSSL and the NUMS “ed” curves are not.  Point decompression would be about a 10% performance hit, but this hit may be mitigated (for stronger curves) or negated (for weaker ones) by the use of the Montgomery ladder.  Some of the software is also hashing the results and some are not.  (Goldilocks hashes; NUMS do not; I don’t know about the others.)  Goldilocks tests whether points are on the curve or twist while Curve25519 does not, but this test is cheap and adds little security.

The software benchmarked here has different amounts of optimization and is designed for different platforms.  Curve41417 has only been benchmarked on Cortex A8+NEON, and the NUMS curves have only been benchmarked on SBR.

The OpenSSL curves don’t include the latest optimizations, since they’re from 1.0.1 or 1.0.1f, compiled however the OS maintainers decided.

Curve25519-donna is not at all optimized for ARM, but I don’t have any other vectorless ARM numbers to go by, since I couldn’t get Curve25519 working in SUPERCOP on that platform.

I expect that the NUMS curves would perform passably well in scalar code on the Cortex-A9, because UMAAL can help with the carry handling.  But they would be at a disadvantage in NEON, where carry handling is much more expensive.  So I would expect the situation on Tegra 2 (with its fast scalar core but no NEON) to be comparable to that on Sandy Bridge, but on A8+NEON I would expect it to be considerably worse for the NUMS curves.

In the other direction, I expect that the numbers for Curve41417 would be similar on Sandy Bridge to how they are on NEON.  Field arithmetic is probably comparable to Ed448-Goldilocks, just as on NEON, so curve ops should be about 8% faster due to the 8% smaller curve.

I know that variable-base scalar multiplication is not the only benchmark which matters, but it’s consistently available across many curves.

I believe that all of the software contains comparable levels of side-channel protection.

Cheers,
— Mike

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 14 Sep 2014 20:22:29 -0400

Well one thing that leaps out is that I can get 512 bits of the NUMS
curves for the price of 256 bits of the NIST curves. And that is a BIG
difference as far as I am concerned.

The performance difference between the NUMS curves and the various
'cherry picked' primes is visible but much less significant.

On Sun, Sep 14, 2014 at 6:59 PM, Michael Hamburg <[email-masked]> wrote:
> I hacked up some plots for ECDH (protected variable-base scalarmul) on Intel
> Sandy Bridge and Cortex A8, A9 platforms at
>
> http://ed448goldilocks.sourceforge.net/comparison/
>
> Lots of caveats follow!
>
> It’s important to note that the curves aren’t all on equal footing here.
> The measurements are from the NUMS paper, the Curve41417 paper, `openssl
> speed`, the Goldilocks bench utility (on SBR and Tegra 2); curve25519-donna
> (Curve25519 on Tegra2), SUPERCOP (Curve25519 on other platforms, Goldilocks
> on A8+NEON).  Of these, SUPERCOP and `openssl speed` almost certainly give
> less favorable numbers.
>
> I haven’t fully implemented Ed480-Ridinghood.  The point in the graph is an
> estimate based on the field arithmetic being identical to Ed448-Goldilocks
> on 64-bit except for the shift amounts.  This is also why it doesn’t appear
> in the 32-bit numbers: it cannot use the same arithmetic on 32-bit
> platforms, but instead would take ~50% longer, which is why I didn’t propose
> it.
>
> Curve25519, Curve41417, Goldilocks, and the MS “mont” curves are performing
> point (de)compression, but OpenSSL and the NUMS “ed” curves are not.  Point
> decompression would be about a 10% performance hit, but this hit may be
> mitigated (for stronger curves) or negated (for weaker ones) by the use of
> the Montgomery ladder.  Some of the software is also hashing the results and
> some are not.  (Goldilocks hashes; NUMS do not; I don’t know about the
> others.)  Goldilocks tests whether points are on the curve or twist while
> Curve25519 does not, but this test is cheap and adds little security.
>
> The software benchmarked here has different amounts of optimization and is
> designed for different platforms.  Curve41417 has only been benchmarked on
> Cortex A8+NEON, and the NUMS curves have only been benchmarked on SBR.
>
> The OpenSSL curves don’t include the latest optimizations, since they’re
> from 1.0.1 or 1.0.1f, compiled however the OS maintainers decided.
>
> Curve25519-donna is not at all optimized for ARM, but I don’t have any other
> vectorless ARM numbers to go by, since I couldn’t get Curve25519 working in
> SUPERCOP on that platform.
>
> I expect that the NUMS curves would perform passably well in scalar code on
> the Cortex-A9, because UMAAL can help with the carry handling.  But they
> would be at a disadvantage in NEON, where carry handling is much more
> expensive.  So I would expect the situation on Tegra 2 (with its fast scalar
> core but no NEON) to be comparable to that on Sandy Bridge, but on A8+NEON I
> would expect it to be considerably worse for the NUMS curves.
>
> In the other direction, I expect that the numbers for Curve41417 would be
> similar on Sandy Bridge to how they are on NEON.  Field arithmetic is
> probably comparable to Ed448-Goldilocks, just as on NEON, so curve ops
> should be about 8% faster due to the 8% smaller curve.
>
> I know that variable-base scalar multiplication is not the only benchmark
> which matters, but it’s consistently available across many curves.
>

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 14 Sep 2014 17:46:04 -0700

While this is partly true, it’s also an example of the NIST curves not getting an entirely fair shake because I just ran `openssl speed` with whatever was on my Mac, whereas most of the other curves are optimized.

I’ve added teal dots from the Gueron-Krasnov NIST-P256 paper (citing also the Käsper-Langley paper) to show this effect: at least for NIST-P256, the Mavericks OpenSSL release is about 3.4x worse than the state of the art.

— Mike

> On Sep 14, 2014, at 5:22 PM, Phillip Hallam-Baker <[email-masked]> wrote:
>

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 14 Sep 2014 21:03:58 -0700

The chart looks consistent with my measurements
http://www.ietf.org/mail-archive/web/cfrg/current/msg05053.html for x86-64.

Relying on approximate numbers with visual extrapolation and my eye sight:

1. Fully optimized with AVX2:
    365/220=1.66

2. Really apples-to-apples OpenSSL v.s. NUMS, in particular:
* 64 bit C code with uint128
* same author
* code that takes advantage of special structure of the primes
    570/220=2.60

In addition, I timed the #2 scenario on the discontinued Xeon CPU E5540 
@ 2.53GHz, LGA 1366, Nehalem architecture, for similar 2.79 factor (v.s. 
my reference 2.70 for Ivy bridge). I was timing curve25519-donna-master, 
but NUMS/Curve25519 this should not matter when comparing with P-256.

The architecture-neutral C code should demonstrate a factor of about 2.7 
slower performance between P-256 and Curve25519. In the case of OpenSSL 
it must be properly configured. I don't see why ARM code would be 
different here.

The factor of ~5 corresponds to OpenSSL doing Montgomery reduction 
treating NIST prime as a random prime. The factor of 5, therefore, 
corresponds to the code doing Brainpool-style random prime Fp 
operations. Prime-specific optimization should be allowed in both cases 
for fairness.

I've mentioned a couple of times that Curve25519 (and NUMS) are only 50% 
faster than P-256 for AVX2-optimized code. There is a similar unfairness 
present in this claim, however, this is a bit less unfair because:
* the comparison uses the best code easily available today
* there is a chance that Curve25519 optimized for AVX2 will see lower 
payout because the parallelism of AVX2 may reduce the benefit of the 
special structure of the pseudo-Mersenne prime.

The ratio that should be used by default is ~2.7.

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 14 Sep 2014 22:36:02 -0700

> If I am doing RSA 2048 then I an doing four times the work of RSA 1028

As can be seen with timing of openssl speed rsa1024/rsa2048/2048, the 
factor is ~7.5 (e.g. in op.sec: 5940.2/791.2/111.8)

 > But if I am doing a symmetric cipher then 256 bits is more likely to

This is exactly 40% more work with AES in bulk encryption (10 rounds 
v.s. 14, not counting 1 XOR as a round).

> main reasons we have to look beyond RSA.

RSA 2048 and DH 2048 are on the margin of standard security at 110 bits, 
as considered by NIST. There is a measurable penalty for stronger 
security if one were to do the upgrade with RSA/DH/DSA.

1024 EDH in TLS is common today and still the default in OpenSSL.