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

Olafur Gudmundsson <> Tue, 25 March 2014 15:06 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 3E0A31A0171 for <>; Tue, 25 Mar 2014 08:06:42 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.801
X-Spam-Status: No, score=0.801 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id qaMDUQqsjX6n for <>; Tue, 25 Mar 2014 08:06:38 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id F31451A0199 for <>; Tue, 25 Mar 2014 08:06:37 -0700 (PDT)
Received: from localhost (localhost.localdomain []) by (SMTP Server) with ESMTP id C647A9907B; Tue, 25 Mar 2014 11:06:36 -0400 (EDT)
X-Virus-Scanned: OK
Received: by (Authenticated sender: with ESMTPSA id 44D5399714; Tue, 25 Mar 2014 11:06:35 -0400 (EDT)
Content-Type: multipart/alternative; boundary="Apple-Mail=_78F08D8E-277C-4911-976A-7A6702BC43DC"
Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\))
From: Olafur Gudmundsson <>
In-Reply-To: <>
Date: Tue, 25 Mar 2014 11:06:34 -0400
Message-Id: <>
References: <> <> <> <> <>
To: Michael Hamburg <>
X-Mailer: Apple Mail (2.1510)
Subject: Re: [Cfrg] Validation performance Re: new curves vs. algorithms
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 25 Mar 2014 15:06:43 -0000

On Mar 21, 2014, at 6:16 PM, Michael Hamburg <> wrote:

> On Mar 21, 2014, at 12:00 PM, Olafur Gudmundsson <> wrote:
>> On Mar 21, 2014, at 2:29 PM, Michael Hamburg <> 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,  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.