Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff, CCS, 05
The authors describe an efficient dictionary attack on password which trades-off space for time similar to Oechslin's rainbow attack but with a better coverage. They observe that the more a word is phonetically similar to a word in someone's native language, the more it is memorable. Based on this observation, they use zero and first order Markov models to prune the search space. They also observe that digits are usually appended at the end, usually the first character is the uppercase one, etc., simple rules in the passwords. A set of regular expressions are developed to account for these rules. The authors cracking algorithm incorporates both of these aspects and from 150 real passwords, the algorithm recovered 67.6% using a search space of 2e9.
Citation (ACM Ref): Arvind Narayanan and Vitaly Shmatikov. 2005. Fast dictionary attacks on passwords using time-space tradeoff. In Proceedings of the 12th ACM conference on Computer and communications security (CCS '05). ACM, New York, NY, USA, 364-372. DOI=10.1145/1102120.1102168 http://doi.acm.org/10.1145/1102120.1102168
Citation (ACM Ref): Arvind Narayanan and Vitaly Shmatikov. 2005. Fast dictionary attacks on passwords using time-space tradeoff. In Proceedings of the 12th ACM conference on Computer and communications security (CCS '05). ACM, New York, NY, USA, 364-372. DOI=10.1145/1102120.1102168 http://doi.acm.org/10.1145/1102120.1102168
Password Cracking Using Probabilistic Context-Free Grammars, SSP, 09
A large corpus of disclosed passwords was divided into a training set and a test set. The authors wrote a program to automatically create a context-free grammar based on the training set. The resulting grammar helped them to automatically produce word-mangling rules and from them, password guesses to be used in password cracking. The passwords were produced in decreasing order of probability. Using the same number of guesses, the algorithm cracked 28-129% more passwords than John the Ripper. The algorithm can be trained on any input dictionary, e.g., Finnish.
Citation (ACM Ref): Matt Weir, Sudhir Aggarwal, Breno de Medeiros, and Bill Glodek. 2009. Password Cracking Using Probabilistic Context-Free Grammars. In Proceedings of the 2009 30th IEEE Symposium on Security and Privacy (SP '09). IEEE Computer Society, Washington, DC, USA, 391-405. DOI=10.1109/SP.2009.8 http://dx.doi.org/10.1109/SP.2009.8
Citation (ACM Ref): Matt Weir, Sudhir Aggarwal, Breno de Medeiros, and Bill Glodek. 2009. Password Cracking Using Probabilistic Context-Free Grammars. In Proceedings of the 2009 30th IEEE Symposium on Security and Privacy (SP '09). IEEE Computer Society, Washington, DC, USA, 391-405. DOI=10.1109/SP.2009.8 http://dx.doi.org/10.1109/SP.2009.8
Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms, SSP, 12
The authors evaluate guessing resistance against offline attacks that result from several password composing policy. They collected 12,000 passwords, created under different policies, using MTurk. As a cracking algorithm they found Weir's probabilistic context free grammar as the best. Though according to NIST's guidelines, comprehensive8 and basic16 should have provided equivalent resistance to guessing, in practice basic16 performs better and as it's also more memorable, the authors conclude that basic16 is the best policy among the ones they examined.
They found that effective attacks on passwords created under complex or rare-in-practice composition policies require access to abundant, closely matched training data. They also found that Shannon entropy and NIST guidelines can only provide a rough correlation with guess resistance and is unable to correctly predict quantitative differences in guessability among password sets.
Citation (ACM Ref): Patrick Gage Kelley, Saranga Komanduri, Michelle L. Mazurek, Richard Shay, Timothy Vidas, Lujo Bauer, Nicolas Christin, Lorrie Faith Cranor, and Julio Lopez. 2012. Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms. InProceedings of the 2012 IEEE Symposium on Security and Privacy (SP '12). IEEE Computer Society, Washington, DC, USA, 523-537. DOI=10.1109/SP.2012.38 http://dx.doi.org/10.1109/SP.2012.38
They found that effective attacks on passwords created under complex or rare-in-practice composition policies require access to abundant, closely matched training data. They also found that Shannon entropy and NIST guidelines can only provide a rough correlation with guess resistance and is unable to correctly predict quantitative differences in guessability among password sets.
Citation (ACM Ref): Patrick Gage Kelley, Saranga Komanduri, Michelle L. Mazurek, Richard Shay, Timothy Vidas, Lujo Bauer, Nicolas Christin, Lorrie Faith Cranor, and Julio Lopez. 2012. Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms. InProceedings of the 2012 IEEE Symposium on Security and Privacy (SP '12). IEEE Computer Society, Washington, DC, USA, 523-537. DOI=10.1109/SP.2012.38 http://dx.doi.org/10.1109/SP.2012.38