Paramiko returns "Bad authentication type", but can connect manually [duplicate]

I have a Python 3 application running on CentOS Linux 7.7 executing SSH commands against remote hosts. It works properly but today I encountered an odd error executing a command against a "new" remote server (server based on RHEL 6.10):

encountered RSA key, expected OPENSSH key

Executing the same command from the system shell (using the same private key of course) works perfectly fine.

On the remote server I discovered in /var/log/secure that when SSH connection and commands are issued from the source server with Python (using Paramiko) sshd complains about unsupported public key algorithm:

userauth_pubkey: unsupported public key algorithm: rsa-sha2-512

Note that target servers with higher RHEL/CentOS like 7.x don't encounter the issue.

It seems like Paramiko picks/offers the wrong algorithm when negotiating with the remote server when on the contrary SSH shell performs the negotiation properly in the context of this "old" target server. How to get the Python program to work as expected?

Python code

import paramiko
import logging

ssh_user = "my_user"
ssh_keypath = "/path/to/.ssh/my_key.rsa"
server = "server.tld"

ssh_client = paramiko.SSHClient()
ssh_client.set_missing_host_key_policy(paramiko.AutoAddPolicy()) 
ssh_client.connect(server,port=22,username=ssh_user, key_filename=ssh_keypath)  

# SSH command
cmd = "echo TEST : $(hostname)"

stdin, stdout, stderr = ssh_client.exec_command(cmd, get_pty=True)
exit_code = stdout.channel.recv_exit_status() 

cmd_raw_output = stdout.readlines()
out = "".join(cmd_raw_output)
out_msg = out.strip()  

# Ouput (logger code omitted)
logger.debug(out_msg)

if ssh_client is not None:
    ssh_client.close()

Shell command equivalent

ssh -i /path/to/.ssh/my_key.rsa [email protected] "echo TEST : $(hostname)"   

Paramiko logs (DEBUG)

DEB [YYYYmmdd-HH:MM:30.475] thr=1   paramiko.transport: starting thread (client mode): 0xf6054ac8
DEB [YYYYmmdd-HH:MM:30.476] thr=1   paramiko.transport: Local version/idstring: SSH-2.0-paramiko_2.9.1
DEB [YYYYmmdd-HH:MM:30.490] thr=1   paramiko.transport: Remote version/idstring: SSH-2.0-OpenSSH_5.3
INF [YYYYmmdd-HH:MM:30.490] thr=1   paramiko.transport: Connected (version 2.0, client OpenSSH_5.3)
DEB [YYYYmmdd-HH:MM:30.498] thr=1   paramiko.transport: === Key exchange possibilities ===
DEB [YYYYmmdd-HH:MM:30.498] thr=1   paramiko.transport: kex algos: diffie-hellman-group-exchange-sha256, diffie-hellman-group-exchange-sha1, diffie-hellman-group14-sha1, diffie-hellman-group1-sha1
DEB [YYYYmmdd-HH:MM:30.498] thr=1   paramiko.transport: server key: ssh-rsa, ssh-dss
DEB [YYYYmmdd-HH:MM:30.498] thr=1   paramiko.transport: client encrypt: aes128-ctr, aes192-ctr, aes256-ctr, arcfour256, arcfour128, aes128-cbc, 3des-cbc, blowfish-cbc, cast128-cbc, aes192-cbc, aes256-cbc, arcfour, [email protected]
DEB [YYYYmmdd-HH:MM:30.498] thr=1   paramiko.transport: server encrypt: aes128-ctr, aes192-ctr, aes256-ctr, arcfour256, arcfour128, aes128-cbc, 3des-cbc, blowfish-cbc, cast128-cbc, aes192-cbc, aes256-cbc, arcfour, [email protected]
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: client mac: hmac-md5, hmac-sha1, [email protected], hmac-sha2-256, hmac-sha2-512, hmac-ripemd160, [email protected], hmac-sha1-96, hmac-md5-96
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: server mac: hmac-md5, hmac-sha1, [email protected], hmac-sha2-256, hmac-sha2-512, hmac-ripemd160, [email protected], hmac-sha1-96, hmac-md5-96
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: client compress: none, [email protected]
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: server compress: none, [email protected]
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: client lang: <none>
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: server lang: <none>.
DEB [YYYYmmdd-HH:MM:30.499] thr=1   paramiko.transport: kex follows: False
DEB [YYYYmmdd-HH:MM:30.500] thr=1   paramiko.transport: === Key exchange agreements ===
DEB [YYYYmmdd-HH:MM:30.500] thr=1   paramiko.transport: Kex: diffie-hellman-group-exchange-sha256
DEB [YYYYmmdd-HH:MM:30.500] thr=1   paramiko.transport: HostKey: ssh-rsa
DEB [YYYYmmdd-HH:MM:30.500] thr=1   paramiko.transport: Cipher: aes128-ctr
DEB [YYYYmmdd-HH:MM:30.500] thr=1   paramiko.transport: MAC: hmac-sha2-256
DEB [YYYYmmdd-HH:MM:30.501] thr=1   paramiko.transport: Compression: none
DEB [YYYYmmdd-HH:MM:30.501] thr=1   paramiko.transport: === End of kex handshake ===
DEB [YYYYmmdd-HH:MM:30.548] thr=1   paramiko.transport: Got server p (2048 bits)
DEB [YYYYmmdd-HH:MM:30.666] thr=1   paramiko.transport: kex engine KexGexSHA256 specified hash_algo <built-in function openssl_sha256>
DEB [YYYYmmdd-HH:MM:30.667] thr=1   paramiko.transport: Switch to new keys ...
DEB [YYYYmmdd-HH:MM:30.669] thr=2   paramiko.transport: Adding ssh-rsa host key for server.tld: b'caea********************.'
DEB [YYYYmmdd-HH:MM:30.674] thr=2   paramiko.transport: Trying discovered key b'b49c********************' in /path/to/.ssh/my_key.rsa
DEB [YYYYmmdd-HH:MM:30.722] thr=1   paramiko.transport: userauth is OK
DEB [YYYYmmdd-HH:MM:30.722] thr=1   paramiko.transport: Finalizing pubkey algorithm for key of type 'ssh-rsa'
DEB [YYYYmmdd-HH:MM:30.722] thr=1   paramiko.transport: Our pubkey algorithm list: ['rsa-sha2-512', 'rsa-sha2-256', 'ssh-rsa']
DEB [YYYYmmdd-HH:MM:30.723] thr=1   paramiko.transport: Server-side algorithm list: ['']
DEB [YYYYmmdd-HH:MM:30.723] thr=1   paramiko.transport: Agreed upon 'rsa-sha2-512' pubkey algorithm
INF [YYYYmmdd-HH:MM:30.735] thr=1   paramiko.transport: Authentication (publickey) failed.
DEB [YYYYmmdd-HH:MM:30.739] thr=2   paramiko.transport: Trying SSH agent key b'9d37********************'
DEB [YYYYmmdd-HH:MM:30.747] thr=1   paramiko.transport: userauth is OK.
DEB [YYYYmmdd-HH:MM:30.748] thr=1   paramiko.transport: Finalizing pubkey algorithm for key of type 'ssh-rsa'
DEB [YYYYmmdd-HH:MM:30.748] thr=1   paramiko.transport: Our pubkey algorithm list: ['rsa-sha2-512', 'rsa-sha2-256', 'ssh-rsa']
DEB [YYYYmmdd-HH:MM:30.748] thr=1   paramiko.transport: Server-side algorithm list: ['']
DEB [YYYYmmdd-HH:MM:30.748] thr=1   paramiko.transport: Agreed upon 'rsa-sha2-512' pubkey algorithm
INF [YYYYmmdd-HH:MM:30.868] thr=1   paramiko.transport: Authentication (publickey) failed...

Shell command logs

OpenSSH_7.4p1, OpenSSL 1.0.2k-fips  26 Jan 2017
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 58: Applying options for *
debug2: resolving "server.tld" port 22
debug2: ssh_connect_direct: needpriv 0
debug1: Connecting to server.tld [server.tld] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: key_load_public: No such file or directory
debug1: identity file /path/to/.ssh/my_key.rsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /path/to/.ssh/my_key.rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.4
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH_5* compat 0x0c000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to server.tld:22 as 'my_user'
debug3: hostkeys_foreach: reading file "/path/to/.ssh/known_hosts"
debug3: record_hostkey: found key type RSA in file /path/to/.ssh/known_hosts:82
debug3: load_hostkeys: loaded 1 keys from server.tld
debug3: order_hostkeyalgs: prefer hostkeyalgs: [email protected],rsa-sha2-512,rsa-sha2-256,ssh-rsa
debug3: send packet: type 20
debug1: SSH2_MSG_KEXINIT sent
debug3: receive packet: type 20
debug1: SSH2_MSG_KEXINIT received
debug2: local client KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256,[email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1,ext-info-c
debug2: host key algorithms: [email protected],rsa-sha2-512,rsa-sha2-256,ssh-rsa,[email protected],[email protected],[email protected],[email protected],[email protected],ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,ssh-dss
debug2: ciphers ctos: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],aes128-cbc,aes192-cbc,aes256-cbc
debug2: ciphers stoc: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],aes128-cbc,aes192-cbc,aes256-cbc
debug2: MACs ctos: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,[email protected],zlib
debug2: compression stoc: none,[email protected],zlib
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: host key algorithms: ssh-rsa,ssh-dss
debug2: ciphers ctos: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: ciphers stoc: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: MACs ctos: hmac-md5,hmac-sha1,[email protected],hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: MACs stoc: hmac-md5,hmac-sha1,[email protected],hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: compression ctos: none,[email protected]
debug2: compression stoc: none,[email protected]
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug1: kex: algorithm: diffie-hellman-group-exchange-sha256
debug1: kex: host key algorithm: ssh-rsa
debug1: kex: server->client cipher: aes128-ctr MAC: [email protected] compression: none
debug1: kex: client->server cipher: aes128-ctr MAC: [email protected] compression: none
debug1: kex: diffie-hellman-group-exchange-sha256 need=16 dh_need=16
debug1: kex: diffie-hellman-group-exchange-sha256 need=16 dh_need=16
debug3: send packet: type 34
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<3072<8192) sent
debug3: receive packet: type 31
debug1: got SSH2_MSG_KEX_DH_GEX_GROUP
debug2: bits set: 1502/3072
debug3: send packet: type 32
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug3: receive packet: type 33
debug1: got SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Server host key: ssh-.:**************************************************
debug3: hostkeys_foreach: reading file "/path/to/.ssh/known_hosts"
debug3: record_hostkey: found key type RSA in file /path/to/.ssh/known_hosts:8..2
debug3: load_hostkeys: loaded 1 keys from server.tld
debug1: Host 'server.tld' is known and matches the RSA host key.
debug1: Found key in /path/to/.ssh/known_hosts:82
debug2: bits set: 1562/3072
debug3: send packet: type 21
debug2: set_newkeys: mode 1
debug1: rekey after 4294967296 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug3: receive packet: type 21
debug1: SSH2_MSG_NEWKEYS received
debug2: set_newkeys: mode 0
debug1: rekey after 4294967296 blocks
debug2: key: <foo> (0x55bcf6d1d320), agent
debug2: key: /path/to/.ssh/my_key.rsa ((nil)), explicit
debug3: send packet: type 5
debug3: receive packet: type 6
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug3: send packet: type 50
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug3: start over, passed a different list publickey,gssapi-keyex,gssapi-with-mic,password
debug3: preferred gssapi-keyex,gssapi-with-mic,publickey,keyboard-interactive,password
debug3: authmethod_lookup gssapi-keyex
debug3: remaining preferred: gssapi-with-mic,publickey,keyboard-interactive,password
debug3: authmethod_is_enabled gssapi-keyex
debug1: Next authentication method: gssapi-keyex
debug1: No valid Key exchange context
debug2: we did not send a packet, disable method
debug3: authmethod_lookup gssapi-with-mic
debug3: remaining preferred: publickey,keyboard-interactive,password
debug3: authmethod_is_enabled gssapi-with-mic
debug1: Next authentication method: gssapi-with-mic
debug1: Unspecified GSS failure.  Minor code may provide more information
No Kerberos credentials available (default cache: KEYRING:persistent:0)

debug1: Unspecified GSS failure.  Minor code may provide more information
No Kerberos credentials available (default cache: KEYRING:persistent:0)

