Question: 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 my_user@server.tld "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, rijndael-cbc@lysator.liu.se 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, rijndael-cbc@lysator.liu.se DEB [YYYYmmdd-HH:MM:30.499] thr=1 paramiko.transport: client mac: hmac-md5, hmac-sha1, umac-64@openssh.com, hmac-sha2-256, hmac-sha2-512, hmac-ripemd160, hmac-ripemd160@openssh.com, hmac-sha1-96, hmac-md5-96 DEB [YYYYmmdd-HH:MM:30.499] thr=1 paramiko.transport: server mac: hmac-md5, hmac-sha1, umac-64@openssh.com, hmac-sha2-256, hmac-sha2-512, hmac-ripemd160, hmac-ripemd160@openssh.com, hmac-sha1-96, hmac-md5-96 DEB [YYYYmmdd-HH:MM:30.499] thr=1 paramiko.transport: client compress: none, zlib@openssh.com DEB [YYYYmmdd-HH:MM:30.499] thr=1 paramiko.transport: server compress: none, zlib@openssh.com 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: ssh-rsa-cert-v01@openssh.com,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,curve25519-sha256@libssh.org,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: ssh-rsa-cert-v01@openssh.com,rsa-sha2-512,rsa-sha2-256,ssh-rsa,ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-ed25519-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,ssh-dss debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1 debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1 debug2: compression ctos: none,zlib@openssh.com,zlib debug2: compression stoc: none,zlib@openssh.com,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,rijndael-cbc@lysator.liu.se debug2: ciphers stoc: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se debug2: MACs ctos: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96 debug2: MACs stoc: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96 debug2: compression ctos: none,zlib@openssh.com debug2: compression stoc: none,zlib@openssh.com 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: umac-64@openssh.com compression: none debug1: kex: client->server cipher: aes128-ctr MAC: umac-64@openssh.com 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 no-more-sessions@openssh.com 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 eow@openssh.com 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 . 

Answer: 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.