** 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

This warning indicates that your SSH session negotiated a classical key exchange (KEX) algorithm rather than a post-quantum (PQ) or hybrid post-quantum algorithm. In practical terms, the confidentiality of traffic in that session relies on cryptographic assumptions that powerful quantum computers could break in future.

Why this matters

• Quantum risk (harvest-now-decrypt-later): Attackers can record encrypted traffic now and decrypt it later once quantum capabilities are available. Using a PQ or hybrid PQ KEX protects the session key against this.
• What PQ KEX changes: SSH’s KEX establishes the session’s symmetric keys. Modern OpenSSH supports a hybrid KEX that combines classical elliptic-curve Diffie-Hellman with a quantum-resistant algorithm. This protects confidentiality even if classical algorithms are broken in future.
• What it does not change: SSH host key and user authentication signatures remain classical (e.g., Ed25519 or RSA). The PQ change helps confidentiality; authenticity still uses traditional signature algorithms in current mainstream OpenSSH.

Prerequisites

• OpenSSH 9.0 or newer on both server and client is recommended. These versions support the hybrid PQ KEX:
• sntrup761x25519-sha512@openssh.com

If your OpenSSH version is older, upgrade first.

# Check client version
ssh -V

# On Linux servers (Debian/Ubuntu)
sudo apt update
sudo apt install --only-upgrade openssh-server openssh-client

# On RHEL/CentOS/Alma/Rocky
sudo dnf upgrade openssh-server openssh-clients

# On Fedora
sudo dnf upgrade openssh

Step 1: Confirm support for PQ KEX

  ssh -Q kex | grep -E 'sntrup|x25519'

• List KEX algorithms supported by your SSH client:

Expect to see:

  sntrup761x25519-sha512@openssh.com

  sudo sshd -T | sed -n 's/^kexalgorithms //p'

• On the server, check the effective KEX setting (if any):

If no line is printed, the server is using its built-in defaults.

Step 2: Configure the SSH server to prefer a post-quantum KEX

   sudo cp /etc/ssh/sshd_config /etc/ssh/sshd_config.backup.$(date +%F)
   sudo nano /etc/ssh/sshd_config

1. Back up and edit the SSH daemon configuration:

1. Add or update a KexAlgorithms line. Two common policies are shown below.

     KexAlgorithms sntrup761x25519-sha512@openssh.com,curve25519-sha256,curve25519-sha256@libssh.org

• Prefer PQ (recommended, keeps safe fallbacks for older clients):

This prioritises the hybrid PQ algorithm, then falls back to modern classical KEX if required.

     KexAlgorithms sntrup761x25519-sha512@openssh.com

• Enforce PQ-only (breaks older clients that lack PQ support):

Notes:

• Place this setting outside any Match blocks unless you intend to vary it by user/host.
• On RHEL/Alma/Rockey you should instead create a file named 00-px-kex.conf in the sshd_config.d directory and place the KexAlgorithms in there instead. 
• Avoid listing obsolete KEX (e.g., diffie-hellman-group14-sha1) unless you must support legacy clients.

   sudo sshd -t

1. Validate the configuration before applying:

No output indicates success. Errors will be printed if there are typos or unknown algorithms.

   # Most systemd distributions
   sudo systemctl reload sshd 2>/dev/null || sudo systemctl reload ssh

   # If reload is unsupported on your platform, use restart instead (with caution)
   # sudo systemctl restart sshd 2>/dev/null || sudo systemctl restart ssh

1. Reload the SSH service to apply changes (keep an existing root session open in case you need to roll back):

   sudo sshd -T | sed -n 's/^kexalgorithms //p'

1. Confirm the daemon now advertises your intended KEX list:

Step 3: (Optional) Prefer PQ KEX on SSH clients

Even with a correctly configured server, old client preferences may negotiate a non-PQ KEX. You can prefer PQ KEX on the client:

  ssh -o KexAlgorithms=sntrup761x25519-sha512@openssh.com user@server

• Per-connection:

  Host myserver
      HostName server.example.com
      KexAlgorithms sntrup761x25519-sha512@openssh.com,curve25519-sha256,curve25519-sha256@libssh.org

• Persistent client setting (~/.ssh/config):

Step 4: Test and verify it is working

  ssh -vv user@server exit |& sed -n 's/^debug1: kex: algorithm: //p'

• Verify negotiation from the client side:

Expected output:

  sntrup761x25519-sha512@openssh.com

  ssh -vvv user@server exit |& grep -E 'kex: algorithm'

• Alternatively, use a more verbose trace and look for the selected KEX:

  nmap -sV --script ssh2-enum-algos -p 22 server.example.com

• Enumerate what the server advertises (from a scanning host with Nmap installed):

Under “kex_algorithms”, ensure sntrup761x25519-sha512@openssh.com appears and, ideally, is listed first.

  sudo sshd -T | sed -n 's/^kexalgorithms //p'

• Confirm effective server configuration again:

Common issues and remedies

• The algorithm is unknown when testing the config:
• Your OpenSSH is too old. Upgrade to 9.0+ and try again.

    sudo cp /etc/ssh/sshd_config.backup.* /etc/ssh/sshd_config
    sudo sshd -t && sudo systemctl reload sshd 2>/dev/null || sudo systemctl reload ssh

• Clients can no longer connect after enforcing PQ-only:
• Restore your backup and keep fallbacks:
• Or re-add curve25519-sha256 fallbacks after the PQ algorithm.

• The scanner still reports non-PQ usage:
• Ensure both ends support PQ and that PQ is listed first in their preferences.
• Confirm with ssh -vv that negotiation picks sntrup761x25519-sha512@openssh.com.
• Clear any Match blocks that override KexAlgorithms for particular users or addresses.

Summary

Enabling and preferring the hybrid post-quantum KEX sntrup761x25519-sha512@openssh.com in /etc/ssh/sshd_config protects the confidentiality of SSH sessions against future quantum adversaries while maintaining compatibility with modern clients. Verify by inspecting the negotiated KEX in a verbose SSH connection and by enumerating the server’s offered algorithms.