Subject: [Cfrg] Anyone got figures for Suite B vs CFRG?

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 4 Nov 2015 12:09:02 -0500

I have been trying to find figures comparing the CFRG ECC operations
vs the Suite B curves on the same platform. Don't need exact figures,
just a fair comparison.

My gut feeling is that the Goldilocks curve (448) and P-384 should be
roughly the same speed. How does 448 stack up against P-256 though?

Since 448 has more bits and follows what we now consider to be the
preferable 'rigid' approach, there is a clear case for 448 over P-384
and possibly over P-256.

Rather than looking for all sorts of devious explanations for the
recent NSA advice, it seems most likely to me that they looked at
their objectives and the direction of the market and concluded that
the market is choosing a set of curves that meets their objectives
better than the 2005 Suite B advice.

There isn't much chance that P-256 is going to see further deployment
at this stage. Anyone who wants speed will go for 255-19 and anyone
who wants more security will go for P-384 or 448. So taking it off the
table is a positive move.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 4 Nov 2015 19:50:39 +0200

> roughly the same speed. How does 448 stack up against P-256 though?

For high-speed implementation of P-384, I would expect it to be
very close to Goldilocks in speed (at least according to some back-of-
the-envelope calculations).

But note that openssl implementation of P-384 is hilariously bad
speedwise... Slower than P-521(!). Don't know if it is cache-safe.

And IIRC the openssl P-521 isn't too hot either.

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Nov 2015 02:53:07 +0900

> On 5 Nov 2015, at 2:09 AM, Phillip Hallam-Baker <[email-masked]> wrote:
> 

A fair comparison is hard to get. You can only compare different implementations on specific platforms, and who’s to say that implementation A of algorithm B is as good as implementation C of algorithm D?  Closest we can get is this:
http://bench.cr.yp.to/results-dh.html

The numbers there suggest that both Curve25519 and Curve448 are faster than even P-256. There have been claims made that there are better, more optimized implementations of P-256, but we haven’t seen them yet.

Unfortunately, P-384 is nowhere to be found in those results.

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

---

From: John Mattsson <[email-masked]>
Date: Wed, 4 Nov 2015 17:54:05 +0000

I think these are the best data available:

http://bench.cr.yp.to/results-dh.html
http://bench.cr.yp.to/results-sign.html

Curve448 stack up very nicely against P-256.

- Faster on ECDH (x64)
- Equal on signing and slower on verify (x64) (but these are comparisons
of EdDSA vs. ECDSA as well).

I think P-256 will still grow for several years before curve25519 gets
implemented everywhere.

Cheers,
John

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Nov 2015 02:55:14 +0900

> On 5 Nov 2015, at 2:50 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

That part at least is no longer true.  On my laptop and OpenSSL 1.0.2d I get 10,563 ops/s for P-256, 1,162 for P-384, and 566 for P-521.

Still seems like the 9x factor between P-256 and P-384 is a little too high.

Yoav

---

From: John Mattsson <[email-masked]>
Date: Wed, 4 Nov 2015 17:57:34 +0000

> Unfortunately, P-384 is nowhere to be found in those results.

ecdonaldp384, or?

---

From: "Mehmet Adalier (Antara Teknik)" <[email-masked]>
Date: Wed, 4 Nov 2015 18:02:14 +0000 (UTC)

regarding ECDSA P-256,
taraEcCRYPT(tM) perf on a single core Xeon E5 1275v3 (similar to a circa 2013 i7), 3.5GHz is
Sign:  45,300 ops/secondSign with pre-calculated-random # (allowed by list spec) 63,807 ops/second
verify: 31,805 ops/second.
see presentation: http://csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/session6-adalier-mehmet.pdf
additionally taraEcCRYPT is completely thread safe and scales with additional cores, or can be dispatched on specific cores for background processing.
our P-384 and P-521 implementations use the same core engine (albeit wider register space) and scale.we will be publishing results on these soon.
mehmet
      From: John Mattsson <[email-masked]>
 To: Phillip Hallam-Baker <[email-masked]>; "[email-masked]" <[email-masked]> 
 Sent: Wednesday, November 4, 2015 9:54 AM
 Subject: Re: [Cfrg] Anyone got figures for Suite B vs CFRG?

- Faster on ECDH (x64)

Cheers,
John

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Nov 2015 03:03:08 +0900

> On 5 Nov 2015, at 2:57 AM, John Mattsson <[email-masked]> wrote:
> 
> 

Right, but I was looking at DH results, not signatures. In DH there’s only nistp256, no nistp384.

