Introduction

Since the xkcd note on password strength, there has been a lot of attention for password entropy.

However, this raised the question: what if you used a strong scheme, but happened to get a weak password?

I can think of two main problems:

1. You choose a password via one strong scheme, but it is also possible to get this password via an existing used weaker scheme
2. You choose a password via one strong scheme, but it is also possible to get this password via a not yet used weaker scheme

Example 1

You pick a single number uniformly random from anywhere between 0 and 2^n for a large n. Ignoring practical inconveniences, there is a chance that you draw 0. Now you are stuck with a password that could be generated via so many weak schemes that you would really not be safe if you use it.

Example 2

You compile a nice large set of words, and draw four of them. You draw: 'correcthorsebatterystaple'. You are very satisfied as you are not aware of any weak scheme that would produce this. However, the next day some guy uses it in a comic, and it becomes immediately part of the scheme 'use a popular quote as your password' which is not nearly as strong as you would like.

Suppose you have to pick a pin code for your bank. It is only four digits, but an attacker has limited tries available. Uniformly picking one of the codes gives an attacker who knows your 'scheme' least chance to crack the code in time. However, you know that some lazy people will choose things like 0000 1111 1234, and that attackers are more likely to try those. So your random draw ends in 0000 (not impossible), now what?

Question

I imagine that part of this problem can be prevented, and hopefully the other part can at least be monitored, but I don't know how one would approach this in practice, so therefore I ask:

How to practically deal with the fact that your properly generated password may actually be or become weak?

• The point of a scheme is to produce a password that can pass the defined criteria. Schemes are not the point, the product of the scheme is the point. Oct 29, 2014 at 16:18
• @schroeder I am not sure whether you agree with me, but that is indeed a point I am trying to make. The examples may be refined a bit, but what I am trying to state is: You can use a very strong scheme, but in the end you have a password. The attacker assume you used any scheme, so if you end up with a password that can be produced via a weak scheme, I believe you have a problem. But now I wonder how to deal with that. Oct 29, 2014 at 16:49
• I'm not sure that your assumption about attackers is true. Attackers assume you have a password, I'm not sure that they focus on your 'scheme' to create it. If they can derive your scheme, then it doesn't matter what the product is, strong or not, they will enumerate the passwords from your scheme. Oct 29, 2014 at 17:01
• If it is weak (example 1), regenerate a new password. If it becomes weak (example 2), change the password. Oct 30, 2014 at 5:42

Well, in the example you gave, that is like me setting my password manager to generate a random password of length 8 with no restrictions to the alphabet used, and it producing 'password' as a result.

In such a case, I would laugh a very hardy laugh, take a screenshot, then click the button to regenerate a different 8 characters.

But the fact that this may happen to 1 person in the history of the universe shouldn't be enough to cause you concern. When dealing with true randomness perceived/abstracted randomness that is beyond your control, there's nothing you can do about it.

• I suppose this is the only practical approach. And that this is most relevant in cases where you work with a very limited range of allowed passwords. Have included an additional example of a more likely way for this problem to occur. Oct 30, 2014 at 9:07

You don't get a weak password out of a strong scheme, because there is no such thing as password strength. Sometimes we say "this password is weak", but what we really mean (that is, if the "we" that is speaking knows what he is talking about) is that "this password generation method is weak".

The important point here is that password security, just like anything else in cryptography, is probabilistic in nature. For instance, when we generate a RSA key, we are just assuming that any attacker will not guess the private key right away through sheer luck. We can live with that assumption because we know that the probability of the attacker getting that lucky is sufficiently small to be neglected. The same applies to passwords: if the generation process produces passwords with "40 bits of entropy", then this means that on average, attackers will need 239 tries to find the right one. However, they may get lucky, or unlucky, on any specific password; this is an average.

Probabilities rule our whole lives. Every single decision we take is in fact probabilistic; we accept to, say, take a bus ride because we balance the convenience of taking the bus with the involved risks, risks being a combination of the consequences of an unfortunate event and the probability that such an event occurs. Namely, we take the bus because we rely on the bus not being struck by a falling asteroid, and also because sitting close to a smelly unhygienic fellow traveller is both non-lethal and still not frequent enough to warrant travelling on foot instead.

