35

Why doesn't software automatically detect password-cracking attacks, and thwart them?

Long version:

Suppose that someone tries a brute-force password-cracking attack on some program XYZ that requires password authentication.

My understanding is that such an attack would consist of iterating over the set of "all possible passwords", supplying each in turn to XYZ, until one of them works. For this strategy to have any probability of success, the attacker would have to be able to supply to XYZ very many candidate passwords per second. Therefore, it would be trivial to program XYZ to detect this pattern (that is, distinguish it from the case where a legitimate user mistypes the correct password a few times), and automatically escalate the authentication requirement for the next, say, 10 minutes.

The idea is that the owner of XYZ would be allowed to set two "passwords": a "level 1 password" (AKA "the password") that is relatively easy to remember and easy to type, but also relatively easy to crack by brute force, and a "level 2 password" (AKA "the passphrase") that could be extremely long, impossible to crack by brute force, but also very inconvenient for (legitimate) daily use.

Someone who knew the convenient-but-weak password would hardly ever need to use the uncrackable-but-inconvenient passphrase.

I'm sure there's some huge flaw in this scheme, otherwise passwords would not the headache to legitimate users that it is. What is the explanation?

Peter Mortensen
  • 877
  • 5
  • 10
kjo
  • 1,043
  • 2
  • 9
  • 15
  • 1
    There is no password which is "impossible to crack by brute force". It possibly will take very very long but one the day the password will be cracked. BTW your set of "all possible passwords" is (theoretically) infinitely. – idmean Jun 26 '14 at 16:25
  • 1
    http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ Passphrases are still vulnerable to dictionary attacks, so you can't get too lazy with them. – Andrew Hoffman Jun 26 '14 at 17:59
  • 2
    The question is a little too generic, so you have several kind of answers. Are you referring to internet servers, lan servers, or local software? – LatinSuD Jun 26 '14 at 17:59
  • 1
    Possible duplicate of this [question](http://security.stackexchange.com/questions/47103/cant-brute-force-password-cracking-somehow-be-throttled). – Mario Jun 26 '14 at 19:12
  • @wumm There's nothing wrong with iterating over an infinite set :) Since no password itself has an infinite number of characters, you will iterate to it eventually – Cruncher Jun 27 '14 at 15:38
  • @wumm: do you realize how utterly unreadable posts become when they attempt to anticipate and cover for quibbles like yours? – kjo Jun 28 '14 at 01:01
  • No I didn't realized that writing "nearly impossible" and "trying every combination" would be more unreadable. I'm sorry for you that you can't understand a well meant note. – idmean Jun 28 '14 at 07:04
  • 1
    Along with everything else, keep in mind that if a baddie has a bot network they can make the attempt through multiple bots, so that no single IP address racks up too many failed attempts. – Hot Licks Jun 29 '14 at 11:58

5 Answers5

58

Reasonably often, they do. Any reasonable system will lock you out if you make too many online attacks (or legitimate incorrect attempts) to access the account.

The problem comes with offline attacks. The server (or whatever you are authenticating too) has to have something to compare the password to. This is typically either an encrypted value that can be decrypted with the password or a hash. If this value is compromised, such as when an attacker gains access to the database of users, they can then try to run the hash or decryption on their own computer and bypass all the counts of how many times things have been tried. They can also try guessing orders of magnitude faster since they are working locally and don't have to wait for a network.

With an offline attack, it is possible to try thousands if not millions of attacks a second and it suddenly becomes trivial to attack simple passwords within minutes, if not seconds. There is no way to prevent the attack since we have no control over the system being used to check the password. This is why it is important to change your password after a DB compromise is discovered.

AJ Henderson
  • 41,816
  • 5
  • 63
  • 110
  • 3
    Well.... not "mostly". Reasonable systems, sure - but that's not "most"... ;-) – AviD Jun 26 '14 at 14:07
  • @AviD - fair point, is "Reasonably often" more agreeable with reality? – AJ Henderson Jun 26 '14 at 14:09
  • This requires that the cracker has to know when a candidate password is the correct one, *without* supplying it to XYZ. The only way I can come up with is that upon finding the right "key" (whatever it is) some encrypted file is decodable into something "human readable"/"recognizable" (e.g. dictionary words, personal names, &c.). If so, the attack would be thwarted if the "decoded" file contains only strings that are not more "recognizable" than are those in the encoded version. Of course, "random-looking" passwords are not practical. I just want to make sure I fully understand your answer. – kjo Jun 26 '14 at 14:34
  • 3
    @kjo - the decoded value has to be something that the application can recognize as valid too if it is all that it has to go on. If it isn't recognizable, then the login process won't know right from wrong either. The attacker can use the same approach. – AJ Henderson Jun 26 '14 at 14:46
  • @kjo: Well, if you want to securely store perfectly random noise that you never use for anything ever, that might be a feasible approach. When the attacker provides the wrong password, they get the wrong noise, and they have no idea. It's unbreakable - but breaking it is worthless. You can't even use it to secure encrypted data (which looks random) or noise you actually used or plan to use for something (say, as a one-time-pad), because then the attacker has a way to distinguish wrong from right. – user2357112 Jun 26 '14 at 18:59
  • 1
    @kjo Have a look at [this old cryptogram article](https://www.schneier.com/crypto-gram-9812.html#plaintext) about how brute-force attacks recognize success. – blahdiblah Jun 26 '14 at 21:54
  • 1
    @kjo All the attacker has to do is replicate what the application server does to determine if a candidate password is valid; this process obviously must be possible and not depend on things like the output being "recognizable". Typically the steps are 1) build candidate password 2) append the appropriate salt(s) 3) hash the resulting string 4) check the hash output against the DB 5) repeat until it matches. – Aaron Dufour Jun 27 '14 at 06:44
  • @AaronDufour: thanks that answers the question in my comment. I suppose that one way to thwart this form of attack would be for the application to perform an operation that the attacker cannot replicate on a different machine (e.g. the application may rely on a machine-specific key baked into the hardware). – kjo Jun 28 '14 at 00:58
  • 1
    @kjo that can still be emulated unless the key is protected. This is the idea behind an hsm, but such things aren't cheap or easy to work with. – AJ Henderson Jun 28 '14 at 04:27
