2

In this question, discussing whether http://howsecureismypassword.net is safe to use, @ThomasPornin commented

"Mathematically, the strength of a password depends on the process which generated the password, and cannot be measured on the password alone"

Is this true? If so, can someone please explain why?


[Update] After seeing @Pascal's answer, the penny dropped.

I had interpreted it as "for any given password, how you arrived at it makes a difference", rather than "different methods have different results, some more secure than others".

3 Answers3

4

A password strength checker cannot actually know how random your password is, what a strength checker does is try a combination of preprogrammed password generation/guessing methods and try to evaluate the strength of a given password based on those.

For example, if you enter the password:

correct horse battery staple

The site gives you 15 octillion years, which is misleading because I generated that password non-randomly by reading a certain comic.

Or a password like:

passwordpasswordpasswordpassword

claims to be 2 octillion years, despite the obviously non-random password.

The point is, if the password generation method you use is not preprogrammed to the strength calculator, then a strength checker can give an impression that a password is stronger than it actually is.

Better password checkers like zxcvbn have more preprogrammed patterns to check against, but it's still limited by the same fundamental issue.

Lie Ryan
  • 31,089
  • 6
  • 68
  • 93
3

This is mostly right.

Password strength is measured by how large the search space is for the given password (assuming every password in the search space is equally likely - more on that later on). The search space for a one-digit password is very small {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and a brute-force attack (trying out every combination) by a human can find your password in about five seconds. A fast or purpose-built computer can do it in under a nanosecond.

A password consisting only of digits that is 100 digits long provides a much larger search space. There are 10^100 possible combinations, so a brute-force attack will, on average, need to try half of these combinations to find your password. This will take a very, very long time, even if you have a computer that can try a million combinations every second.

However, if you choose your 100-digit number non-randomly, e.g. if you prefer a 100-digit combination that consists of alternating 1's and 0's because that's easier to remember, the large search space won't protect you. An attacker who takes human behavior into account will program his computer to try combinations such as this one first and therefore find your password much much sooner than if you'd chosen your 100 digits randomly.

So the process by which you arrive at your password is relevant. If you don't use a truly random process, chances are that your password will be weak and easily cracked.

If you give me a password to look at, sometimes I can determine that it's a bad password at once. If your password is "123456", or "password", or any other of the most common passwords people use these days, it's obviously a very bad password, and I can determine it by looking at the password alone, simply because I see that it's not random at all. But if you give me something like "15-L-s-04-02", it's harder for me to determine whether this is a strong password or not. If you have a daughter called "Liv Sarah" which was born on second of April 2015, the password is very weak if we're dealing with an attacker that knows and targets you specifically, even though the search space isn't that bad (digits, a special character, lowercase and uppercase characters, 12 characters long -> search space of size 2^73, or a password strength of 73 bits, which isn't very good, but still fairly decent).

So: bad passwords can be determined by simply looking at the passsword. It's much harder to determine whether a password is good by simply looking at it, because it's important to know whether it has some kind of meaning for you that another person might ultimately guess.

Still, we can usually determine whether a password is good or bad just by looking at it because we know most password habits of people, so even if I don't know your daughter's name or birthday, I still know that lots of people use names, initials and date components as parts of their passwords, so I'd program my computer to try a few thousand most common passwords first, then have it try combinations with date components or initials, then shuffle these components around in different combinations etc, and the "15-L-s-04-02" would still be found much, much earlier than if I'd just tried every possible combination of 12 characters.

Out of Band
  • 9,150
  • 1
  • 21
  • 30
1

The practical definition of the strength of a password is how long it takes for a password cracking tool to crack it, i.e. how many wrong guesses the cracker will make before finding the correct password.

There is no way to get a precise value from this definition, since it depends on the cracking tool. Different tools will try passwords in different order, possibly even randomized, and you can't know about all the cracking tools out there, let alone about the new tools and configurations that people will use on your password in the future.

for any given password, how you arrived at it makes a difference

There's a kernel of truth in that. If you publish a password, its strength becomes essentially 0 β€” crackers will just put it on their list. The strength of the password is what is kept secret from crackers. As long as you haven't published the password, you know what its precise strength is, the best you can do is get an approximation. And the only way to get such an approximation is in knowing the process by which you arrived at the password. If there is something in the password generation process that is secret, such that crackers don't know how you produced it, then your password is at least as strong as guessing that secret.

The best secret is a completely random input. How much uncertainty there is in a piece of information is called entropy, and random input has maximum entropy. If you generate a password randomly amongst a set of 2N possible choices, and you keep the choice secret, then your password has an entropy of N bits. That guarantees that the strength of the password is at least 2N: since a cracker has no information on your random choice, the best thing it can do is try them all, and on average it'll succeed after 2N-1 attempts. Anything in the password that isn't purely random increases the chance that the cracker will succeed earlier, because they can apply the same non-random selection you did, whereas they can't repeat a random selection and get the same outcome except by coincidence.

Given only the password itself, there is no way to know how much secrecy went into its generation, so there is no way to estimate its strength (other than β€œ0, since you just told me what it is”).

See also our many questions on the topic, including:

Gilles 'SO- stop being evil'
  • 50,912
  • 13
  • 120
  • 179