These last few days i got publickey (denied) when access some of my server, mostly the old one to newer one, such as Ubuntu 20.04 or Debian 11 to ubuntu 22.04.

debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering public key: /home/user/.ssh/id_rsa RSA ... agent
debug1: send_pubkey_test: no mutual signature algorithm <-- ssh-rsa is not enabled 
debug1: No more authentication methods to try.
user@hostname: Permission denied (publickey).

After looking around i read upon openssh release note that said:

So then i look around finding openssh version on my servers, Ubuntu 22.04

openssh-server/jammy,now 1:8.9p1-3

Debian 11

openssh-server/stable,now 1:8.4p1-5+deb11u1

I think so yeah its the problem, lets just upgrade it. But no, as debian prefer stability it imposibble to upgrade openssh to 8.9 like ubuntu, except we rebuild the openssh ourself from upstream source. There is few solutions to this, in terms to get newer version of openssh.

• The easiest is to upgrade old installation Deb11 to Debian Testing or Debian Sid, vice versa Ubuntu 20.04 to Ubuntu 22.04
• Tweak /etc/ssh/sshd_config to enable ssh-rsa1

I'm using second solution, as the machine was in production statet rolling out update must be done slowly and carefully, not all machine can be updated Debian 11 to Debian Testing is a no, even it pretty stable on non production environment.

# nano /etc/ssh/sshd_config

Add these two lines on the bottom

HostKeyAlgorithms +ssh-rsa
PubkeyAcceptedKeyTypes +ssh-rsa

Then safe the file and restart the openssh-server

# systemctl restart ssh.service

Then you can connect to the previously denied machine, this change happen on the newer machine, essentially force openssh to receive ssh-rsa connection.

The other way is regenerate all your key to recommended algorithym, as per usuall we usually do:

$ ssh-keygen -t rsa

replace the command to:

$ ssh-keygen -t ed25519

then wipe out our id_rsa and id_rsa.pub usually placed on ~/.ssh/ except you define custom one. The caveat of this, we need to put our key again to the remote server.

This is my sshd_config:

#       $OpenBSD: sshd_config,v 1.103 2018/04/09 20:41:22 tj Exp $

# This is the sshd server system-wide configuration file.  See
# sshd_config(5) for more information.

# This sshd was compiled with PATH=/usr/bin:/bin:/usr/sbin:/sbin

# The strategy used for options in the default sshd_config shipped with
# OpenSSH is to specify options with their default value where
# possible, but leave them commented.  Uncommented options override the
# default value.

Include /etc/ssh/sshd_config.d/*.conf

Port 24
#AddressFamily any
#ListenAddress 0.0.0.0
#ListenAddress ::

#HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_ecdsa_key
#HostKey /etc/ssh/ssh_host_ed25519_key

# ssa-rsa force enable
#HostKeyAlgorithms +ssh-rsa
#PubkeyAcceptedKeyTypes +ssh-rsa

# Ciphers and keying
#RekeyLimit default none

# Logging
#SyslogFacility AUTH
#LogLevel INFO

# Authentication:

#LoginGraceTime 2m
#PermitRootLogin prohibit-password
#StrictModes yes
#MaxAuthTries 6
#MaxSessions 10

PubkeyAuthentication yes

# Expect .ssh/authorized_keys2 to be disregarded by default in future.
#AuthorizedKeysFile     .ssh/authorized_keys .ssh/authorized_keys2

#AuthorizedPrincipalsFile none

#AuthorizedKeysCommand none
#AuthorizedKeysCommandUser nobody

# For this to work you will also need host keys in /etc/ssh/ssh_known_hosts
#HostbasedAuthentication no
# Change to yes if you don't trust ~/.ssh/known_hosts for
# HostbasedAuthentication
#IgnoreUserKnownHosts no
# Don't read the user's ~/.rhosts and ~/.shosts files
#IgnoreRhosts yes

# To disable tunneled clear text passwords, change to no here!
PasswordAuthentication yes
#PermitEmptyPasswords no

# Change to yes to enable challenge-response passwords (beware issues with
# some PAM modules and threads)
ChallengeResponseAuthentication no

# Kerberos options
#KerberosAuthentication no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes
#KerberosGetAFSToken no

# GSSAPI options
#GSSAPIAuthentication no
#GSSAPICleanupCredentials yes
#GSSAPIStrictAcceptorCheck yes
#GSSAPIKeyExchange no

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.
UsePAM yes

#AllowAgentForwarding yes
#AllowTcpForwarding yes
#GatewayPorts no
#X11Forwarding yes
#X11DisplayOffset 10
#X11UseLocalhost no
#PermitTTY yes
#PrintMotd no
#PrintLastLog yes
#TCPKeepAlive yes
#PermitUserEnvironment no
#Compression yes
#ClientAliveInterval 0
#ClientAliveCountMax 3
#UseDNS no
#PidFile /var/run/sshd.pid
#MaxStartups 10:30:100
#PermitTunnel no
#ChrootDirectory none
#VersionAddendum none

# no default banner path
#Banner none

# Allow client to pass locale environment variables
AcceptEnv LANG LC_*

# override default of no subsystems
Subsystem       sftp    /usr/lib/openssh/sftp-server

# Example of overriding settings on a per-user basis
#Match User anoncvs
#       X11Forwarding no
#       AllowTcpForwarding no
#       PermitTTY no
#       ForceCommand cvs server

sources:

• OpenSSH release notes
• zdnet article about SHA1
• stackoverflow
• atlassian ssh-rsa fix