Beyond the Dictionary of the Probable: A Possibility-Based Brute-Force Attack

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?

Briana Butler

Briana Butler is an Engineering Data Analyst at Webroot. Her work focuses on mapping the architecture of engineering systems, integrations, and data flows, providing a high level view for all audiences. She works inside the engineering organization connecting data use and storage across the entire company, as well as assisting in GDPR initiatives. Briana graduated with a degree from the University of Colorado in Operations and Information Management, focusing on analytics. Beyond her love of data, she also loves hiking around the great Rocky Mountains.

Randy Abrams

Randy Abrams has worked in the security industry since 1997. While with Microsoft, Randy created and administered the process used to ensure new products were released free of viruses. Randy played a pivotal role in convincing Microsoft to share critical security information with the antimalware research community.In 2005, Abrams joined the IT security firm ESET as director of technical education. While at ESET, he was a popular cybersecurity blogger, podcaster, and speaker at numerous security conferences around the world. In 2012, Abrams moved NSS Labs where he served as a research director focusing on the analysis of endpoint protection testing. He joined Webroot in 2017 as a senior security analyst.A unique perspective and articulate insights have made Randy a sought-after resource for media commentary on cybersecurity issues and some of the world’s most high-profile security breaches. He has made appearances in media outlets including Reuters, The Wall Street Journal, Forbes, The Washington Post, TechCrunch, NPR, and many more.Randy is passionate about password education and phishing education. Bill Gates will give you $1 USD for every person you share this bio with.Randy has also served as the vice president of the Association of Anti-Virus Asian Researchers since 2002.

The Dynamic Security Ecosystem
Other Topics