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

From: Olafur Gudmundsson <[email-masked]>
Date: Fri, 21 Mar 2014 13:19:56 -0400

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

---

From: Santosh Chokhani <[email-masked]>
Date: Fri, 21 Mar 2014 17:56:16 +0000

You cannot expect EC to match RSA for public key operation performance given the typical 17 bit exponent for RSA public key.

The perform problem for EC and discrete logs in finite field gets worse for pubic key operations when taking PKI into consideration because of a number of certificates and their revocation status need to be checked (all use public key operations) before trust in a public key is established.

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Olafur Gudmundsson
Sent: Friday, March 21, 2014 1:20 PM
To: [email-masked]
Subject: [Cfrg] Validation performance Re: new curves vs. algorithms

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. 

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. 

> 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

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
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 21 Mar 2014 11:29:41 -0700

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

---

From: Olafur Gudmundsson <[email-masked]>
Date: Fri, 21 Mar 2014 14:30:37 -0400

> The perform problem for EC and discrete logs in finite field gets worse for pubic key operations when taking PKI into consideration because of a number of certificates and their revocation status n…
Santosh, 

FWIW, all I care about is raw performance of core operations, as that is what is used by the protocols i work on and 
that is what can be used for comparisons when selecting algorithms. 
Different protocols/systems add different overheads and in many cases these overhead are algorithm independent. 

	Olafur

---

From: Olafur Gudmundsson <[email-masked]>
Date: Fri, 21 Mar 2014 15:00:53 -0400

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

Here is a common example you look up "_443._tcp.serverx.lax.content.example.  TLSA" 
each dot here is a zone boundary 
thus to validate the TLSA record you need to have following work done by your validator 
1.	.example DS  signed by root key ZSK 
2.	.example DNSKEY signed by .example KSK
3.	.content.example DS  signed by .example  ZSK 
4.	.content.example DNSKEY signed by content.example KSK 
5.	lax.content.example DS signed by content.example. ZSK 
6.	lax.content.example. DNSKEY signed by lax.content.example KSK 
7.     _443._tcp.severx.lax.content.example. TLSA signed by serverx.lax.content. ZSK 

KSK is a Key Signing key that is vouched for by the DS 
ZSK is a Zone Signing key that is included in the DNSKEY set. 
In some operations the KSK is different from the ZSK, but in other cases it is the same one. 
A validator can not predict what keys it will need until when it sees the query. 
Depending on what is in the cache of the validator it starts at the lowest step it can. 

> * How frequently will implementations be verifying multiple signatures simultaneously?
as in signatures by the same key at the same time?  almost never 

> This improves performance (double or more) when verifying more than one signature at a time.

If there is one time overhead in starting to use key that might get aggregated over the time the key stays in cache on
the validator,  the same key may get used many times during the time it is cached. 
For example your validator is likely to reuse the ZSK for ".com"  over the one day it can be cached,
on the other hand, if it ever looks up ogud.com it is unlikely to reuse that key much :-) 

> worth 64 microseconds by itself, which is more time than either algorithm takes to verify.

For DNS operators that have high load link speed is not an issue. 
This curve is good news,  but you raise a new question can the key be 
represented on the wire in such a way that the pre computation is not needed ? 
Same question for the signatures ? 

In a paper that I read by DJB he argued for compressing keys and signatures, but for 
high-speed-low-latency use the tradeoff between size and speed might be different. 

> are reused.  ECC will also have smaller signatures and faster (and possibly precomputable)

I hope that we can find signature curves that make RSA redundant in any use, as that 
helps overcome UDP packet size limits we are dealing with. 

The reason I posted my message was the desire to inject real work needs into the discussions
and make crypto people aware that "strength" and "size" are not only important issues in selecting a
good curve. 

> — Mike
Toast
	Olafur

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 21 Mar 2014 15:16:47 -0700

> as in signatures by the same key at the same time?  almost never 

It’s not necessary for them to be with the same key.  Over the same curve is enough for batching.
Bernstein even argues that you could have one thread acting as a batch ECC server and just doing
64 verifies at a time.  But that might not be acceptable here, because it trades latency for throughput.

In your example, if all those sigs come in simultaneously, then you can batch all the ECC ones which
share a curve.  But if the validator is checking each DS before doing the next lookup, then the
opportunities for batching will be limited.

Anyway, there are two different optimizations:
* Validating multiple signatures at the same time, if they’re over the same curve.
* Validating multiple signatures, not necessarily at the same time, if they’re done with the same key.

Validating multiple signatures at the same time with the same key ought to be even faster, but
like you said, that doesn’t come up very often.

> Same question for the signatures ? 

Sort of.  It’s a time/memory tradeoff.  The numbers there are for 7.5kiB precomputed tables.  But
doubling or quadding or octing the key size (octing would make it 2048 bits) might make a
noticeable difference, either by enabling this table optimization or just by avoiding decompression.

Surely link speed matters to some degree.  Even on a gigabit link, 7.5GiB is still a microsecond,
plus it slows down all the traffic on that link.

Anyway, I dunno if it’s this curve in particular that’s good news.  It’s not that much faster than
curve25519, and if you want a fancy superfast curve that’s not in widespread use, one of the
GLS/GLV curves will have faster verifies.

> high-speed-low-latency use the tradeoff between size and speed might be different. 

Yeah, it might be worth not compressing keys, or even expanding them if GLS/GLV isn’t in play.

> and make crypto people aware that "strength" and "size" are not only important issues in selecting a

I think that people are focused on a stronger curve at the moment because there are a
ton of fast 256-ish-bit curves, and Curve25519 is good for almost everything at that strength.

Consider, for example, http://bench.cr.yp.to/results-dh.html.  Pretty much all of those curves are
~256 bits.

— Mike

---

From: Olafur Gudmundsson <[email-masked]>
Date: Tue, 25 Mar 2014 11:06:34 -0400

> like you said, that doesn’t come up very often.

When I read this I translated it to "By having fewer curves opportunities for faster verification increase" 
which is another argument for my tirade on dnsop mailing list against adding 3 brain pool curves to DNSSEC
algorithm list. 

> noticeable difference, either by enabling this table optimization or just by avoiding decompression.

What I meant if the compression/ease-of-use format adds few bytes (like <= 8) then it might be worth it
once the keys become RSA size i.e. over 1024 bits then it is not worth it . 

> Consider, for example, http://bench.cr.yp.to/results-dh.html.  Pretty much all of those curves are

Thanks for the link that is lots of info, it is going to take a while for me to digest that. 

	Olafur

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 25 Mar 2014 11:58:02 -0700

> which is another argument for my tirade on dnsop mailing list against adding 3 brain pool curves to DNSSEC

It might be hard to hold that line while asking for Curve25519 support, but good luck.

> once the keys become RSA size i.e. over 1024 bits then it is not worth it . 

Public keys are 32 bytes and signatures are 64 bytes.  Adding 32 bytes to the public key either saves ~5-10% for decompression, or adds ~5-10% for a second decompression but saves some amount afterwards.  Adding <= 8 bytes does nothing.  Adding 32 bytes to the signature saves a decompression if you’re batching, but if you aren’t batching it may save less than that.  Altogether, probably not worth it.

> Thanks for the link that is lots of info, it is going to take a while for me to digest that. 

You’re welcome,
— Mike