What is the best Distributed Brute Force countermeasure?

Question

First, a little background: It is no secret that I am implementing an auth+auth system for CodeIgniter, and so far I'm winning (so to speak). But I've run into a pretty non-trivial challenge (one that most auth libraries miss entirely, but I insist on handling it properly): how to deal intelligently with large-scale, distributed, variable-username brute-force attacks.

I know all the usual tricks:

1. Limiting # of failed attempts per IP/host and denying the offenders access (e.g. Fail2Ban) - which no longer works since botnets have grown smarter
2. Combining the above with a blacklist of known 'bad' IPs/hosts (e.g. DenyHosts) - which relies on botnets falling for #1, which they increasingly don't
3. IP/host whitelists combined with traditional auth (sadly useless with dynamic IP users and the high churn on most web sites)
4. Setting a sitewide limit on # of failed attempts within a N minute/hour period, and throttling (suspending) all login attempts after that for a number of minutes/hours (with the problem that DoS attacking you becomes botnet child's play)
5. Mandatory digital signatures (public-key certificates) or RSA hardware tokens for all users with NO login/password option (without question a rock-solid solution, but only practical for closed, dedicated services)
6. Enforced ultra-strong password schemes (e.g. >25 nonsense characters with symbols - again, too impractical for casual users)
7. And finally, CAPTCHAs (which could work in most cases, but are annoying for users and virtually useless against a determined, resourceful attacker)

Now, these are just the theoretically workable ideas. There are plenty of rubbish ideas that blow the site wide open (e.g. to trivial DoS attacks). What I want is something better. And by better, I mean:

• It has to be secure(+) against DoS and brute-force attacks, and not introduce any new vulnerabilities that might allow a slightly sneakier bot to continue operating under the radar

• It has to be automated. If it requires a human operator to verify each login or monitor suspicious activity, it's not going to work in a real-world scenario

• It has to be feasible for mainstream web use (ie. high churn, high volume, and open registration that can be performed by non-programmers)

• It can't impede the user experience to the point where casual users will get annoyed or frustrated (and potentially abandon the site)

• It can't involve kittens, unless they are really really secure kittens

(+) By 'secure', I mean at least as secure as a paranoid user's ability to keep his password secret

So - let's hear it! How would you do it? Do you know of a best-practice that I haven't mentioned (oh please say you do)? I admit I do have an idea of my own (combining ideas from 3 and 4), but I'll let the true experts speak before embarrassing myself ;-)

Answer 1

Damn, no kittens. I’m unable to offer advice, then. :(

Answer 2

Looks like you are trying to defend against slow distributed brute force. Not that much you can do about it. We are using a PKI and no password logins. It helps, but if your clients chance workstations every once in a while, this is not very applicable.

Answer 3

1) What about requiring a one-time-password before entering their normal password? That would make it very obvious that someone was attacking before they got many opportunities to guess the main password?

2) Keep a global count/rate of login failures - this is the indicator for an attack - during an attack be stricter about login failures e.g. ban IPs more rapidly.

Answer 4

If I understand the MO of brute force attacks properly, then one or more usernames are tried continuously.

There are two suggestions which I don't think I've seen yet here:

• I always thought that the standard practice was to have a short delay (a second or so) after each wrong login for every user. This deters brute-force, but I don't know how long a one second delay would keep a dictionary attack at bay. (dictionary of 10,000 words == 10,000 seconds == about 3 hours. Hmm. Not good enough.)
• instead of a site-wide slow down, why not a user-name throttle. The throttle becomes increasingly harsh with each wrong attempt (up to a limit, I guess so the real user can still login)

Edit: In response to comments on a username throttle: this is a username specific throttle without regard to the source of the attack.

If the username is throttled, then even a coordinated username attack (multi IP, single guess per IP, same username) would be caught. Individual usernames are protected by the throttle, even if the attackers are free to try another user/pass during the timeout.

From an attackers point of view, during the timeout you may be able to take a first time guess at 100 passwords, and quickly discover one wrong password per account. You may only be able to make a 50 second guesses for the same time period.

From a user account point of view, it still takes the same average number of guesses to break the password, even if the guesses are coming from multiple sources.

For the attackers, at best, it will be the same effort to break 100 accounts as it would 1 account, but since you're not throttling on a site wide basis, you can ramp up the throttle quite quickly.

Extra refinements:

• detect IPs that are guessing multiple accounts - 408 Request Timeout
• detect IPs that are guessing the same account - 408 Request Timeout after a large (say 100) number of guesses.

UI ideas (may not be suitable in this context), which may also refine the above:

• if you are in control of the password setting, then showing the user how strong their password is encourages them to pick a better one.
• if you are in control of the login page, after a small (say 10) number of guesses of a single username, offer a CAPTCHA.

Answer 5

No matter how good your system is, it'll fail under a long enough attack. There are some good ideas here, on how to extend a password's duration. (I personally like the idea of exponentially-increasing attempt rate limiting per-user and per-IP address.) But no matter what you go with, you'll need to back it up with some password rules.

I'd encourage you to figure out how fast a password can be cracked, and have users change them twice as often as that. Hope this helps.

Edit: If you expect a lot of lazy attackers, requiring some CAPTCHA after multiple failed attempts is good: it raises the bar a little. If you're worried about a lot of intelligent attackers, hire a security consultant. ;)

Answer 6

I don't believe there is a perfect answer but I would be inclined to approach it on a basis of trying to confound the robots if an attack is sensed.

