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

2 Answers 2

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

Using $\log_2(\textrm{number of possible passwords})$ in an $n$ character password, and a $c$ character alphabet containing the restricted characters mentioned, and assuming $n\geq 4,$ so that the restrictions can be satisfied we have $$ \log_2\left[ 26 \binom{n}{1} 26 \binom{n-1}{1} 10 \binom{n-2}{1} 32 \binom{n-3}{1} c^{n-4}\right]= $$ or $$ \log_2\left[ n(n-1)(n-2)(n-3) 26^2\cdot 10 \cdot 32 \cdot c^{n-4}\right] $$ since the number of ways of choosing $k$ positions out of $n$ places is $\binom nk.$

Edit: For your parameters this is approximately 69.350 and is consistent with the bound in the other answer.

$\endgroup$
2
  • 1
    $\begingroup$ Wolframalpha tell me that this is $\approx 72.449$ for $c=94$ and $n=10$ which would be higher than for unrestricted passwords. That can't be the case. $\endgroup$
    – Maeher
    Jul 10, 2020 at 15:12
  • $\begingroup$ Where does the second 10 come from? and how does (n-3) go missing? $\endgroup$
    – Maeher
    Jul 10, 2020 at 15:32

Your Answer

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

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