Subject: [Cfrg] Not the same thread -> was Re: Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)

From: Paul Lambert <[email-masked]>
Date: Wed, 25 Feb 2015 08:47:48 -0800

Could we please get some discipline on this list to not pollute conversation threads – especially well formed threads asking for poll with random questions, comments and rants.

Paul

From: Phillip Hallam-Baker <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, February 25, 2015 at 8:22 AM
To: Stephen Farrell <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)

Do we have figures for performance of these versus RSA2048?

Yes, we get a reversal of the public/private speed advantage on signature. And that in itself is a huge win on the server side

RSA signature verification takes 0.16 ms on a reasonably current machine (signature is 6ms)

http://www.cryptopp.com/benchmarks.html

How much faster/slower one curve is over another matters much less to me than whether the curve is faster or slower than what I am already using. I am not going to be using P521 or P448 curves on a constrained device, I will go for P255.

If we had figures comparing the curve candidates to RSA it would probably be illuminating.

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 25 Feb 2015 09:58:37 -0800

Thanks, Paul.

On 3.6GHz Haswell with OpenSSL 1.0.1f:
RSA-2048: sign 1028us, verify 31us
Ed448: sign 51us, verify 163us, dh 148us
Ed480: sign 55us, verify 183us, dh 170us
E-521: sign 79us, verify 256us, dh 241us

On 1GHz Cortex A8 with OpenSSL 1.0.1f:
RSA-2048: sign 39.8ms, verify 1.2ms
Ed448: sign 0.7ms, verify 1.9ms, dh 1.9ms

On both CPUs, the elliptic curves are slower than RSA for verification, 
but much faster for signing.  The Haswell core is about 5-8x faster for 
RSA verify, and 20x slower for signing.

The A8 is more favorable to EC, probably because OpenSSL (or this build 
of it) doesn't use NEON for RSA.  It is only 60% faster for RSA 
verification, and 57x slower for signing.  But client devices don't sign 
very often.

-- Mike

On 02/25/2015 08:47 AM, Paul Lambert wrote:
>
> Could we please get some discipline on this list to not pollute 
> conversation threads – especially well formed threads asking for poll 
> with random questions, comments and rants.
>
> Paul
>
>
> Cc: "[email-masked] <mailto:[email-masked]>" <[email-masked] 
> <mailto:[email-masked]>>
>     Yes, we get a reversal of the public/private speed advantage on
>     signature. And that in itself is a huge win on the server side
>
>     How much faster/slower one curve is over another matters much less
>     to me than whether the curve is faster or slower than what I am
>     already using. I am not going to be using P521 or P448 curves on a
>     constrained device, I will go for P255.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 25 Feb 2015 13:03:23 -0500

I don't see that asking for data as a rant.

Early in the process it was implied that we would be making the decision on
the basis of data. If people give me the facts I may change my opinion.

On Wed, Feb 25, 2015 at 11:47 AM, Paul Lambert <[email-masked]> wrote:

> conversation threads – especially well formed threads asking for poll with
> random questions, comments and rants.
>
> Paul
>
>
> From: Phillip Hallam-Baker <[email-masked]>
> To: Stephen Farrell <[email-masked]>
> Cc: "[email-masked]" <[email-masked]>
> Yes, we get a reversal of the public/private speed advantage on signature.
> And that in itself is a huge win on the server side
>
> How much faster/slower one curve is over another matters much less to me
> than whether the curve is faster or slower than what I am already using. I
> am not going to be using P521 or P448 curves on a constrained device, I
> will go for P255.
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 25 Feb 2015 14:30:51 -0500

> E-521: sign 79us, verify 256us, dh 241us

OK so ignoring the likelihood that we do an ephemeral in addition since
that is a good thing to do anyway and if the key agreement is designed
right, a WF-128 ephemeral only improves a WF-256 key.

For the server side

RSA2048: One decrypt, 1028 us
E-521: One DH agreement 241 us

So anything we do is a win on the server side. No need to consider the
other curves. EC is going to be faster. And that is before we consider
games like precalculation.

For the client side, if we have one intermediate and one EE cert:

RSA2040: One encrypt, two verifies, 93usec
EC 521: One DH, two verifies, 753 usec.

OK so performance is possibly an issue on the client. But only if we are on
a constrained device or the client is making a huge number of key
negotiations. And why would you want to do that on a constrained device.

Taking 448 as the baseline, 480 is 15% slower, 521 is 60% slower

