What is the best Distributed Brute Force countermeasure?

What is the best Distributed Brute Force countermeasure?

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 by raupach for What is the best Distributed Brute Force countermeasure?

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 by Douglas Leeder for What is the best Distributed Brute Force countermeasure?

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 by jamesh for What is the best Distributed Brute Force countermeasure?

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 by ojrac for What is the best Distributed Brute Force countermeasure?

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 by davethegr8 for What is the best Distributed Brute Force countermeasure?

There are three factors of authentication:

1. A user knows something (ie, a password)
2. A user has something (ie, a key fob)
3. A user is something (ie, retina scan)

Usually, websites only enforce policy #1. Even most banks only enforce policy 1. They instead rely on a "knows something else" approach to two-factor authentication. (IE: A user knows their password and their mother's maiden name.) If you are able, a way to add in a second factor of authentication is not too difficult.

If you can generate around 256 characters of randomness, you could structure that in a 1616 table, and then ask the user to give you the value in the table of cell A-14, for example. When a user signs up or changes their password, give them the table and tell them to print it off and save it.

The difficulty with that approach is that when a user forgets their password, as they will, you can't just offer the standard "answer this question and put in a new password", since that's vulnerable to brute-force as well. Also, you can't reset it and email them a new one, since their email could be compromised as well. (See: Makeuseof.com and their stolen domain.)

Another idea (which involves kittens), is what BOA calls SiteKey (I believe they trademarked the name). Briefly, you have the user upload an image when they register, and when they attempt to login, ask them to pick their image out of 8 or 15 (or more) random ones. So, if a user uploads a picture of their kitten, theoretically only they know exactly which picture is theirs out of all the other kittens (or flowers or whatever). The only real vunerability this approach has is the man-in-the-middle attack.

One more idea (no kittens though), is to track IPs that users access the system with, and require them to perform additional authentication (captcha , pick a kitty, pick a key from this table) when they log in from an address they haven't before. Also, similar to GMail, allow the user to view where they have logged in from recently.

Edit, New Idea:

Another way of validating login attempts is to check whether or not the user has come from your login page. You can't check referrers, since they can be easily faked. What you need is to set a key in the _SESSION var when the user views the login page, and then check to make sure that key exists when they submit their login information. If bot does not submit from the login page, it will not be able to login. You can also facilitate this by involving javascript in the process, either by using it to set a cookie, or adding some information to the form after it has loaded. Or, you can split the form up into two different submits (ie, the user enters their username, submits, then on a new page enters their password and submit again.)

The key, in this case, is the most important aspect. A common method of generating them is some combination of the user's data, their IP, and the time it was submitted.

Answer by Loren Pechtel for What is the best Distributed Brute Force countermeasure?

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 by Jens Roland for What is the best Distributed Brute Force countermeasure?

All right, enough stalling; here's what I've come up with so far

(sorry, long post ahead. Be brave, friend, the journey will be worth it)

Combining methods 3 and 4 from the original post into a kind of 'fuzzy' or dynamic whitelist, and then - and here's the trick - not blocking non-whitelisted IPs, just throttling them to hell and back.

Note that this measure is only meant to thwart this very specific type of attack. In practice, of course, it would work in combination with other best-practices approaches to auth: fixed-username throttling, per-IP throttling, code-enforced strong password policy, unthrottled cookie login, hashing all password equivalents before saving them, never using security questions, etc.

Assumptions about the attack scenario

If an attacker is targeting variable usernames, our username throttling doesn't fire. If the attacker is using a botnet or has access to a large IP range, our IP throttling is powerless. If the attacker has pre-scraped our userlist (usually possible on open-registration web services), we can't detect an ongoing attack based on number of 'user not found' errors. And if we enforce a restrictive system-wide (all usernames, all IPs) throttling, any such attack will DoS our entire site for the duration of the attack plus the throttling period.

So we need to do something else.

The first part of the countermeasure: Whitelisting

What we can be fairly sure of, is that the attacker is not able to detect and dynamically spoof the IP addresses of several thousand of our users(+). Which makes whitelisting feasible. In other words: for each user, we store a list of the (hashed) IPs from where the user has previously (recently) logged in.

Thus, our whitelisting scheme will function as a locked 'front door', where a user must be connected from one of his recognized 'good' IPs in order to log in at all. A brute-force attack on this 'front door' would be practically impossible(+).

(+) unless the attacker 'owns' either the server, all our users' boxes, or the connection itself -- and in those cases, we no longer have an 'authentication' issue, we have a genuine franchise-sized pull-the-plug FUBAR situation

The second part of the countermeasure: System-wide throttling of unrecognized IPs

