Briana Butler & Randy Abrams, Webroot

This paper presents an uncommon mathematical analysis of the effects of common constraints on the number of character permutations that can produce a viable password. I mentioned the question of “how many passwords are eliminated?” to cryptographer Michael Wood, the inventor of the REDOC III encryption algorithm. Michael had never considered this mathematical angle and he found it very interesting. Nobody I have spoken with has considered this question. Ultimately Maurice Schmidtler, a machine learning expert at Webroot, provided an algorithm that allowed us to quickly test the impact of a variety of constraints on passwords of a variety of lengths.

Dictionary and passphrase token attacks against passwords are types of probability-based attacks. When these fail, attacks turn to the improbable and eventually attempt the impossible. We refer to brute-force attacks which eliminate attempts against impossible “passwords” as “possibility-based attacks.”

If a password can be one to eight characters long, how many permutations of passwords are possible? It is actually about 70.6 trillion more than 95^8. If an attacker knows that the password must be 8 characters long, then that length constraint has reduced the maximum number of brute-force attempts potentially required to crack the set of unconstrained passwords by about 70.6 trillion permutations. This constraint is beneficial, but each additional character set constraint reduces the maximum number of brute-force attempts potentially required to crack a password. The number of possible eight character passwords begins to decrease significantly.

If a password must include both uppercase and lowercase letters, then the following compositions of character sets no longer result in passwords. This list is not comprehensive.

• Lowercase letters and symbols only.
  Example: ;,qg”d\i
• Uppercase letters and symbols only.
  Example: %JJ(*@WE
• Numbers and symbols only.
  Example: ‘2<6}|79
• Lowercase letters, numbers and symbols only.
  Example: 9@pd04}”
• Uppercase letters, numbers and symbols only.
  Example: 3}GI;+Y<

For an eight-character password meeting uppercase and lowercase alphabetic requirement, we start seeing double digit decreases in the percentage of possible passwords available from the unconstrained set. Additional constraints begin making larger and larger impacts. In this presentation we will pose and answer, or at least attempt to answer, the following questions:

• How many passwords are eliminated by character set constraints?
• Why is it so difficult to account for each of the possible passwords?
• How is the maximum entropy of the remaining passwords affected?
• If a brute force attack only attempts possible passwords, does it matter?
• Can compositional analysis of known passwords be used to enhance a hybrid probability/possibility attack?

In this presentation mathematical analysis is combined with compositional password analysis in order to explore potential refinements to a possibility-based brute force attack. Ultimately we are left with the most important questions…

• Can a possibility-based brute-force attack be created, and if so, what would a post-dictionary hybrid probability/possibility brute force attack look like?
• How might one defend against a possibility-based brute force attack?

And finally,

• How can 43^16 become roughly equal to 95^16 when creating a password?