14

For "online attacks", they do, to various extents and with varying success. Usually, it's merely an annoyance to the legitimate user and not a big deterrent for criminals.
For offline attacks it is impossible. If someone has your password database, you can't prevent them from doing something with it (though you can delay them somewhat).

Cell phones operate in the exact manner that you describe. After entering your PIN incorectly beyond some threshold (e.g. 3 attempts), you need the PUK to unblock the device. If that ever happens to me, I'll be greatly pissed, since I threw away the piece of paper where that 10-digit number is noted.

My AVM router will lock you out for 5 seconds, doubling the amount of time with every failed login. Thus, after 10 failed attempts you have a 42 minute wait before you can retry.

Such a scheme is, however, only moderately intelligent. While it is unlikely that you will have a typing error 10 times in a row, it is perfectly possible that you can't remember which of the 10 passwords (passwords that you use rarely in a variety of places, or among passwords that you have changed over time) is the correct one. Also, it allows for a denial of service attack with comparatively little work.
Of course, the attacker, too, has to wait between login attempts, but he only waits 21 minutes where you will have to wait 42 minutes (or 6 hours while you wait 12). Also, if someone is just being malicious, waiting doesn't hurt, you can always set an alarm clock to 6 hours, and do another false login in the evening. For the legitimate user, it will be a complete day of waiting, if this works out (and more importantly, waiting does hurt if you actually need to do something).
Other systems that I've seen with some websites are even less intelligent. In one case, a few years back, I've been forced to change my password to unlock my account because someone did a couple of false logins. Which is, of course, total nonsense since the password had demonstrably not been compromised (as these login attempts were unsuccessful). That "security" measure was only a very major annoyance for the customer, with no benefit.

In the implementors' defence, it is not at all easy (if possible) to come up with something that works much better.

Damon
  • 5,001
  • 1
  • 19
  • 26
10

There is one other scenario that would be difficult to detect.

First lets look at scenarios that are easy to defend against;

Easy: Defence against brute force attack on a single user.

Brute force attacks are also easy to defend against, if a single user is the target of the attack. We can just lock that user's account. This may annoy the user, but it allows us to prevent the system from being compromised.

  • login to UserJoe
  • login to UserJoe
  • login to UserJoe
  • login to UserJoe
  • login to UserJoe
  • Lock UserJoe's account

Easy: Defence against brute force attack from single IP address

Brute force attacks that are easy to detect and defend against, if all of the requests come from the same IP address.

We can just bar that IP address from making any more requests.

  • SomeIPAddress1 attempting to login
  • SomeIPAddress1 attempting to login
  • SomeIPAddress1 attempting to login
  • SomeIPAddress1 attempting to login
  • Prevent SomeIPAddress1 from attempting future logins

Impossible (?): Defence against a botnet brute-forcing new user on every attempt.

Suppose that someone using a botnet is trying to brute force your system. They have will have different IP addresses so you can't filter logins by IP address.

Next suppose that they try to login to a different user every attempt.

So the requests could look like this:

  • SomeIPAddress1 attempting to login to UserJoe
  • SomeIPAddress2 attempting to login to UserAnne
  • SomeIPAddress3 attempting to login to UserMarc
  • SomeIPAddress4 attempting to login to UserHanah
  • ...

I can't think of any way to differentiate legitimate logins from fake logins.

TildalWave
  • 10,801
  • 11
  • 45
  • 84
sixtyfootersdude
  • 530
  • 3
  • 11
  • For the botnet situation, isn't it possible to change the login page/handler just enough so that existing bots cannot authenticate to it without receiving new code from the "master", or, better yet, to require a captcha? – nanofarad Jun 26 '14 at 19:33
  • @hexafraction I think that any changes that you can do to the login could also be made to the bots. This may buy you some time but it isn't really a reliable security mechanism. Good point on the captcha. – sixtyfootersdude Jun 26 '14 at 20:23
  • 3
    Even captcha is not the barrier it might seem to be. Put up some desirable resource on the internet, and put it behind a captcha. Only, instead of generating a new captcha, on each page load, just grab a captcha challenge from the site you want to crack. When your own human visitor gives you the answer, use it on the original site. The resources could be game ROMs, MP3 audio files, pornography, or any other downloadable content that people desire. One could even, with a botnet of compromised machines, do a captcha once an hour randomly on the desktop. Captcha is not the end-all answer. – ErikE Jun 27 '14 at 04:58
  • I don't like the captcha solution. Maybe just add some delay to the account validation. Increase the delay with the number of failed logins. Also check your user accounts for very simple passwords. Lockout those accounts and send a password change mail. – PiTheNumber Jun 27 '14 at 07:19
  • In the case of the botnet, assuming you've got something like fail2ban running and each bot only gets two tries before it's locked out for an hour, you're still putting up a decent defense... – Shadur Jun 27 '14 at 10:03
  • @Shadur - That that is probably two tries **per IP address** per hour, which could still be a lot of tries. – sixtyfootersdude Jun 27 '14 at 15:09
  • But still about an order of magnitude less tries than without fail2ban. Possibly enough to make the difference. – Shadur Jun 27 '14 at 15:13
  • Note that if you get many failing login attempts, even from many variable IP addresses, attempts that do not end up being valid, you can detect such and block all logins for a while. Depending on the type of websites you have that could be more secure than leaving the door open... – Alexis Wilke Jan 13 '16 at 07:42
2

It's always going to be a balancing act of how much time to make someone wait after an incorrect login attempt. It's not unreasonable to keep increasing the wait time after each attempt (and eventually lock out further attempts until some sort of reset), but this needs to be tied to the IP address the attempt is coming in on, so that the legitimate user doesn't get locked out, too (victimized because someone is trying to break into their account). However, a distributed attack (from many IP addresses) can load down the system to the point that it just becomes a plain DDoS attack.

If someone is determined to try a whole bunch of passwords (not necessarily every possible one, just the most common/likely ones) and has a herd of zombified machines to do it, either they'll eventually succeed, or bring the system to its knees. Don't forget that enforcing a wait time (turning away login requests) or denying an IP address also uses up resources. And if you have so many passwords that you can't remember which one to use, you've got a problem with your methodology if you have to go through all of them!

A "security question" challenge (basically, an alternate password) after so many failed attempts is possible, as is mailing a one-use password (reset) to a registered email address (whether automatically or "forgot password" request), as is a lockout on this IP address for a given time or until an administrator is asked to unlock it. I've seen all these methods used.

If the attacker has inside information, namely, the hashed or encrypted password file, they can do most of their work offline and just log in once (after they figure out the password to use). Passwords should always be stored as hashes (one-way encryptions), and never in plain text or even in a reversible encrypted form. Hashes are difficult (but not impossible) to recover the plain text password from, especially if they're salted (so that the hash is not the same for two different users who happened to choose "secret" for their password).

Phil Perry
  • 91
  • 1
0

Because customer do not pay for security.

You need to create a database table. Collect IP addresses from failed logins. Cleanup this table regularly. Create another table with blocked IP addresses and keep it cleaned up too. You see it takes some effort, and customers don't like to pay extra just for security.

As a developer you should use frameworks which will take care of those problems. Also you might want to have a look at fail2ban.

Peter Mortensen
  • 877
  • 5
  • 10
PiTheNumber
  • 5,394
  • 4
  • 19
  • 36
  • I still don't think there is any defence against the scenario that I describe in my answer: http://security.stackexchange.com/a/61936/874 – sixtyfootersdude Jun 26 '14 at 19:14