Passwords are no exception to this rule. We use passwords for authentication because we estimate that the involved risks are low enough. A sub-theme is that attackers are also humans who take probability-dependent decisions; an attacker will not try to guess the password if the password generation method is such that his chances of success are very low. Attackers who run PC farms must think in terms of average; namely, they must think in terms of costs and bills, which are good examples of everyday averages.

Another way to state it is that the probability that you draw "correcthorsebatterystaple" (2-44 in the conditions assumed in the comic) is equal to the probability of the attacker guessing your password in one try if you got any other of the 244 possibilities. If you deem that the latter probability is low enough to be tolerated, then so must be the former.

Thus, worrying specially about the occasional "weak" password is not rational -- this is only a subcase of the average password security. It is, in fact, the same problem. You can just consider that by generating your own password, you are "just" performing yourself the first attacker's try. If you consider it that way, then you see that you are not actually giving any advantage to the attacker regardless of the password you obtained.

(It may be argued that if you apply defensive procedures, e.g. generating a new password if you find that the one you got is "weak", then you are actually shrinking your password space, and that reduces security, not increases it.)

• The last paragraph is exactly where I disagree. Because if you reduce the password space you reduce entropy, but I can simply not believe that if you disallow knownly weak passwords, you actually decrease security. So, it may not be very likely to happen, but shouldn't you prevent picking a password which could come from a weaker scheme? Oct 29, 2014 at 16:44
• Just to be clear, I like this answer but feel like its not complete yet. To continue on your analogy: The chance that a bus is hit by an asteroid is small in general. But if you happen to obtain the additional information that an asteroid is coming and the bus will cross one of the three likely landing spots, you may still not choose to take this specific bus ride. Oct 29, 2014 at 16:55
• Password security is often counterintuitive. But stopping to think in terms of "password strength", instead of "password generation process strength", may help. For instance, every single password value may be generated with a "weak scheme" (for password P, the scheme that always produces P is weak -- since it always produces the same password -- and yet produces P). The key to understanding is that "knownly weak passwords" don't really exist (though we may want to believe it, and usual terminology tends to support their existence). Oct 29, 2014 at 17:18
• Analogies usually break down when looked at to closely. I don't claim that the bus is a metaphor for passwords; it is only an illustration that we all use probabilistic decisions in all aspects of our lives, so passwords should be no exception. Oct 29, 2014 at 17:21
• It is true that anything can be created by a weak scheme, but I still believe that if you know that some weak schemes are popular, you should take that into account. Have added an additional example to make the situation less extremely hypothethical. Oct 30, 2014 at 9:10

Your first example does not seem strong to me. Any password generator that can generate a password of length 1, is not strong, so your statement, `You choose a password via one strong scheme...` seems like it does not apply.

As for your second example, the chances of 4 random words you have chosen becoming popular are so astronomical that I'm not sure it's worth worrying about.

In summary - don't use the first scheme and I wouldn't worry about the second example.

• "Any password generator that can generate a password of length 1, is not strong". It is fairly trivial to modify the example in a way that it will generate a weak password of longer length, but I will just ask to focus on the problem, not the example itself. So: What if you have a strong scheme that can get you a weak password? Oct 29, 2014 at 16:41

Any password can be broken by 'bad luck'. The point of generating a strong password is to minimize the probability to be struck by bad luck.

In your first example, the probability to get 0 is 1/(2^n), you just have to pick a n big enough to be probabilistically safe, which is n=128 by today standards.

• But what if you pick n=128, and you would happen to get 0, or 1234 for that matter. Surely you don't deny that it would be problematic to use this password as you don't know which scheme an attacker will assume? Oct 29, 2014 at 16:46

xkcd articles are fun and often very insightful, but sometimes they miss the point.

Security is not improved by using stronger passwords, it is improved by using stronger policies. Social engineering is most likely how you will get hacked.

Ordinary desktop computers can test over a hundred million passwords per second using password cracking tools that run on a general purpose CPU and billions of passwords per second using GPU-based password cracking tools.

A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST. 2^30 is only one billion permutations and would take an average of 16 minutes to crack. -Wikipedia

No login system should allow 1000 guesses/sec, or else you're swimming up DoS creek. It probably shouldn't even allow 10 guesses/sec/account. Without protection against this, even "very strong" passwords can be brute forced.

Also consider the situation where an attacker obtains a password hash or the database from your server; they can now run their cracking tools offline without hitting your server constantly and without triggering alarms that notify an admin.

