How to deal with password schemes that can produce weak passwords?

Question

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.

Additional example

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?

Answer 1

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 2³⁹ 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 2⁴⁴ 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.)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

• The definitive guide to form based website authentication
• 2007 Annual Study: U.S. Cost of a Data Breach (Vontu/Symantec PDF)
• Password Cracking (Wikipedia)
• xkcd 936: Password Strength Explained (Explain xkcd)
• Why Strong Passwords Don't Matter
• XKCD #936: Short complex password, or long dictionary passphrase?
• Do Strong Web Passwords Accomplish Anything? (Microsoft PDF)