0
$\begingroup$

If we have a set amount of usable characters, but no other restrictions on the potential characters in a completely random fixed length password, we can easily calculate the entropy by doing:

$\log_2(c^{n})$

or

$\log_2(c)*n$

with $c$ being the number of possible characters, and $n$ being the length of the password.

However, when there are restrictions being set on the contents of the random password, this obviously lowers the entropy.


For example, if you have $94$ usable characters, of which $10$ are digits, $26$ are lower case letters, $26$ are upper case letters, and $32$ are special characters.

If there are no other restrictions, this gives us

$\log_2(94^{10}) = 65.5$

which means $65.5$ bits of entropy.


Now, if we have $94$ usable characters and the following restrictions are set:

  • 1 character must be an uppercase letter ($26$ options)
  • 1 character must be a lowercase character ($26$ options)
  • 1 character must be a digit ($10$ options)
  • 1 character must be a special charater ($32$ options)

How do you calculate the entropy for a truly random fixed length password with these restrictions in mind?

$\endgroup$
2
  • $\begingroup$ Note that the choice to calculate for a truly random value as well as a fixed length password is done intentionally to limit the scope of the question. $\endgroup$ Jul 10, 2020 at 9:39
  • $\begingroup$ Please see the two useful answers. $\endgroup$
    – kodlu
    Jul 11, 2020 at 23:46

3 Answers 3

2
$\begingroup$

It looks like the formula you're using is $\log_2(\textrm{number of possible passwords})$.

You don't explicitly mention a length, so I'll assume 10.

So with those restrictions, let's calculate the number of possible passwords.

Without any restrictions, the total number of possible passwords is $94^{10}$.

Let's count the number of invalid passwords. $(94-26)^{10}$ don't contain an uppercase letter. $(94-26)^{10}$ don't contain a lowercase letter. $(94-32)^{10}$ don't contain a special character. $(94-10)^{10}$ don't contain a digit.

There's overlap in those. For example, $(94-52)^{10}$ contain neither uppercase nor lowercase letters.

Number of invalid passwords = $(94-26)^{10} + (94-26)^{10} + (94-32)^{10} + (94-10)^{10} - \left((94-52)^{10} + (94-58)^{10} + (94-36)^{10} +(94-58)^{10} + (94-36)^{10} + (94-42)^{10}\right) + \left(26^{10} + 26^{10} + 32^{10} + 10^{10}\right)$

This yields $64.81$ bits.


Sanity check:

Ignoring order, The restrictions give $26 \cdot 26 \cdot 10 \cdot 32 \cdot 94^{6}$ possible number of passwords. That's one uppercase, one lowercase, one digit, one special character, and the remaining 6 can be anything. Taking the $\log_2$ of this yields $57.05$ bits.

This is a lower bound. The $65.5$ you mention in the question provides an upper bound. The answer lies inside the bounds as expected.

$\endgroup$
0
0
$\begingroup$

TL;DR:

I think the right formula is:

$94 ^ {10} - ( (94 − 26) ^ {10} + (94 − 26) ^ {10} + (94 − 32) ^ {10} + (94−10) ^ {10} )$

Explanation:

Aman Grewal's answer is an enlightening idea: extracting the set of invalid passwords from the entire full random set is the way to go. But I find the formula he wrote to be incorrect.

I think the formula for the number of invalid passwords is simple as:

$(94 − 26) ^ {10} + (94 − 26) ^ {10} + (94 − 32) ^ {10} + (94−10) ^ {10}$

He took overlaps into account, which I think is wrong. Those overlaps are subsets of this formula. The fact that the whole of these subsets are duplicates within the supersets is irrelevant, and these duplicates should not be tampered with any further. If you extract the superset of invalid passwords (with passwords containing exactly 3 character types) from the entire full random set, the subsets will get ditched along with it, and that's it.

I also find his other formula wrong: $26 \cdot 26 \cdot 10 \cdot 32 \cdot 94 ^ 6$.
The $94 ^ 6$ part, that can be anything, will contain one or more character types for sure. Including these character types in the $26 \cdot 26 \cdot 10 \cdot 32$ part will be unnecessary, because you don't need further assurance for these to be in the password. But to find out which ones these are, you need to do checks while the password is being built or something, for which a simple formula is probably not enough. Therefore, I think this is a wrong way to form a formula, and that's why I said that the first approach of Aman Grewal is the right one.

I'm not a math professor, so check your facts, but I strongly believe I'm right about all this.

$\endgroup$
2
  • $\begingroup$ That's overestimates the number of invalid passwords. In particular, passwords containing only special characters are counted 3 times in the sum: in the first $(94−26)^{10}$ term because they contain no uppercase, in the second $(94−26)^{10}$ term because they contain no lowercase, and in the $(94−10)^{10}$ term because they contain no digit. $\endgroup$
    – fgrieu
    Mar 4 at 9:05
  • $\begingroup$ You're right. I'll delete the bogus answer once you've read this. $\endgroup$
    – Bene Laci
    Mar 13 at 12:28
0
$\begingroup$

It’s an interesting little maths problem, but why the restrictions? It makes passwords just harder to type, and i can just add another letter or two if you think it’s not secure enough.

And please don’t restrict the password length. I actually tried to comment on an article aimed at the layman about the importance of passwords, and they required a password with five to fifteen letters. Passwords supplied by safari are 20 letters, so people switch to something less secure.

And worst is rule changes. Where passwords were used, and after rule changes they didn’t follow the new rules and wouldn’t be accepted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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