Subject: [TLS] Thoughts on TLS 1.3 cryptography performance

From: Watson Ladd <[email-masked]>
Date: Wed, 12 Mar 2014 18:10:31 -0700

Dear all,
Below are some thoughts about the TLS 1.3 cryptography, based on
actual performance measurements together with information about what
is actually offered and new research. It also addresses some issues I
have with the 1-RTT handshake currently proposed.

Currently a state-of-the-art handshake involves 2 exponentiations and
a signature on the server side and 2 exponentiations on the client
side and a verification. One is fixed base, the other variable base.

On haswell the fastest ECDHE agreement takes 45,468 cycles, using a
GLS curve. Curve25519 weighs in at 162,460 cycles. These are medians.
nistp256 would be in the neighborhood of efp256s, at 273,656 cycles,
and the key generation for ECDSA signatures with P256 weighs in at
253,307. (Key generation can use precomputed multiples). This pattern
holds for almost all architectures.

Recent research gets 72,220 cycles using genus 2 curves:
https://eprint.iacr.org/2014/134.pdf.  Now, you may wonder why you've
never heard of GLS, and the reason is that there is a slight loss of
security from the endomorphisms. Point counting on surfaces is a pain,
so that's why this is new work.

In the land of signatures life is a bit harder. ECDSA validation for
P256 takes 850,000 cycles, probably because multiexponentiation wasn't
used. Signing takes 373,486 cycles. Even Ed25519 takes 68,552 cycles
to sign and 206,886 to verify.

What about RSA? Signing with a 1024 bit key takes 1,279,440cycles.

I went and validated these numbers will OpenSSL speed on my machine. I
can sign with ECDSA P256 ten times as fast as RSA 2048. There is a
reason every heavily loaded server is moving to ECDSA_ECDHE as quickly
as possible.

However, we can do better.

The trick is to note that the only time a signature needs to be
generated is when the data it protects changes, and the only time it
needs to be checked is when you forget whether what it was protecting
was protected by it.

Therefore, if we have the server send g^a, g^x, and the client g^c,
g^y, and compute the premaster secret using the so-called "triple DH"
H(g^(ay) |g^(cx) |g^(xy)), so long as the client remembers g^a, it
doesn't need to check for a signature. And so long as the server
doesn't change g^a, it doesn't need to recompute a signature. (Hashing
in the transcript should be done, but I think the Premaster->Master
transformation does that?)

The extra work done is two exponentiations, replacing a signature
generation. This is a slight loss if you are using ECDSA and replace
it with ECDHE P256, but with Curve25519  replacing ECDSA it's a win.

Furthermore, if the client recalls g^a it doesn't need to ask for a
certificate, and we have a 1-RTT handshake, with obvious fallback to a
negotiation if the group is wrong or the client wants to see the
certificate for g^a again. Asking for the certificate can take place
over the secure channel established

If we don't mind licensing HMQV we can use that, or remove the g^(xy)
if we want PFS so long as the client generated g^c randomly and forgot
what c was. This adds a lot more performance by removing an
exponentiation. Thanks to Dan Brown for pointing out that HMQV
continues to exist on the CFRG list.

End of the day, TLS 1.3 won't be adopted because it's more secure:
look at TLS 1.0 vs. TLS 1.1 on the SSL Observatory. It will be adopted
because it is faster and reduces load on servers, and we should do our
best to make sure it is also more secure, simpler to implement well,
and includes more of the necessary extension drafts then TLS 1.2
currently does.

Lastly, we should strongly consider requiring that miTLS be updated in
line with the TLS 1.3 spec. We finally have mechanical validation of
security: we shouldn't lose it.

Sincerely,
Watson Ladd

---

From: Michael D'Errico <[email-masked]>
Date: Wed, 12 Mar 2014 18:41:56 -0700

Watson Ladd wrote:
> Dear all,
> Below are some thoughts about the TLS 1.3 cryptography....

Is the plan to send client version { 0x03 0x04 } and continue to be
subject to downgrade attacks, version intolerance, etc. that plague
browsers today?  Or is there some other way to signify support for
version 1.3?

Mike

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 12 Mar 2014 18:48:09 -0700

On Wed, Mar 12, 2014 at 6:41 PM, Michael D'Errico <[email-masked]>wrote:

> subject to downgrade attacks,

Well, we need to address the downgrade attack problem in any case,
and so I was assuming any solution that worked for TLS 1.2 would
work for 1.3.

