Number of attempts to brute force an average password / non intrusive yet meaningful limits?

Question

There are several useful answers on SO regarding prevention of brute forcing a password of a web service by applying throttling. I couldn't find any good numbers though and I have little expertise in this area, so the question is:

How many attempts does it usually take to brute-force an average password of 6 or more characters (with no additional knowledge that may help, but taking into account that passwords are probably prone to dictionary attacks) and based on that, what are meaningful limits to apply to the throttling algorithm without disrupting the user experience?

This is my current scheme:

• The login form uses a nonce, so the attacker has to wait for a complete request cycle to complete to both get the result of the login attempt and retrieve a new token.
• I allow the login form to be retrieved 50 times per IP with less than a minute between requests, after that the IP will be blocked for 1 minute. Any new attempts within this one minute will restart the timeout.
• There's a sleep applied for each fetching of the login page of # of attempts / 5, so after 5 requests with less than a minute between requests it'll take > 1 second to fetch the form, after 10 requests > 2 seconds, etc.
• Additionally, I'm only allowing 100 failed login attempts per user account with 2 hours between attempts, after that the account is blocked for 2 hours.
• To avoid frequent DoS'ing of accounts, IPs can be whitelisted (no limits applied) or blacklisted (any login attempt ignored completely).

Based on the answers so far, I have tweaked it to work like this:

• Retrieving the login form is progressively slowed down on a per IP basis. Each new request is slept for # of requests / 2 seconds. The counter is reset after 10 minutes of no login activity.
• I'm keeping a FIFO stack of login attempts for each IP. If an IP fails to log in 30 times within 2 hours, it's suspended. I'm also keeping a list of number of suspensions per IP, and the suspension time is calculated as 2 ^ (# of suspensions + 1) hours. This should lead to a rapid de facto blacklisting of continually offending IPs.
• Additionally, if an account failed to log in 20 times within one day it's being suspended for 2 hours. I'm not too sure about this measure yet, since this means accounts can be DoS'd quite easily. Short of a massive distributed botnet though, offending IPs should become de facto blacklisted faster than an account can be permanently DoS'd. It's also quite an effective measure to protect an account.

I think these limits should not harm normal users, even ones that regularly forget their password and try to log in several times. The IP limits should also work okay with heavily NAT'ed users, given the average size of the service. Can somebody prove this to be efficient or inefficient with some solid math? :)

Answer 1

From the question it sounds like the fastest they could possibly try passwords is 50 per minute. Based on that and using random 6 digit passwords:

• all lower case: 26^6 = 308,915,776 possible passwords = worst case 12 years, 6 years on average
• lower case and numbers: 36^6 = 82 years max, 41 years on average

Of course, dictionary attacks would be much faster, but I don't have the numbers for that.

EDIT: I tried to link Google calculator results backing this up, but ^ seems to mess up links on here.

EDIT2:

Dictionary attacks (from http://www.outpost9.com/files/WordLists.html):

• all listed words (75,000): ~1 day
• list of 816 common passwords: ~16 minutes
• really long word list: ~12 days (I looked at this and I'm guessing it contains most non-technical people's passwords)

The last one is scary, but 12 days is still a long time. If you're really worried, you could track every incorrect password until the user gets a correct password, then if the list gets to over like 100 different attempts, just ban the IP address and send an email to the user.

Answer 2

You have a couple of good controls there, but you really should tighten it more. A regular user shouldn't fail to log in more than five times. If he does, show him a CAPTCHA.

Remember that under no circumstances should you lock the account. It's called an account lockout vulnerability. This allows an arbitrary user to log out other users from the service (DOS, denial of service).

I've approached this problem of login throttling many times and the one I like is that you create a field of failed attempts and the last failed attempt date in your database. Whenever someone (anyone) fails to log into account X, you increase the value of X's failed attempts and update the last failed attempt date. If the failed attempt count exceeds Y (for example, five), then show a CAPTCHA for the specific user. So, you won't have a huge database of banned IPs to throttle the login form, instead you have just two more fields per user. It also makes little sense to ban/throttle based on IPs, because of botnets and proxies (both legal and illegal ones). When IPv6 comes out in fashion, you will be more doomed I presume. It makes much more sense to throttle based on targeted accounts. So, when your account X is being targeted by a botnet, the login form will be throttled with a CAPTCHA. The obvious drawback here is that if your CAPTCHA fails... so does your login throttling.

So, in the essence it goes like this:

• Someone failed to log into account X - increase the failed attempts field.
• If there are more than 5 failed attempts, and the last failed attempt happened one hour ago, it's seems that the account is under attack, show the CAPTCHA.
• On the other hand, if the last failed attempt occured more than a day ago, it seems that the attack has ended, lower your shields and don't require CAPTCHA.

It's basically a shield that turns on when there's a massive targeted attack against particular accounts. The good thing about this kind of approach is that it won't matter if I own a farm of PCs across the world - I can't brute force a single account because it's account based.

The two bad things about this is that if the CAPTCHA fails you have nothing left. You could of course improve this situation by placing other protections, too. The second problem is that if I had a bot-net, I could use one PC per one account, and then it's likely that with a million computer network I crack at least one account, but this approach works only in non-targeted attacks.

I hope this gave you some thoughts.