You are connecting to an OpenSSH server using an RSA private key and the following error is displayed:

You check the OpenSSH server logs and find the following entry:

You are not able to authenticate with the SSH server.

Paramiko

Your program is using the Paramiko SSH library. Paramiko will throw an exception:

What does the error mean?

SSH today supports three RSA signature algorithms:

  • ssh-rsa
  • rsa-sha2-256
  • rsa-sha2-512

The original signature algorithm supported only ssh-rsa. That signature used SHA-1. The hash algorithm SHA-1 is considered weak/broken today, so SHA-1 was replaced with SHA-2. The SSH key types rsa-sha2-256 and rsa-sha2-512 replaced ssh-rsa. The OpenSSH server disabled the ssh-rsa signature algorithm in version 8.8 on 2021-09-26.

The SHA-1 signature algorithm is defined in RFC4253 Section 6.6.

The SHA-2 signature algorithms are defined in RFC8332.

The server error message means that the client is using RSA keys with SHA-1 signatures and the signature algorithm has been disabled in the SSH server.

The SSH client is older than version 8.8 and the OpenSSH server is version 8.8 or newer.

SSH Key Type Confusion

The OpenSSH team decided to keep the key type name ssh-rsa, even after deprecating the signature algorithm with the same name. I guess this would break other features such as the authorized_keys file, the known_hosts file, SSH server fingerprint programs, and more. Their goal was probably to keep the blast radius from this change as small as possible.

The critical point is the word ssh-rsa is used in several contexts. It can mean the SSH key type and the SSH signature algorithm. Same name but very different meanings:

  • ssh-rsa is used as the SSH Key Type e.g the type of public key cryptography (RSA, DSA, ECDSA, EdDSA).
  • ssh-rsa is used as the SSH Signature Algorithm e.g. the protocol used during key exchanges (RSA+SHA-1, RSA+SHA-2).

Solutions:

  1. If you are using the SSH client program, upgrade the client to be at the same version or newer than the SSH server. Support for rsa-sha2-256 and rsa-sha2-512 was released in version 8.8 (2021-09-26).
  2. If you are using an SSH library, upgrade the library.
    • For example, the Python Paramiko library did not support rsa-sha2-256 and rsa-sha2-512 until version 2.9.0 (2021-12-23). Older versions of Paramiko would fail to connect to OpenSSH server version 8.8 or newer when using RSA keys. Older libraries used SHA-1 for the signature algorithm instead of SHA-2.
  3. Enable ssh-rsa in the OpenSSH server. This is not recommended for security reasons.
    • Edit the sshd_config file. For Debian-based systems: /etc/ssh/sshd_config.
    • Add the following line:
      • PubkeyAcceptedKeyTypes=+ssh-rsa

Verify that your SSH server does not support ssh-rsa

The SSH client that is part of the OpenSSH tool suite has several useful command line options.

This option declares the SSH key types that the SSH client will use:

  • -o PubkeyAcceptedKeyTypes=ssh-rsa

This option disables asking for a password:

  • -o PasswordAuthentication=no

Combine those options and connect to your SSH server. If ssh-rsa is supported the connection will succeed. That means the server is vulnerable to attack. Review the server’s configuration and disable ssh-rsa if possible. If not, upgrade the server to a version that supports RSA+SHA-2.

Paramiko

The following Python program will also generate the same error but with a different exception message. If this program succeeds, the SSH server is vulnerable.

force_rsa_error.py:

Run the program:

An exception is thrown:

Solution:

Change this line:

Change the key_type to the support signature algorithm rsa-sha2-256:

The program supports a third command line argument which you can use to change the key_type for testing:

On success the program prints the SSH fingerprint:

Summary

Once you understand the error message, the solution becomes obvious. An important point to mention is that the problem is caused by a security fix. The SHA-1 security risk is very dangerous today. Under More Information, I provide a couple of article links.

Unless required, do not enable ssh-rsa by modifying the OpenSSH server configuration file with this change: PubkeyAcceptedKeyTypes=+ssh-rsa. If you do, roll out client updates as soon as possible and disable ssh-rsa.

More Information