Abstract
It is not rare that one person uses the same password across his/her different accounts or uses the same substring(s) to build different passwords. Similarly, different persons may use the same passwords or same substring(s) in their passwords. How do the shared passwords or substrings impact the strength of the passwords? In this research, we find that using the dictionaries with shared substrings can easily and effectively crack most hashed passwords. We used Generalized Suffix Tree to systematically analyze more than 35 million plaintext passwords. The shared substrings found by Generalized Suffix Tree are compiled into dictionaries/word lists. By using these dictionaries, the Dictionary (Combinator) Attack of Hashcat cracked \(89\%\), \(80\%\), \(90\%\), \(89\%\) of English, Russian, Chinese, and French domain passwords respectively. In this work, we treat Combinator Attack as a special case of Dictionary Attack and use these two terms interchangeably.
This work is supported by ELSA high performance computing cluster at The College of New Jersey. ELSA is funded by National Science Foundation grant OAC-1828163.
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
Similar content being viewed by others
References
Molva, R., Tsudik, G.: Authentication method with impersonal token cards. In: Proceedings 1993 IEEE Computer Society Symposium on Research in Security and Privacy, Oakland, CA (1993)
Yubico.com. https://www.yubico.com/
Hashcat. https://hashcat.net/wiki/
Google Says Not To Worry About 5 Million ‘Gmail Passwords’ Leaked. https://www.forbes.com/sites/kashmirhill/2014/09/11/google-says-not-to-worry-about-5-million-gmail-passwords-leaked/#307f08f07a8d
Selena, L.: Every single Yahoo account was hacked - 3 billion in all. http://money.cnn.com/2017/10/03/technology/business/yahoo-breach-3-billion-accounts/index.html (2017)
Jeremi M.G.: How LinkedIn’s password sloppiness hurts us all. https://arstechnica.com/information-technology/2016/06/how-linkedins-password-sloppiness-hurts-us-all/ (2016)
Edvardas, M.: RockYou2021: largest password compilation of all time leaked online with 8.4 billion entries. https://cybernews.com/security/rockyou2021-alltime-largest-password-compilation-leaked/ (2021)
John the Ripper password cracker. https://www.openwall.com/john/
Cain and Abel (software). https://en.wikipedia.org/wiki/Cain_and_Abel_%28software%29
Brute Force Attack. https://www.owasp.org/index.php/Brute_force_attack
Morris, R., Thompson, K.: Password security: a case history. CACM 22(11), 594–597 (1979)
Tatl, E.I.: Cracking more password hashes with patterns. In: IEEE Transactions on Information Forensics and Security, vol. 10, no. 8, pp. 1656–1665. IEEE Press, New York (2015)
https://wiki.skullsecurity.org/Passwords#Password_dictionaries
Weir, M., Aggarwal, S., Medeiros, B.d., Glodek, B.: Password cracking using probabilistic context-free grammars. In: 2009 30th IEEE Symposium on Security and Privacy, pp. 391–405 (2009). https://doi.org/10.1109/SP.2009.8
Veras, R., Collins, C., Thorpe, J.: On the semantic patterns of passwords and their security impact. In: Proceedings of the Network and Distributed System Security Symposium (2014)
Xu, R., Chen, X., Wang, X., Shi, J.: An In-depth study of digits in passwords for Chinese websites. In: 2018 IEEE Third International Conference on Data Science in Cyberspace (DSC), Guangzhou, pp. 588–595 (2018). https://doi.org/10.1109/DSC.2018.00094
Melicher, W., et al.: Fast, lean, and accurate: modeling password guessability using neural networks. In: USENIX Security Symposium (2016)
Bieganski, P., Riedl, J., Carlis, J., Retzel, E.F.: Generalized suffix trees for biological sequence data. In: Proceedings of the Twenty-Seventh Hawaii International Conference on Biotechnology Computing, pp. 35–44 (1994)
Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997). ISBN 978-0-521-58519-4
McCreight, E.M.: A Space-economical Suffix Tree Construction Algorithm. ACM (1976)
Jeremi M.G.: How LinkedIn’s password sloppiness hurts us all (2016). https://arstechnica.com/information-technology/2016/06/how-linkedins-password-sloppiness-hurts-us-all/
bibitemch201billPass Kumar, M.: Collection of 1.4 Billion Plain-Text Leaked Passwords Found Circulating Online. https://thehackernews.com/2017/12/data-breach-password-list.html
CrackStation’s Password Cracking Dictionary. https://crackstation.net/crackstation-wordlist-password-cracking-dictionary.htm
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Li, J. et al. (2022). Integrate Generalized Suffix Tree into Dictionary Attack. In: Rocha, A., Adeli, H., Dzemyda, G., Moreira, F. (eds) Information Systems and Technologies. WorldCIST 2022. Lecture Notes in Networks and Systems, vol 468. Springer, Cham. https://doi.org/10.1007/978-3-031-04826-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-04826-5_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-04825-8
Online ISBN: 978-3-031-04826-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)