Fixing the OpenSSH Post-Quantum Warning on RHEL 9

Fired up my RHEL9 server today, something that I have not done in a while due to the savage summer heat in the southern US. All my Dell servers have had the summer off for this reason.

Upon login via ssh I saw a warning message, which I do not think I have seen before on this machine – all my other Dell servers are RHEL 10, and this one was built with RHEL 9 due to deprecated support for older processors in RHEL 10. Specifically the Intel Xeon E5-2697 (Ivy Bridge) v2.

Anyway, below is the warning message.

** 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 means that the SSH client supports post-quantum key exchange, but the RHEL 9 SSH server did not offer one. It does not indicate that the current connection is broken; it warns about possible future decryption of captured traffic.

Hence the “store now, decrypt later“ message above.

SNDL/HNDL

“Store Now, Decrypt Later” (also called Harvest Now, Decrypt Later) is when an attacker intercepts encrypted traffic, not with the idea of decrypting it now, but rather once they have access to a more powerful quantum computer running advanced algorithms. Today’s standard SSH connections rely on classical asymmetric cryptography (like Elliptic Curve Diffie-Hellman) which quantum computers can theoretically break.

Meaning, you may not be vulnerable now, but you could be later.

Most newer OpenSSH clients warn when a connection does not negotiate a post-quantum key-exchange algorithm because long-lived or sensitive data captured today could remain valuable in the future.

Honestly this is not a big concern in my lab, but the warning will drive me up a wall.

The RHEL 9 Fix

The good news is that RHEL 9.1 and later support the following hybrid post-quantum SSH key-exchange method. So we can remediate.

sntrup761x25519-sha512@openssh.com

This combines the post-quantum sntrup761 algorithm with the traditional X25519 elliptic-curve key exchange. Because it is hybrid, the connection remains protected as long as either component remains secure.

Red Hat added support for this algorithm to the RHEL 9 system-wide cryptographic-policy framework, but it must be explicitly enabled through a custom subpolicy.

Confirm the RHEL Version

First, lets confirm that the server is running RHEL 9.1 or later:

cat /etc/redhat-release

You can also check the installed OpenSSH and crypto-policy package versions:

rpm -q openssh-server crypto-policies

Update OpenSSH and the Crypto-Policy Packages

sudo dnf update openssh-server crypto-policies

This ensures that the server has the RHEL packages that include support for the SNTRUP hybrid key-exchange algorithm.

In my case, this step initially revealed a separate Red Hat subscription problem:

Status code: 403 for https://cdn.redhat.com/...

A 403 from the Red Hat CDN generally means that the server can reach the repository, but the system is not currently authorized to download its content. This may be caused by an expired developer subscription, stale registration data, an invalid entitlement, or a system identity left over from an earlier installation.

Useful commands for checking the registration state include:

sudo subscription-manager identity
sudo subscription-manager status
sudo subscription-manager repos --list-enabled

As I said this machine has been powered off for a while, so lets refresh registration and repository metadata.

sudo subscription-manager refresh
sudo dnf clean all
sudo rm -rf /var/cache/dnf
sudo dnf makecache

In my case, the system registration is stale, so I need to unregister and re-register.

sudo subscription-manager unregister
sudo subscription-manager clean
sudo subscription-manager register

After registration, we ensure that the standard RHEL 9 repositories are enabled:

sudo subscription-manager repos \
  --enable=rhel-9-for-x86_64-baseos-rpms \
  --enable=rhel-9-for-x86_64-appstream-rpms

Then rebuild the DNF cache:

sudo dnf clean all
sudo rm -rf /var/cache/dnf
sudo dnf makecache

Create a Custom Crypto-Policy Module

Next we create a new policy module named SNTRUP:

sudo tee /etc/crypto-policies/policies/modules/SNTRUP.pmod >/dev/null <<'EOF'
key_exchange = +SNTRUP
EOF

The module name must use uppercase characters because crypto-policy module filenames are conventionally uppercase and end with .pmod.

The policy adds the SNTRUP algorithm to the key-exchange methods permitted by the existing system-wide policy.

Apply the Policy

Apply the custom module on top of the normal RHEL DEFAULT policy:

sudo update-crypto-policies --set DEFAULT:SNTRUP

Confirm that the new policy is active:

update-crypto-policies --show

You are looking for expected output as shown below.

DEFAULT:SNTRUP

RHEL uses system-wide cryptographic policies to configure applications including OpenSSH, TLS libraries, IPsec, DNSSEC, and Kerberos. Using a crypto-policy module is therefore preferable to manually changing generated OpenSSH backend files.

Restart SSH

Next we restart sshd so that it reads the updated cryptographic policy:

sudo systemctl restart sshd

And we confirm that the service restarted without issue

sudo systemctl status sshd --no-pager

Verify the Server Configuration

Run the command below to check the current SSH server key-exchange configuration:

sudo sshd -T | grep -i '^kexalgorithms'

The output should include:

sntrup761x25519-sha512@openssh.com

We can also inspect the generated OpenSSH server crypto-policy backend:

grep -i kexalgorithms \
  /etc/crypto-policies/back-ends/opensshserver.config

Files beneath /etc/crypto-policies/back-ends/ are generated by the crypto-policy framework and should not normally be edited directly. Manual changes may be overwritten the next time the system policy is updated.

Now it’s time to test.

7. Test a New SSH Connection

Open a new terminal window, leaving the existing window open just in case we broke something. In the second window, connect with verbose logging:

ssh -vv user@server

Look for a line similar to:

debug1: kex: algorithm: sntrup761x25519-sha512@openssh.com

The original post-quantum warning should no longer appear.

A more focused test can be performed by explicitly requesting the algorithm:

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

If this succeeds, both the SSH client and server support the hybrid key exchange.

We can check whether the local SSH client recognizes the algorithm with:

ssh -Q kex | grep -i sntrup

Expected output:

sntrup761x25519-sha512@openssh.com

Depending on the client version, another SNTRUP variant may also be listed.

Troubleshooting

If the algorithm does not appear in the output from sshd -T, first confirm that the custom policy is active:

update-crypto-policies --show

Then confirm that the policy module contains the correct entry:

cat /etc/crypto-policies/policies/modules/SNTRUP.pmod

It should contain:

key_exchange = +SNTRUP

Reapply the policy and restart SSH:

sudo update-crypto-policies --set DEFAULT:SNTRUP
sudo systemctl restart sshd

Check the SSH service logs for errors:

sudo journalctl -u sshd -b --no-pager

You can also validate the SSH configuration before restarting the service:

sudo sshd -t

No output means that the configuration passed validation.

Important FIPS Consideration

Do not replace an existing FIPS policy with DEFAULT:SNTRUP on a system required to operate in FIPS mode.

Check the current policy first:

update-crypto-policies --show

Also check whether the kernel is operating in FIPS mode:

cat /proc/sys/crypto/fips_enabled

A value of 1 means that FIPS mode is active.

Algorithms permitted by the normal RHEL DEFAULT policy are not automatically permitted under the RHEL FIPS policy. Red Hat documents that certain Curve25519-based SSH key exchanges are not allowed in FIPS mode, so the SNTRUP hybrid method should not be enabled without validating the applicable compliance requirements.

Rolling Back the Change

To remove the SNTRUP subpolicy and return to the standard RHEL default policy:

sudo update-crypto-policies --set DEFAULT
sudo systemctl restart sshd

Confirm the result:

update-crypto-policies --show

Expected output:

DEFAULT

The custom policy file can then be removed if it is no longer needed:

sudo rm -f /etc/crypto-policies/policies/modules/SNTRUP.pmod

Final Result

After enabling the RHEL crypto-policy module, restarting sshd, and creating a new connection, the server and client should negotiate:

sntrup761x25519-sha512@openssh.com

The SSH session still uses familiar symmetric encryption and authentication mechanisms. The portion being changed is the initial key exchange used to establish the session keys.

This does not make the entire SSH protocol “post-quantum.” It adds a hybrid post-quantum key-exchange mechanism designed to protect the session-establishment process against both traditional attacks and the future possibility of cryptographically capable quantum computers.

This server that has a few years of useful service (specifically for my Infiniband testing), but cannot move to RHEL 10. So enabling the supported RHEL 9 hybrid key exchange is “good enough”.