Re: [Cfrg] Validation performance Re: new curves vs. algorithms

[Michael Hamburg <[e-mail]>]

Hi Olafur,

Can you give some insight on a couple aspects of DNSSEC validation:

* How frequently will implementations be verifying signatures with the same small set of keys?
* How frequently will implementations be verifying multiple signatures simultaneously?

For example, Ed25519 can batch verify, and many EC signatures schemes have this ability.
This improves performance (double or more) when verifying more than one signature at a time.

As for verification with precomputation, consider the following benchmarks from my laptop.
RSA OpenSSL 1.0.1f:
                  sign    verify    sign/s verify/s
rsa 1024 bits 0.000155s 0.000012s   6443.4  84645.8
rsa 2048 bits 0.001172s 0.000036s    853.1  27954.7

252-bit “Montgomery Station” curve, measurements in milliseconds and cycles:
Keygen                        0.013ms,   40812
Sign                          0.014ms,   45763
Verify                 PASS   0.047ms,  155313
Precompute             PASS   0.061ms,  201570
Verify pre             PASS   0.016ms,   53747
Compute shared secret  PASS   0.042ms,  136256

So verification takes 47µs, vs 36µs with RSA-2048.  But if a key is used frequently, then a
61µs precomputation using 7.5kiB of RAM will drop the verification time to 16µs, which is
indeed faster than RSA.  Additionally, with a curve like this, signatures are 64 bytes instead
of 256 bytes.  If your client is verifying and has a 24 megabit link, then this difference is
worth 64 microseconds by itself, which is more time than either algorithm takes to verify.

This is also not the fastest curve in the world, it’s just a project I had lying around.  GLS/GLV-
flavored curves are faster, at least if you don’t have precomputation.  The math for this curve,
like with most curves, supports batch verification, but I haven’t coded it up (I think only
Ed25519 actually implements this).

So in sum, I hope that any new 256-ish-bit curve will perform comparably to RSA-2048 for
verification, though the exact details will depend on the implementation and on whether keys
are reused.  ECC will also have smaller signatures and faster (and possibly precomputable)
signing.

Cheers,
— Mike


On Mar 21, 2014, at 10:19 AM, Olafur Gudmundsson <[e-mail]> wrote:

> 
> While we are it, here is another criteria to keep in mind when designing/recommending new curves. 
> This relates to an old question I asked on CFRG in 2006 (wow that is a long time ago) 
> in regards to using ECC in DNSSEC 
> http://www.ietf.org/mail-archive/web/cfrg/current/msg01170.html
> 
> Since then DNSSEC has specified the use of 3 curves P256, P384[RFC6605] and ECC-GOST[RFC5933], 
> none of these seems to be in wide spread use, as support is rolling out. 
> 
> What we have learned in the mean time (from DNS perspective), is verification time is the most critical part
> as the world wants happy eyeballs to work and any microseconds that verification takes add up.
> Consider the case that most web pages have in excess of 50 links and many of those are unique
> and can not be reused by resolvers/validators. 
> 
> Fast signing is nice as that may enable on the fly signing off unique names. 
> 
> As for criteria I would propose the following, as starting point for discussion 
> 	verification time < verification of 2048 bit RSA signature
> 	signing time      <  signing with 1024  bit RSA key 
> 
> As an example comparing here is comparison of 
> performance of RSA1024 and 2048 bit keys  vs NIST P256 and P384 on modern hardware, only relative performance should
> be derived. 
> 
>> OpenSSL> version 
>> OpenSSL 1.0.1 14 Mar 2012
>> OpenSSL> speed rsa1024 rsa2048 ecdsap256 ecdsap384
>> Doing 1024 bit private rsa's for 10s: 38935 1024 bit private RSA's in 9.97s
>> Doing 1024 bit public rsa's for 10s: 621683 1024 bit public RSA's in 9.98s
>> Doing 2048 bit private rsa's for 10s: 5792 2048 bit private RSA's in 9.98s
>> Doing 2048 bit public rsa's for 10s: 187826 2048 bit public RSA's in 9.97s
>> Doing 256 bit sign ecdsa's for 10s: 58772 256 bit ECDSA signs in 9.98s 
>> Doing 256 bit verify ecdsa's for 10s: 23120 256 bit ECDSA verify in 9.97s
>> Doing 384 bit sign ecdsa's for 10s: 34564 384 bit ECDSA signs in 9.97s 
>> Doing 384 bit verify ecdsa's for 10s: 7695 384 bit ECDSA verify in 9.98s
>> OpenSSL 1.0.1 14 Mar 2012
>> built on: Tue Jun  4 07:26:06 UTC 2013
>> options:bn(64,64) rc4(8x,int) des(idx,cisc,16,int) aes(partial) blowfish(idx) 
>> compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Wformat-security -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT -DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
>>                  sign    verify    sign/s verify/s
>> rsa 1024 bits 0.000256s 0.000016s   3905.2  62292.9
>> rsa 2048 bits 0.001723s 0.000053s    580.4  18839.1
>>                              sign    verify    sign/s verify/s
>> 256 bit ecdsa (nistp256)   0.0002s   0.0004s   5889.0   2319.0
>> 384 bit ecdsa (nistp384)   0.0003s   0.0013s   3466.8    771.0
> 
> 
> As you can see these ECC curves verification performance SUCKS big time when we compare smallest sizes. 
> I know the RSA code is much more mature than the ECC code but the verification code needs to improve by 25x 
> For these curves Signing speeds meets the criteria. 
> 
> 	Olafur 
> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg