Suddenly, my ssh requires a password--debug1: send_pubkey_test: no mutual signature algorithm

Question

Went to check something on my Ubuntu server:

jlouthan@siege  ~/.ssh  ssh metroplex.theologic.us
([email protected]) Password:

That is odd because I have ssh keys.

Troubleshooting, I generated a new set of RSA keys. Failed.

Debugging...

 ✘ jlouthan@siege  ~/.ssh  ssh -v -i ~/.ssh/id_rsa theologic.us@metroplex
OpenSSH_9.0p1, LibreSSL 3.3.6
debug1: Reading configuration data /Users/jlouthan/.ssh/config
debug1: /Users/jlouthan/.ssh/config line 6: Applying options for metroplex
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 21: include /etc/ssh/ssh_config.d/* matched no files
debug1: /etc/ssh/ssh_config line 54: Applying options for *
debug1: Authenticator provider $SSH_SK_PROVIDER did not resolve; disabling
debug1: Connecting to metroplex.theologic.us port 22.
debug1: Connection established.
debug1: identity file /Users/jlouthan/.ssh/id_rsa type 0
debug1: identity file /Users/jlouthan/.ssh/id_rsa-cert type -1
debug1: identity file /Users/jlouthan/.ssh/metroplex type 0
debug1: identity file /Users/jlouthan/.ssh/metroplex-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_9.0
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Debian-5+deb8u8
debug1: compat_banner: match: OpenSSH_6.7p1 Debian-5+deb8u8 pat OpenSSH* compat 0x04000000
debug1: Authenticating to metroplex.theologic.us:22 as 'theologic.us'
debug1: load_hostkeys: fopen /Users/jlouthan/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: [email protected]
debug1: kex: host key algorithm: ssh-dss
debug1: kex: server->client cipher: [email protected] MAC: <implicit> compression: none
debug1: kex: client->server cipher: [email protected] MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: SSH2_MSG_KEX_ECDH_REPLY received
debug1: Server host key: ssh-dss SHA256:GXA6AafJJKEdnL4lusDm5TH1fc/GTio4LJntMgh+bNo
debug1: load_hostkeys: fopen /Users/jlouthan/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: Host 'metroplex.theologic.us' is known and matches the DSA host key.
debug1: Found key in /Users/jlouthan/.ssh/known_hosts:10
debug1: rekey out after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey in after 134217728 blocks
debug1: get_agent_identities: bound agent to hostkey
debug1: get_agent_identities: ssh_fetch_identitylist: agent contains no identities
debug1: Will attempt key: /Users/jlouthan/.ssh/id_rsa RSA SHA256:Z25lvSAQZuzG7UFECKHDuqciThd0iKIGPOzbzbbJht8 explicit
debug1: Will attempt key: /Users/jlouthan/.ssh/metroplex RSA SHA256:rWsd4LuBWgHKBtwP+tlO8g19hr1KfK18kLMm/15T6U0 explicit
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Offering public key: /Users/jlouthan/.ssh/id_rsa RSA SHA256:Z25lvSAQZuzG7UFECKHDuqciThd0iKIGPOzbzbbJht8 explicit
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Offering public key: /Users/jlouthan/.ssh/metroplex RSA SHA256:rWsd4LuBWgHKBtwP+tlO8g19hr1KfK18kLMm/15T6U0 explicit
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Next authentication method: keyboard-interactive
([email protected]) Password:

Answer 1

Simple google debug1: send_pubkey_test: no mutual signature algorithm returned this article:

SSH-RSA key rejected with message "no mutual signature algorithm" 1

And simple research on ED25519 2

I just regenerated a set of keys for that server:

ssh-keygen -t ed25519 -f ~/.ssh/metroplex
Generating public/private ed25519 key pair.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /Users/jlouthan/.ssh/metroplex
Your public key has been saved in /Users/jlouthan/.ssh/metroplex.pub
The key fingerprint is:
SHA256:igRaUb0na9RWV13b7yJoSGu+3fPttSZpWGYC6/qUNM0 jlouthan@siege
The key's randomart image is:
+--[ED25519 256]--+
|  ....       ...o|
|   .  .   . .   +|
|  o    o . .   ..|
| o .  + +.o     .|
|.   .. =SooE    .|
|   . .oo.+oo + . |
|    ... =oo B o o|
|       o.+ o.= +o|
|       .=o. oo+oo|
+----[SHA256]-----+

And logged in just fine, sans password prompt:

jlouthan@siege  ~/.ssh  ssh metroplex.theologic.us

The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.