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

[Olafur Gudmundsson <[e-mail]>]

On Mar 21, 2014, at 6:16 PM, Michael Hamburg <[e-mail]> wrote:

> 
> On Mar 21, 2014, at 12:00 PM, Olafur Gudmundsson <[e-mail]> wrote:
> 
>> 
>> On Mar 21, 2014, at 2:29 PM, Michael Hamburg <[e-mail]> wrote:
>> 
>>> * How frequently will implementations be verifying multiple signatures simultaneously?
>> 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.


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. 

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

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 . 


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

>> 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. 
> 
> Yeah, it might be worth not compressing keys, or even expanding them if GLS/GLV isn’t in play.
> 
>>> 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.
>>> 
>> 
>> 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. 
> 
> 
> 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.
> 

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

	Olafur