General Framework for Evaluating Password Complexity and Strength
This work addresses the critical issue of weak password selection in authentication systems, which affects security across enterprises and users, by providing a more accurate and practical evaluation framework.
The paper tackles the problem of accurately assessing password resistance to cracking attacks by formalizing the concepts of password complexity and strength, and develops a general framework for calculating these metrics based on attacker resources and strategies. The result is a practical framework that captures human biases and known attack techniques, and includes a method to evaluate the accuracy of existing password strength estimators.
Although it is common for users to select bad passwords that can be easily cracked by attackers, password-based authentication remains the most widely-used method. To encourage users to select good passwords, enterprises often enforce policies. Such policies have been proven to be ineffectual in practice. Accurate assessment of a password's resistance to cracking attacks is still an unsolved problem, and our work addresses this challenge. Although the best way to determine how difficult it may be to crack a user-selected password is to check its resistance to cracking attacks employed by attackers in the wild, implementing such a strategy at an enterprise would be infeasible in practice. We first formalize the concepts of password complexity and strength with concrete definitions emphasizing their differences. Our framework captures human biases and many known techniques attackers use to recover stolen credentials in real life, such as brute-force attacks. Building on our definitions, we develop a general framework for calculating password complexity and strength that could be used in practice. Our approach is based on the key insight that an attacker's success at cracking a password must be defined by its available computational resources, time, function used to store that password, as well as the topology that bounds that attacker's search space based on that attacker's available inputs, transformations it can use to tweak and explore its inputs, and the path of exploration which can be based on the attacker's perceived probability of success. We also provide a general framework for assessing the accuracy of password complexity and strength estimators that can be used to compare other tools available in the wild.