Even with constant training and good policies, realize that there are always risks when dealing with resources that are secured by passwords and accessed by remote users, no matter how secure the system is. Mitigate these risks by categorizing them (laptop users, public wifi users, users who do a lot of file downloading) and make sure that if their accounts are compromised they cannot be used to bring down the entire system or access all of the confidential information within. Accounts will get compromised if someone is determined enough, and permissions are your friend.

The number one cause of security breach is due to non-malicious employee error. Lost or stolen laptops account for 49% of security breaches. One successful phish or keylogger can snatch any password of any strength.

Possible Solutions

Sometimes the solution to these problems - password security - can actually expose the system to further tampering (DoS) when done incorrectly. It's not an easy problem because if it was, we wouldn't be discussing this.

At the network level, detect and block or throttle bulk login requests/patterns. This could be easy or hard depending on available software/hardware, but I imagine it is available even with consumer-grade firewalls.

At the application level, add a short ~2 second delay when validating a password. It should slow down brute force attacks enough to make them ineffective without denying real users. After each failed attempt, increase the delay by a few seconds. Reset the delay to normal once that user makes a successful login. It's important to note this technique does not stop accepting login attempts, it simply adds a delay while processing them or before sending the response back to the client.

You could additionally allow the user to gain access through a white-listed IP address (might be troublesome - make sure it's static), VPN connection, or a text message code (two-factor authentication). Enforce encrypted VPN connections and HTTPS to protect against man-in-the-middle eavesdropping.

Don't lock out accounts after failed login attempts, because that allows malicious users to purposely lock out other people. However, if the users have a way to access the system from a LAN or VPN, you could probably use account lock outs without much trouble. Windows Server environments are typical of this.

There's no point in black-listing IP addresses; they can be spoofed and/or the attack could be distributed across several hundred machines with various IP addresses, some of which may be "trusted" proxies or ISP endpoints that you end up black-listing in the process, blocking real users.

Longer passwords are a good deterrent, but equally important is a decent username. If your username is "admin", which most WordPress sites are guilty of not changing, it will be much easier to crack the account. In fact, most WordPress attackers rely on the default "admin" user and won't go further without that being present.

Another option would be to outsource your login and authentication to a third-party - an OAuth2 provider such as Google or Facebook works well.

Source: Dealt with numerous data breaches, none of which were due to password strength. Saved a company from full meltdown when a PC on the LAN got infected with CryptoLocker and managed to encrypt 40,000 network files in under a few minutes before I caught it. Virus arrived through email and made it passed all security measures - a corporate Sonicwall firewall, MX Logic spam filter, MS Exchange spam filter, Symantec Endpoint Protection and Symantec Mail Security for Microsoft Exchange. No backups? You are now out of business. We had our ducks in a row. The only thing that could have prevented this was the user.

References

• I don't think that this addresses the question the OP made. Oct 31, 2014 at 17:02
• It's an alternative answer, but it definitely addresses the question, which was "How to practically deal with the fact that your properly generated password may actually be or become weak?" Practically all passwords are weak, live with it and optimize/mitigate elsewhere. Just because John the Ripper can't crack a 4 word password today doesn't mean it can't be engineered to crack those tomorrow. A 25-GPU array can perform 350 billion guesses per second and you know what? Tomorrow's GPUs will do twice that. Will tomorrow's passwords be twice as long to compensate? Oct 31, 2014 at 17:46
• As a side note, I try not to give redundant answers that I know someone else has or will provide. I think my answer adds a lot of value to this question. Oct 31, 2014 at 17:51
• I think your answer is useful, if the question was "How can I mitigate users picking bad passwords/losing their password". However, the OP is infact the user picking the password and not the developer mitigating the issue. Oct 31, 2014 at 17:55
• xkcd mentions 1000 guesses/sec as a plausible attack on a remote web service. I would hope any user reading this experiences a strange twitch in the eye brow. Why design or use a web service that is open to being massively flooded or brute forced? It's like using a public Wifi at Starbucks - maybe nobody will snoop your traffic on Tuesdays, but maybe that's because Joe bad guy doesn't get coffee on Tuesday. Regardless of how the day pans out, you're constantly at high risk. Users need to know this. Nobody has raised the issue. Oct 31, 2014 at 21:26