Re: [TLS] Thoughts on TLS 1.3 cryptography performance

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:tls-bounces@ietf.org] On Behalf Of Watson Ladd
Sent: Wednesday, March 12, 2014 9:11 PM
To: tls@ietf.org
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.

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

_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls