15
$\begingroup$

While using Keepass and using it to generate random passwords, I always have noticed the "quality" section but truthfully have never known what it actually means.

Quality

So my questions are;

  1. How much entropy is enough?
  2. How much is overkill?
  3. How does entropy actually apply to the length of time it may take for an attacker to guess a password?
  4. How is entropy calculated and how may my addition of a new character affect the number of bits?
  5. What is the theoretical max?

Thanks!

$\endgroup$
  • $\begingroup$ I don't know that particular program, but probably when it says $n$ bits of entropy it means that the password is chosen uniformly among $2^n$ possible strings. Thus if you have an alphabet of $k$ characters and choose uniformly a string of length $\ell$, you have $k^\ell$ possible strings, and thus $\log_2(k^\ell)$ bits of entropy. $\endgroup$ – fkraiem Jan 21 '17 at 12:35
12
$\begingroup$

How much entropy is enough?

For a password, something around truly 96-bits of entropy is enough. After all password usually go through some slow password hashing which increases the work load for attacks significantly. And even with a super-fast verification function 96-bit should be just out of reach of attackers.

How much is overkill?

Going above 500-bit is very likely to be overkill, even for an actually imperfect source of entropy. If your entropy is "true" (ie what is reported would actually be the entropy), then there's literally no point in going beyond 256-bit and maybe even 192-bit.

How does entropy actually apply to the length of time it may take for an attacker to guess a password?

Entropy denotes the uncertainity in a string1 and is measured logarithmically in bits. So if you increase the entropy by one, the string is twice as uncertain and thus can take twice as many values which means an attacker has to try twice the amount of passwords. Shortly put: Let $l$ be the actual entropy (in bits), then there are $2^l$ possible different values to be tried.

How is entropy calculated and how may my addition of a new character affect the number of bits?

What I strongly suspect this tool to be doing is to analyze the character set used in your password, looking for common words in a dictionary and then making its guess for the entropy (try this by comparing the entropy of potat with potato, the latter being reported at 12 bits and the former at 20). The upper bound for the entropy is $$\leq{|\Sigma|}^n$$ where $\Sigma$ is the alphabet / group of characters that the tool estimates could appear in your password and $n$ is the length of the password. For example if you use upper-case it's gonna include those as opposed to excluding them if you don't have an upper-case letter.
Note that what the tool reports is an estimate at best and the actual entropy can be significantly lower due to a bad RNG being used, an implementation flaw or you simply having bad luck and hitting a string that's more easily guessed / guessed sooner by an attacker.

What is the theoretical max?

Theoretically there's none. Practically it's limited by the size of your RAM probably (because the password has to fit in there).


1Actually the uncertainity in a random variable, but that's details here.

$\endgroup$
  • 2
    $\begingroup$ Also note that to calculate a password's entropy, what matters is how it was constructed and not what it is made of. 24 random letters have a different entropy compared to a 24 letter word. $\endgroup$ – Dreadlockyx Jan 21 '17 at 14:25
  • 2
    $\begingroup$ @Dreadlockyx This is a very important point! Empirical entropy requires an assumption on the sample space. (...which is rather arbitrary from a theoretical standpoint and may be completely off in practice.) $\endgroup$ – yyyyyyy Jan 21 '17 at 15:46
4
$\begingroup$

The first thing to say is you shouldn't automatically trust password strength meters without knowing their methodology and verifying whether it's a good one. Many are really terrible. Keepass' isn't obviously bad, but it shouldn't be taken as gospel either.

How much entropy is enough? How much is overkill?

It really depends on the security target dictated by the scenario and your risk tolerance. I feel comfortable using about 80 bits for website passwords managed by a password manager—good balance between usability when I have to type them in (12-14 characters) and security. For websites, a 45-character password with 265 bits of entropy (like your graphic) strikes me as overkill many times over. It's just going to be a pain to type it in when you need it.