Those figures might change a bit depending on optimization but I rather
doubt they will change greatly.

So on the one hand we have a measurable performance difference that makes
no real difference and on the other we have a measurable security
difference that makes no real difference.

Curve 521 does have the advantage of matching the work factor of AES 256.
It also has the advantage of squaring the work factor. The best
cryptanalytic technique we have to date is the meet in the middle attack
which reduces the work factor by the root, 2DES (112 bits) has the same
strength as DES (56 bits).

I don't care about the color of the bikeshed. What I care about is the
possibility that someone hates the color of ours so much that they insist
on building a new bike shed so that they can have their color. The Russian
requirement for P512 looked like it was an objection of that form till it
turned out that particular choice seems to have been made to exclude the US
proposal.

Tying back to the NIST discussion. If they really care about the color of
the bike shed, that is something I would personally consider very relevant.
Same for Microsoft or Google.

If P384 is the NIST baseline then I think it is easy to upsell them to 448.

If P521 is their established baseline then we could probably persuade them
to replace the P384 curve with ours but they are likely keeping their 521
curve.

>From time to time I attend meetings where it would be really easy to say to
someone with decision making ability that one of the best things that the
US Govt could do in the short term for cyber security would be to publish a
FIPS for the IETF curves. The problem being that the person who has
decision making authority has no idea what public key crypto is let alone
why they would want a particular curve.

If I push that button and the response that comes back up the chain is 'Our
521 curve is a billion billion times stronger', I doubt we get what we
want. If the response that comes back is 'we prefer Weinerschnitzel curves
with the double Irish option because they may have better security against
Schnorkelplage attack', it is rather more likely we get our way.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 25 Feb 2015 21:57:56 +0200

> Ed448: sign 0.7ms, verify 1.9ms, dh 1.9ms

What is DH (Diffie-Hellman) in that?

Compressed edwards scalarmult? Uncompressed Edwards scalarmult?
Montgomery ladder? Does it include key generation time (for not
reusing keys)?

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 25 Feb 2015 12:06:14 -0800

> On Feb 25, 2015, at 11:57 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

Montgomery ladder scalarmult with a few cheap bells and whistles: unified point compression which includes a correctly computed sign, rejecting points on the twist, and hashing the output with the input public keys to make a session key.

It doesn’t include key generation time.  Key generation takes about as long as signing.

— Mike

---

From: Derek Atkins <[email-masked]>
Date: Thu, 26 Feb 2015 10:56:07 -0500

> E-521: sign 79us, verify 256us, dh 241us

I asked this in the previous thread but it was lost, so I'll ask this
again in this thread: Why are you looking at RSA 2048 for this
comparison?  That's only a 2^112 work factor (C.f. Section 1 of
RFC4492).

If you want a 2^256 work factor you need to go up to RSA 15360.  If you
only want to get to 2^128 then you need to look at RSA 3072.

Let's at least compare apples to apples.

> On both CPUs, the elliptic curves are slower than RSA for verification, but
> much faster for signing.  The Haswell core is about 5-8x faster for RSA verify,
> and 20x slower for signing.

But at quite different security levels, so it's not telling us anything
useful.  I think Ed448 is more like an RSA-4096 level (or possibly even
larger than that).

> The A8 is more favorable to EC, probably because OpenSSL (or this build of it)
> doesn't use NEON for RSA.  It is only 60% faster for RSA verification, and 57x
> slower for signing.  But client devices don't sign very often.

-derek

>         How much faster/slower one curve is over another matters much less to
>         me than whether the curve is faster or slower than what I am already
>         using. I am not going to be using P521 or P448 curves on a constrained
>         device, I will go for P255.
>        

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 26 Feb 2015 12:38:04 -0500

> Let's at least compare apples to apples.

The reason is that as far as customers are concerned, they are switching
from RSA2048 to something else. We have already established that the CPU
demands of RSA2048 are not prohibitive for any class of device currently
using TLS.

If I am looking at buying a new van, the question I am going to ask is not
which one has most capacity, fuel economy, etc. but whether it is the same,
better or worse than what I already have and whether the current situation
is acceptable or not. If I am moving from a van to a truck I am going to
ask what the impact on fuel consumption is even though I know the truck
holds more because I know if my current fuel costs are acceptable or not.

We already have an EC curve that is optimized for new applications in
constrained devices etc. So knowing how we are doing relative to the
baseline of RSA2048 is informative.

