Many of today’s widely used communication protocols rely heavily on classical public-key schemes, which a sufficiently powerful quantum computer could break using Shor’s algorithm. However, encrypted communication is already at risk, since attackers can record and store it and, once such a computer exists, decrypt it. Quantum-resistant schemes have been developed to prevent this, and some of them are already standardized by NIST. They are now being integrated into existing protocols such as TLS and SSH. That mainly requires adapting the key exchange and the signature schemes. This thesis focuses on the key exchange. The cryptographic security of the new schemes has been well studied. In contrast, much less is known about their performance in SSH and their behavior under real-world network conditions. This highlights the need to test and compare classical, PQC and hybrid KEX algorithms in SSH under various network constraints.
As part of this thesis, a framework based on the OpenSSH fork from the OQS project was developed to record and analyze the SSH handshake under emulated network conditions, using two independent measurement methods. The conditions examined are latency, packet loss, bandwidth limitation, jitter and MTU. For all 61 SSH KEX algorithms, the framework determines the total KEX time and its distribution across the individual phases, the amount of data transmitted in bytes, the number of TCP packets and TCP retransmits, and the timeout rate.
In most of the network scenarios tested, KEX performance is governed not by the computation time of the individual KEX algorithm but by the amount of data transmitted. The clearest example is the Classic McEliece variant classic-mceliece-348864, which needs over 900 TCP packets at the smallest tested MTU of 576 B, whereas most of the other algorithms require only 25 to 35. Classic McEliece is thus impractical for real-world networks. Without network constraints, by contrast, most PQC algorithms are quite competitive with the classical ones, as the BIKE, ML-KEM and Kyber families as well as sntrup761 are up to around 5 ms faster than the classical curve25519-sha256, which is preferred by default in OpenSSH. The hybridization of PQC algorithms also has little impact on network behavior, since it adds at most 3.2% more bytes. KEX time increases by up to a fifth, but only because the implementation used performs classical and PQC key generation sequentially. This proportion could be reduced through parallel computation. Overall, the ML-KEM family and sntrup761 are recommended choices. Their hybrid variants are already available in OpenSSH.