Fix userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes

In this article we will fix the server log line userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes so public-key login works again. Newer OpenSSH prints the same reject with PubkeyAcceptedAlgorithms.

What the message means:

• An RSA authentication attempt used a signature algorithm that is not in the server’s accepted list
• In many cases that is the legacy SHA-1 ssh-rsa signature
• On older OpenSSH builds the log text may only identify the RSA key type, not the exact algorithm offered
• Confirm the real algorithm with ssh -vvv (signing using ...) before changing the server

Do not start by re-enabling SHA-1 on the server. First:

• Test whether the same RSA key works with rsa-sha2-256 or rsa-sha2-512
• Or switch to Ed25519

I reproduced the failure and those fixes on RHEL 8.10.

What Does userauth_pubkey key type ssh-rsa not in PubkeyAcceptedKeyTypes Mean?

userauth_pubkey is the SSH server step that checks your public key login. The rest of the line means an RSA signature the client offered is not in the server’s accepted list.

That name is easy to misread for two reasons.

First, ssh-rsa appears in two places:

Key takeaway from that table:

• Seeing ssh-rsa at the start of authorized_keys does not mean the login must use SHA-1
• The same RSA key can authenticate with rsa-sha2-256 or rsa-sha2-512

Second, the log line prints the name from the key object, not a guaranteed copy of the algorithm the client just offered:

• On OpenSSH 8.0, any RSA key object’s type string is ssh-rsa
• I allowed only ssh-rsa on the server while the client signed with rsa-sha2-512
• The server still logged key type ssh-rsa not in PubkeyAcceptedKeyTypes
• The rejected algorithm was rsa-sha2-512; the printed name was still ssh-rsa

So treat the log as a starting diagnosis, not a full answer:

• An RSA signature was refused against the server’s accepted list
• The line alone does not prove which RSA signature name was refused
• Confirm with the client’s signing using ... line (ssh -vvv) or the server’s effective acceptance list

The server is not saying “RSA keys are banned.” Ways the same key (or a new one) can still work:

• Client signs with rsa-sha2-256 or rsa-sha2-512
• Or you switch to an ed25519 key

Option naming:

• Newer OpenSSH: PubkeyAcceptedAlgorithms
• Older OpenSSH: PubkeyAcceptedKeyTypes
• The failure meaning is the same

Do not fix this by changing HostKeyAlgorithms:

• That setting is about verifying the server host key
• This error is about the signature used to authenticate the user

Quick Fix

Confirm the Error in Server Logs

From the laptop or jump host, try SSH with your RSA private key. This command asks SSH to use only public-key authentication for this attempt, so a password prompt or Kerberos/GSSAPI path does not hide the key failure:

ssh -o PreferredAuthentications=publickey -o IdentitiesOnly=yes -i ~/.ssh/id_rsa root@203.0.113.10

root@203.0.113.10: Permission denied (publickey,gssapi-keyex,gssapi-with-mic,password).

Permission denied with publickey in the list means key auth was tried and failed. The client still does not say why. Run a verbose attempt and keep the important debug lines:

ssh -vvv -o BatchMode=yes -o PreferredAuthentications=publickey \
  -o IdentitiesOnly=yes -i ~/.ssh/id_rsa root@203.0.113.10 true 2>&1 \
  | grep -E 'Offering|Server accepts|sign_and_send|Authentications that|Permission denied'

debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Offering public key: /root/.ssh/id_rsa RSA SHA256:XPhBjLTON+Hs+nkHLQ4Fb5lwruWhXylCltVHvfJoaxo explicit
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
root@203.0.113.10: Permission denied (publickey,gssapi-keyex,gssapi-with-mic,password).

Here the client offered the RSA key, but you never see Server accepts key.

On the SSH server, search /var/log/secure or /var/log/auth.log (or journalctl -u sshd) for the algorithm reject. This lab uses /var/log/secure:

grep 'PubkeyAcceptedKeyTypes' /var/log/secure