Off the top of my mind:

Switch to an alternate login screen. It has multiple username and password blanks which really do appear but only one of them is in the right place. The field names are RANDOM--a session key is sent along with the login screen, the server can then find out what fields are what. Succeed or fail it's then discarded so you can't try a replay attack--if you reject the password they get a new session ID.

Any form that is submitted with data in a wrong field is assumed to be from a robot--the login fails, period, and that IP is throttled. Make sure the random field names never match the legit field names so someone using something that remembers passwords isn't mislead.

Next, how about a different sort of captcha: You have a series of questions that won't cause problems for a human. However, they are NOT random. When the attack starts everyone is given question #1. After an hour question #1 is discarded, never to be used again and everyone gets question #2 and so on.

The attacker can't probe to download the database to put into his robot because of the disposable nature of the questions. He has to send new instructions out to his botnet within an hour to have any ability to do anything.

Answer 7

A few simple steps:

Blacklist certain common usernames, and use them as a honeypot. Admin, guest, etc... Don't let anyone create accounts with these names, so if someone does try to log them in you know it's someone doing something they shouldn't.

Make sure anyone who has real power on the site has a secure password. Require admins/ moderators to have longer passwords with a mix of letters, numbers and symbols. Reject trivially simple passwords from regular users with an explanation.

One of the simplest things you can do is tell people when someone tried to log into their account, and give them a link to report the incident if it wasn't them. A simple message when they log in like "Someone tried to log into your account at 4:20AM Wednesday blah blah. Click here if this wasn't you." It lets you keep some statistics on attacks. You can step up monitoring and security measures if you see that there's a sudden increase in fraudulent accesses.

Answer 8

To summarize Jens' scheme into a pseudo state transition diagram/rulebase:

1. user + password -> entry
2. user + !password -> denied
3. user + known_IP(user) -> front door, // never throttle
4. user + unknown_IP(user) -> catflap
5. (#denied > n) via catflaps(site) -> throttle catflaps(site) // slow the bots
6. catflap + throttle + password + captcha -> entry // humans still welcome
7. catflap + throttle + password + !captcha -> denied // a correct guess from a bot

Observations:

• Never throttle the front door. The Elbonian state police have your computer, in your house, but are unable to interrogate you. Brute force is a viable approach from your computer.
• If you provide a "Forgetten your password?" link, then your email account becomes part of the attack surface.

These observations cover a different type of attack to the ones you are trying to counter.

Answer 9

I have to ask whether you've done cost-benefit analysis of this problem; it sounds like you're trying to protect yourself from an attacker who has enough web presence to guess a number of passwords, sending maybe 3-5 requests per IP (since you've dismissed IP throttling). How much (roughly) would that kind of attack cost? Is it more expensive than the value of the accounts you're trying to protect? How many gargantuan botnets want what you've got?

The answer might be no -- but if it is, I hope you're getting help from a security professional of some sort; programming skill (and StackOverflow score) do not correlate strongly to security know-how.

Answer 10

Since several folks included CAPTCHA as a fallback human mechanism, I'm adding an earlier StackOverflow question and thread on CAPTCHA's effectiveness.

Has reCaptcha been cracked / hacked / OCR’d / defeated / broken?

Using CAPTCHA doesn't limit improvements from your throttling and other suggestions, but I think the number of answers that include CAPTCHA as a fallback should consider the human-based methods available to people looking to break security.

Answer 11

My highest recommendation is to simply make sure that you keep users informed of bad login attempts to their accounts-- Users will likely take the strength of their password much more seriously if they are presented with evidence that somebody is actually trying to get into their account.

I actually caught somebody that hacked into my brother's myspace account because they had tried to get into the gmail account I setup for him and used the 'reset my password by email' feature... which went to my inbox.

Answer 12

Disclaimer: I work for a two-factor company, but am not here to plug it. Here're some observations.

Cookies can be stolen with XSS and browser vulns. Users commonly change browsers or clear their cookies.

Source IP addresses are simultaneously dynamically variable and spoofable.

Captcha is useful, but doesn't authenticate a specific human.

Multiple methods can be combined successfully, but good taste is certainly in order.

Password complexity is good, anything password-based critically depends on passwords having sufficient entropy. IMHO, a strong password written down in a secure physical location is better than a weak password in memory. People know how to evaluate the security of paper documents much better than they know how to figure the effective entropy in their dog's name when used as a password for three different websites. Consider giving users the ability to print out a big or small page full of one-time use pass codes.

Security questions like "what was your high-school mascot" are mostly another lousy form of "something you know", most of them are easily guessable or outright in the public domain.

As you noted, throttling back failed login attempts is a trade-off between preventing brute-force attacks and ease of DoSing an account. Aggressive lockout policies may reflect a lack of confidence in password entropy.

I personally don't see the the benefit to enforcing password expiration on a website anyway. Attacker gets your password once, he can change it then and comply with that policy just as easily as you can. Perhaps one benefit is that the user might notice sooner if the attacker changes the account password. Even better would be if the the user were somehow notified before the attacker gained access. Messages like "N failed attempts since last login" are useful in this respect.

The best security comes from a second factor of authentication which is out-of-band relative to the first. Like you said, hardware tokens in the "something you have" are great, but many (not all) have real admin overhead associated with their distribution. I don't know of any biometric "something you are" solutions good for websites. Some two-factor solutions work with openid providers, some have PHP/Perl/Python SDKs.