In order to make a whitelist work for an open-registration web service, where users switch computers frequently and/or connect from dynamic IP addresses, we need to keep a 'cat door' open for users connecting from unrecognized IPs. The trick is to design that door so botnets get stuck, and so legitimate users get bothered as little as possible.

In my scheme, this is achieved by setting a very restrictive maximum number of failed login attempts by unapproved IPs over, say, a 3-hour period (it may be wiser to use a shorter or longer period depending on type of service), and making that restriction global, ie. for all user accounts.

Even a slow (1-2 minutes between attempts) brute force would be detected and thwarted quickly and effectively using this method. Of course, a really slow brute force could still remain unnoticed, but too slow speeds defeat the very purpose of the brute force attack.

What I am hoping to accomplish with this throttling mechanism is that if the maximum limit is reached, our 'cat door' slams closed for a while, but our front door remains open to legitimate users connecting by usual means:

• Either by connecting from one of their recognized IPs
• Or by using a persistent login cookie (from anywhere)

The only legitimate users who would be affected during an attack - ie. while the throttling was activated - would be users without persistent login cookies who were logging in from an unknown location or with a dynamic IP. Those users would be unable to login until the throttling wore off (which could potentially take a while, if the attacker kept his botnet running despite the throttling).

To allow this small subset of users to squeeze through the otherwise-sealed cat door, even while bots were still hammering away at it, I would employ a 'backup' login form with a CAPTCHA. So that, when you display the "Sorry, but you can't login from this IP address at the moment" message, include a link that says "secure backup login - HUMANS ONLY (bots: no lying)". Joke aside, when they click that link, give them a reCAPTCHA-authenticated login form that bypasses the site-wide throttling. That way, IF they are human AND know the correct login+password (and are able to read CAPTCHAs), they will never be denied service, even if they are connecting from an unknown host and not using the autologin cookie.

Oh, and just to clarify: Since I do consider CAPTCHAs to be generally evil, the 'backup' login option would only appear while throttling was active.

There is no denying that a sustained attack like that would still constitute a form of DoS attack, but with the described system in place, it would only affect what I suspect to be a tiny subset of users, namely people who don't use the "remember me" cookie AND happen to be logging in while an attack is happening AND aren't logging in from any of their usual IPs AND who can't read CAPTCHAs. Only those who can say no to ALL of those criteria - specifically bots and really unlucky disabled people - will be turned away during a bot attack.

EDIT: Actully, I thought of a way to let even CAPTCHA-challenged users pass through during a 'lockdown': instead of, or as a supplement to, the backup CAPTCHA login, provide the user with an option to have a single-use, user-specific lockdown code sent to his email, that he can then use to bypass the throttling. This definitely crosses over my 'annoyance' threshold, but since it's only used as a last resort for a tiny subset of users, and since it still beats being locked out of your account, it would be acceptable.

