Building better passwords using probabilistic techniques

Password creation policies attempt to help users generate strong passwords but are generally not very effective and tend to frustrate users. The most popular policies are rule based which have been shown to have clear limitations. In this paper we consider a new approach that we term analyze-modify that ensures strong user passwords while maintaining usability. In our approach we develop a software system called AMP that first analyzes whether a user proposed password is weak or strong by estimating the probability of the password being cracked. AMP then modifies the password slightly (to maintain usability) if it is weak to create a strengthened password. We are able to estimate the strength of the password appropriately since we use a probabilistic password cracking system and associated probabilistic context-free grammar to model a realistic distribution of user passwords. In our experiments we were able to distinguish strong passwords from weak ones with an error rate of 1.43%. In one of a series of experiments, our analyze-modify system was able to strengthen a set of weak passwords, of which 53% could be easily cracked to a set of strong passwords of which only 0.27% could be cracked with only a slight modification to the passwords. In our work, we also show how to compute and use various entropy measures from the grammar and show that our system remains effective with continued use through a dynamic updating capability.