30
$\begingroup$

I need to calculate the possible combinations for 8 characters password. The password must contain at least one of the following: (lower case letters, upper case letters, digits, punctuations, special characters).

Assume I have 95 ascii characters (lower case letters, upper case letters, digits, punctuations, special characters).

  • lower case letters = $26$
  • upper case letters = $26$
  • digits = $10$
  • punctuations & special characters = $33$

The general formula for the possible passwords that I can from from these 95 characters is: $95^8$.

But, accurately, I feel the above formula is incorrect. Please, correct me. The password policy requires at least one of the listed above ascii characters. Therefore, the password possible combinations = $(26)*(26)*(10)*(33)*(95)*(95)*(95)*(95)$

Which calculation is correct?

EDIT: Please, note that I mean 8 characters password and exactly 8. Also, There is no order specified (i.e. it could start with small letter, symbol, etc.). But it should contain at least one of the specified characters set (upper case, lower case, symbol, no., etc.).

$\endgroup$
  • $\begingroup$ Your second suggestion seems right - and can be shortened to (26^2)*10*33*(95^4) - but something feels just a little off about it. Regardless, this is off-topic for Information Security. It might be on-topic for Mathematics. We'll see if they want it migrated. $\endgroup$ – Iszi Apr 4 '14 at 18:17
  • $\begingroup$ Also of note, that password policy is ridiculously weak. 8-character passwords haven't been "strong enough" for quite some time. 12 is the new 8, but many are recommending 15, 20, or more. And please don't ever implement something that imposes a maximum length on the password. (Or at least, not a maximum that can be measured in two digits.) $\endgroup$ – Iszi Apr 4 '14 at 18:19
  • $\begingroup$ 6.70 x 10^15 possible combinations $\endgroup$ – Adi Apr 4 '14 at 18:23
  • $\begingroup$ @Adnan That's the number of possible passwords without restrictions on any of the characters - not what's being looked for here. $\endgroup$ – Iszi Apr 4 '14 at 18:26
  • $\begingroup$ @Iszi Please note the policy says "at least one of the characters should be...". $\endgroup$ – Adi Apr 4 '14 at 18:28
29
$\begingroup$

Start with all $8$-character strings: $95^8$

Then remove all passwords with no lowercase ($69^8$), all passwords with no uppercase ($69^8$), all passwords with no digit ($85^8$) and all passwords with no special character ($62^8$).

But then you removed some passwords twice. You must add back all passwords with:

  • no lowercase AND no uppercase: $43^8$
  • no lowercase AND no digit: $59^8$
  • no lowercase AND no special: $36^8$
  • no uppercase AND no digit: $59^8$
  • no uppercase AND no special: $36^8$
  • no digit AND no special: $52^8$

But then you added back a few passwords too many times. For instance, an all-digit password was remove three times in the first step, then put back three times in the second step, so it must be removed again:

  • only lowercase: $26^8$
  • only uppercase: $26^8$
  • only digits: $10^8$
  • only special: $33^8$

Grand total: $95^8 - 69^8 - 69^8 - 85^8 - 62^8 + 43^8 + 59^8 + 36^8 + 59^8 + 36^8 + 52^8 - 26^8 - 26^8 - 10^8 - 33^8 = 3025989069143040 \approx 3.026\times10^{15}$

$\endgroup$
  • 5
    $\begingroup$ For reference to the OP: this is the inclusion-exclusion principle. $\endgroup$ – Magdiragdag Apr 4 '14 at 18:57
  • $\begingroup$ @Thomas Pornin the password must contains at least one of the (lower case, upper case, digit, symbol and punctuation). I do not understand why you assume passwords with no lower case, upper case, etc. as you explained. $\endgroup$ – user2192774 Apr 4 '14 at 19:09
  • $\begingroup$ @user2192774 I presume your policy means that you must have at least one of each character type. For four character types, there's 15 possible states of character inclusion/exclusion that a non-null password may be in and only 1 of those states is valid. Were the character distribution even (that is, if there were equally as many uppercase, lowercase, digit, and symbol characters to choose from) the formula would be simple - just raise the total possible characters to a power equal to the password length and divide by 15. $\endgroup$ – Iszi Apr 4 '14 at 19:32
  • $\begingroup$ However, that is not the case. There are more symbols than there are letters of each class, and more than twice as many letters of each class as there are digits. Thus, we have to use more complicated methods like this. $\endgroup$ – Iszi Apr 4 '14 at 19:34
  • $\begingroup$ A bit old question, was looking out of interest but my combinatorics would tell me $26^2\times10\times33\times95^4\times(8!)/((2!)\times(4!)) \approx 1.5 \times 10^{16}$. $\endgroup$ – user88595 Feb 18 '16 at 14:45
