# Is there an equation to calculate the number of instances of a series of characters exist in a given key space?

If I'm using 16-18 character-length passwords with 94 different possible values-per-character (lower alphas, upper alphas, numbers, and special characters), is there an equation I can use to calculate how many times a series of the same value will be presented?

What I'm trying to find out is with granular password complexity programs, you can specify the max number of characters that can be seen adjacent to each other before they are discarded. What I want to know is, if a low value (e.g. 2) is used, how severly does this impact the key space for resistence against brute force attacks.

As in, in a 16 character password's keyspace of 94^16, if the number of same-values can't be 2 or more, how many possible passwords are removed from the available passwords an attacker has to use?

e.g. in the case of 2 same-value characters, the following passwords would be rejected:

1. 12345667890abcdefgWW - because of the 66 and WW
2. sadfl;jkxz089--qwer - because of the --
3. a;lksdjf%%;slkdaj;;zlc - because of the %% and ;;
4. 2134@!#\$SAf;ljkasdf\$\$\$\$cQ - because of the \$\$\$\$

...is there an equation to perform this type of calculation?

• Sounds like it would be 94*93^15 for no adjacent characters, right? Apr 8, 2014 at 16:28
• I have no idea -- that's why I'm asking if an equation exists to perform this calculation. Apr 8, 2014 at 17:06
• grc.com/haystack.htm Dec 11, 2016 at 22:29

For n-character passwords without two identical adjacent characters, @Stephen gives the solution: that's 94*93n-1 passwords. Reasoning is simple: you are free to use any of the 94 characters for the first character, then for each subsequent character you may use any of the 94 except the one which you just used, so 93.

For n = 16, you may see that you keep about 85.2% of the complete space of 9416 possible 16-character passwords. You lose less than 15%, so the security reduction is not huge.

If you want to avoid sequences of three identical characters, then the computation is more complex, but the involved space reduction will necessarily be lower, because any password with three consecutive identical characters is also a password with two consecutive identical characters. Therefore you will always keep at least your 85.2% of the original space. Moreover, the number of passwords with three identical consecutive characters is no more than (n-2)*94n-2 (this is a gross overestimate); for n = 16 this figure is about 0.16% of the total space, so ruling out passwords with three identical consecutive characters will leave you more than 99.84% of your original space.

For the formula above, I just "choose" the position for the first character in the three-character sequence, and I get to choose n-2 characters freely. This is an overestimate because I am counting twice the passwords with two sequences, thrice the passwords with three sequences, and so on. But an overestimate is sufficient to show that the space reduction effect is negligible.

Reduction of user patience, however, might not be so negligible. Remember that every single "password complexity" rule will be considered as a burden by the user, and antagonizing the user is the last thing you really want in practice.

• That last paragraph really should be right at the top IMO.
– user
Apr 10, 2014 at 14:00
• @Michael, I disagree, acquiesence to user concerns in the realm of security is exactly why computer security is in the gross state that it is today. Apr 10, 2014 at 19:15
• How does adding yet more, arbitrary even, rules about what makes a valid password (rules that are almost certainly unique to each service) improve security? How is `qwertyuiopasdfghjkl` (no repeating characters, but look down on that keyboard of yours) more secure than `qkarbopcljcmwqqilom` (immediately repeating characters in the case of `qq`, generated completely at random)? If you're concerned about weak passwords, there are probably hundreds of "actually used passwords" dictionaries available; grab a few of those and check candidate passwords against them instead.
– user
Apr 11, 2014 at 7:14