TLS 1.3 PQ Auth Performance Study
Panos Kampanakis (pkampana)
Hi all,
We wanted to bring up our paper (https://eprint.iacr.org/2020/071 ) that just appeared in NDSS 2020 as input to NIST's Round 3 decision process.
The paper evaluates the NIST PQ Signature candidates used in X.509 certificates for TLS 1.3 server authentication. Note that we do not make assertions on the security of any of the schemes. As expected, the best performing candidates are Dilithium and Falcon mostly because they do not introduce extra-round trips (when the TCP initcwnd is set to 10MSS). As we did not test the AVX2 optimized code at the time, some of the schemes seem a little worse than they can be, but the results would not deviate by a lot when the most commonly used initcwnd of 10MSS is in place at the server. Time sensitive TLS applications would probably want to make use of the two better performing algorithms. Non time-sensitive applications like VPNs that stay up for long periods of time could make use of other algorithms (with relatively efficient signing) because handshake time is amortized over long-lasting connections.
Section VII discusses how these PQ certificates could be integrated to existing protocols, potential performance improving techniques and implications if the better performing algorithms are not standardized.
Rgs,
Panos
D. J. Bernstein
> As expected, the best performing candidates are Dilithium and Falcon
> mostly because they do not introduce extra-round trips (when the TCP
> initcwnd is set to 10MSS).
major content-distribution networks already setting initcwnd more than
twice that (more precisely, between 22 and 46):
https://www.cdnplanet.com/blog/initcwnd-settings-major-cdn-providers/
This undermines conclusions based upon the initcwnd=10 assumption. It's
weird to see benchmarks not covering larger values of initcwnd. (That's
ip route change ... initcwnd ... under Linux.)
> As we did not test the AVX2 optimized code at the time, some of the
> schemes seem a little worse than they can be
Figure 3 are around 100ms. For SPHINCS+ this appears to come primarily
from CPU time, and simply switching to the AVX2 software would have
removed most of the CPU time.
The primary goal of benchmarks is to predict the performance that users
will see. Taking reference software instead of the fastest software is
contrary to this. Even worse, the resulting performance understatements
vary from one scheme to another, corrupting comparisons.
Furthermore, reference software should be designed for readability. For
people auditing and verifying AVX2 software, it's very helpful to factor
* comparing AVX2 implementations to specifications
into two (or more) steps:
* compare reference implementations to specifications;
* compare AVX2 implementations to reference implementations.
Do we want reference software having its readability compromised for the
sake of better performance, simply to protect against measurements that
use the reference software and refuse to use faster software?
---Dan
Panos Kampanakis (pkampana)
Hi Dan,
Thank you for the comments.
About the AVX2 optimizations, we did not include them as most of this work took place in the summer of 2019 and the tooling was not ready at the time. AVX2 would save ~40ms from SPHINCS+ handshakes, ~5.5ms from Falcon, ~8ms from MQDSS, ~2.5ms from Picnic. We say a few times in the paper that as signing gets faster, TCP Congestion will be the bottleneck. The point is that as long as we have extra round-trips these will be the most penalizing factor. Btw, even for AVX2 optimized SPHINCS+, 20ms signing will usually not be acceptable for a live TLS signer because it would significantly decrease his throughput as we show in the paper with Falcon’s unoptimized ~6ms signing.
About the TCP initcwnd, we did not experiment with higher (than the most common 10MSS) TCP initcwnd for the reasons explained in Section VII-C. Yes we could have avoided round-trips by increasing it to higher values. We could have increased it to any value to fit any scheme’s cert chain and that would give us some extra data points. I think the point is proven anyway though: If initcwnd fits the cert chain + OCSP staple + CertVerify then you do better because you avoid round-trips.
A couple of clarifications about the initcwnd:
- Increasing TCP initcwnd from the most commonly used 10MSS to ~18MSS to accommodate LUOV, ~26MSS to accommodate qTesla, ~35MSS to accommodate SPHINCS+ (double that if are talking HTTPS) or more in every Internet server that wants to support PQ Auth could save round-trips but is a pretty drastic change. It could have adverse effects in lossy environments while in the TCP slow-start phase. RFC3742 talks about the issue and Appendix A of RFC6928 lists a set of concerns as well. It would affect all applications running over TCP even for 3rd party TCP connections travelling on the same link that do not do TLS or PQ authentication. I am all for increasing TCP initcwnd in all TCP implementations, but I would not do it without lengthy and careful real-world experimentation on the Internet like what Google did to push for the change to 10MSS.
- some, not all, content providers (CDNs) may support higher initcwnds but these are highly optimized with various other mechanisms, well-tested and monitored environments. A content provider does not pick a 20 or 30MSS initcwnd light-heartedly. Some even dropped their initcwnd from what they were using in 2014 in the study you cited. Additionally, not all TLS applications are behind a CDN, most of them are not. CDNs represent a fraction of the web, the do not represent all TLS deployments.
- Regardless of initcwnd, Dilithium and Falcon would still outperform all other schemes in a TLS context.
Rgs,
Panos
-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of D. J. Bernstein
Sent: Wednesday, February 26, 2020 6:54 PM
To: pqc-...@list.nist.gov
Subject: Re: [pqc-forum] TLS 1.3 PQ Auth Performance Study
* PGP Signed by an unknown key
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20200226235338.27210.qmail%40cr.yp.to.
* Unknown Key
* 0x3B0E5459