OpenSSH v7 and DSA key support. AKA “Permission denied (publickey)”

sshI have a little personal server farm with a handful of hosts that run things like my websites, a BBS and my VPN server. I recently upgraded my desktop to Kubuntu 16.04 and suddenly my SSH key was no longer working. I started seeing this when I tried to log in:

I began troubleshooting to determine what was wrong with my key. I had just upgraded my workstation, after all, I could have restored the wrong keys from my backup. That is when I discovered that I was able to log in to some of my servers, just not all of them. That puzzled me because I knew I had not touched the servers and I thought that they all used the same key. What could cause my key to work on some servers, but not others? It had to be a client-side issue but I didn’t know what.

I have a continuity plan to access my servers if anything like this should happen so I implemented it and it allowed me to look in the auth.log. I saw these messages in the server logs:

The “preauth” bit gave me the clue I needed. It means that it was the client that was declining to auth; it was not the server rejecting the auth. I jacked up the verbosity on my ssh client and saw this:

This message told me what was happening:

It turns out that OpenSSH v7 has disallowed the use of DSA keys by default. The debug output above showed me that my newly installed workstation did indeed come with OpenSSH v7. To verify that this was my problem I logged in to all my backups and confirmed that the running servers that I was unable to log in to had only DSA keys on them. So, now I knew what to fix, but that did not help me restore full access to my servers right now. To do that, I had to temporarily weaken my SSH client by telling it to allow the use of DSA keys. Adding this to /etc/ssh/ssh_config did the trick:

That told my SSH client to allow my DSA keys to be used and I was back in to my servers. I’ve now replaced all my DSA keys with RSA keys and removed that directive from my SSH config because there’s no reason to continue running a weakened system.