I have been using PKI based SSH connections for over 10 years. Suddenly, after a server update - some of the connections stopped working. I am using the same PKI keys I have used for years (each server has it's own keys, I have a small set of personal keys).Working - looks like this:C:\Users\michael>ssh2 -p 2222 root@192.168.129.64 dateAuthentication successful.Fri Nov 25 10:30:42  2016Not working looks like:C:\Users\michael>ssh2 root@192.168.129.64 datewarning: Authentication failed.Disconnected; key exchange or algorithm negotiation failed (Algorithm negotiation failed.).What changed?
SSH stopped working after a server update? What happened?
openssh
FYI: this is a Q&A - where I provide my answer to the question, more are welcome - I like to learn (what I missed)!I hope it increases your understanding of how openssh connects and/or how to debug openssh connection issuesAfter an update - side-effects may come into play. With OpenSSH - defaults change frequently. OpenBSD (who maintain/develop OpenSSH) have a policy of OpenBSD to not be concerned about backwards compatibility. This can 'break' things that are, read were, working well.There is a massive hint - that I did not notice when this first happened to me (using the GUI interface, and I just clicked it away and 'was angry' with 'stupid update - new version is broken'. Turns out the new version was not broken - but OpenBSD/OpenSSH starting changing the key exchange defaults starting with OpenSSH-6.7p1 see: http://www.openssh.com/txt/release-6.7, noteably:Changes since OpenSSH 6.6Potentially-incompatible changessshd(8): The default set of ciphers and MACs has been altered to  remove unsafe algorithms. In particular, CBC ciphers and arcfour*  are disabled by default.The full set of algorithms remains available if configured  explicitly via the Ciphers and MACs sshd_config options.My problem is I have an old client that does not have any of the new defaults, so it cannot connect.Two solution paths: fix/patch the server or - fix/patch the client.Server solution: bring back old settings so old clients can continue to connect that is, - friendly to existing clients - edit the sshd_config file and add back (enough) of the old ciphers. The key lines to change/add in sshd_config being:ciphers aes128-ctr,aes192-ctr,aes256-ctr,chacha20-poly1305@openssh.com,aes256-cbcKexAlgorithms  curve25519-sha256@libssh.org,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1macs hmac-sha2-256,hmac-sha2-512,hmac-sha1-96,hmac-sha1Just add:# Ciphers# The dafaults starting with OpenSSH 6.7 are:# aes128-ctr,aes192-ctr,aes256-ctr,chacha20-poly1305@openssh.com# older clients may need an older cipher, e.g.# ciphers aes128-cbc,aes192-cbc,aes256-cbc,blowfish-cbc,arcfour# only adding aes256-cbc as an old cipherciphers aes128-ctr,aes192-ctr,aes256-ctr,chacha20-poly1305@openssh.com,aes256-cbc# KEX Key Exchange algorithms# default from openssh 6.7 are:# curve25519-sha256@libssh.org,diffie-hellman-group-exchange-sha256,\#  diffie-hellman-group14-sha1# an older kex are: none,KexAlgorithms diffie-hellman-group1-sha1# only adding diffie-hellman-group-sha1  as an old KEX# and this should be deleted ASAP as it is clearly one of the problems with SSL based encryptionKexAlgorithms  curve25519-sha256@libssh.org,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1# MAC message authentification code# the new defaults are:# umac-64-etm@openssh.com,umac-128-etm@openssh.com,# hmac-sha2-256-etm@openssh.com,hmac-sha2-512-# etm@openssh.com,# umac-64@openssh.com,umac-128@openssh.com,# hmac-sha2-256,hmac-sha2-512# older defaults (still supported) are:# macs hmac-sha1,hmac-md5# consider removing hmac-sha1-96,hmac-sha1,hmac-md5 Soon!macs hmac-sha2-256,hmac-sha2-512,hmac-sha1-96,hmac-sha1Solution #2 - fix/replace the clientAn easy way to see what ciphers you current client supports (assuming CLI) is ssh -h and see if that provides something like:Supported ciphers:  3des-cbc,aes256-cbc,aes192-cbc,aes128-cbc,blowfish-cbc,twofish-cbc,twofish256-cbc,twofish192-cbc,twofish128-cbc,des-cbc@ssh.com,cast128-cbc,rc2-cbc@ssh.com,arcfour,noneSupported MAC algorithms:  hmac-md5,hmac-md5-96,hmac-sha1,hmac-sha1-96,hmac-sha256@ssh.com,hmac-sha256-96@ssh.com,hmac-ripemd160@ssh.com,hmac-ripemd160-96@ssh.com,hmac-tiger128@ssh.com,hmac-tiger128-96@ssh.com,hmac-tiger160@ssh.com,hmac-tiger160-96@ssh.com,hmac-tiger192@ssh.com,hmac-tiger192-96@ssh.com,noneAnother useful command is: ssh -Vssh2: SSH Secure Shell 3.2.9 Windows ClientProduct: SSH Secure Shell for WorkstationsLicense type: none (non-commercial)Mine - was - an very old client - for my desktop. Looking above you can see it does not support any of the - 15 years later - preferred algorithms, not even one -cbr (rotating), only -cbc (block-copy).If you client does not have an option to provide the keys, etc. supported (OpenSSH should have the option -Q) just start a connection to yourself, e.g., ssh -v localhost and there are lines such as this to tell you wat is known:debug1: SSH2_MSG_KEXINIT sentdebug1: SSH2_MSG_KEXINIT receiveddebug2: kex_parse_kexinit: ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-grousha1,diffie-hellman-group1-sha1debug2: kex_parse_kexinit: ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.ssh-dss-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-dss-cert-v00@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-rsa,ssh-dssdebug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysatiu.se...And what was found (and used):debug2: mac_setup: found hmac-sha1debug1: kex: server->client aes128-ctr hmac-sha1 nonedebug2: mac_setup: found hmac-sha1debug1: kex: client->server aes128-ctr hmac-sha1 noneExtra: debug info from a failed connect - more detailsOr, what was tried, but missed.debug: OpenSSH: Major: 7 Minor: 3 Revision: 0debug: Ssh2Transport: All versions of OpenSSH handle kex guesses incorrectly.debug: Ssh2Transport: Algorithm negotiation failed for c_to_s_cipher: client list: aes128-cbc,3des-cbc,twofish128-cbc,cast128-cbc,twofish-cbc,blowfish-cbc,aes192-cbc,aes256-cbc,twofish192-cbc,twofish256-cbc,arcfour vs. server list : chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.comdebug: Ssh2Transport: Algorithm negotiation failed for s_to_c_cipher: client list: aes128-cbc,3des-cbc,twofish128-cbc,cast128-cbc,twofish-cbc,blowfish-cbc,aes192-cbc,aes256-cbc,twofish192-cbc,twofish256-cbc,arcfour vs. server list : chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.comdebug: Ssh2Transport: lang s to c: `', lang c to s: `'debug: Ssh2Transport: Couldn't agree on kex or hostkey alg. (chosen_kex = NULL, chosen_host_key = ssh-rsa)debug: Ssh2Common: DISCONNECT received: Algorithm negotiation failed.Edit: added 02-jan-2017New Section - what about keys that stop working?On my server I have an 'old' client and the 'latest' client installed - and get different behavior connecting to a server. Here the issue is not cipher mis-matches - but use of an archaic PKI pair - based on DSA.In short, openssh-7(.3) no longer sends (by default, maybe not at all) DSA public keys.Below I compare the output of two versions of openssh/usr/bin/ssh (old version, left-side) and/opt/bin/ssh (new version, right-side) - the command is:${version}/ssh -v user@host dateAs you scan through the output below I hope you notice the steps and messages are generally the same. The key difference comes after the string SSH2_MSG_SERVICE_ACCEPTWhat I want you to notice is that the old version offers (and is accepted by the 'old' server - the DSA based key pair while the new server never offers the DSA based key.Note: the 'solution' for this is to add (at least one of) the rsa, ecdsa, or the ed25519 based PKI pairs.OpenSSH_6.0p1, OpenSSL 1.0.2h  3 May 2016                     | OpenSSH_7.3p1, OpenSSL 1.0.2h  3 May 2016debug1: Reading configuration data /etc/ssh/ssh_config        | debug1: Reading configuration data /var/openssh/etc/ssh_confidebug1: Failed dlopen: /usr/krb5/lib/libkrb5.a(libkrb5.a.so): <        0509-026 System error: A file or directory in the pat <                                                              <debug1: Error loading Kerberos, disabling Kerberos auth.      <debug1: Connecting to x061 [192.168.129.61] port 22.            debug1: Connecting to x061 [192.168.129.61] port 22.debug1: Connection established.                                 debug1: Connection established.debug1: identity file /home/michael/.ssh/id_rsa type 1          debug1: identity file /home/michael/.ssh/id_rsa type 1                                                              > debug1: key_load_public: No such file or directorydebug1: identity file /home/michael/.ssh/id_rsa-cert type -1    debug1: identity file /home/michael/.ssh/id_rsa-cert type -1debug1: identity file /home/michael/.ssh/id_dsa type 2          debug1: identity file /home/michael/.ssh/id_dsa type 2                                                              > debug1: key_load_public: No such file or directorydebug1: identity file /home/michael/.ssh/id_dsa-cert type -1    debug1: identity file /home/michael/.ssh/id_dsa-cert type -1debug1: identity file /home/michael/.ssh/id_ecdsa type 3        debug1: identity file /home/michael/.ssh/id_ecdsa type 3                                                              > debug1: key_load_public: No such file or directorydebug1: identity file /home/michael/.ssh/id_ecdsa-cert type -   debug1: identity file /home/michael/.ssh/id_ecdsa-cert type -debug1: Remote protocol version 2.0, remote software version  | debug1: key_load_public: No such file or directorydebug1: match: OpenSSH_6.0 pat OpenSSH*                       | debug1: identity file /home/michael/.ssh/id_ed25519 type -1                                                              > debug1: key_load_public: No such file or directory                                                              > debug1: identity file /home/michael/.ssh/id_ed25519-cert typedebug1: Enabling compatibility mode for protocol 2.0            debug1: Enabling compatibility mode for protocol 2.0debug1: Local version string SSH-2.0-OpenSSH_6.0              | debug1: Local version string SSH-2.0-OpenSSH_7.3                                                              > debug1: Remote protocol version 2.0, remote software version                                                              > debug1: match: OpenSSH_6.0 pat OpenSSH* compat 0x04000000                                                              > debug1: Authenticating to x061:22 as 'padmin'debug1: SSH2_MSG_KEXINIT sent                                   debug1: SSH2_MSG_KEXINIT sentdebug1: SSH2_MSG_KEXINIT received                               debug1: SSH2_MSG_KEXINIT receiveddebug1: kex: server->client aes128-ctr hmac-md5 none          | debug1: kex: algorithm: ecdh-sha2-nistp256debug1: kex: client->server aes128-ctr hmac-md5 none          | debug1: kex: host key algorithm: ssh-rsa                                                              > debug1: kex: server->client cipher: aes128-ctr MAC: umac-64@o                                                              > debug1: kex: client->server cipher: aes128-ctr MAC: umac-64@odebug1: sending SSH2_MSG_KEX_ECDH_INIT                          debug1: sending SSH2_MSG_KEX_ECDH_INITdebug1: expecting SSH2_MSG_KEX_ECDH_REPLY                       debug1: expecting SSH2_MSG_KEX_ECDH_REPLYdebug1: Server host key: RSA 9f:0a:4d:a8:1b:ba:e6:d4:1a:b2:cd | debug1: Server host key: ssh-rsa SHA256:ORf5UVI7mRm/9MthM2qXMdebug1: Host 'x061' is known and matches the RSA host key.      debug1: Host 'x061' is known and matches the RSA host key.debug1: Found key in /home/michael/.ssh/known_hosts:57          debug1: Found key in /home/michael/.ssh/known_hosts:57debug1: ssh_rsa_verify: signature correct                     | debug1: rekey after 4294967296 blocksdebug1: SSH2_MSG_NEWKEYS sent                                   debug1: SSH2_MSG_NEWKEYS sentdebug1: expecting SSH2_MSG_NEWKEYS                              debug1: expecting SSH2_MSG_NEWKEYS                                                              > debug1: rekey after 4294967296 blocksdebug1: SSH2_MSG_NEWKEYS received                               debug1: SSH2_MSG_NEWKEYS receiveddebug1: Roaming not allowed by server                         | debug1: Skipping ssh-dss key /home/michael/.ssh/id_dsa - notdebug1: SSH2_MSG_SERVICE_REQUEST sent                         <debug1: SSH2_MSG_SERVICE_ACCEPT received                        debug1: SSH2_MSG_SERVICE_ACCEPT receiveddebug1: Authentications that can continue: publickey,password   debug1: Authentications that can continue: publickey,passworddebug1: Next authentication method: publickey                   debug1: Next authentication method: publickeydebug1: Offering RSA public key: /home/michael/.ssh/id_rsa      debug1: Offering RSA public key: /home/michael/.ssh/id_rsadebug1: Authentications that can continue: publickey,password   debug1: Authentications that can continue: publickey,passworddebug1: Offering DSA public key: /home/michael/.ssh/id_dsa    | debug1: Offering ECDSA public key: /home/michael/.ssh/id_ecdsdebug1: Server accepts key: pkalg ssh-dss blen 433            | debug1: Authentications that can continue: publickey,passworddebug1: read PEM private key done: type DSA                   | debug1: Trying private key: /home/michael/.ssh/id_ed25519debug1: Authentication succeeded (publickey).                 | debug1: Next authentication method: keyboard-interactiveAuthenticated to x061 ([192.168.129.61]:22).                  | debug1: Authentications that can continue: publickey,passworddebug1: channel 0: new [client-session]                       | debug1: Next authentication method: passworddebug1: Requesting no-more-sessions@openssh.com               | padmin@x061's password:debug1: Entering interactive session.                         |