2
$\begingroup$

I read this wiki article and saw this formula for random password's information entropy. Also the wiki article mention that the symbol count for non case sensitive is 36. Is there a way I can calculate the password space with this information.Entropy per symbol for different symbol sets random password's information entropy

$\endgroup$
  • 2
    $\begingroup$ The password space isn't something you calculate; it's just the set of all strings consisting of eight alphabet characters (case insensitive). The size of the password space is 26**8, or about 209 billion. And if you want to know the amount of entropy of such a password selected uniformly at random, then that would be 4.7 entropy bits per character × 8 characters = 37.6 bits. (In the equation you provided, L=8, and N=26.) $\endgroup$ – squeamish ossifrage Mar 1 '18 at 10:59
  • $\begingroup$ @squeamishossifrage Where L is the length of the password and N is the number of possible values for a character. $\endgroup$ – DannyNiu Mar 1 '18 at 14:24
  • $\begingroup$ So what would case sensitive 8 character would look like. (26^8)*(26^8) $\endgroup$ – socrates louis Mar 4 '18 at 23:55
  • $\begingroup$ @socrateslouis If you allow mixed case, then you are using an alphabet of 26*2=52 characters. So the number of possible 8-character passwords is 52**8 ≈ 53.46 trillion. $\endgroup$ – squeamish ossifrage Mar 6 '18 at 10:15
2
$\begingroup$

The choice of 8 fully random characters is exactly 3 bits as $\log_2(8) = 3$. So to calculate the strength in bits you simply multiply with the size of the password: e.g. 16 * 3 = 48 bits of strength for 16 characters.

To translate that to the password space - the number of possible passwords - you simply can perform $2^{48}$ which means that there are 281,474,976,710,656 possible passwords. A little known trick to get an idea of the number of decimal digits is to multiply by 3 and then divide by 10 and round up: so $\large\lceil\normalsize{48 * 3 \over {10}}\large\rceil\normalsize = 15$, i.e. above number contains 15 digits. A more direct method is to simply perform exponentiation with the password size: $8^{16}$ will give you the same large number. However, I use the trick above to perform such calculations without calculator.

Note that protection against brute force should require key stretching by e.g. using a password hash. For such kind of passwords additional protection (such as account locking) should be implemented. The system needs to deal with low entropy passwords.


The trick above depends on a little known constant: 3.3219280948873626. This is the result of $\ln(10)\over\ln(2)$, i.e. each decimal digit takes about 3.3219280948873626 bits to be represented. It's quite close to 3.3333 wich makes calculations rather efficient. The little difference makes it so that $2^{10} = 1024$, or just over a thousand (a kilo in ancient Greek).

$\endgroup$
0
$\begingroup$

You can't easily calculate the entropy of a human-generated password. I'm talking about human-generated passwords, not machine-generated encryption keys. This is a hugely important distinction that people often miss.

It's tempting to use the H log formula that you've included at the bottom of your question. That only applies to independently and identically distributed (IID) characters. That's what a key derivation function provides, and which you such probably be considering. A human password is like "SECRET" and "JamesBond1" as I use. Those characters are not remotely IID.

Some numbers to create a context:-

A key of 8 IID characters chosen from an alphabet of 26 has exactly $ log_2 $(26) x 8 = 37.6 bits of entropy. Or $ \approx 2 \times 10^{11}$ (~200 billion) possibilities.

But a password is not a key. The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use, and 47,156 obsolete words. That's around 220,000 words. Even if we chose say a single word randomly, that's only ~18 bits. Combinations or words may increase this, but the fact that some of those are much longer than eight characters also reduces this. 18 bits = 262,144 and is only $ \approx \frac{1}{1,000,000} $ of the size an equivalent length IID key space would be. See, it's getting hard.

Shakespeare wrote at about 1.7 bits /character, so his eight character laptop password would have only been 13.4 bits, giving a potential space of ~11,000. That's $ \approx \frac{1}{20,000,000}$ of IID space. This estimate is almost rubbish, but who can do better and it highlights the hard issue.

Passwords are generally made of words that we know. Those words follow strict rules (if you can spell). And randomly chosen letters tend to be towards the centre of the keyboard. Humans are very bad at generating randomness, which is why we no longer simply use typists to create one time pads. The most scientific estimates we have are detailed in NIST Special Publication 800-63, Electronic Authentication Guideline, Appendix A. Quoting:-

  • the entropy of the first character is taken to be 4 bits;

  • the entropy of the next 7 characters are 2 bits per character; this is roughly consistent with Shannon’s estimate that “when statistical effects extending over not more than 8 letters are considered the entropy is roughly 2.3 bits per character;”

Adding up, you'd have an eight character password entropy of 18 bits, and a space of 262,144. Surprisingly identical to my own cockamamie estimate. That publication is obsolete now, and the current version doesn't feature any form of entropy assessment.

There is also NIST 800-90B Recommendation for the Entropy Sources Used for Random Bit Generation. There are formulae there that attempt to calculate the entropy of random non IID sequences, but are unsuitable for strings as short as eight characters. And there is strong evidence from How to interpret the entropy results for a NIST test file? and NIST 800-90B /Non-IID track - min-entropy result > 8 for 8-bit symbol that the formulae are unsound.

Without having to read between the lines, NIST says it's hard too:

"Users’ password choices are very predictable..."

$\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.