Passwords: Divided they Stand, United they Fall
This work addresses password security for users and systems vulnerable to offline attacks, offering a novel framework that generalizes existing attack methods and provides a defensive strategy, though it builds incrementally on prior probabilistic and dictionary-based approaches.
The paper tackles the threat of offline password attacks by proposing a space partition attack model that divides the password search space into partitions based on data from leaks and other sources, proving that attackers maximize success by exploring partitions in order of density. It shows that real-world password databases have small search spaces, making them vulnerable, and proposes a system to counter attacks by distributing users across partitions to achieve uniform densities.
Today, offline attacks are one of the most severe threats to password security. These attacks have claimed millions of passwords from prominent websites including Yahoo, LinkedIn, Twitter, Sony, Adobe and many more. Therefore, as a preventive measure, it is necessary to gauge the offline guessing resistance of a password database and to help users choose secure passwords. The rule-based mechanisms that rely on minimum password length and different character classes are too naive to capture the intricate human behavior whereas those based on probabilistic models require the knowledge of an entire password distribution which is not always easy to learn. In this paper, we propose a space partition attack model which uses information from previous leaks, surveys, attacks and other sources to divide the password search space into non-overlapping partitions and learn partition densities. We prove that the expected success of a partition attacker is maximum if the resulting partitions are explored in decreasing order of density. We show that the proposed attack model is more general and various popular attack techniques including probabilistic-based, dictionary-based, grammar-based and brute-force are just different instances of a partition attacker. Later, we introduce bin attacker, another instance of a partition attacker, and measure the guessing resistance of real-world password databases. We demonstrate that the utilized search space is very small and as a result even a weak attacker can cause sufficient damage to the system. We prove that partition attacks can be countered only if partition densities are uniform. We use this result and propose a system that thwarts partition attacker by distributing users across different partitions. Finally, we demonstrate how some of the well-known password schemes can be adapted to help users in choosing passwords from the system assigned partitions.