-1
$\begingroup$

The answer I get is 0.3051925477389360000E+16 = 3,051,925,477,389,360. This answer is taken from the answer at Derive an algorithm for computing the number of restricted passwords for the general case? . This problem is more difficult than it appears. $95^8$ is not the right answer. (26)∗(26)∗(10)∗(33)∗(95)∗(95)∗(95)∗(95) is not the right answer and you can't just multiply this product by the number of permutations. This is because if for example the punctuation special character first appears in the fifth position in the password with the first lower case letter, first upper case letter, and first digit appearing in the first 3 positions of the password then there are only $(95-33) = 62$ characters that can appear in the fourth position of the password. Because of this problem a different approach is necessary. An approach that gives the right answer is done by summing as follows:

The number of passwords for permutation $I_k$ with password positions j1, j2, j3, and j4 is

$$S(I_k,j1,j2,j3,j4)=f1*g_{I(1)}*(n_t-(g_{I(2)}+g_{I(3)}+g_{I(4)}))^{(j2-1-j1)}*g_{I(2)}*(n_t-(g_{I(3)}+g_{I(4)}))^{(j3-1-j2)}*gI_{(3)}*(n_t-g_{I(4)})^{(j4-1-j3)}*g_{I(4)}*n_t^{(n-j4)}$$ .

$$S(I_k)=\sum_{j4=4}^n \sum_{j3=3}^{j4-1} \sum_{j2=2}^{j3-1} \sum_{j1=1}^{j2-1} S(I_k,j1,j2,j3,j4)$$

gives the number of passwords corresponding to permutation, $I_k$.

$$Total=\sum_{k=1}^{24} S(I_k)$$ gives the total number of passwords satisfying the requirement. The algorithm for computing the number of passwords meeting the requirement is more completely described at the web site indicated above.

$\endgroup$
-2
$\begingroup$

There's a simple flaw with the original equation:

It was stated that you have:

  • 26 lowercase letters (a-z)
  • 26 uppercase letters (A-Z)
  • 10 digits (0-9)
  • 33 punctuations and special characters

  1. How many total choices can each character within the password use?

    ADD the above numbers to answer that: $26+26+10+33 = 95$

  2. How many characters is the password in question?

    I believe we identified 8 in this scenario.

  3. How many combinations for this password are there?

    $$\text{(Possible choices)}^\text{(How many characters long)}=\text{(How many combinations)}$$

    Or per this example, $96^8=6634204312890625$

  4. Based on 8 characters of anything you can type, the answer is as simple as above.

    As stated in a more convoluted, albeit more descriptively accurate, the number changes based on password requirements.

  5. From a hacker / pentester perspective, entropy is stronger than mental complexity.

    If people use all lowercase because rules don't force them to use something else, yes, their password is weaker being all lowercase, because I can probe the password based on just lowercase ($26^8$).

    Wow, no rule against using humanly recognized words? (That was a common rule early-mid 2000s) The password rules themselves actually make a weaker password than the mathematically possible $96^8$.

  6. Password entropy makes this even more fun as we demonstrate that the entropy of password

    A#1WepOjII95&^2!

    is actually weaker than the password

    OMGmathMakesMyHeadWant2EXPLODE

  7. If you're looking at this from a security standpoint, use a long run-on phrase for a more challenging time being cracked. Using rainbow tables, it's now possible to crack a 64-character password within 4 minutes on a single computer.

    No, your $120 Atom laptop isn't likely to meet that kind of hacking efficiency. It's simply saying you don't need a cluster of computers anymore.

$\endgroup$

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