Password system, possible solutions

Question

I am trying to solve a problem with a password system. I need to figure out the probability of the password being guessed.

If I have an 8-character alphanumeric password.

it cannot be all #'s, meaning it must have a letter in it it cannot have character's in sequence (ex. abcdefgh or a1234567) it can not have the word "johnbook"

Answer 1

I write down the rules: eight characters, not all digits, no embedded sequence (where a sequence is at least two successive letters or digits where one is "one more" or "one less" than the previous), and not "johnbook".

If we consider characters left-to-right, then we have 36 choices for the first character, and then 34 for each subsequent character (because of the "no sequence" rule: after an 'm' you cannot have an 'l' or an 'n'). This means 36*34⁷ = 1890840605184 possible passwords -- but we have to adjust that to account for the other rules: we must remove the all-digits passwords (10*9⁷ = 47829690 passwords) and also "johnbook" (1 password). The grand total is then: 1890792775493 passwords. If you choose the password with perfect uniformity, then the attacker has exactly 1 chance in that of guessing the password at his first try. On average, the attacker will try 945396387747 passwords before hitting the right one.

Note that I assumed the following:

• only lowercase letters (to account for uppercase, change 34 to 60 and 36 to 52);
• prohibition on sequences begins at sequences of two characters (we forbid 'ef', not just 'efg') and includes decreasing sequences ('gfe' is also bad);
• sequences "wrap around" the end of the alphabet ('za' is a sequence, and so is '90').

Such rules may make your users grumpy.

Answer 2

Generally the probability comes down to the size of the range. So for, say, a 4 character password, the password space the number of available characters raised to the power of the number of places in the password.

For example, a bank pin - 4 digits, 10 characters (0-9) - 1000 possible passwords, making the probability 1/10000.

Now your problem is harder, since your range is not all available passwords, you have removed some of the highly guessable passwords. What you're going to have to do is figure out how many potential passwords are eliminated by each rule, and make sure you account for rules overlapping... for example 12345678 is both a sequence AND all characters. Then take the total password space, subtract the passwords that are forbidden by each rule, making sure not to count a given type of password twice.

I'm not sure what you mean by "it cannot have the word "johnbook" " perhaps I'm being way too literal - obviously "johnbook" is just one password. Do you mean it can't have that particular word, or it can't have any known common name or short word combination? For example, is "bethdesk" also forbidden? What is the size of the dictionary being checked and all are all word combinations long and short forbidden? You should be able to use combinatorics to figure this out, but you need the algorithm or rules of password checking to know how much this limits the size of the password space.

Also, virtually any word combination is also going to be an "all character" sequence - so have you basically eliminated that, or is the system checking for obvious substitutions - like "passw0rd"?