What would be a good set of criteria to consider a password safe?

Question

Nowadays we see many websites with a "security meter" for the password.

I actually think this is a great feature since it gives the final user the sense of how insecure their password could be. I wish I had a dollar for each time I heard final users stating how secure their password "password" is.

The issue with those meters is that they can be really unreliable. Recently I just discovered one that just gives the security by how many characters you input. That means that if you use stuff like: 111111111 or 123456789 it considers it to be the ultimate secure password.

Lets define 3 levels of security. Bad,medium, good. What would be a good set of rules to consider a password in each group?

Clearly length, character diversity (including small case, large case, numbers) are important, but some of these passwords would still be vulnerable to dictionary attacks.

What would be a good set of tests for each level?

This can be up for discussion since the threat and risk depends on how important the information protected by the password is. A good password to login to, let's say "home cooking forum" is not as important as the bank one. For the sake of the answer let's consider the an average website like an online shop or youtube as the reference.

Answer 1

The concept you are looking for is called password entropy. Entropy is the measure of how many different combinations is possible, and is usually measured in bits. Entropy both depends on the length of your password (concatenate two passwords and you sum the entropy) and how you generate it.

If your password is a random string generated from the base64 charset, each character has 6 bits of entropy. If you randomly pick 5 words from a list of 4086 english words, each word has 12 bits of entropy, and there is a total entropy of 60 bits. Therefore, a 5 word password chosen as above is as secure as a 10 char base64 string (or a 15 char hexadecimal string), and somewhat easier to remember.

Some things to note: A base64 charset generally has uppercase and lowercase alphabetical, numerals, and 4 other characters. 5 non random words (such as a grammatically correct phrase), in typical english, has 2.62

I'll finish later.

Answer 2

Programmatically 'measuring' password security is really hard: What you want is a number that tells you how hard it is for an attacker to guess the password.

A good approximation usually is to look at the number of possible passwords that would result from using the same generation algorithm, operating under the assumption that the attacker knows the generation algorithm and that the password is picked randomly among all the possible outputs of this algorithm.

This is easy to get, if you define the algorithm yourself and give the user a fixed, generated password. You can then do a calculation along the lines of "10 characters randomly selected from a set of 62 characters" = 839299365868340224 possibilities ~ 59.5 bits of entropy.

Unfortunately a lot of sites let the user choose the password and then things get hairy. Now neither you nor the attacker knows the generation algorithm. The attacker has to settle for the next smartest thing: Try a couple of reasonable algorithms, and all generated passwords for each algorithm (skipping duplicates). Sensibly the attacker would start with common algorithms (such as "name of a family member") and/or ones that generate only a small number of possible passwords ("4-digit PIN").

Now to get a numeric grasp on the security of the resulting password you can't just look at the total number of possible passwords, but have to also take into account the order that an attacker would try them in. Something along the lines of a weighed average of the number of passwords per algorithm and probability of that algorithm being used.

There's a closely related concept called Kolmogorov complexity: It describes the information content of a string as the length of the shortest program (in some generic programming language) that can recreate the string. Example: "aaaaa" and "abcdefghijklmnopqrstuvwxyz" have approximately the same complexity of 3 if our language allows to say things like "5*a" and "a-z", while "oabuf" would have complexity 5.

A smart attacker would try passwords in order of increasing Kolmogorov complexity, so you would be home free if you could calculate that. Unfortunately you can't.

Overall the best approach to password security is to give useful advice to users on how to choose a good password, see this study. This paper recommends the pass phrase method: Take a sentence, and use the first letters of all the words. This gives good memorability and security. Another good method is the XKCD method, also known as correct horse battery staple (the comic also gives a good illustration of my remarks on multiple algorithms above).

Given that you can't reasonably compute password strength without knowing the algorithm, and you can't generally know the algorithm, I would suggest refraining from trying to do so. Having a non-functioning password strength meter will send the wrong signals to your users (for example, most password strength meters vastly underestimate the strength of XKCD passwords). Instead:

• Give advice on how to choose a good password
• Don't make it hard to use a good password (e.g. by having arbitrary limits on the length and character set; you're going to hash the password anyway, right?)
• Use cracklib on the server side to weed out catastrophically bad passwords.

Answer 3

The problem with only considering entropy is that it does not take into account the possibility of guessing based on contextual information (such as language, culture, the nearness of keyboard characters etc. etc.) only on systematic brute forcing.

The problem is similar to why people playing the lottery don't choose a string of consecutive numbers like 1,2,3,4,5,6 - they instinctively believe that this is a less likely combination to occur even though the randomness, or degree of entropy in the choice pool, is exactly the same for any randomly chosen sequence. In password choice this turns out to be a good intuition, but for the lottery it isn't because there is no contextual input into the choice of winning numbers drawn from the balls.

A random generator could come up with the password 'password' if asked to choose 8 characters from 1-9, a-z, and some punctuation. It's unlikely (well as likely as any other combination) but it could happen. If it did you'd claim that this was insecure because although a true brute force program chunking through all combinations would take a long time, a sensible password cracking program would find it almost instantly (well, if it were based on English language anyway!)

So passwords should be chosen based on a reasonably measure of entropy as well as other contextually sensitive information such as commonly thought of patterns etc.

So, length and larger character sets (to provide a large enough search space) and the lack of contextually relevant/meaningful patterns is the way to go.

The problem with online measuring systems and 'hackability-meters' is that they don't know the context of the use of the password e.g. if it's for a cooking site in the UK and you choose GBBOnadya2WIN! it may not be secure.