Sep 22 12:27:58 ssh-server sshd[1340265]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]
Sep 22 12:27:58 ssh-server sshd[1340265]: Connection closed by authenticating user root 203.0.113.20 port 58704 [preauth]
Sep 22 12:34:25 ssh-server sshd[1345155]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]
Sep 22 12:34:47 ssh-server sshd[1345474]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]
Sep 22 12:35:00 ssh-server sshd[1345614]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]

Those lines mean:

• An RSA public-key offer was rejected against the acceptance list
• The public key can already be in authorized_keys
• Confirm which signature the client used with ssh -vvv in the next section

This lab used RHEL 8.10 OpenSSH 8.0p1 on both ends (OpenSSL 1.1.1k FIPS). Package checks were openssh-clients-8.0p1-25.el8_10.x86_64 and openssh-server-8.0p1-25.el8_10.x86_64.

Preferred Fix: Use rsa-sha2 with the Existing RSA Key

One RSA private key can prove who you are in more than one way:

Force SHA-2 for one attempt, with no server edit:

ssh -vvv -o BatchMode=yes -o PreferredAuthentications=publickey \
  -o IdentitiesOnly=yes -i ~/.ssh/id_rsa \
  -o PubkeyAcceptedKeyTypes=rsa-sha2-512,rsa-sha2-256 \
  root@203.0.113.10 'echo RSA_SHA2_OK' 2>&1 \
  | grep -E 'Server accepts|sign_and_send|Authentication succeeded|RSA_SHA2'

debug1: Server accepts key: /root/.ssh/id_rsa RSA SHA256:XPhBjLTON+Hs+nkHLQ4Fb5lwruWhXylCltVHvfJoaxo explicit
debug3: sign_and_send_pubkey: RSA SHA256:XPhBjLTON+Hs+nkHLQ4Fb5lwruWhXylCltVHvfJoaxo
debug3: sign_and_send_pubkey: signing using rsa-sha2-512
debug1: Authentication succeeded (publickey).
RSA_SHA2_OK

If this command succeeds:

• Your RSA key is fine
• The failure was the signature algorithm, not the key itself
• You do not need to enable ssh-rsa on the server
• Persist the RSA-SHA2 client setting or update the client, then stop here

Use -vvv, not -v. sign_and_send_pubkey: signing using is a debug3 line and disappears at -v.

For a normal login without dumping debug noise:

ssh -o PubkeyAcceptedKeyTypes=rsa-sha2-512,rsa-sha2-256 \
  -i ~/.ssh/id_rsa root@203.0.113.10

On newer OpenSSH clients the option is named PubkeyAcceptedAlgorithms.

Persist it for that host in ~/.ssh/config:

Host 203.0.113.10 ssh-server ssh-server.lab.example
  IdentityFile ~/.ssh/id_rsa
  IdentitiesOnly yes
  PubkeyAcceptedKeyTypes rsa-sha2-512,rsa-sha2-256

Client Host stanzas are covered in more depth in the ssh config guide.

If your log text is the older sshd: ssh-rsa algorithm is disabled warning instead of this PubkeyAcceptedKeyTypes reject, see sshd: ssh-rsa algorithm is disabled.

Why did the client choose ssh-rsa?

Older clients or vendor crypto-policy settings can cause an RSA key to use the legacy SHA-1 signature instead of RSA-SHA2. Do not guess from:

• The key filename
• The authorized_keys first field

Run ssh -vvv and look for signing using .... In this test:

• The failing client showed signing using ssh-rsa
• Forcing RSA-SHA2 changed it to signing using rsa-sha2-512
• Authentication succeeded

Alternative: Use an Ed25519 Key

You do not need to replace a healthy RSA key merely because ssh-rsa / SHA-1 is disabled:

• If RSA-SHA2 works, keeping the existing RSA key is often the least disruptive fix
• OpenSSH has supported RSA-SHA2 since 7.2

If the system must comply with FIPS requirements, verify which key algorithms are permitted by that environment; RSA-SHA2 is usually the less disruptive path for an existing RSA key.

