Jimmy Ruska has taken the time to combine data from 3 compromised-password lists, and the results are pretty interesting.
If an attacker can try just a single password against every user on your web application, he’ll compromise about 1% of them. Even with a fairly stringent 3-attempt lockout policy, about 2-3% of your users will be compromised.
More complex password requirements aren’t the answer here; many of the most popular passwords are at least 7 characters, and have 1 or more digits. Disallowing any passwords appearing on one of these lists would alleviate the issue, but seems like a pretty shoddy user-experience.
There is one way to prevent this site-wide brute force attack: do not give away a list of log-in usernames for your site! This attack only works if the attacker can enumerate all logins to your web app. This is an easy task for many sites, like Digg, where usernames are publicly plastered all over the site. Sites like Mint on the other hand, which use e-mail addresses for log-in, are immune.
The key point is that you should never reveal whether a particular e-mail/username is registered with your site. That means your “log-in failed” page should not indicate whether or not the username was correct, for example. If there is any way to determine if a given username is registered, an attacker can leverage that to pull off a site-wide brute force.
So, is your site enabling brute-force attacks? If so, now is the time to go change your architecture to stop this attack in its tracks.