Distributed SSH Brute Force Attempts?

I'd read not long ago on the ISC Diary that someone has noticed that a there's a newly discovered way to avoid automated tools such as Denyhosts and Fail2ban. It appears that the attacks are now distributed across an IP pool of compromised machines. Maybe botnet masters are leveraging their botnets to attempt to bruteforce login attempts without risking the attacking hosts.

I think I'm seeing this in my home firewall logs:

Nov 23 15:23:01 delly sshd[67946]: error: PAM: authentication error for illegal user artois from 1-1-4-27a.vhe.sth.bostream.se
Nov 23 15:23:01 delly sshd[67946]: Failed keyboard-interactive/pam for invalid user artois from 82.182.188.187 port 35763 ssh2
Nov 23 15:24:18 delly sshd[67949]: Invalid user arty from 58.26.48.162
Nov 23 15:24:18 delly sshd[67949]: error: PAM: authentication error for illegal user arty from 58.26.48.162
Nov 23 15:24:18 delly sshd[67949]: Failed keyboard-interactive/pam for invalid user arty from 58.26.48.162 port 5785 ssh2
Nov 23 15:25:17 delly sshd[67955]: Invalid user arty from 200.170.141.134
Nov 23 15:25:17 delly sshd[67955]: error: PAM: authentication error for illegal user arty from 200-170-141-134.static.ctbctelecom.com.br
Nov 23 15:25:17 delly sshd[67955]: Failed keyboard-interactive/pam for invalid user arty from 200.170.141.134 port 57360 ssh2
Nov 23 15:26:31 delly sshd[67958]: Invalid user arty from 219.76.222.27
Nov 23 15:26:31 delly sshd[67958]: error: PAM: authentication error for illegal user arty from n219076222027.netvigator.com
Nov 23 15:26:31 delly sshd[67958]: Failed keyboard-interactive/pam for invalid user arty from 219.76.222.27 port 47176 ssh2
Nov 23 15:28:48 delly sshd[67963]: Invalid user arva from 58.196.4.2
Nov 23 15:28:49 delly sshd[67963]: error: PAM: authentication error for illegal user arva from 58.196.4.2
Nov 23 15:28:49 delly sshd[67963]: Failed keyboard-interactive/pam for invalid user arva from 58.196.4.2 port 50637 ssh2
Nov 23 15:33:27 delly sshd[67982]: Invalid user arvid from 125.77.106.246
Nov 23 15:33:27 delly sshd[67982]: error: PAM: authentication error for illegal user arvid from 125.77.106.246
Nov 23 15:33:27 delly sshd[67982]: Failed keyboard-interactive/pam for invalid user arvid from 125.77.106.246 port 51673 ssh2
Nov 23 15:34:40 delly sshd[67985]: Invalid user arvin from 85.39.252.226
Nov 23 15:34:40 delly sshd[67985]: error: PAM: authentication error for illegal user arvin from host226-252-static.39-85-b.business.telecomitalia.it
Nov 23 15:34:40 delly sshd[67985]: Failed keyboard-interactive/pam for invalid user arvin from 85.39.252.226 port 43706 ssh2
Nov 23 15:35:54 delly sshd[67991]: Invalid user arvin from 217.126.90.161
Nov 23 15:35:55 delly sshd[67991]: error: PAM: authentication error for illegal user arvin from 161.red-217-126-90.staticip.rima-tde.net
Nov 23 15:35:55 delly sshd[67991]: Failed keyboard-interactive/pam for invalid user arvin from 217.126.90.161 port 36755 ssh2
Nov 23 15:37:11 delly sshd[67994]: Invalid user arvin from 200.232.181.40
Nov 23 15:37:11 delly sshd[67994]: error: PAM: authentication error for illegal user arvin from 200-232-181-40.dsl.telesp.net.br
Nov 23 15:37:11 delly sshd[67994]: Failed keyboard-interactive/pam for invalid user arvin from 200.232.181.40 port 56318 ssh2
Nov 23 15:39:16 delly sshd[67997]: Invalid user arwan from 200.248.82.130
Nov 23 15:39:17 delly sshd[67997]: error: PAM: authentication error for illegal user arwan from 200.248.82.130
Nov 23 15:39:17 delly sshd[67997]: Failed keyboard-interactive/pam for invalid user arwan from 200.248.82.130 port 53388 ssh2
Nov 23 15:40:24 delly sshd[68003]: Invalid user arwan from 217.126.90.161
Nov 23 15:40:25 delly sshd[68003]: error: PAM: authentication error for illegal user arwan from 161.red-217-126-90.staticip.rima-tde.net
Nov 23 15:40:25 delly sshd[68003]: Failed keyboard-interactive/pam for invalid user arwan from 217.126.90.161 port 43871 ssh2
Nov 23 15:41:33 delly sshd[68006]: Invalid user arwen from 200.209.6.130
Nov 23 15:41:34 delly sshd[68006]: error: PAM: authentication error for illegal user arwen from 200.209.6.130
Nov 23 15:41:34 delly sshd[68006]: Failed keyboard-interactive/pam for invalid user arwen from 200.209.6.130 port 14808 ssh2
Nov 23 15:42:48 delly sshd[68016]: Invalid user arwen from 123.14.10.64
Nov 23 15:42:49 delly sshd[68016]: error: PAM: authentication error for illegal user arwen from 123.14.10.64
Nov 23 15:42:49 delly sshd[68016]: Failed keyboard-interactive/pam for invalid user arwen from 123.14.10.64 port 7600 ssh2
Nov 23 15:43:50 delly sshd[68020]: reverse mapping checking getaddrinfo for techregister.worcesteracademy.org [68.112.227.30] failed - POSSIBLE BREAK-IN ATTEMPT!
Nov 23 15:43:50 delly sshd[68020]: Invalid user arwen from 68.112.227.30
Nov 23 15:43:50 delly sshd[68020]: error: PAM: authentication error for illegal user arwen from 68.112.227.30
Nov 23 15:43:50 delly sshd[68020]: Failed keyboard-interactive/pam for invalid user arwen from 68.112.227.30 port 38273 ssh2
Nov 23 15:45:03 delly sshd[68039]: Invalid user arya from 196.28.50.162
Nov 23 15:45:03 delly sshd[68039]: error: PAM: authentication error for illegal user arya from www.cfse.gov.pr
Nov 23 15:45:03 delly sshd[68039]: Failed keyboard-interactive/pam for invalid user arya from 196.28.50.162 port 55647 ssh2
Nov 23 15:46:10 delly sshd[68042]: Invalid user arya from 81.12.221.74
Nov 23 15:46:10 delly sshd[68042]: error: PAM: authentication error for illegal user arya from em.asiban.ro
Nov 23 15:46:10 delly sshd[68042]: Failed keyboard-interactive/pam for invalid user arya from 81.12.221.74 port 16653 ssh2
Nov 23 15:47:23 delly sshd[68050]: Invalid user arya from 190.34.148.178
Nov 23 15:47:23 delly sshd[68050]: error: PAM: authentication error for illegal user arya from 190.34.148.178
Nov 23 15:47:23 delly sshd[68050]: Failed keyboard-interactive/pam for invalid user arya from 190.34.148.178 port 58738 ssh2
Nov 23 15:48:29 delly sshd[68053]: reverse mapping checking getaddrinfo for britannic-iss-medidean-working.e1-4-0-0-57.0.ar2.lon3.gblx.net [64.213.54.106] failed - POSSIBLE BREAK-IN ATTEMPT!
Nov 23 15:48:29 delly sshd[68053]: Invalid user asa from 64.213.54.106
Nov 23 15:48:29 delly sshd[68053]: error: PAM: authentication error for illegal user asa from 64.213.54.106
Nov 23 15:48:29 delly sshd[68053]: Failed keyboard-interactive/pam for invalid user asa from 64.213.54.106 port 42991 ssh2
Nov 23 15:49:46 delly sshd[68056]: Invalid user asa from 91.135.200.86
Nov 23 15:49:47 delly sshd[68056]: error: PAM: authentication error for illegal user asa from 91.135.200.86
Nov 23 15:49:47 delly sshd[68056]: Failed keyboard-interactive/pam for invalid user asa from 91.135.200.86 port 10262 ssh2
Nov 23 15:50:52 delly sshd[68062]: Invalid user asa from 200.20.187.222
Nov 23 15:50:53 delly sshd[68062]: error: PAM: authentication error for illegal user asa from 200.20.187.222
Nov 23 15:50:53 delly sshd[68062]: Failed keyboard-interactive/pam for invalid user asa from 200.20.187.222 port 52959 ssh2

Don't focus on the attacking IPs, but look at the referenced users. There are now tools that look like they're scaling attacks on a listing of common logins (or maybe even dictionary attacks) so that there's less risk of detection. There are current tools that look for attacks in a thresholded manner (example: 4 attacks in 5 sec warrants a block of that attacking IP). This new method of attack will not trigger the thresholding blocks.

More than ever, SSH key-based authentication should be used. This will prevent a successful login when under attack via brute forcing methods.

I can already see attack detection tools being adjusted to focus on tracking user accounts being bruteforced and banning all IPs that try to access user accounts based on time (example: 4 attacks on account asa in 5 sec will warrant a ban of all subsequent IPs for the next day or so...and not block if the IP is listed within a whitelist).

Your thoughts?