Of course for signatures ecdonaldp384 seems to be 13.5x slower than ecdonaldp256, so my openssl results are not so out of line. We still don’t know how good those implementations are, but for sure Ed448 is much much faster than P-384.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 4 Nov 2015 20:14:39 +0200

On Thu, Nov 05, 2015 at 02:55:14AM +0900, Yoav Nir wrote:
> That part at least is no longer true.  On my laptop and OpenSSL 1.0.2d
> I get 10,563 ops/s for P-256, 1,162 for P-384, and 566 for P-521.

Might depend on how it is built... On system openssl (1.0.2d apparently)
on my (old) desktop, I get somewhat higher figures for P-256 and P-384,
plus much higher figures for P-521, pushing it quite a bit above P-384 in
speed.

> Still seems like the 9x factor between P-256 and P-384 is a little too high.

Yeah, much too high. Should be more like 3-4x or so.

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Nov 2015 03:25:58 +0900

> On 5 Nov 2015, at 3:14 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

So I recompiled OpenSSL without the assembly-language accelerations to make it “fair”, and now P-256 is just over 2x the speed of P-384, and P-521 is again half the speed. So that makes more sense.

Yoav

---

From: Adam Langley <[email-masked]>
Date: Wed, 4 Nov 2015 10:44:42 -0800

> So I recompiled OpenSSL without the assembly-language accelerations to make it “fair”, and now P-256 is just over 2x the speed of P-384, and P-521 is again half the speed. So that makes more sense.

P-256 has received an order of magnitude more optimisation effort than
P-384. The best reference is figure six of
https://eprint.iacr.org/2013/816.pdf.

Roughly, for a point multiplication (without precomputation of the
point) on an E5-2690 core at 2.9GHz (Sandy Bridge, with TurboBoost
disabled, I think, although I didn't reboot to confirm):

curve25519: 17396 ops/sec
P-256: 10469 ops/sec
P-384: 1075.2 ops/sec

For curve25519 I'm using the version in the Go crypto library. For
P-256 I'm using BoringSSL, which contains Intel's optimised code
(although there are some tricks still to be merged). For P-384 I'm
using BoringSSL, which should be basically the same code as OpenSSL. I
don't have a curve448 to hand.

Cheers

AGL

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 4 Nov 2015 21:11:01 +0200

> don't have a curve448 to hand.

Based on EBATS data, I would guess factor of 3.91, which would be
about 4450 Curve448 ops/sec or so..

(For Haswell and above, the factor is more like 3.25 than 3.91...
Extra instructions 448 implementations use?)

-Ilari

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 4 Nov 2015 15:22:27 -0500

> So I recompiled OpenSSL without the assembly-language accelerations to make it “fair”, and now P-256 is just over 2x the speed of P-384, and P-521 is again half the speed. So that makes more sense.

Thanks all.

I think that makes the case for CFRG well enough. Reading through the
comments in the thread it looks like the following are justifiable:

* CFRG-448 is roughly same speed as P-384 with equivalent implementation effort
* CFRG-448 is roughly same speed as P-256 with likely implementation effort.

I am not really interested in the potential performance as the likely
performance. If we were in a selection contest the potential matters.
Now the selection is over it is much more likely that people are going
to spend their time working out further optimization of CFRG-448 and
CFRG-255 than P-384 or P-256.

The choice of the NIST curves was heavily influenced by a set of IPR
issues that no longer apply. Since then we have new considerations -
rigidity, constant execution speed, etc. The NSA has made it a lot
easier for NIST to sign up to the CFRG curves.

One other point that occurs to me is that constant execution time
might prove to be a chimera as CPU optimizations bite folk in the
butt.

One way to be really sure on private key operations would be to split
the private key with a random number, perform operations separately on
each half and then recombine the result. This probably doesn't slow
the machine down at all if it has multiple cores.

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 4 Nov 2015 17:59:00 -0800

> On Nov 4, 2015, at 12:22 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 
> Thanks all.
> 

Roughly.  However, Gueron and Krasnov’s heavily optimized P-256 has made it into OpenSSL.  So at least on modern Intel platforms, “likely implementation effort” includes something that’s ~twice as fast as Goldilocks.  But on other software platforms, I’d expect CFRG-448 to be a bit faster than P-384 with equivalent effort, and about the same speed as P-256 with likely effort.

> the machine down at all if it has multiple cores.

Lighter-weight blinding techniques are also possible.  As our German colleagues have pointed out, adding a random multiple of the group order slows the computation down by at least 50% for any of the curves in question except P-256.  But Euclidean splitting as (r*a + b), for random small r, should work.

Cheers,
— Mike