Problem - "too many authentication failures"

Problem - "too many authentication failures"

I ran into a strange situation today.  I was trying to SSH into a partner's Ubuntu server in their lab over VPN from my laptop.  When I used PuTTY, I kept getting "too many authentication failures" immediately upon entering the username (no password given yet).  

The partner insisted they were able to access the server and verified the credentials.  But then I noticed they were using OpenSSH client.  I tried it, and it worked.  

Huh, this only affects PuTTY?  

Well, now I had access to the server's sshd logs, and I could see:

Dec 31 18:26:13 xxxxxxx sshd[1022]: userauth_pubkey: key type ssh-dss not in PubkeyAcceptedAlgorithms [preauth]

Dec 31 18:26:14 xxxxxxx sshd[1022]: error: maximum authentication attempts exceeded for admin from 192.168.101.254 port 57881 ssh2 [preauth]

Dec 31 18:26:14 xxxxxxx sshd[1022]: Disconnecting authenticating user admin 192.168.101.254 port 57881: Too many authentication failures [preauth]

Solution

Apparently, they've turned-off support for older DSS keys.  Makes sense, DSS has been obsolete for a while now.

So now I knew were to go look.  And low and behold, my PuTTY Pageant key agent had some old DSS keys loaded.  So I removed the old keys from Pageant, and now it works.  

That is odd though, you would expect sshd to fallback to password auth if none of the keys worked, but apparently it triggered the "too many authentication failures" logic.

I spent two days trying to figure this out.  Google searches were useless, so I thought I should add this pearl of wisdom to the vast sea of Internet knowledge, and hopefully save someone some time.