debug2: we did not send a packet, disable method
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: <foo>
debug3: send_pubkey_test
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Trying private key: /path/to/.ssh/my_key.rsa
debug3: sign_and_send_pubkey: RSA SHA256:**********************************
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 52
debug1: Authentication succeeded (publickey).
Authenticated to server.tld ([server.tld]:22).
debug1: channel 0: new [client-session]
debug3: ssh_session2_open: channel_new: 0
debug2: channel 0: send open
debug3: send packet: type 90
debug1: Requesting [email protected]
debug3: send packet: type 80
debug1: Entering interactive session.
debug1: pledge: network
debug3: receive packet: type 91
debug2: callback start
debug2: fd 3 setting TCP_NODELAY
debug3: ssh_packet_set_tos: set IP_TOS 0x08
debug2: client_session2_setup: id 0
debug1: Sending environment.
debug3: Ignored env XDG_SESSION_ID
debug3: Ignored env HOSTNAME
debug3: Ignored env SELINUX_ROLE_REQUESTED
debug3: Ignored env TERM
debug3: Ignored env SHELL
debug3: Ignored env HISTSIZE
debug3: Ignored env SSH_CLIENT
debug3: Ignored env SELINUX_USE_CURRENT_RANGE
debug3: Ignored env SSH_TTY
debug3: Ignored env CDPATH
debug3: Ignored env USER
debug3: Ignored env LS_COLORS
debug3: Ignored env SSH_AUTH_SOCK
debug3: Ignored env MAIL
debug3: Ignored env PATH
debug3: Ignored env PWD
debug1: Sending env LANG = xx_XX.UTF-8
debug2: channel 0: request env confirm 0
debug3: send packet: type 98
debug3: Ignored env SELINUX_LEVEL_REQUESTED
debug3: Ignored env HISTCONTROL
debug3: Ignored env SHLVL
debug3: Ignored env HOME
debug3: Ignored env LOGNAME
debug3: Ignored env SSH_CONNECTION
debug3: Ignored env LESSOPEN
debug3: Ignored env XDG_RUNTIME_DIR
debug3: Ignored env _
debug1: Sending command: echo TEST : $(hostname)
debug2: channel 0: request exec confirm 1
debug3: send packet: type 98
debug2: callback done
debug2: channel 0: open confirm rwindow 0 rmax 32768
debug2: channel 0: rcvd adjust 2097152
debug3: receive packet: type 99
debug2: channel_input_status_confirm: type 99 id 0
debug2: exec request accepted on channel 0
TEST : server.tld
debug3: receive packet: type 96
debug2: channel 0: rcvd eof
debug2: channel 0: output open -> drain
debug2: channel 0: obuf empty
debug2: channel 0: close_write
debug2: channel 0: output drain -> closed
debug3: receive packet: type 98
debug1: client_input_channel_req: channel 0 rtype exit-status reply 0
debug3: receive packet: type 98
debug1: client_input_channel_req: channel 0 rtype [email protected] reply 0
debug2: channel 0: rcvd eow
debug2: channel 0: close_read
debug2: channel 0: input open -> closed
debug3: receive packet: type 97
debug2: channel 0: rcvd close
debug3: channel 0: will not send data after close
debug2: channel 0: almost dead
debug2: channel 0: gc: notify user
debug2: channel 0: gc: user detached
debug2: channel 0: send close
debug3: send packet: type 97
debug2: channel 0: is dead
debug2: channel 0: garbage collecting
debug1: channel 0: free: client-session, nchannels 1
debug3: channel 0: status: The following connections are open:
  #0 client-session (t4 r0 i3/0 o3/0 fd -1/-1 cc -1)

debug3: send packet: type 1
Transferred: sent 3264, received 2656 bytes, in 0.0 seconds.
Bytes per second: sent 92349.8, received 75147.4
debug1: Exit status 0
.

Imo, it's a bug in Paramiko. It does not handle correctly absence of server-sig-algs extension on the server side.

Try disabling rsa-sha2-* on Paramiko side altogether:

ssh_client.connect(
  server, username=ssh_user, key_filename=ssh_keypath,
  disabled_algorithms=dict(pubkeys=["rsa-sha2-512", "rsa-sha2-256"]))

(note that there's no need to specify port=22, as that's the default)

I've found related Paramiko issue:
RSA key auth failing from paramiko 2.9.x client to dropbear server

Though it refers to Paramiko 2.9.0 change log, which seems to imply that the behavior is deliberate:

When the server does not send server-sig-algs, Paramiko will attempt the first algorithm in the above list. Clients connecting to legacy servers should thus use disabled_algorithms to turn off SHA2.


Since 2.9.2, Paramiko will say:

DEB [20220113-14:46:13.882] thr=1 paramiko.transport: Server did not send a server-sig-algs list; defaulting to our first preferred algo ('rsa-sha2-512')
DEB [20220113-14:46:13.882] thr=1 paramiko.transport: NOTE: you may use the 'disabled_algorithms' SSHClient/Transport init kwarg to disable that or other algorithms if your server does not support them!


Obligatory warning: Do not use AutoAddPolicy – You are losing a protection against MITM attacks by doing so. For a correct solution, see Paramiko "Unknown Server".


Your code for waiting for command to complete and reading its output is flawed too. See Wait to finish command executed with Python Paramiko. And for most purposes, the get_pty=True is not a good idea either.