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

From: Andrey Jivsov <[email-masked]>
Date: Sat, 16 Aug 2014 18:10:35 -0700

I timed libsodium, curve25519-donna, MSR ECCLib, and openssl-master.

In all cases minor tweaks to the source code were added to measure and 
report the timing. I made sure to time the variable base scalar 
multiplication. I also timed the fixed base multiplication and 
precomputation (only needed for MSR ECCLib).

Operations are reported as operations per second. I used default compile 
options.

MSR ECCLib was slightly faster in variable base operations. It uses 
assembler code.

Interestingly, MSR ECCLib Weierstrass a=-3 curves are only 10% slower 
than curve25519-donna. At the same time all pseudo-Mersenne prime curves 
are ~5 times faster than NIST P-256 (this is better than factor of 2 
back-of-envelope difference in modp multiplication performance)

The factor of 2+ improvement for fixed base calculation in MSR ECCLib is 
impressive. Note, however, the significant penalty that precalculation 
step adds. If the pre-calculation is included in timing, we could do 
~50% more EDH agreements with NIST P-256.

CPU: Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, no AVX2. Fedora Core 20 64 
bit.

https://github.com/jedisct1/libsodium
modified tests in libsodium/test/default to take the timing:
crypto_scalarmult_curve25519_base: 15620.2 op/s
crypto_scalarmult_curve25519: 15602.8 op/s

https://github.com/agl/curve25519-donna:
make ./speed-curve25519-donna-c64 && ./speed-curve25519-donna-c64
63 us, 15722.1 op/s
(also modified to check variable base v.s. generator 9 -- no difference)

OpenSSL 1.0.1e-fips 11 Feb 2013:
openssl speed ecdhp256 (ECDH_compute_key)
  256 bit ecdh (nistp256)   0.0003s   3245.4  op      op/s
and from git://git.openssl.org/openssl.git:
  256 bit ecdh (nistp256)   0.0003s   3406.7  op      op/s

MSR ECCLib 
http://research.microsoft.com/en-us/downloads/149804d4-b5f5-496f-9a17-a013b242c02d/

In the function that prints "Crypto operations: Weierstrass a=-3 over 
GF(2^256-189)":
with variable base (baseecdh_secret_agreement_Jac256) 14047.9 op/sec
with fixed base (ecdh_keygen_Jac256) 35370 op/sec
table precomp (ecdh_generator_table_Jac256) 1284.03 op/sec
table precomp+keygen+variable base 1056.86 op/sec
"ECDH(E) runs in [...] 328926 cycles"

In the function that prints "Crypto operations: twisted Edwards a=-1 
over GF(2^256-189)"
with variable base (ecdh_secret_agreement_Ted256): 17482 op/sec
with fixed base (ecdh_keygen_Ted256) 35370 op/sec: 45762.9 op/sec
table precomp (ecdh_generator_table_Ted256) 1346.98 op/sec
table precomp+keygen+variable base 1195.89 op/sec
"ECDH(E) runs in [...] 261385 cycles"

memcpy of the 32 bytes: 595968511 op/sec, see attached code
( i.e. memcpy count / crypto_scalarmult_curve25519 count = 38042 )

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 17 Aug 2014 10:09:44 -0700

> On Aug 16, 2014, at 6:10 PM, Andrey Jivsov <[email-masked]> wrote:
> 

Thanks for the data!

> In all cases minor tweaks to the source code were added to measure and report the timing. I made sure to time the variable base scalar multiplication. I also timed the fixed base multiplication and precomputation (only needed for MSR ECCLib).
> 
> Operations are reported as operations per second. I used default compile options.
> 
> MSR ECCLib was slightly faster in variable base operations. It uses assembler code.
> 
> Interestingly, MSR ECCLib Weierstrass a=-3 curves are only 10% slower than curve25519-donna. At the same time all pseudo-Mersenne prime curves are ~5 times faster than NIST P-256 (this is better than factor of 2 back-of-envelope difference in modp multiplication performance)
> 
> The factor of 2+ improvement for fixed base calculation in MSR ECCLib is impressive. Note, however, the significant penalty that precalculation step adds. If the pre-calculation is included in timing, we could do ~50% more EDH agreements with NIST P-256.

Precomputation on the curve’s base point shouldn't be included in timing, because it will be hard-coded in a production version.  Handling it will be cheap, unless it’s big enough to cause CPU cache thrashing.

> CPU: Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, no AVX2. Fedora Core 20 64 bit.

Do you know if TurboBoost was on?  That CPU can boost to 3.7 GHz, so the cycle counts could be 12% different one way or another.

> MSR ECCLib http://research.microsoft.com/en-us/downloads/149804d4-b5f5-496f-9a17-a013b242c02d/
> 
> In the function that prints "Crypto operations: Weierstrass a=-3 over GF(2^256-189)":
> In the function that prints "Crypto operations: twisted Edwards a=-1 over GF(2^256-189)"
> <memcpy-timing.c>_______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 17 Aug 2014 12:55:59 -0700

> Precomputation on the curve’s base point shouldn't be included in timing, because it will be hard-coded in a production version.  Handling it will be cheap, unless it’s big enough to cause CPU cach…

That's a possibility. Tables need to be reasonably small to make this 
attractive.

I think the optimal solution will be application-specific.

While powerful servers are good candidates to take advantage of 
pre-computation, they also have the ability to run a separate pipeline 
to produce pre-generated pairs as well, for the entire cost of DH 
protocol done in 1 variable-base scalar multiplication, something that 
the crypto alone cannot possibly beat.

Small systems may care about executable binary size (code+static data), 
memory size, and pre-computation cost.

Also, let's not discard a possibility of a brief ephemeral value re-use.

