With which algorithm I can prevent a brute force on a login?

Question

I want make my software more secure. I want prevent it from brute force attack. I know that a strong password is the best but I can not control it.

• The algorithm must scale from a very small system with only some users to a very large system.
• A captcha is not an option.
• No real user should be blocked because there is an attack. I think it is fatal if the admin can not login anymore because there is an attack.

I have think about the follow solutions:

• Only a hard coded count of failure per time are possible. After this the login will have a delay. But this will not scale. Also is it it very simple to prevent a valid login with an attack.
• Only a count of failures per IP address is possible. After the limit the login will be delayed. But with a bot net this help not. Also can a bot net consume large resources if all the ip addresses and the count of attempts must be stored.
• Only a count of failures per user is possible. Then it can be possible to prevent a valid login of the attacked user.

Are there a good algorithm to prevent brute force attack?

Answer 1

Time is your friend.

Think about what happens when you draw money from "ye average banking machine".

1. User inserts card (read: email/name/whatever),
2. Machine says "hi, please enter pincode" (read: password/whatever)
3. User can now enter correct pincode within 3 attempts. If that fails, the card is withdrawn and the user will have to wait for the next day to personally apply for a new card and pincode, explaining to his bank what happened.

Now, in your situation you most probably don't want people to come knocking at your door because they failed to enter the correct code. To avoid this, you'll simply have to strip the "come and apply for a new card" thing and what's left is "wait until tomorrow".

So, if you give a user 3 attempts to verify himself/herself and he/she fails... make her wait for an hour before he/she can try again.

If someone would still try to go for a brute force attack, it would enable him to try ("3 attempts per hour" maximum x "24 hours in a day" maximum = 3 x 24 =) 72 attempts a day.

Depending on what he/she is trying to brute-force, 72 attempts a day (which are 26280 attempts in a 365-day year) is wa-ay too slow.

This way - and as long as "reverse engineering" to find a backdoor isn't an option - your "software" should be safe from brute-forcing anything.

UPDATE

A little update, based on the comments to this answer...

Now, what about people getting locked out because one or more malicious people abuse the user name of a specific member and simply try to make sure such a user can't log in because they simply entered a wrong password 3 times?

Right, sounds like a "Denial Of Service"-alike attack. But that won't stop you from doing it this way, as such attacks can be circumvented easy. All you have to do is to make sure you don't forget about a second layer of security for such cases.

Remember that there are things like "security questions". Someone might be able to know or guess your username, but it'll take a truckload of time to get around a security question when locked... unless you know the answer. The security question could be limited to simply "unlock" the "locked" login area.

Think about how Google and Co. do it:

1. login with username/email and password,
2. fails several times gives a lockout,
3. answering security question correctly lifts lockout.

Use a captcha at (1) and (3) to slow down any brute-forcing attempts and you're all set.

If you explicitly do not want to use a captcha (which makes me wonder why), you will have to implement a "user-ip", "time-of-access" checking implementation and slow down access to the system for a random 1 to 2 seconds. This shouldn't be a problem as this would be a similar implementation as the lockout-procedure, only that you don't lockout but slow-down things at certain points so a brute-force attack takes time. A 1 second slowdown on 1 page will limit brute-forcing to 60 attempts per minute, while you're locking out the brute-forcer after 3 failed attempts. Same goes for the security question: slow it down. The brute-forcer will have to be smart enough to deal with both points and will have to brute-force both of them at the same time... stealing his valuable resources and time to cause havoc.

However you do it. If you do it like this, there's no need for the admin to even leave the coffee machine while all that's going on, and it solves any problems you think you might have discovered relating to "locking out legit users with a DOS-alike attack".

Let's look at the initial example I provided above in (3):

If that fails, the card is withdrawn and the user will have to wait for the next day to personally apply for a new card and pincode, explaining to his bank what happened.

Well, the "security question" option to enable legit users from lifting the lockout is just like being forced to personally visit and talk to your bank. Just easier.

Also, this "unlocking" procedure can be useful for the admin/sysop as a simple log file showing the number of "attempts" can help the admin to track down attempts of a definitive attack. Any script kid could try to lock out users by entering the wrong password 3 times... but if someone fails answering the security question severaltimes, there's something bad going.

And last but not least: just like an onion, such security layers can even be wrapped into each other (if it makes sense, like in high-security environments).

The simple trick is to make it hard for people to mess with things, while keeping the regular user happy.

I can only repeat: time is your friend... (the rest is simple logic)

Answer 2

Why do you think that your approach of delaying the login after a fixed amount of failed attempts doesn't scale? In my opinion, it scales perfectly well: for each IP (or session cookie or whatever) and time slice, there's a fixed amount of login attempts, making it infeasible to launch a brute-force attack.

Apart from that, I wouldn't worry about botnets, since the owner of a sufficiently powerful botnet can easily generate enough traffic on your uplink such that no other connections are possible/feasible, be they login attempts or not.

EDIT: adding to the comments and just to have this issue pointed out clearly: you can't defend against DoS attacks due to the nature of TCP/IP (and DNS). The best you can do is to protect those resources that are not vulnerable to DoS, possibly affecting valid users. That is, when storing failed login attempts, don't store more than N login attempts in order to prevent that a successful DoS completely fills your available disk space in addition to your available bandwidth (which you can't protect).

The simple analogy of a house might help here: you can protect your door, but not the street leading to it.

Answer 3

Things i would do to prevent brute-force on login system (highly strict and complicated):

1. Delay of X seconds in checking each login attempt, x between 2-4 seconds.
2. Disallow for 30-50 mins after 7 failures for each IP
3. Disallow for 30-50 mins after 7 failures for each Account Login Attempt (IP is varying, username is same)
4. Measure Keystrokes on the Login page using Javascript.
5. Measure time spent by user on server.
6. password length atleast 6, enforce use of atleast 1 symbol, 1 digit and 1 alphabet.

Depending on the purpose of the brute-forcer, if he/she wants to disrupt your services, and has unlimited resources, there is no stopping him. but if he is trying to login system, he will fail (hopefully).

EDIT-->

3) not complex, its exactly same as logging IP address 2) with #3 in effect, clearly the account being targetted is not the same account, so 100,000 bots cannot brute-force for 1 single account 700,000 times in one hour (but only 7 times)... 5) this is not "delaying user of client side" but "measure the time client spend filling the username/password"

