The cost of quantum-safe SSH
** WARNING: connection is not using a post-quantum key exchange algorithm.
** This session may be vulnerable to "store now, decrypt later" attacks.
** The server may need to be upgraded. See https://openssh.com/pq.html
If you’ve seen this message before, you probably already know which protocol this post is about. Since October 2025, OpenSSH prints it every time a server can’t negotiate a quantum-safe key exchange. Most companies use SSH to administer their machines and move files between them, and that’s exactly the traffic a harvest-now-decrypt-later attacker wants to record today.
OpenSSH has offered a post-quantum key exchange by default since April 2022. Four years later, most servers still don’t support one. In May 2026, Forescout looked at 160 million internet-facing SSH servers and found only 12% do. This third post in our PQC series covers both halves of SSH’s migration, key exchange and authentication, and measures what each one costs.
Where the quantum risk sits in SSH
SSH encrypts the session and authenticates both ends. Both sides usually prove their identity with a digital signature, though the server can also let clients log in with a password. By default, no certificate authority vouches for the server’s public key. The client simply trusts the one it saw on the first connection and stores it in known_hosts. As for the user’s public key, it has to be added on the server beforehand.
Encryption works as in TLS. Client and server agree on a shared secret, then encrypt everything with a symmetric cipher such as AES or ChaCha20. That part is already quantum-safe. The key exchange and the signatures aren’t. With a cryptographically relevant quantum computer, anyone who recorded a session can recover the shared secret and decrypt it. The same machine can forge signatures, letting an attacker impersonate your server or log in as one of your users.
SSH exchanges keys differently from TLS 1.3. Both sides first send a KEXINIT message listing the algorithms they support, including key exchange and host key algorithms. For each, the first algorithm on the client’s list that the server also supports is chosen. Only then does the client send its half of the key exchange, so it never sends a post-quantum key share to a server that can’t use it.
Hybrid on both halves
OpenSSH went hybrid for both the key exchange and the signatures. Each post-quantum algorithm runs alongside a classical one, so an attacker has to break both, and if the post-quantum half breaks, the connection stays as safe as it is today.
OpenSSH 10.0 made mlkem768x25519-sha256 the default key exchange, the same X25519 and ML-KEM-768 pairing as in TLS. It replaced sntrup761x25519-sha512, OpenSSH’s quantum-safe default since 2022, which isn’t a NIST standard.
Signatures followed in October 2026, when OpenSSH 10.6 enabled ssh-mldsa44-ed25519. Each signature pairs an ML-DSA-44 signature with an Ed25519 one, and both must verify. Servers can use it for host keys, and users to log in.
Post-quantum security comes at a price, and that price is size:
Signatures cost the most, almost 40 times their classical size. In TLS, that’s a real problem: the server sends a whole certificate chain, and every certificate carries its own public key and signature. By default, SSH doesn’t use certificate chains. Each side sends one key and one signature, so the extra size stays limited. That’s why post-quantum signatures are practical in SSH today, while the web waits for Merkle Tree Certificates.
However, hybrid signatures are more contested than hybrid key exchange. Filippo Valsorda argued composites add complexity for little gain, since ML-DSA is mature enough to stand alone. OpenSSH shipped the composite anyway. That’s what your tools will support, so it’s the one to deploy for SSH.
What it costs
We measured real SSH logins between the same client and server, over the same network path every time. Sizes and times cover everything from the TCP handshake to the moment the user is logged in. The key exchange and the signatures migrate independently, so we measured them separately.
Key exchange
Host and user keys stay Ed25519. We toggled only the hybrid key exchange on each side, which gives the same four configurations as in our TLS post:
- Classical. Neither side supports mlkem768x25519-sha256.
- Client only. The client offers it and the server doesn’t support it.
- Server only. The reverse.
- Both PQC. Both sides support it, and it’s the one they negotiate.
The hybrid key exchange adds 2.6 KB, taking the handshake from 6.0 KB to 8.6 KB, which corresponds to what we’d expect from the ML-KEM key share and ciphertext.
When only one side supports the hybrid, SSH avoids the overhead TLS pays. Both sides list their algorithms in KEXINIT before anyone sends a key share, so a PQC client never sends its 1.2 KB share to a classical server. The only extra bytes are about 80 B of algorithm names. However, that caution isn’t free and costs SSH one round trip on every connection, PQC or not, whereas TLS 1.3 sends its key share in the first message. But for the PQC transition, it means you can enable the hybrid on clients and servers in any order, and nobody pays for it in the meantime.
Time doesn’t move. On a good network, the four configurations finish within 3 ms of each other, which is within measurement noise. Degraded Wi-Fi doesn’t change that either. Unlike TLS, SSH needs many round trips before the user is logged in, and each one adds its own delay, so a few extra milliseconds disappear in the noise.
Authentication
With the hybrid key exchange on, we switched the keys to ssh-mldsa44-ed25519. First the user key, then the host key, then both. The mixed cases are what a real migration looks like. The host key is the easy part. An admin generates one per server, and any up-to-date client can check it without a hybrid key of its own. User keys take longer, because every user has to create one and add it to every server they log into.
Switching the user key to ssh-mldsa44-ed25519 takes the handshake from 8.6 KB to 15.3 KB, switching the host key to 14.0 KB, and switching both to 20.7 KB, 2.4 times the size with Ed25519 keys.
Why does a post-quantum user key cost more than a host key? Each side sends one signature, but its public key crosses the network several times. The user key is sent three times before login, whereas the host key is sent twice, once by the server and once by the client to bind the login to that server. A third copy of the host key follows right after login, when the server shares its host keys so the client can update its known_hosts. But we stop measuring at login, so it isn’t counted here.
Time also increases. Post-quantum keys on both sides add about 10 ms to the handshake on a good network, and 20 ms on degraded Wi-Fi. As in TLS, the cost comes from the packets, not computation. Every extra packet gives loss and jitter one more chance to slow the login down.
Two halves, two timelines
The key exchange is what you can and should focus on today. An up-to-date OpenSSH client and server negotiate the hybrid without anyone touching a config file, so upgrading is all it takes.
Signatures can wait. A recorded session can be decrypted years later, but a forged signature only helps an attacker during a live connection, once a quantum computer exists. The signature migration takes more work. Admins have to generate a hybrid host key on every server. Every user has to generate a hybrid key, add it to every machine they log into and, above all, delete their old classical keys from those servers.
That cleanup really matters. Unlike TLS certificates, SSH keys don’t expire by default. Forget one old key in authorized_keys, and a quantum attacker can use it to log into your machine. Finding out which servers still negotiate a classical key exchange, and which keys are still lying around, starts with a cryptographic inventory.
