Subject: Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib, and openssl-master

From: Andrey Jivsov <[email-masked]>
Date: Wed, 08 Oct 2014 18:01:26 -0700

Now that the P-256 enhancements are in the OpenSSL tree, let commands 
speak for themselves.

Type in a Linux terminal on a Haswell machine (no HT, no 
SpeedStep/Turboboost) and observe:

1. P-256:

$ git clone git://git.openssl.org/openssl.git A
$ cd A
$ ./config
$ make && apps/openssl speed ecdhp256

15078.1 op/s

2. X25519:

$ git clone https://github.com/brainhub/curve25519-donna.git B
$ cd B
$ make speed-curve25519-donna-c64 && ./speed-curve25519-donna-c64

17289.4 op/s

-----------------------------

17383.6 / 15168.1 = 14.6% faster

The difference is about the cost of point decompression/coordinate 
conversion (e.g. Edwards coordinate conversion to Montgomery + point 
multiplication would have about the same performance as P-256 point 
multiplication).

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 8 Oct 2014 19:05:18 -0700

Whoa, they improved the performance by 50% since the paper and initial patch?!

> On Oct 8, 2014, at 6:01 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> Now that the P-256 enhancements are in the OpenSSL tree, let commands speak for themselves.
> 
> Type in a Linux terminal on a Haswell machine (no HT, no SpeedStep/Turboboost) and observe:
> 
> 1. P-256:
> 
> The difference is about the cost of point decompression/coordinate conversion (e.g. Edwards coordinate conversion to Montgomery + point multiplication would have about the same performance as P-256 point multiplication).
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 08 Oct 2014 22:02:55 -0700

> Whoa, they improved the performance by 50% since the paper and initial patch?!

on 09/03/2014 I reported 40% advantage of Curve25519-donna 
(17384.8/12348.9=1.40). Now it's 14% (17383.6/15168.1=1.146). That's on 
an AVX2 machine.

On my older i5 machine (not an AVX2 machine) the ratio is also improved. 
With the same instructions as quoted below:

was 14131.5/5231.7=2.7 (reported on 09/03/2013)
now: 14251.3/11105.2=1.27
(apparently due to Montgomery-style assembler code specialized for P-256 
prime)

This is even more interesting. These performance improvements 
apparently cover most of x86 CPUs in use today, clients and servers.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Oct 2014 22:05:48 -0700

On Wed, Oct 8, 2014 at 10:02 PM, Andrey Jivsov <[email-masked]> wrote:
> (17384.8/12348.9=1.40). Now it's 14% (17383.6/15168.1=1.146). That's on an
> AVX2 machine.
>
> This is even more interesting. These performance improvements apparently
> cover most of x86 CPUs in use today, clients and servers.

Wouldn't the speedups from reducing the number of field operations by
changing the curve shape stack on top of these? I don't really see the
relevance to picking which wire format to use.

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

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 08 Oct 2014 22:47:14 -0700

> relevance to picking which wire format to use.
Just to be clear, I was saying that the apparent factor of ~2 
improvement of P-256 on non-AVX2 machine appears to be due to highly 
tuned Montgomery modulo prime reduction code, hardcoded for P-256 prime.

Montgomery curve has fewer underlying filed operations. The performance 
benefit will be lower than due to prime reduction/hardware/instruction 
assistance. However, given that the numbers are fairly close now, we can 
expect change in leadership depending on the mix of features. For 
example,  a hypothetical mix of the P-256 underlying field operations 
found in the code that I timed and a Montgomery curve on top would 
probably move such an implementation into the lead in the tests I performed.

P-256 has an advantage that it's in standards, widely deployed, can do 
point additions (without penalty of coordinate conversion), and you can 
get X.509 certs with it. It would have been easier to argue on its 
disadvantages if it had worse performance than it appears to have. I am 
aware of other disadvantages of P-256.

In your other e-mail, Watson, regarding AVX2/vector operations + X25519, 
it's an interesting question. The issues here are:
* will this hide some benefits of the 2^n-1 prime?
* increase code complexity?
* it seems that this is of no use to mobile devices (in the near future 
anyway)
* but servers will benefit from this.

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 08 Oct 2014 23:52:18 -0700

On 10/8/2014 10:47 PM, Andrey Jivsov wrote:
>
> Montgomery curve has fewer underlying filed operations. The 
> performance benefit will be lower than due to prime 
> reduction/hardware/instruction assistance. However, given that the 
> numbers are fairly close now, we can expect change in leadership 
> depending on the mix of features. For example,  a hypothetical mix of 
> the P-256 underlying field operations found in the code that I timed 
> and a Montgomery curve on top would probably move such an 
> implementation into the lead in the tests I performed.
Yeah, or getting Shay and Vlad to hand-tune an x25519 implementation :-)
> point additions (without penalty of coordinate conversion), and you 
> can get X.509 certs with it. It would have been easier to argue on its 
> disadvantages if it had worse performance than it appears to have. I 
> am aware of other disadvantages of P-256.
>
> In your other e-mail, Watson, regarding AVX2/vector operations + 
> X25519, it's an interesting question. The issues here are:
Possibly.  You probably won't be able to use Langley and Bernstein's 
carry handling techniques, but fewer coefficients is always good.
> * increase code complexity?
Compared to a version without handwritten asm?  The field arithmetic 
will definitely be more complex.
> * it seems that this is of no use to mobile devices (in the near 
> future anyway)
Curve25519 performs quite well on ARM NEON.
> * but servers will benefit from this. 

Cheers,
-- Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 9 Oct 2014 19:54:18 -0700

benefit will be lower than due to prime reduction/hardware/instruction
assistance. However, given that the numbers are fairly close now, we can
expect change in leadership depending on the mix of features. For example,
a hypothetical mix of the P-256 underlying field operations found in the
code that I timed and a Montgomery curve on top would probably move such an
implementation into the lead in the tests I performed.
> Yeah, or getting Shay and Vlad to hand-tune an x25519 implementation :-)

BTW, I may be wrong on this one, but the latest performance boost I
reported yesterday is due to OpenSSL team, I believe.

>> P-256 has an advantage that it's in standards, widely deployed, can do
point additions (without penalty of coordinate conversion), and you can get
X.509 certs with it. It would have been easier to argue on its
disadvantages if it had worse performance than it appears to have. I am
aware of other disadvantages of P-256.
> Compared to a version without handwritten asm?  The field arithmetic will
definitely be more complex.

... and the combined code not so neat ...

anyway)
> Curve25519 performs quite well on ARM NEON.

My list is regarding vector operations. I was alluding that one of the
driving forces for new ECC is its excellent performance on mobile devices
but many of them don't have vector athithetic. Therefore, there is no
immediate ownership apparent of such vectorized code (until it is in
OpenSSL :-)).