version intolerance, etc. that plague
> browsers today?  Or is there some other way to signify support for

It seems to me that using the existing version selection mechanism is
the default choice, but certainly this is something that in principle
the WG could decide to change.

-Ekr

Mike
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Santosh Chokhani <[email-masked]>
Date: Thu, 13 Mar 2014 02:27:34 +0000

Does your calculation include certification path verification and associated public key operations?  Note that certification path verification will also entail revocation (CRL or OCSP certificate and OCSP response) verification.

-----Original Message-----
From: TLS [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: Wednesday, March 12, 2014 9:11 PM
To: [email-masked]
Subject: [TLS] Thoughts on TLS 1.3 cryptography performance

Dear all,
Below are some thoughts about the TLS 1.3 cryptography, based on actual performance measurements together with information about what is actually offered and new research. It also addresses some issues I have with the 1-RTT handshake currently proposed.

Currently a state-of-the-art handshake involves 2 exponentiations and a signature on the server side and 2 exponentiations on the client side and a verification. One is fixed base, the other variable base.

On haswell the fastest ECDHE agreement takes 45,468 cycles, using a GLS curve. Curve25519 weighs in at 162,460 cycles. These are medians.
nistp256 would be in the neighborhood of efp256s, at 273,656 cycles, and the key generation for ECDSA signatures with P256 weighs in at 253,307. (Key generation can use precomputed multiples). This pattern holds for almost all architectures.

Recent research gets 72,220 cycles using genus 2 curves:
https://eprint.iacr.org/2014/134.pdf.  Now, you may wonder why you've never heard of GLS, and the reason is that there is a slight loss of security from the endomorphisms. Point counting on surfaces is a pain, so that's why this is new work.

In the land of signatures life is a bit harder. ECDSA validation for
P256 takes 850,000 cycles, probably because multiexponentiation wasn't used. Signing takes 373,486 cycles. Even Ed25519 takes 68,552 cycles to sign and 206,886 to verify.

I went and validated these numbers will OpenSSL speed on my machine. I can sign with ECDSA P256 ten times as fast as RSA 2048. There is a reason every heavily loaded server is moving to ECDSA_ECDHE as quickly as possible.

The trick is to note that the only time a signature needs to be generated is when the data it protects changes, and the only time it needs to be checked is when you forget whether what it was protecting was protected by it.

Therefore, if we have the server send g^a, g^x, and the client g^c, g^y, and compute the premaster secret using the so-called "triple DH"
H(g^(ay) |g^(cx) |g^(xy)), so long as the client remembers g^a, it doesn't need to check for a signature. And so long as the server doesn't change g^a, it doesn't need to recompute a signature. (Hashing in the transcript should be done, but I think the Premaster->Master transformation does that?)

The extra work done is two exponentiations, replacing a signature generation. This is a slight loss if you are using ECDSA and replace it with ECDHE P256, but with Curve25519  replacing ECDSA it's a win.

Furthermore, if the client recalls g^a it doesn't need to ask for a certificate, and we have a 1-RTT handshake, with obvious fallback to a negotiation if the group is wrong or the client wants to see the certificate for g^a again. Asking for the certificate can take place over the secure channel established

If we don't mind licensing HMQV we can use that, or remove the g^(xy) if we want PFS so long as the client generated g^c randomly and forgot what c was. This adds a lot more performance by removing an exponentiation. Thanks to Dan Brown for pointing out that HMQV continues to exist on the CFRG list.

End of the day, TLS 1.3 won't be adopted because it's more secure:
look at TLS 1.0 vs. TLS 1.1 on the SSL Observatory. It will be adopted because it is faster and reduces load on servers, and we should do our best to make sure it is also more secure, simpler to implement well, and includes more of the necessary extension drafts then TLS 1.2 currently does.

Lastly, we should strongly consider requiring that miTLS be updated in line with the TLS 1.3 spec. We finally have mechanical validation of
security: we shouldn't lose it.

Sincerely,
Watson Ladd

---

From: Watson Ladd <[email-masked]>
Date: Wed, 12 Mar 2014 20:00:00 -0700

> Does your calculation include certification path verification and associated public key operations?  Note that certification path verification will also entail revocation (CRL or OCSP certificate a…

You raise a deeply interesting point: if you batch verify, calculation
is cheaper. However, neither RSA nor ECDSA can be batch verified.
Schnorr can, but was patented, and Schnorr wanted to get paid, which
is why it isn't used in X509. Furthermore, the cost of signing is the
real issue, and the entire path verification can be cached.

Even if the client has to do a lot of verification of OCSP responses
anyway, saving server CPU is worthwhile.

Sincerely,
Watson Ladd

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

---

From: Nico Williams <[email-masked]>
Date: Wed, 12 Mar 2014 23:54:58 -0500

Isn't session resumption with session tickets faster still and
-provided the insufficiency of binding from resumed to original
session is fixed- as secure?  Ah, you want PFS even on resumption, but
surely that could be added, and even then the result should still
perform even better than your proposal.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Wed, 12 Mar 2014 23:12:12 -0700

> perform even better than your proposal.

 The performance gain doesn't work like that. It's not from the client
having seen the g^a before, but that the server doesn't need to sign a
new value every time it does a handshake. The client can avoid
validations if it can remember a global database of public
information, but if not it is only slightly worse off then today in
calculation.

By contrast resumption only works if the client maintains some data
that has to be kept secret, and if the server still remembers how to
read the tickets that it handed out. Having resumption doesn't stop
servers going to ECDHE and ECDSA for efficiency reasons. Particularly
at higher security, RSA is extremely slow: my computer can only do 111
RSA 4096 signatures a second. It can do 24 times as many P521
signatures. Even if a small minority of all connections require a
public key operation, that difference matters. (Signatures are
equivalent to decryption, in case people were wondering about RSA
handshakes sans PFS)

Adding PFS to resumption requires two exponentiations client and
server side: one fixed base, one variable base. At that point we've
done enough work to completely redo the connection with HMQV. (well,
modulo the client regenerating its key periodically, or maybe once per
connection for anonymity, and I've ignored the fact that in genus 2 or
on Kummer varieties you have a problem with HMQV and have to do triple
DH instead) I don't see anyone paying that penalty anytime soon.

But don't take my word for it: from Cloudflare: "Because ECDSA is so
much more efficient for our servers, supporting these certificates is
an essential step for enabling SSL for free in 2014." CPU matters.

Sincerely,
Watson Ladd

---

From: Nico Williams <[email-masked]>
Date: Thu, 13 Mar 2014 01:26:57 -0500

> information, but if not it is only slightly worse off then today in

Well, but with resumption the signature validation is also optimized
away for a while.

> read the tickets that it handed out.  [...]

Ah!  Thanks, that's the key.  It's OK to expect servers to remember
how to read their session tickets.  As for the need to keep session
resumption tickets private on the client side... certainly the client
would have to provide integrity protection to any cache of signature
validations and server public ECDH keys, but ticket compromise is
rather severe: past non-PFS resumptions are compromised and the
attacker can impersonate the client in future resumptions regardless
of past PFS use.  Of course, in your scheme if the client can't
protect its local cache then it's subject to some MITM attacks, but
that's a much smaller concern.

Thanks,

Nico
--

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 13 Mar 2014 01:01:31 -0700

On Wed, Mar 12, 2014 at 11:26 PM, Nico Williams <[email-masked]>wrote:

> rather severe: past non-PFS resumptions are compromised

Not necessarily.  The cached session key doesn't need to be the same as the
session key for previous sessions.  And 0-RTT resumptions could have a DH
exchange overlaid on the 1st RT, so they get PFS after that RT.

> and the
> of past PFS use.

And impersonate the server to the client.

>  Of course, in your scheme if the client can't

On the other side of the balance - doing 0-RTT resumption based on session
tickets saves at least 1 DH compared to the 0-RTT flow in EKR's draft or
QUIC.  If clients need to re-authenticate with something like ChannelID, it
might save a second asymmetric op.  Seems worth considering.

Trevor

---

From: Nico Williams <[email-masked]>
Date: Thu, 13 Mar 2014 11:34:42 -0500

> exchange overlaid on the 1st RT, so they get PFS after that RT.

I didn't say previous sessions are compromised, I said "past non-PFS
resumptions are compromised", since they were non-PFS and the session
resumption ticket used to resumed them is compromised, it follows that
those past resumptions are compromised.

> And impersonate the server to the client.

Yes.

> might save a second asymmetric op.  Seems worth considering.

I don't think anyone has made an argument against session resumption
in this thread.  Watson's proposal is one that reduces asymmetric
crypto load in a way that reminds me of resumption, but isn't, and in
particular in a way that is less brittle on the client side w.r.t.
confidentiality protection of local secrets.

Now, the client is bound to have to provide confidentiality protection
for local secrets in *all* cases, but in Watson's scheme generally
only of long-term keys or current session keys).  So I'm not really
too concerned about the client's need to keep resumption tickets
secret: it can always store the resumption keys encrypted in another
secret, so as to minimize the number of secrets to store in a secure
element/token/whatever.  But I am concerned about the need for PFS on
resumption in order to limit the extent of resumption ticket cache
compromise; if you're going to lose the 0-RTT resumption for it, might
as well pick the best "fast reauthentication" protocol possible, and
that might be Watson's.

Nico
--

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 13 Mar 2014 09:48:20 -0700

On Thu, Mar 13, 2014 at 9:34 AM, Nico Williams <[email-masked]>wrote:

>  But I am concerned about the need for PFS on

WRT this specific point, I wanted to observe that computational cost
(within reason) is less important than round trip delay, for a number of
reasons:

- We already have a mechanism for radically reducing the cryptographic
  cost by replacing RSA certificates with EC certificates, so we're going
  to get a large speedup without changing the pattern of crypto operations
  much at all.

- It's possible to ameliorate computational cost by throwing money at the
  problem in terms of more CPU, but it's much harder to unilaterally
  do much about round-trip delay.

- Computers are still getting faster and cheaper, but the speed of light
  is unlikely to change.

I'm certainly not suggesting that we shouldn't minimize the number of
cryptographic operations where practical, but generally I think it's more
important to minimize the number of round trips.

-Ekr

---

From: Nico Williams <[email-masked]>
Date: Thu, 13 Mar 2014 11:52:49 -0500

> (within reason) is less important than round trip delay, for a number of

My concern is in the sense of "this needs to be a security
consideration, and Watson's protocol is worth considering at least as
an option" (modulo IPR, if any).

Nico
--

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 13 Mar 2014 10:17:17 -0700

On Thu, Mar 13, 2014 at 9:48 AM, Eric Rescorla <[email-masked]> wrote:

> (within reason) is less important than round trip delay
>

True, but a 0-RTT session ticket resumption requires less computation than
a 0-RTT handshake based on a semi-static ECDH key (like QUIC, or your
draft) without any RTT tradeoff.

(My understanding of both QUIC and your draft is that in the 0-RTT case
they perform an "overlaid" DH while exchanging application data in the
initial RT, so subsequent data gets PFS while the initial RT does not.
 This could be done with session tickets as well.)

Also: if the semi-static handshake is going to require an expensive client
re-authentication (ChannelID, PAKE, a slow smartcard, etc.), then the
savings for resumption are even greater.

Trevor

---

From: Watson Ladd <[email-masked]>
Date: Thu, 13 Mar 2014 10:29:07 -0700

> an option" (modulo IPR, if any).

Triple DH is unpatented AFAIK. MQV patent expires soon, but I don't
like it. With Triple DH we can use genus 2 for even more speed, and
when Kim Laine finishes his PhD, genus 3. Genus 3 is amazing because
the arithmetic is modulo a 64 bit prime. We can't do higher genus
stuff+MQV because of the lack of an addition formula on the compact
forms.

Sincerely,
Watson Ladd

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 13 Mar 2014 10:46:24 -0700

On Thu, Mar 13, 2014 at 10:29 AM, Watson Ladd <[email-masked]> wrote:

> Triple DH is unpatented AFAIK. MQV patent expires soon

It's a little more complex than this.

I think HMQV has a patent from IBM as well as the Certicom MQV patents.

Triple DH itself is unpatented and derives from [1,2].  But when hashing
identity information into the session key, Microsoft's KEA+ patent (which
covers doing this with a "Double DH") might possibly be viewed as relevant.

(I think that's an obvious combination of prior art, and arguably not
directly relevant.  But it creates some uncertainty.)

Trevor

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.8493
[2] http://www.iacr.org/cryptodb/archive/2005/ASIACRYPT/283/283.pdf

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 13 Mar 2014 11:02:12 -0700

>  This could be done with session tickets as well.)

Thanks for making this point. I think it gets to precisely the questions we
need
to be asking, namely:

1. Do we want to provide a mechanism for a client and server to form a new
TLS connection without doing any public key operations?

2. Do we want to provide a mechanism for a client and server to do a
0-RTT handshake which minimizes the number of public key operations,
potentially at the cost of linkability. (It's possible to do a 0-RTT
handshake
without linkability if the server uses the same DH key for a lot of clients,
but not if you use the same session ticket repeatedly, though maybe you
could swap the ticket each time.)

-Ekr