Essentially, the attackers are bypassing brute force attempts by coming from thousands of different bot-controlled IPs, which allows them to try far more passwords against a given system. Most brute-force protection focuses on source IP, and with a botnet they have plenty of those to spare.
Here are two simple countermeasures:
Switch to Pure Key-based Authentication
I say pure because it doesn’t help to just enable key-based authentication; you have to disable passwords as an option altogether or you won’t be increasing your resistance to brute-forcing at all.
Give it a try and compare your logs before and after.
Move Your SSH Port
There’s a lot to be said for simply not being there when attacks are coming in. There’s a lot of debate on this one, but I stand firmly on the side of obscurity being a good addition to a security posture, as long as the cost of implementation isn’t prohibitive.
So if you have a small user-base, or if you have an easy means of updating the client your users use, simply move your SSH daemon to another port. These attacks are automated and aren’t likely to hit on any port other than 22. The amount of additional effort required to mount similar attacks against all 65,000+ ports makes the attempts a waste of time for attackers, and makes it very much worth the time for you.
As you can see from this crude experiment I did back in March, moving your SSH port does in fact make a difference in the number of brute-force probes you’ll see, and if you combine this avoidance measure with additional security (key-based auth) you’ll have improved your situation significantly. From my experiment post:
The stats over the weekend are now over 18,000 connections to port 22, and five (5) to port 24
Just remember to always any additional security first, then add avoidance/obscurity afterwards. ::