Tokenizing Complex Passwords Using Breadth-First Search and Dictionary Matching
Keywords:
Password Tokenization, Breadth-First Search, Password Cracking, CybersecurityAbstract
Despite the adoption of complex password policies, users often create passwords that follow predictable patterns involving dictionary words, numbers, and symbols. Traditional tokenization techniques used for password analysis frequently overlook or misclassify symbolic and numeric elements, resulting in incomplete strength evaluations and less effective cracking strategies. This study presents a Breadth-First Search (BFS)-based tokenization framework that systematically segments passwords into meaningful components, including words from dictionaries, numeric sequences, and symbolic tokens. The BFS algorithm examines all possible substring combinations to identify the most comprehensive segmentation path. Remaining unmatched symbols and numbers are processed in a dedicated post-analysis phase to ensure complete token representation. Experiments conducted on a real-world dataset of 100,000 passwords demonstrate that the proposed approach outperforms baseline tokenizers in terms of token coverage and segmentation accuracy, while maintaining efficient processing times. The improved tokenization results contribute to a more accurate assessment of password complexity and support the development of stronger password-cracking models. These findings emphasize the importance of structure-aware parsing methods in advancing password security analysis.
Downloads
References
R. Morris and K. Thompson, “Password security: A case history,” Communications of the ACM, vol. 22, no. 11, pp. 594–597, 1979, doi:10.1145/359168.359172.
M. Khadka, “A systematic appraisal of multi-factor authentication mechanisms for cloud-based e-commerce platforms and their effect on data protection,” Journal of Emerging Cloud Technologies and Cross-Platform Integration Paradigms, vol. 6, no. 12, pp. 12–21, 2022. Available: https://hammingate.com/index.php/JECTCIP/article/view/2022-12-07/10
F. Di Nocera, G. Tempestini, and M. Orsini, “Usable security: A systematic literature review,” Information, vol. 14, no. 12, p. 641, 2023, doi:10.3390/info14120641.
M. Jubur, P. Shrestha, and N. Saxena, “An in-depth analysis of password managers and two-factor authentication tools,” ACM Computing Surveys, vol. 57, no. 5, pp. 1–32, 2025, doi:10.1145/3711117.
A. Narayanan and V. Shmatikov, “Fast dictionary attacks on passwords using time-space tradeoff,” in Proceedings of the 12th ACM Conference on Computer and Communications Security, 2005, pp. 364–372, doi:10.1145/1102120.1102168.
J. Bonneau, “The science of guessing: Analyzing an anonymized corpus of 70 million passwords,” in 2012 IEEE Symposium on Security and Privacy, IEEE, 2012, pp. 538–552, doi:10.1109/SP.2012.49.
K. Reaz and G. Wunder, “Expectation entropy as a password strength metric,” in 2022 IEEE Conference on Communications and Network Security (CNS), IEEE, 2022, pp. 1–2, doi:10.1109/CNS56114.2022.9947259.
D. Florêncio and C. Herley, “A large-scale study of web password habits,” ACM Transactions on the Web (TWEB), vol. 10, no. 4, pp. 1–26, 2016, doi:10.1145/1242572.1242661.
C. Castelluccia and M. Duermuth, “Adaptive password-strength meters from Markov models,” in International Conference on Information Security and Cryptology, Springer, 2012, pp. 1–15. Available: https://www.ndss-symposium.org/wp-content/uploads/2017/09/06_3.pdf
W. Melicher, “Modeling security weaknesses to enable practical run-time defenses,” Ph.D. dissertation, Carnegie Mellon University, 2019.
H. V. Cook and L. J. Jensen, “A guide to dictionary-based text mining,” in Bioinformatics and Drug Discovery, Springer, 2019, pp. 73–89.
B. Hitaj, P. Gasti, G. Ateniese, and F. Perez-Cruz, “PassGAN: A deep learning approach for password guessing,” in Applied Cryptography and Network Security (ACNS 2019), Springer, 2019, pp. 217–237, doi:10.1007/978-3-030-21568-2_11.
S. Nam, S. Jeon, and J. Moon, “Generating optimized guessing candidates toward better password cracking from multi-dictionaries using relativistic GAN,” Applied Sciences, vol. 10, no. 20, p. 7306, 2020, doi:10.3390/app10207306.
A. Kuznetsov and D. A. Vyshemirsky, “One approach to solving tokenization problem for analysis of large-scale collections of user-defined passwords,” Bit Numerical Mathematics, vol. 24, pp. 50–60, 2017.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.
M. Kurant, A. Markopoulou, and P. Thiran, “On the bias of BFS (breadth-first search),” in 2010 22nd International Teletraffic Congress (ITC 22), IEEE, 2010, pp. 1–8, doi:10.1109/ITC.2010.5608727.
A. Z. Ismaeel and I. M. Zebari, “Comparing traversal strategies: Depth-first search vs. breadth-first search in complex networks,” Asian Journal of Research in Computer Science, vol. 18, no. 2, pp. 60–73, 2025.
M. Weir, S. Aggarwal, B. De Medeiros, and B. Glodek, “Password cracking using probabilistic context-free grammars,” in 2009 IEEE Symposium on Security and Privacy, IEEE, 2009, pp. 391–405.
M. Weir, S. Aggarwal, M. Collins, and H. Stern, “Testing metrics for password creation policies by attacking large sets of revealed passwords,” in Proceedings of the 17th ACM Conference on Computer and Communications Security, 2010, pp. 162–175.
W. Li and J. Zeng, “Leet usage and its effect on password security,” IEEE Transactions on Information Forensics and Security, vol. 16, pp. 2130–2143, 2021.
A. Kanta, I. Coisel, and M. Scanlon, “A novel dictionary generation methodology for contextual-based password cracking,” IEEE Access, vol. 10, pp. 59,178–59,188, 2022.
T. Yang and D. Wang, “RankGuess: Password guessing using adversarial ranking,” in 2025 IEEE Symposium on Security and Privacy (SP), IEEE, 2025, pp. 682–700.
A. N. Kuznetsov and D. A. Vyshemirsky, “One approach to solving the tokenization problem in the analysis of large collections of user passwords,” Information Technology Security, vol. 24, no. 2, pp. 50–60, 2017.
E. I. Tatli and E. Seker, “Password replacement patterns,” in 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT), IEEE, 2018.
M. Zhang, J. Fan, and D. Chen, “Efficient dictionary matching by Aho-Corasick automata of truncated patterns,” International Journal of Computing Science and Mathematics, vol. 7, no. 4, pp. 323–329, 2016.
M. Gibson, M. Conrad, and C. Maple, “Infinite alphabet passwords: A unified model for a class of authentication systems,” in 2010 International Conference on Security and Cryptography (SECRYPT), IEEE, 2010.
J. Zhang, S. Liu, L. Gong, H. Zhang, Z. Huang, and H. Jiang, “Beqain: An effective and efficient identifier normalization approach with BERT and the question answering system,” IEEE Transactions on Software Engineering, vol. 49, no. 4, pp. 2597–2620, 2022.
M. Gamon, “High-order sequence modeling for language learner error detection,” in Proceedings of the Sixth Workshop on Innovative Use of NLP for Building Educational Applications, 2011, pp. 180–189.
F. Ariai, J. Mackenzie, and G. Demartini, “Natural language processing for the legal domain: A survey of tasks, datasets, models, and challenges,” ACM Computing Surveys, vol. 58, no. 6, pp. 1–37, 2025.
