SSH keys are no longer working after upgrading to Ubuntu 16.04.LTS – Help!

I recently upgraded one of my laptops to Ubuntu 16.04.LTS (going from 14.04.LTS). The upgrade went very smooth and I have no issues with the resulting operating environment 🙂 Having said that, I quickly discovered a quite serious issue for me when I attempted connecting to one of many servers I need to get into. All of a sudden, my SSH key was no longer accepted by the server, and I was prompted for a password! WTF!?

I immediately feared the worst and started looking at the server(s), tailing log files, enabling debugging, etc. No trace was to be found other than that no key was presented by the client. The servers were intact, the authorized_keys had not been compromised, and vanilla ice cream was still the number one flavor. The problem is not with Ubuntu 16.04.LTS. The problem is with my SSH key, as well as a recent change in “acceptable keys” by OpenSSH, version 7.

Doing “ssh -vvv user@server.com” told me that the SSH client couldn’t find an acceptable key to present to the server. After having figured that out, and facepalming for a few seconds, I added this to my /etc/ssh/ssh_config file:

PubkeyAcceptedKeyTypes=+ssh-dss

Saved the file and tried again. Voila! One could say many things about using this type of SSH key, but rest assured I will change mine. You should too if you run into this problem. This is a workaround, not a fix or a solution. So sit down with some vanilla ice cream (with actual vanilla) and something nice to drink and go through the process of replacing your public SSH keys everywhere.