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

[Andrey Jivsov <[e-mail]>]

On 08/17/2014 10:09 AM, Michael Hamburg wrote:
>
>> On Aug 16, 2014, at 6:10 PM, Andrey Jivsov <[e-mail]> wrote:
>>
>> I timed libsodium, curve25519-donna, MSR ECCLib, and openssl-master.
>
> 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.

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.

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

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.

>
>> 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 )
>> <memcpy-timing.c>_______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> 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