If we were looking at additional load on the server then we would have to
be very concerned because that is a bottleneck.

> but

The reason we are moving away from RSA is that 1) Index calculus continues
to improve and 2) RSA hits steeply diminishing returns, its more like
16Kbit keys to get an interesting improvement in performance.

RSA2048 is the baseline for performance. It is not the baseline for
security. The objective here is to improve security without adverse impact
on performance.

The reason I was asking the question is that if we can do P521 at lower
cost than RSA2048 then the fact that P448 takes only 62% of the time that
P521 does isn't very interesting. If P521 was going to be a lot slower on
the server then my customers would be really concerned about performance
and demand P448 and we would have an objective criteria on which we can
justify an answer.

As it is, I don't see performance as being an objective discriminator
because there is only a negative impact on clients and the CPU overhead on
the client side is a negligible fraction of the PKI overhead. I would bet
that we improve performance client side for TLS on a Raspberry Pi 2 under
real world test conditions using P521 over RSA2048 simply because all the
cert chains etc are much smaller. Yes verifying signatures takes 8 times as
long. But we are talking about an operation that takes a 1.2 ms on an
iPhone CPU today.

If we go for P521 then nobody can possible criticize us for having chosen
something less secure than we did.

If went for P521 and P448 I guarantee that my world will only use P521 and
P255.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 26 Feb 2015 18:22:30 -0800

> demands of RSA2048 are not prohibitive for any class of device currently

What about devices and services that don't use TLS because of the CPU
demands? Or is encrypting everything no longer on the agenda? Is
Cloudflare conducting a RSA2048 private key operation every time I
connect? Is Google?

> is acceptable or not. If I am moving from a van to a truck I am going to ask
> what the impact on fuel consumption is even though I know the truck holds
> more because I know if my current fuel costs are acceptable or not.

> baseline of RSA2048 is informative.

Down at the bottom this email you explain that public CAs won't be
using Curve25519. Never mind that encrypted data, not past
authentication, needs to survive into the future. Never mind that CAs
didn't rush out and compete to make RSA3072 keys, or even depreciate
RSA1024 with anything close to a reasonable timescale. But if what you
say is in fact true, then devices don't have a choice: they need to
carry out a verification with superfluous strength unless they aren't
going to use TLS.

Brian Smith and Tony Aceri have lengthy emails explaining the problem,
which you've entirely ignored. I've explained why it makes sense for
authentication to be weaker than encryption: again, email entirely
ignored. Are you going to explain what we're missing?

>
> If we were looking at additional load on the server then we would have to be
> very concerned because that is a bottleneck.
>
>
> to improve and 2) RSA hits steeply diminishing returns, its more like 16Kbit
> keys to get an interesting improvement in performance.
>

Objective for who? Of course, there already is an adverse impact on
performance: none of the options had faster verification.

>
> The reason I was asking the question is that if we can do P521 at lower cost
> than RSA2048 then the fact that P448 takes only 62% of the time that P521
> does isn't very interesting. If P521 was going to be a lot slower on the
> server then my customers would be really concerned about performance and
> demand P448 and we would have an objective criteria on which we can justify
> an answer.

By "your clients" you mean the people whose CSRs you sign to make
certificates, right?

They get to pick which algorithm to use on the server to sign the key
exchange. Which algorithm the root certificate uses to sign the
intermediate and the intermediate the entity cert are entirely
irrelevant to this process. Of course, it's not irrelevant to the
client, which has to conduct a large number of verifications, and
where additional time is a real PITA.

> long. But we are talking about an operation that takes a 1.2 ms on an iPhone
> CPU today.

What PKI overhead is there aside from the CPU cycles to verify
signatures? But let's actually do the calculation. 10^8 bits per
second, and we've replaced 2048 bits with 521*2=1042 bits, so saving
1006 bits per signature. That means we've saved 10 microseconds per
signature. The minimal cert chain is three certs, so we saved 30
microseconds. And then we throw it all away doing three verifications.
Even if we save .1 milliseconds per signature, it all vanishes with
the extra time for verification, even on fast CPUs. You'll need
batching to even get close.

> something less secure than we did.

No, they still can: after all, there are an infinite number of primes,
and any bigger prime would increase security. But why aren't you
turning this around and saying that if we pick P448 no one can
criticize us for not increasing performance?

> If went for P521 and P448 I guarantee that my world will only use P521 and

