[TLS] Thoughts on TLS 1.3 cryptography performance

[Watson Ladd <[e-mail]>]

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