(Also, note that none of this happens if the attack is any less sophisticated than the nasty distributed version I've described here. If the attack is coming from just a few IPs or only hitting a few usernames, it will be thwarted much earlier, and with no site-wide consequences)

---

So, that is the countermeasure I will be implementing in my auth library, once I'm convinced that it's sound and that there isn't a much simpler solution that I've missed. The fact is, there are so many subtle ways to do things wrong in security, and I'm not above making false assumptions or hopelessly flawed logic. So please, any and all feedback, criticism and improvements, subtleties etc. are highly appreciated.

Answer by patros for What is the best Distributed Brute Force countermeasure?

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 by jamesh for What is the best Distributed Brute Force countermeasure?

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 by ojrac for What is the best Distributed Brute Force countermeasure?

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 by Matthew Glidden for What is the best Distributed Brute Force countermeasure?

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 by nvuono for What is the best Distributed Brute Force countermeasure?

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 by Marsh Ray for What is the best Distributed Brute Force countermeasure?

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.

Answer by cballou for What is the best Distributed Brute Force countermeasure?

I had previously answered a very similar question over at How can I throttle user login attempts in PHP. I'll reiterate the proposed solution here as I believe many of you will find it informational and useful to see some actual code. Please bare in mind that using a CAPTCHA might not be the best solution due to the increasingly accurate algorithms being used in CAPTCHA busters nowadays:

You cannot simply prevent DoS attacks by chaining throttling down to a single IP or username. Hell, you can't even really prevent rapid-fire login attempts using this method.

Why? Because the attack can span multiple IPs and user accounts for the sake of bypassing your throttling attempts.

I have seen posted elsewhere that ideally you should be tracking all failed login attempts across the site and associating them to a timestamp, perhaps:

CREATE TABLE failed_logins(      id INT(11) UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,      username VARCHAR(16) NOT NULL,      ip_address INT(11) UNSIGNED NOT NULL,      attempted DATETIME NOT NULL  ) engine=InnoDB charset=UTF8;  

Decide on certain delays based on the overall number of failed logins in a given amount of time. You should base this on statistical data pulled from your failed_logins table as it will change over time based on the number of users and how many of them can recall (and type) their password.

---

10 failed attempts = 1 second  20 failed attempts = 2 seconds  30 failed attempts = reCaptcha  

---

Query the table on every failed login attempt to find the number of failed logins for a given period of time, say 15 minutes:

---

SELECT COUNT(1) AS failed FROM failed_logins WHERE attempted > DATE_SUB(NOW(), INTERVAL 15 minute);  

---

If the number of attempts over the given period of time is over your limit, either enforce throttling or force all user's to use a captcha (i.e. reCaptcha) until the number of failed attempts over the given time period is less than the threshold.

// array of throttling  $throttle = array(10 => 1, 20 => 2, 30 => 'recaptcha');    // assume query result of $sql is stored in $row  $sql = 'SELECT MAX(attempted) AS attempted FROM failed_logins';  $latest_attempt = (int) date('U', strtotime($row['attempted']));  // get the number of failed attempts  $sql = 'SELECT COUNT(1) AS failed FROM failed_logins WHERE attempted > DATE_SUB(NOW(), INTERVAL 15 minute)';  // assume the number of failed attempts was stored in $failed_attempts  krsort($throttle);  foreach ($throttle as $attempts => $delay) {      if ($failed_attempts > $attempts) {          // we need to throttle based on delay          if (is_numeric($delay)) {              $remaining_delay = time() - $latest_attempt - $delay;              // output remaining delay              echo 'You must wait ' . $remaining_delay . ' seconds before your next login attempt';          } else {              // code to display recaptcha on login form goes here          }          break;      }  }  

Using reCaptcha at a certain threshold would ensure that an attack from multiple fronts would be minimized and normal site users would not experience a significant delay for legitimate failed login attempts. I can't gaurantee prevention, as it's already been expanded upon that CAPTCHA's can be busted. There are alternative solutions, perhaps a variant of "Name this animal", which could work quite well as a substitute.

Answer by Joseph W for What is the best Distributed Brute Force countermeasure?

You could also throttle based on the strength of a users password.

When a user registers or changes their password you calculate a strength rating for their password, say between 1 and 10.

Something like "password" scores a 1 whereas "c6eqapRepe7et*Awr@ch" might score a 9 or 10 and the higher the score the longer it takes for throttling to kick in.

Answer by Mike Mestnik for What is the best Distributed Brute Force countermeasure?

The first answer I've usually heard when asking this question is to change ports, but forget about that and just disable IPv4. If you only allow clients from IPv6 networks you'r no longer pray for simple network scanning and attackers will resort to DNS lookups. Don't run on the same address as your Apache(AAAA)/Sendmail(MX->AAAA)/what have you given out to everybody(AAAA). Make sure your zone can't be xferd, wait you'r allowing your zone to be downloaded by anybody?

If the bots find your server setup new hostnames, just prepend some gibberish to your hostnames, and change your address. Leave the old names and even setup **honeypot names for the bot net to timeout on.

** Test your reverse(PTR) records(under ip6.arpa.) to see if they can be used to zero in on /4's that have records VS /4s that don't. I.E. Typically ip6.arpa would have ~32 "."s in an address but trying with the last few missing might elude the network blocks that have records VS others that don't. If you take that further it becomes possible to skip large portions of the address space.

In the worst case users will have to setup an IPv6 tunnel, it's not like they'd have to go as far as VPNing into a DMZ... Though one wonders why that's not the first option.

Also Kerberos is cool, but IMHO LDAP blows(What's technically wrong with NISPlus? I've read that Sun decided that users wanted LDAP and because of this they dropped NIS+). Kerberos does work fine without LDAP or NIS, just have to manage users on a host by host basis. Using Kerberos gives you an easy to use, if not automated, PKI.

Answer by Tim 333 for What is the best Distributed Brute Force countermeasure?

Bit late here but I was thinking, assuming a hard case - the attacker uses a lot of random IPs, random user names and a random password selected from say a list of the 10,000 most popular.

One thing you could do, especially if the system seems under attack in that there are a lot of wrong password attempts on the system and especially if the password is low entropy is to ask a secondary question like what are your parents first names, for example. If an attacker hits a million accounts trying the password 'password1' there's a good chance they'll get a lot but their odds of also getting the names right would reduce successes dramatically.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72