Abstract
Passwords are widely used for user authentication, and will likely remain in use in the foreseeable future, despite several weaknesses. One important weakness is that human-generated passwords are far from being random, which makes them susceptible to guessing attacks. Understanding the adversaries capabilities for guessing attacks is a fundamental necessity for estimating their impact and advising countermeasures.
This paper presents OMEN, a new Markov model-based password cracker that extends ideas proposed by Narayanan and Shmatikov (CCS 2005). The main novelty of our tool is that it generates password candidates according to their occurrence probabilities, i.e., it outputs most likely passwords first. As shown by our extensive experiments, OMEN significantly improves guessing speed over existing proposals.
In particular, we compare the performance of OMEN with the Markov mode of John the Ripper, which implements the password indexing function by Narayanan and Shmatikov. OMEN guesses more than 40% of passwords correctly with the first 90 million guesses, while JtR-Markov (for T = 1 billion) needs at least eight times as many guesses to reach the same goal, and OMEN guesses more than 80% of passwords correctly at 10 billion guesses, more than all probabilistic password crackers we compared against.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bishop, M., Klein, D.V.: Improving system security via proactive password checking. Computers & Security 14(3), 233–249 (1995)
Bonneau, J.: The science of guessing: analyzing an anonymized corpus of 70 million passwords. In: Proc. IEEE Symposium on Security and Privacy. IEEE (2012)
Bonneau, J., Herley, C., van Oorschot, P.C., Stajano, F.: The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. In: Proc. IEEE Symposium on Security and Privacy. IEEE (2012)
Burr, W.E., Dodson, D.F., Polk, W.T.: Electronic authentication guideline: NIST special publication 800-63 (2006)
Castelluccia, C., Dürmuth, M., Perito, D.: Adaptive password-strength meters from Markov models. In: Proc. Network and Distributed Systems Security Symposium (NDSS). The Internet Society (2012)
Dell’Amico, M., Michiardi, P., Roudier, Y.: Password strength: an empirical analysis. In: Proc. 29th conference on Information communications, INFOCOM 2010, pp. 983–991. IEEE Press, Piscataway (2010)
Egelman, S., Bonneau, J., Chiasson, S., Dittrich, D., Schechter, S.: It’s not stealing if you need it: A panel on the ethics of performing research using public data of illicit origin. In: Blyth, J., Dietrich, S., Camp, L.J. (eds.) FC 2012. LNCS, vol. 7398, pp. 124–132. Springer, Heidelberg (2012)
HashCat. OCL HashCat-Plus (2012), http://hashcat.net/oclhashcat-plus/
Kedem, G., Ishihara, Y.: Brute force attack on unix passwords with SIMD computer. In: Proc. 8th Conference on USENIX Security Symposium, SSYM 1999, vol. 8. USENIX Association (1999)
Kelley, P.G., Komanduri, S., Mazurek, M.L., Shay, R., Vidas, T., Bauer, L., Christin, N., Cranor, L.F., Lopez, J.: Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms. In: Proc. IEEE Symposium on Security and Privacy. IEEE (2012)
Klein, D.V.: Foiling the cracker: A survey of, and improvements to, password security. In: Proc. USENIX UNIX Security Workshop (1990)
Komanduri, S., Shay, R., Kelley, P.G., Mazurek, M.L., Bauer, L., Christin, N., Cranor, L.F., Egelman, S.: Of passwords and people: Measuring the effect of password-composition policies. In: CHI 2011: Conference on Human Factors in Computing Systems (2011)
Li, Z., Han, W., Xu, W.: A large-scale empirical analysis of chinese web passwords. In: Proc. 23rd USENIX Security Symposium, USENIX Security (August 2014)
Ma, J., Yang, W., Luo, M., Li, N.: A study of probabilistic password models. In: Proc. IEEE Symposium on Security and Privacy. IEEE Computer Society (2014)
Morris, R., Thompson, K.: Password security: a case history. ACM Communications 22(11), 594–597 (1979)
Narayanan, A., Shmatikov, V.: Fast dictionary attacks on passwords using time-space tradeoff. In: Proc. 12th ACM conference on Computer and communications security (CCS), pp. 364–372. ACM (2005)
OpenWall John the Ripper (2012), http://www.openwall.com/john
The password meter, http://www.passwordmeter.com/
PCFG Password Cracker implementation Matt Weir (2012), https://sites.google.com/site/reusablesec/Home/password-cracking-tools/probablistic_cracker
Provos, N., Mazières, D.: A future-adaptive password scheme. In: Proc. Annual Conference on USENIX Annual Technical Conference, ATEC 1999. USENIX Association (1999)
Schechter, S., Herley, C., Mitzenmacher, M.: Popularity is everything: a new approach to protecting passwords from statistical-guessing attacks. In: Proc. 5th USENIX Conference on Hot Topics in Security, pp. 1–8. USENIX Association (2010)
Spafford, E.H.: Observing reusable password choices. In: Proc. 3rd Security Symposium, pp. 299–312. USENIX (1992)
Weir, M., Aggarwal, S., Collins, M., Stern, H.: Testing metrics for password creation policies by attacking large sets of revealed passwords. In: Proc. 17th ACM Conference on Computer and Communications Security (CCS 2010), pp. 162–175. ACM (2010)
Weir, M., Aggarwal, S., de Medeiros, B., Glodek, B.: Password cracking using probabilistic context-free grammars. In: Proc. IEEE Symposium on Security and Privacy, pp. 391–405. IEEE Computer Society (2009)
Word list Collection (2012), http://www.outpost9.com/files/WordLists.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Dürmuth, M., Angelstorf, F., Castelluccia, C., Perito, D., Chaabane, A. (2015). OMEN: Faster Password Guessing Using an Ordered Markov Enumerator. In: Piessens, F., Caballero, J., Bielova, N. (eds) Engineering Secure Software and Systems. ESSoS 2015. Lecture Notes in Computer Science, vol 8978. Springer, Cham. https://doi.org/10.1007/978-3-319-15618-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-15618-7_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15617-0
Online ISBN: 978-3-319-15618-7
eBook Packages: Computer ScienceComputer Science (R0)