Post-Quantum TLS 1.3 and SSH Performance (preliminary results)

Co-author: Dimitrios Sikeridis.

Motivation

As brought up on multiple occasions, if a real-world quantum computer was ever built, it could jeopardize public key exchange, encryption, and digital signature schemes used in secure tunnel protocols today like (D)TLS, SSH, IKEv2/IPsec and more. To prepare for a post-quantum future, NIST has embarked on a journey of standardizing post-quantum algorithms, IETF has seen RFC draft submissions for using these algorithms and multiple vendors like Cisco, Microsoft, Cloudflare, Google, AWS have been looking at post-quantum key exchange or authentication in TLS. These attempts examine key exchange or authentication performance separately. They have shown some post-quantum algorithms perform slower than classical ones we use today, while others would significantly slow down the TLS handshake.

Almost all secure tunnel protocols would require the introduction of post-quantum algorithms in their key exchange and authentication mechanisms to become quantum-resistant. The performance of quantum-resistant key exchange and authentication altogether has not been extensively investigated yet. Recently we have been focusing on experimenting with quantum-secure key exchange in conjunction with authentication in TLS 1.3 and SSH. The preliminary results are promising as we expected by extrapolating from the previous studies.

PQ Algorithms

We have been focusing on efficient lattice algorithms for key exchange like the ntruhrss701 parameter of the NTRU NIST submission and Kyber-512 of the Kyber submission. These algorithms have relatively small public keys and ciphertexts (≈1KB) with fast keygen/encapsulation/decapsulation (<1ms). Note that our friends at Cloudflare also examined NTRU-HRSS as a good candidate for TLS key exchange.

For authentication we have been experimenting with Dilithium which offers a few KB signatures and public keys with fast signing and verification. The Dilithium and Falcon submissions were shown to perform the best in TLS in our recent NDSS paper. We have also been looking into SPHINCS⁺-128f and SPHINCS⁺-192f from the SPHINCS⁺ NIST submission. SPHINCS⁺ is a well-trusted algorithm which although it performed poorly in TLS, we expected it to perform better in SSH.

Preliminary Results

Below we can see the Median and 95^th percentile of the TLS 1.3 handshake time for classic key exchange (P256 curve ECDH) and signature (2048-bit RSA) certificates, hybrid (classical+post-quantum) key exchange (P256 curve ECDH and ntruhrss701) and classic signature (2048-bit RSA) certificates, classic (P256 curve ECDH) and post-quantum signature (Dilithium III) certificates and hybrid key exchange (P256 curve ECDH and ntruhrss701) and post-quantum signature (Dilithium III) certificates.

We can see that all post-quantum combinations are just within 1-2ms slower than the classical handshake. That generally agrees with Cloudflare’s CECPQ2 results with NTRU-HRSS and our results with Dilithium III. The performance of NTRU-HRSS is probably slightly better than previously because of AVX2 optimizations. Since both NTRU-HRSS and Dilithium III perform fast (<1ms), the additional overhead is introduced by the more public key, ciphertext, and signature data transferred in the post-quantum handshake. This data amounts to approximately 13KB which does introduce extra round-trips due to TCP Congestion Control and thus does not introduce much overhead.

Below we can see the Median and 95^th percentile of the SSH handshake time for classic key exchange (P256 curve ECDH) and signing keys (2048-bit RSA), hybrid key exchange (P256 curve ECDH and ntruhrss701) and classic signing keys (2048-bit RSA), classic (P256 curve ECDH) and post-quantum signing keys (SPHINCS⁺-128f) and hybrid key exchange (P256 curve ECDH and ntruhrss701) with post-quantum signing (SPHINCS⁺-128f) keys.

We can see that hybrid key exchange leads to approximately 1ms SSH handshake slowdown which is in line with the TLS results. That can mostly be attributed to the few KB of extra data (public key, ciphertext) introduced in the handshake by the post-quantum algorithm. When post-quantum SPHINCS⁺-128f keys are introduced for authentication, the handshake slows down more significantly (approximately 30%). The reason is the slower SPHINCS⁺-128f signing and more importantly, the two extra round-trips introduced in each direction by the TCP Congestion Control as the SPHINCS⁺-128f signature (≈17KB) exceeds the TCP Initial Congestion Window (initcwnd). A 30% SSH handshake slowdown may be acceptable since SPHINCS⁺ is one of the most trusted signature algorithms which relies on a mature and well-understood hard problem. Otherwise, better performing signature algorithms like Dilithium and Falcon may be preferable if standardized by NIST.

We have also been experimenting with various TCP Initial Congestion Window (initcwnd) values to study the improvement they can offer by eliminated round-trips introduced by post-quantum algorithms. Results show that increasing the window by 2-3MSS the SPHINCS⁺-128f handshakes significantly. SPHINCS⁺-192f requires over 30MSS congestion window to have a noticeable speed up. The figure below shows the speed up for a post-quantum SSH handshake when eliminating one round-trip each direction by increasing the congestion window. It also includes the flat time of an SSH handshake using classical crypto that does not incur any extra round-trips.

Future Work

We intend to continue our testing to more globally spread clients and servers to assess the impact on more realistic Internet scenarios. We will also test more parameters and algorithm combinations in classic, post-quantum and hybrid scenarios. Hopefully we will be able to show that there are more satisfactory algorithm combinations for a quantum-secure TLS and SSH without sacrificing current performance. We will share our results in due time.