If you prefer a new key type rather than tuning RSA signatures, use ed25519. Generate SSH keys covers key types and ssh-copy-id in more detail:

ssh-keygen -t ed25519 -f ~/.ssh/id_ed25519 -N ''

Install the public key on the server. RSA pubkey auth may still be broken at this point, so ssh-copy-id needs another working method for this step:

• Password auth was enabled on this lab server
• The earlier Permission denied (publickey,gssapi-keyex,gssapi-with-mic,password) line shows password was still offered

ssh-copy-id -i ~/.ssh/id_ed25519.pub root@203.0.113.10

Log in with the new key:

ssh -i ~/.ssh/id_ed25519 root@203.0.113.10

ed25519 does not depend on the ssh-rsa versus rsa-sha2-* choice. In this lab, other admins already logged in with ED25519 while the RSA SHA-1 path was failing:

Sep 22 12:35:29 ssh-server sshd[1346013]: Accepted publickey for root from 203.0.113.30 port 34654 ssh2: ED25519 SHA256:DmBB6a5hDE8hSamuH0sCjp0B7q29B+TVWd0C1kDW2O8

Accepted publickey with ED25519 means that path was already allowed on the same server that rejected ssh-rsa.

Legacy Clients That Only Support ssh-rsa

Use this only when a legacy client cannot speak rsa-sha2-* and you must keep that client working for a short time.

On a normal OpenSSH server (no vendor crypto-policy override), add a temporary drop-in and reload:

cat >/etc/ssh/sshd_config.d/99-allow-ssh-rsa.conf <<'EOF'
# Temporary: allow legacy ssh-rsa signatures (SHA-1). Prefer RSA-SHA2 when possible.
PubkeyAcceptedAlgorithms +ssh-rsa
EOF

On older OpenSSH that still uses the old option name:

cat >/etc/ssh/sshd_config.d/99-allow-ssh-rsa.conf <<'EOF'
PubkeyAcceptedKeyTypes +ssh-rsa
EOF

Check syntax:

sshd -t

Reload sshd so the drop-in takes effect:

systemctl reload sshd

Then verify from the legacy client with ssh -vvv and look for signing using ssh-rsa plus a successful login. Remove the drop-in once the client can speak RSA-SHA2.

If this drop-in appears to do nothing, your distribution may be applying a system-wide crypto policy that overrides normal sshd_config. See the next section.

Why authorized_keys Can Say ssh-rsa and Still Work

Two different uses of the name ssh-rsa:

• authorized_keys lines that start with ssh-rsa identify an RSA public key. That format is still valid.
• The server reject names a signature algorithm. Modern OpenSSH often allows rsa-sha2-256 / rsa-sha2-512 for that same key while disabling the SHA-1 ssh-rsa signature.

Upstream OpenSSH framed the change the same way: existing RSA keys do not need replacing merely because SHA-1 signatures were turned off.

PubkeyAcceptedAlgorithms vs HostKeyAlgorithms

Common traps:

• Assuming a missing key when the key is present and the signature algorithm is wrong
• Mixing HostKeyAlgorithms with user public-key auth algorithms
• Reading the server log’s printed ssh-rsa as proof of which signature the client offered
• Starting with +ssh-rsa before testing RSA-SHA2

Authentication method knobs beyond algorithm lists are covered in OpenSSH authentication methods.

When sshd_config Changes Are Ignored

On most OpenSSH installs, setting PubkeyAcceptedAlgorithms (or PubkeyAcceptedKeyTypes) in sshd_config / sshd_config.d is enough.

On some distributions:

• A system-wide crypto-policy layer can override or replace that setting
• Inspect how your distribution applies crypto policy if a normal OpenSSH change appears ignored
• The rest of this section is the RHEL 8 example from this lab

If +ssh-rsa does not work on RHEL crypto-policy systems

On RHEL 8, systemd often starts sshd as:

sshd -D $OPTIONS $CRYPTO_POLICY