Why didn't this happen for the NIST curves? Why hasn't it happened for
RSA? And why require clients to do more work when P448 offers far more
than adequate security?

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Derek Atkins <[email-masked]>
Date: Fri, 27 Feb 2015 12:14:58 -0500

Phillip Hallam-Baker <[email-masked]> writes:

> The reason is that as far as customers are concerned, they are switching from
> RSA2048 to something else. We have already established that the CPU demands of
> RSA2048 are not prohibitive for any class of device currently using TLS. 

Maybe that's the case for your customers, but certainly not mine.

You're ignoring the classes of devices not using TLS because the CPU
demands of RSA2048 *ARE* prohibitive.  That's where I live these days.
(Honestly, even the cost of ECC is sometimes prohibitive in the space I
live these days).

You're welcome to compare apples to kumquats if you desire, but my
customers need an apples-to-apples comparison.  Is it really too much to
ask for timings of RSA 3072, 4096, 7680, 8192, and 15360??  ;)

> better or worse than what I already have and whether the current situation is
> acceptable or not. If I am moving from a van to a truck I am going to ask what
> the impact on fuel consumption is even though I know the truck holds more
> because I know if my current fuel costs are acceptable or not.

Or your current car just up and died and you get to buy a car from
scratch, which means you don't have to compare your old to your new, but
you're comparing new#1 to new#2 to new#3.  In which case knowing that
your old van used to get 15MPG is completely irrelevant, because all the
new ones you get to choose from are above 20.

> constrained devices etc. So knowing how we are doing relative to the baseline
> of RSA2048 is informative.

Really?  And which one would that be?  We seem to have only shown
consensus for 25519 so far.

> The reason we are moving away from RSA is that 1) Index calculus continues to
> improve and 2) RSA hits steeply diminishing returns, its more like 16Kbit keys
> to get an interesting improvement in performance. 
>
> RSA2048 is the baseline for performance. It is not the baseline for security.
> The objective here is to improve security without adverse impact on
> performance.

That may be YOUR objective, but I don't know that we have consensus on
that being the ONLY objective.  From where I sit I'd like to see it in
the reverse: if I have a particular constraint (space,time,cpu,etc)
what's the best security I can get within that constraint?  Or
similarly, if I only need X-level security, how does it affect my
performance if I switch from AlgA to AlgB?

> than RSA2048 then the fact that P448 takes only 62% of the time that P521 does
> isn't very interesting. If P521 was going to be a lot slower on the server then
> my customers would be really concerned about performance and demand P448 and we
> would have an objective criteria on which we can justify an answer.

True, a 33% reduction in execution time might not be very interesting to
some.  But asking for more data shouldn't ever be a bad thing.

> As it is, I don't see performance as being an objective discriminator because
> there is only a negative impact on clients and the CPU overhead on the client
> side is a negligible fraction of the PKI overhead. I would bet that we improve
> performance client side for TLS on a Raspberry Pi 2 under real world test
> conditions using P521 over RSA2048 simply because all the cert chains etc are
> much smaller. Yes verifying signatures takes 8 times as long. But we are
> talking about an operation that takes a 1.2 ms on an iPhone CPU today.
>

I cannot give you the same guarantee in my world.

-derek

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 27 Feb 2015 13:00:03 -0500

On Fri, Feb 27, 2015 at 12:14 PM, Derek Atkins <[email-masked]> wrote:

> from

No, I am suggesting that the class of device that require more security
than Curve25519 and find P448 performance acceptable that will not find the
additional 60% extra time to do P521 is either the null set or not worth
bothering with.

The choice between P448 and P521 is not going to be a make or break issue
for whether your lightbulb is going to be viable. It isn't even going to
force a choice of chip.

> ask for timings of RSA 3072, 4096, 7680, 8192, and 15360??  ;)

Yes, because the reason we are going to ECC in the first place is they
don't work.

RSA2048 has a WF of approx 112 bits. RSA4096 is only a WF of 128 bits. To
get to 256 bit security you need those 15360 bits.

If RSA15360 performance was acceptable then P521 would definitely be
acceptable.

Remember the days of the BBN Safekeeper which took 9 hours to generate
RSA4096 keypairs? THAT is quite definitely a make/break issue. If an
operation is taking hours or even minutes then 60% is arguably significant.
But I just don't think you are going to be doing P448 or P521 all that many
times.

> consensus for 25519 so far.

That *IS* your constrained curve, sorry.

If you are more constrained than that and can't live with Curve25519 then
Goldilocks isn't going to be relevant to you anyway.