You SSH into your server and see this:

** WARNING: connection is not using a post-quantum key exchange algorithm.
** This session may be vulnerable to "store now, decrypt later" attacks.

Scary. Let’s break it down.

The Threat: Store Now, Decrypt Later

Today’s SSH encryption is mathematically strong; breaking it would take a classical computer millions of years.

But quantum computers play by different rules. A sufficiently powerful quantum computer running Shor’s algorithm can break the math that protects most of today’s public-key cryptography in hours, not millions of years.

Here’s the unsettling part: quantum computers powerful enough to do this don’t exist yet. So why worry now?

Because adversaries, nation-states especially, are already recording encrypted traffic today with the plan to decrypt it later once quantum hardware matures. This is the “store now, decrypt later” (SNDL) attack. If you’re sending anything sensitive over SSH that needs to stay secret for the next 10–20 years, you’re already at risk.

This is not science fiction. The NSA, CISA, and NIST have all issued guidance on migrating to post-quantum cryptography now.

What Is Key Exchange, Anyway?

Before SSH can encrypt your session, both sides need to agree on a shared secret, a temporary key used to encrypt everything else. This negotiation is called key exchange (Kex).

Think of it like this: two people want to agree on a secret color without anyone watching being able to figure it out. Key exchange is the cryptographic version of that trick (look up Diffie-Hellman if you want the details, it’s a beautiful idea).

The problem: the math behind classical key exchange (Diffie-Hellman, elliptic curves) is vulnerable to quantum computers.

Classical vs Post-Quantum Key Exchange

Here’s a quick tour of what SSH supports and where each algorithm stands:

Classical (vulnerable to quantum computers)

All of the above are broken by a quantum computer running Shor’s algorithm.

Post-Quantum (safe against quantum computers)

Both are hybrid algorithms they layer a post-quantum algorithm on top of a classical one. This means:

• If the PQ algorithm has a flaw → X25519 still protects you (classical security).
• If a quantum computer attacks → the PQ layer still protects you.

You get the best of both worlds. Hybrids are the recommended approach during this transition period.

mlkem768x25519-sha256 is the one to prefer long-term. ML-KEM (formerly Kyber) was selected by NIST as the standard post-quantum key encapsulation mechanism in 2024. It’s in OpenSSH 9.9+.

[email protected] uses NTRU Prime, an older PQ candidate. Still solid, available in older OpenSSH. Use it if you’re on 8.5–9.8.

Why the Warning Appears

OpenSSH 8.5+ enables PQ by default in its built-in KexAlgorithms list. But if your sshd_config has a hardcoded KexAlgorithms line, it overrides the defaults and, whoever wrote that line may not have included PQ algorithms.

That’s exactly what triggers the warning: the server is advertising only classical algorithms, so the client (which prefers PQ) falls back to classical.

Check your server:
grep -i kexalgorithms /etc/ssh/sshd_config

If you see a line with only classical algorithms (like curve25519-sha256,diffie-hellman-group-exchange-sha256), that’s your culprit.

The Fix

Step 1: Edit /etc/ssh/sshd_config

Add the PQ algorithm at the front of the list. OpenSSH negotiates in order; first match wins.

If you’re on OpenSSH 9.9+ (check with ssh -V):

KexAlgorithms mlkem768x25519-sha256,[email protected],curve25519-sha256,[email protected],diffie-hellman-group-exchange-sha256

If you’re on OpenSSH 8.5–9.8 (like Ubuntu 24.04’s bundled 9.6p1):

KexAlgorithms [email protected],curve25519-sha256,[email protected],diffie-hellman-group-exchange-sha256

Keep the classical algorithms as fallbacks. Some clients (embedded systems, old hardware) don’t support PQ yet and need them to connect.

To see every algorithm your OpenSSH build actually supports: ssh -Q kex

Step 2: Validate and Restart

Always validate before restarting — a typo in sshd_config can lock you out: sudo sshd -t

If no errors: sudo systemctl restart sshd

Step 3: Verify It Worked

From a client machine, connect with verbose output and grep for the negotiated kex: ssh -v user@yourserver 2>&1 | grep "kex_"

Look for something like: debug1: kex: algorithm: [email protected] or from the server side, check an active connection: sudo ss -tnp | grep :22

What About the Client Side?

The same fix applies to your SSH client config (~/.ssh/config or /etc/ssh/ssh_config). If your client has a hardcoded KexAlgorithms line without PQ, it’ll fall back to classical even when connecting to a PQ-capable server.

To suppress the warning on the client side while you work on fixing servers:

# ~/.ssh/config
Host *
    KexAlgorithms [email protected],curve25519-sha256,diffie-hellman-group-exchange-sha256

But the real fix is upgrading both ends.

TL;DR

The quantum era isn’t here yet, but the window to prepare is now. Updating KexAlgorithms takes two minutes and is one of the easiest wins in modern server hardening.

Ubuntu 24.04 ships OpenSSH 9.6p1, which supports [email protected] out of the box. OpenSSH 9.9+ (available via PPA or newer distros) adds the NIST-standardized mlkem768x25519-sha256.