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

[Michael Hamburg <[e-mail]>]

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.

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

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.

— Mike