IF #2 and #3 are bypassed, the purpose of attack is DOS/DDOS

Maintain average rate of login failure(per hour)(graph like) in your system, with a DDOS attack, failure will go very high (compared to average failure rate) -> You need to take actions manually.

PS: of course it will be complex.

Answer 4

The question is a bit underspecified. I'll assume that the login is verified on a server, and happens from a client application written in a language that has a high performance crypto implementation available.

Then before each login require a proof of work. The classic implementation is that the user must find a value proof so that Hash(challenge&proof) starts with a certain amount of 0 bits. Where challenge&proof is a combination of a server generated challenge and a client generated proof. The client must guess a proof that fulfills the condition. I'm not sure how to combine challenge and proof, if simple concatenation is enough, or if a HMAC based scheme should be used.

The choice of hash function is important, since the attacker might be running different hardware from the legitimate user. I'd look into an scrypt based scheme to avoid efficient GPU and FPGA based attacks.

In an attack situation you can simply increase the difficulty(i.e. the number of required 0 bits), so a login requires more work.

Answer 5

If you require a seven character password, the number of possible alphanumeric mixed case passwords is huge. It would take about 111670 years, at one attempt a second to be sure of getting it.

Make sure that the delay is on a per-user attempting to log in basis, not anyone trying to log it, as that would be very slow system.

This would make a brute force attack unfeasible.

Answer 6

I don't think the choice of algorithm will fully prevent brute force login attempts. Though there are ways to make this harder, depending on the actual scenario.

You can introduce waits and lock outs of various types that will prolong the time it would take to brute force a login attempt. Once a malicious user has gotten hold of the password file this will not prevent this user from using one of the so called rainbow tables with precalculated passwords to get hold of working passwords for all the accounts.

Though there are several ways to prevent this from happening. One way is to introduce a so called salt in the cryptografic calculations. This is simply a value that is specific to each user which prevents the use of precalculated passwords. This means that you have to brute force each and every account as you cannot use the precalculated rainbow tables. This often takes to long time and the malicious user tries another site instead.

Another trick that Unix uses is to use a very time inefficient algorithm that in itself takes very long time to calculate. This also makes it impossible to precalculate passwords.

I have read a very good article on this last trick which both makes it hard to use brute force and practically impossible with today's hardware to precalculate passwords or brute force. Alas Google could not find it for me when a tried to find it.

Found one, but not the one: http://codahale.com/how-to-safely-store-a-password/

Answer 7

Instead of storing the IPs from which failed attempts are made, how about storing the last N IPs from which successful logins have been made? You may already be doing this for "account activity" type reports.

Treat these IPs as a sort of "whitelist" for lockouts. E.g. if 10.1.1.100 and 10.1.2.200 are IPs that have had valid logins for luser, then this is the whitelist. If 172.16.1.50 makes three failed attempts, set the lockout flag for luser to the current timestamp. For the next 15 minutes, any login attempt that does not come from the whitelist will be met with an "Invalid username/password combination" message. (In other words, do not let the attacker know that he has been detected and the user account is locked out; let him continue wasting his resources and don't allow him to optimize the attack.)

For the scenario where the attacker manages to share an IP with the victim, remove an IP address from the whitelist after three failed attempts. (Or increase the threshold if you want to give legit users more chances to fat-finger the password.) This seems like it would be more of a targeted attack against a particular user, which is harder to defend against than a "brute force any account" type of attack (it sounds like the latter is what you're trying to defend against). In this case the legit user will have to reset his password to regain access to the system -- inconvenient but non-fatal.

For the scenario where a user (esp. admin on vacation) is away from his normal IP address, allow the password reset functionality to insert a new entry into the whitelist. A legit user will only try a handful of times before giving up and doing the password reset dance.

---

An alternative to the whitelist/lockout strategy would be to add a secondary challenge to the login process. After three failed login attempts, set a flag on the user's account. If the flag is set, delay 10 seconds, then serve a second screen that requests answers to a pair of "security questions" before checking the username/password combination. When the second screen is submitted, delay for 10 seconds then check the username, password, and security questions and report success/fail in a generic way (i.e. don't provide the attacker with which piece of data mismatched). This will be only slightly inconvenient for the legit user, but slows the attacker down to 3 passwords per minute and makes it so that each password guess has to be combined with a correct security question. Except for a targeted attack (where the attacker may know the answer to "what was the name of your first pet?"), this would require multiple security question guesses per password guess. Of course you'll choose those two questions from a dozen answers that the user has already given during registration.

Make sure to include a cryptorandom token in both the initial and secondary page, and validate these on each submission so that the attacker can't bypass the delays.

At any rate, legit users are going to do the password reset dance after a handful of failed logins anyway.

---

In either case, it would also be useful to send an alert to admins if a certain threshold of lockouts (or secondary screen triggers) is detected so that you can take more active countermeasures in the face of a brute force attack across multiple accounts.

Answer 8

There is no one solution. You can try to slow down the password encryption alghoritm, if you have control over it (this is the solution of OpenBsd MD5). But ypou are going only to slow down the brute force attack.