The Diceware FAQ has some advice on choosing passphrase complexity that you might find helpful. It's not gospel but it's usefully concrete and emphasizes non-password factors you should consider before cranking the password strength up. When you read this keep in mind Diceware passphrases have 12.9 bits of entropy per word (I've annotated the strengths in the headings), and the scenario the author is thinking about is file/email encryption, not website logins:

5 words [64.5 bits]

You would be content to keep paper copies of the encrypted documents you are protecting in an ordinary desk or filing cabinet in an un-secured office.

6 words [77.4 bits]

You need or want strong security, but take no special precautions to protect your computer from unauthorized physical access, beyond locking the front door of your house or office.

7 words [90.3 bits]

  • Your computer is protected from unauthorized access at all times when not in your personal possession by being locked in a room or cabinet in a building where access is controlled 24 hours a day or that is protected by a high quality alarm service.
  • Routine cleaning and building maintenance people do not have physical access to your computer when you are not present.
  • You regularly use an up-to-date anti-virus program purchased off the floor at a computer store.
  • You have verified the signatures on your copy of PGP or your installed Hushmail 2 client.
  • You never run unverified downloaded software, e-mail attachments or unsolicited disks received through the mail on your computer.

8 words [103.2 bits]

  • You take all the steps listed under 7 words above, and:
  • Your computer is kept in a safe or vault at all times when it is not in sight of you or someone you trust.
  • Your computer was purchased off the floor at a randomly selected computer store.
  • All the software used on your computer was distributed with a strong, independently verified electronic signature that you checked, or was purchased off the floor in a randomly selected computer store
  • Your computer has never been repaired or upgraded by anyone you do not trust completely.
  • All disks and tapes used with your computer are either kept in a safe or physically destroyed.
  • You take precautions against audio and video surveillance when entering passphrases.
  • You change your PGP encryption key regularly (at least once a year).
  • You have taken precautions against TEMPEST attacks. See the chapter "Commonsense and Cryptography," in Internet Secrets, from IDG Books Worldwide, for a discussion of what this involves.

Whatever you think of the specific recommendations, this stresses that it makes no sense to have a super-strong passphrase if you haven't made an effort to shore up other avenues for an attacker targeting you.

How does entropy actually apply to the length of time it may take for an attacker to guess a password?

$n$ bits of entropy means that it takes an attacker $2^{n-1}$ guesses on average to find your password. The on average part is important—the actual runtime could be less or more.

So for example, if your attacker can make 2.2 billion ($2.2 \times 10^9$) guesses per second (the max SHA-1 speed from Troy Hunt's article on GPU password cracking):

  • If your password has 44 bits of entropy (like XKCD's famous "correct horse battery staple" comic), then $2^{43} \div 10^9 = 4000$ seconds on average, which is just over an hour. (But that's an average—it could take them as much as two hours.)
  • If your password has 64 bits of entropy (about the same as a 5-word Diceware passphrase), then $2^{63} \div 10^9 = 4.2 \times 10^9$ seconds, which is just under 133 years.

An attacker that dedicates more hardware can speed these attacks up linearly. A defender that uses strong password hashing can slow these down noticeably as well.

How is entropy calculated and how may my addition of a new character affect the number of bits?

If the passwords are chosen uniformly at random from a set of size $x$, then the passwords' entropy is $log_2(x)$ bits, no ifs and buts.

If they're not chosen uniformly at random (some are more likely than others, e.g. like human-chosen passwords), then you design a model that, given a password as input, estimates the average number $g$ of guesses optimal attackers would make before they tried that password. Then the password's entropy is $log_2(g) + 1$ bits. For example, if your estimate is that an attacker guesses $2^{43}$ other passwords before they try "correct horse battery staple", then the entropy is $log_2(2^{43}) + 1 = 44$ bits.

The obvious difficulty here is that to estimate the password's entropy you need to think like the attacker—there's a risk that the attacker can outsmart you and find ways to efficiently attack passwords that your model estimates are stronger than they really are. This is why:

  • You shouldn't trust password strength meters too much. Even the best meters are estimating password strength, and the estimates will often be wrong.
  • Choosing passwords uniformly at random is a good strategy—there's no "arms race" between the attacker and the defender, you can be certain that the strength of your passwords follows from the size of the set you draw them from.

What is the theoretical max?

There isn't one. The practical maximum is how much you can reliably remember and conveniently input into your devices.

$\endgroup$
0
$\begingroup$

The 'quality' test can be flawed intentionally. If the pasword generator and the quality test are on the same website or are controlled by the same institution, you cannot trust the quality test result.

$\endgroup$
  • $\begingroup$ This is probably true but this doesn't really answer the question. Please try and supply a few answers so you can comment. I don't directly see why an institution would want to fool their own users either, that makes more sense for separate institutions, if you ask me. $\endgroup$ – Maarten Bodewes Jan 22 '17 at 2:46
0
$\begingroup$

Much of the math in the prior answers here is quite correct. And it is very correct, very learned, analysis addressing the wrong problem.

Consider that the sole point of a password is to be unguessable (ie, not findable) by an attacker. A password consisting of a single letter is pretty poor since it will fall in, on average, 13 guesses (we assume a 26 character alphabet here, sorry non-English speakers). Regardless of how randomly (ie, high entropy) that single letter was chosen. So, IF we assume brute force is an attacker's best choice, a long password, chosen entirely randomly, is a good choice. For the reasons covered in the prior answers.

But no human (Hans the clever horse might have been able to do better) can remember random stuff very well, and long random stuff still less well. This leads to writing the long random password down, and to the sort of attack one saw in War Games. Don't use Post-it notes stuck in clever places either.

Ok, so choose 10 (or 50 or whatever) names from the great cryptographers list, and concatenate them (alternating one backwards, then one forwards, and so on, if you like) to produce a password. Not in any dictionary anywhere, really long, probably not maximally random but the entropy estimate algorithms would probably rate it highly, ..., so a pretty good password, right? Actually, if your attacker knows you're a cryptography fan, there's no need to assume concatenated names of famous knitters, which makes a guessing attack easier than it might have been. Don't help your attacker, keep his work factor as high as possible. In the middle ground, famous quotes (not from philosophers, as you are known to disdain them -- perhaps an EWD quote, though?) probably aren't as good, and all three of your daughters' names are still worse.

All this is to make the point that a password which cannot be guessed is good, and one that can be guessed is bad. All else is obiter dicta, though perhaps useful. Rules of thumb for entropy estimates are tricky, though good ones might be helpful (how to estimate goodness in this respect?).

Lastly, a horrid example. The digits of pi are (surely it's been proved by now?!) random. So a bunch of them ought to be really good as a password (not easily remembered, but we can't have everything). Until someone gets the idea of trying some of the digit sequences, in which case the randomness is worthless, for password purposes. Entropy matters, but only in the context of expectation by the attacker community. Theoretical entropy is only tangentially related.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.