> Do you know if TurboBoost was on?  That CPU can boost to 3.7 GHz, so the cycle counts could be 12% different one way or another.

I checked my BIOS setting. It says "Intel HT Technology" Not Supported.

I followed:
http://xmodulo.com/2012/06/how-to-find-number-of-cpu-cores-on.html
and also:
http://www.linuxforums.org/forum/red-hat-fedora-linux/155256-3-ways-tell-if-ht-enabled-without-going-through-bios-problems.html

These commands report that I have 1 CPU, 4 cores, 4 processors in Linux. 
I interpret this that I have no Hyperthreading enabled.

I played with a few options in the BIOS that would make the measurements 
constant-time. I noticed one that made a difference: "Intel Turboboost: 
Enabled". It had an effect of boosting the clock speed. With this value 
disabled I get slightly lower op/sec values, but the relationship stayed 
the about the same with all measurements going down.

e.g. before/after:

donna: 15722/14105=1.11
MSR variable base Weierstrass: 14047/12602=1.11
openssl: 3245/3025.2=1.07

The numbers, as seen on the terminal, are at the bottom.

>> http://www.irtf.org/mailman/listinfo/cfrg

[andrey@ivy libsodium]$
crypto_scalarmult_curve25519_base: 14052.8 op/s
crypto_scalarmult_curve25519: 14072.8 op/s

[andrey@ivy curve25519-donna]$
71 us, 14079.1 op/s (fixed base)
70 us, 14105.4 op/s (variable base)

[andrey@ivy openssl-master]$
  256 bit ecdh (nistp256)   0.0003s   3042.2

[andrey@ivy MSR_ECClib_v1.1]$
Crypto operations: Weierstrass a=-3 over GF(2^256-189)

   ECDH(E) runs in ................................................. 
366436 cycles
   ECDH with variable base 
................................................. 12602 op/sec
   ECDH with fixed base (keygen) 
................................................. 31787.3 op/sec
   ECDH table precomp ................................................. 
1148.5 op/sec
   ECDH table precomp+keygen+variablebase 
................................................. 1066.89 op/sec

Crypto operations: twisted Edwards a=-1 over GF(2^256-189)

   ECDH(E) runs in ................................................. 
291183 cycles
   ECDH with one component 
................................................. 15648.9 op/sec
   ECDH with fixed base (keygen) 
................................................. 41296.2 op/sec
   ECDH table precomp ................................................. 
1243.78 op/sec
   ECDH table precomp+keygen+variablebase 
................................................. 1120.32 op/sec

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 17 Aug 2014 21:50:15 -0700

Michael Hamburg's question about hyperthreading made me think what kind 
of performance I can actually get on the whole CPU, as opposed to a 
single core?

I confirmed that, using the Curve25519 as an example, the 
single-threaded op/sec value can be multiplied by the number of cores to 
arrive at the total count.

Which gives us over 60,000 256-bit variable base scalar multiplications 
on a whole CPU. Recall that my reported number was 15764.3 op/sec.

To perform the measurement I wrapped the curve25519-donna code into the 
multithreaded code.

As the prints below show, the op/sec number, per thread, stays at ~15000 
level, deteriorating slightly, until the number of threads reaches the 
number of cores. The total operation count per CPU peaks at the number 
of threads equal the number of cores and then stays constant for higher 
number of threads. (actually, it peaks at the number of cores + 1, but 
that's a small increase).

Prints from the program follow. The diff: 
https://github.com/brainhub/curve25519-donna/commit/8fe32587444b9be3b9ec06cb2334a2cd3fc356cd.

Waiting in thread 1 ...
thread 1: 15616.2 op/sec in 6 sec
Total for CPU: 15616.2 op/sec

Waiting in thread 1 ...
Waiting in thread 2 ...
thread 1: 15221 op/sec in 7 sec
thread 2: 15224.6 op/sec in 7 sec
Total for CPU: 30445.5 op/sec

Waiting in thread 1 ...
Waiting in thread 2 ...
Waiting in thread 3 ...
thread 1: 14950.4 op/sec in 7 sec
thread 2: 14962.4 op/sec in 7 sec
thread 3: 14959.9 op/sec in 7 sec
Total for CPU: 44872.7 op/sec

Waiting in thread 1 ...
Waiting in thread 2 ...
Waiting in thread 3 ...
Waiting in thread 4 ...
thread 1: 14900.6 op/sec in 7 sec
thread 2: 14960.9 op/sec in 7 sec
thread 3: 14937.9 op/sec in 7 sec
thread 4: 14308.3 op/sec in 7 sec
Total for CPU: 59107.7 op/sec

Waiting in thread 4 ...
Waiting in thread 5 ...
Waiting in thread 3 ...
Waiting in thread 1 ...
Waiting in thread 2 ...
thread 1: 12298.4 op/sec in 8 sec
thread 2: 13157.2 op/sec in 8 sec
thread 3: 12187.7 op/sec in 8 sec
thread 4: 11612.9 op/sec in 9 sec
thread 5: 11201.8 op/sec in 9 sec
Total for CPU: 60457.9 op/sec

... and there is no improvement beyond 5 threads.

---

From: James Cloos <[email-masked]>
Date: Mon, 18 Aug 2014 01:47:51 -0400

>>>>> "AJ" == Andrey Jivsov <[email-masked]> writes:

>> Do you know if TurboBoost was on?  That CPU can boost to 3.7 GHz, so the cycle counts could be 12% different one way or another.

AJ> I checked my BIOS setting. It says "Intel HT Technology" Not Supported.

Turboboost != hyperthreading.

cpufreq-info(1) should tell you whether turboboost is in use.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6