Institute for Software Research
School of Computer Science, Carnegie Mellon University


Effect of Grammar on Security of Long Passwords

Ashwini Rao, Birendra Jha*, Gananand Kini

May 2012


This report is an extended version of the paper:
Effect of Grammar on Security of Long Passwords
appearing in the Proceedings of the Third ACM Conference on Data
and Application Security and Privacy, CODASPY'13, 2013.

Keywords: Password, Passphrase, Cracking, Grammar, Policy

Use of long sentence-like or phrase-like passwords such as "abiggerbetterpassword" and "thecommunistfairy" is increasing. In this paper, we study the role of grammatical structures underlying such passwords in diminishing the security of passwords. We show that the results of the study have direct bearing on the design of secure password policies, and on password crackers used for enforcing password security. Using an analytical model based on Parts-of-Speech tagging we show that the decrease in search space due to the presence of grammatical structures can be as high as 50%. A significant result of our work is that the strength of long passwords does not increase uniformly with length. We show that using a better dictionary e.g. Google Web Corpus, we can crack more long passwords than previously shown (20.5% vs. 6%). We develop a proof-of-concept grammar-aware cracking algorithm to improve the cracking efficiency of long passwords. In a performance evaluation on a long password dataset, 10% of the total dataset was exclusively cracked by our algorithm and not by state-of-the-art password crackers.

30 pages

*Massachusetts Institute of Technology

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by