What that means in practice:

• CRYPTO_POLICY comes from /etc/crypto-policies/back-ends/opensshserver.config
• It can set a full -oPubkeyAcceptedKeyTypes=... list on the command line
• That list wins over /etc/ssh/sshd_config.d/

Also note how +ssh-rsa behaves:

• PubkeyAcceptedKeyTypes +ssh-rsa appends to OpenSSH’s compiled-in defaults, not to the crypto-policy list
• On OpenSSH 8.0 those defaults already ended with ssh-rsa
• So a +ssh-rsa drop-in can be a complete no-op even when it is parsed

Prefer a supported crypto-policy override or subpolicy over editing generated backend files directly. After any policy change, verify the generated OpenSSH backend:

grep -E 'PubkeyAccepted(KeyTypes|Algorithms)' \
  /etc/crypto-policies/back-ends/opensshserver.config

On RHEL 9+:

• Red Hat documents update-crypto-policies --set DEFAULT:SHA1 as the supported SHA-1 compatibility switch
• That change is system-wide, not SSH-only
• For an SSH-only exception, use an application-specific OpenSSH path for that release

Check the live RHEL 8 sshd policy

Do not use pidof -s sshd. Use the service main PID:

MAINPID=$(systemctl show -p MainPID --value sshd)

Read that process’s command line:

tr '\0' ' ' < /proc/"$MAINPID"/cmdline; echo

Before the legacy re-enable in this lab, the live -oPubkeyAcceptedKeyTypes= value included:

• ECDSA
• Ed25519
• rsa-sha2-*
• Not ssh-rsa

You can also print the effective list the same way systemd would apply it:

( . /etc/crypto-policies/back-ends/opensshserver.config
  sshd -T $CRYPTO_POLICY | grep -i pubkeyaccepted )

Plain sshd -T on EL8:

• Can still show ssh-rsa from compiled-in defaults
• While the live daemon rejects it

After a change, restart with systemctl.

Troubleshooting PubkeyAcceptedKeyTypes Rejects

Useful generic checks:

ssh -vvv -o PreferredAuthentications=publickey -i ~/.ssh/id_rsa user@host true 2>&1 \
  | grep 'signing using'

A working modern path prints signing using rsa-sha2-512 or rsa-sha2-256. A legacy path prints signing using ssh-rsa.

On the server:

grep -E 'PubkeyAccepted|userauth_pubkey' /var/log/secure /var/log/auth.log 2>/dev/null | tail -20

RHEL-specific follow-ups when a drop-in is ignored. Confirm how systemd starts sshd:

systemctl cat sshd | grep -E 'EnvironmentFile|ExecStart'

Resolve the service main PID:

MAINPID=$(systemctl show -p MainPID --value sshd)

Read that MainPID command line:

tr '\0' ' ' < /proc/"$MAINPID"/cmdline; echo

Summary

What the error means:

• An RSA authentication attempt used a signature algorithm that is not in the server’s accepted list
• Confirm the real algorithm with ssh -vvv (signing using ...)
• Do not start by re-enabling SHA-1

Best fix order:

• Keep the RSA key and make the client use rsa-sha2-512 or rsa-sha2-256
• If that works, stop there
• Ed25519 is a good alternative if you want a new key type
• Re-enable SHA-1 ssh-rsa only for short-lived legacy interoperability, and not on FIPS-required systems

On distributions that apply system-wide crypto policies:

• An sshd_config change may be overridden by the vendor policy layer
• RHEL 8 is one example covered in this article
• If RSA-SHA2 already works from the client, you do not need to change the server policy at all

References

• sshd_config(5) — PubkeyAcceptedAlgorithms / PubkeyAcceptedKeyTypes — which public-key signature algorithms sshd accepts
• OpenSSH release notes — ssh-rsa / SHA-1 deprecation history and rsa-sha2-*
• RHEL: Using system-wide cryptographic policies — how crypto-policies can affect OpenSSH on RHEL