{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:36:53Z","timestamp":1760240213377,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T00:00:00Z","timestamp":1554076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Slow-hash algorithms are proposed to defend against traditional offline password recovery by making the hash function very slow to compute. In this paper, we study the problem of slow-hash recovery on a large scale. We attack the problem by proposing a novel concurrent model that guesses the target password hash by leveraging known passwords from a largest-ever password corpus. Previously proposed password-reused learning models are specifically designed for targeted online guessing for a single hash and thus cannot be efficiently parallelized for massive-scale offline recovery, which is demanded by modern hash-cracking tasks. In particular, because the size of a probabilistic context-free grammar (PCFG for short) model is non-trivial and keeping track of the next most probable password to guess across all global accounts is difficult, we choose clever data structures and only expand transformations as needed to make the attack computationally tractable. Our adoption of max-min heap, which globally ranks weak accounts for both expanding and guessing according to unified PCFGs and allows for concurrent global ranking, significantly increases the hashes can be recovered within limited time. For example, 59.1% accounts in one of our target password list can be found in our source corpus, allowing our solution to recover 20.1% accounts within one week at an average speed of 7200 non-identical passwords cracked per hour, compared to previous solutions such as oclHashcat (using default configuration), which cracks at an average speed of 28 and needs months to recover the same number of accounts with equal computing resources (thus are infeasible for a real-world attacker who would maximize the gain against the cracking cost). This implies an underestimated threat to slow-hash protected password dumps. Our method provides organizations with a better model of offline attackers and helps them better decide the hashing costs of slow-hash algorithms and detect potential vulnerable credentials before hackers do.<\/jats:p>","DOI":"10.3390\/sym11040450","type":"journal-article","created":{"date-parts":[[2019,4,2]],"date-time":"2019-04-02T03:21:26Z","timestamp":1554175286000},"page":"450","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Study on Massive-Scale Slow-Hash Recovery Using Unified Probabilistic Context-Free Grammar and Symmetrical Collaborative Prioritization with Parallel Machines"],"prefix":"10.3390","volume":"11","author":[{"given":"Tianjun","family":"Wu","sequence":"first","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Yuexiang","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Chi","family":"Wang","sequence":"additional","affiliation":[{"name":"VeriClouds Co., Seattle, WA 98105, USA"}]},{"given":"Rui","family":"Wang","sequence":"additional","affiliation":[{"name":"VeriClouds Co., Seattle, WA 98105, USA"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,1]]},"reference":[{"key":"ref_1","unstructured":"(2017, May 08). Why You Shouldn\u2019t Panic about Dropbox Leaking 68 Million Passwords. Available online: https:\/\/www.forbes.com\/sites\/thomasbrewster\/2016\/08\/31\/dropbox-hacked-but-its-not-thatbad\/#675839355576."},{"key":"ref_2","unstructured":"(2017, December 15). Lessons Learned from Cracking 4000 Ashley Madison Passwords. Available online: https:\/\/arstechnica.com\/informationtechnology\/2015\/08\/cracking-all-hacked-ashleymadison-passwords-could-take-a-lifetime\/."},{"key":"ref_3","unstructured":"(2017, November 22). Deep Dive into the Edmodo Data Breach. Available online: https:\/\/medium.com\/4iqdelvedeep\/deep-dive-into-theedmodo-data-breach-f1207c415ffb."},{"key":"ref_4","unstructured":"(2017, September 01). Hashcat. Available online: https:\/\/hashcat.net\/oclhashcat\/."},{"key":"ref_5","unstructured":"(2017, December 01). John the Ripper. Available online: http:\/\/www.openwall.com\/john\/."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Das, A., Bonneau, J., Caesar, M., Borisov, N., and Wang, X. (2014, January 23\u201326). The tangled web of password reuse. Proceedings of the NDSS 2014, San Diego, CA, USA.","DOI":"10.14722\/ndss.2014.23357"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wang, D., Zhang, Z., Wang, P., Yan, J., and Huang, X. (2016, January 24\u201328). Targeted online password guessing: An underestimated threat. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS 2016), Vienna, Austria.","DOI":"10.1145\/2976749.2978339"},{"key":"ref_8","unstructured":"Han, W., Li, Z., Ni, M., Gu, G., and Xu, W. (2016). Shadow attacks based on password reuses: A quantitative empirical view. IEEE Trans. Depend. Secur. Comput."},{"key":"ref_9","unstructured":"(2018, March 03). VeriClouds Whitepapers & Resources. Available online: https:\/\/www.vericlouds.com\/resources\/."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Weir, M., Aggarwal, S., de Medeiros, B., and Glodek, B. (2009, January 17\u201320). Password cracking using probabilistic context-free grammars. Proceedings of the 2009 30th IEEE Symposium on Security and Privacy, Berkeley, CA, USA.","DOI":"10.1109\/SP.2009.8"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Narayanan, A., and Shmatikov, V. (2005, January 7\u201311). Fast dictionary attacks on passwords using time-space tradeoff. Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS 2005), Alexandria, VA, USA.","DOI":"10.1145\/1102120.1102168"},{"key":"ref_12","unstructured":"Castelluccia, C., Durmuth, M., and Perito, D. (2012, January 5\u20138). Adaptive password-strength meters from Markov models. Proceedings of the 2012 Network and Distributed Systems Security Symposium, San Diego, CA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Ma, J., Yang, W., Luo, M., and Li, N. (2014, January 18\u201321). A study of probabilistic password models. Proceedings of the 2014 IEEE Symposium on Security and Privacy, San Jose, CA, USA.","DOI":"10.1109\/SP.2014.50"},{"key":"ref_14","unstructured":"Komanduri, S. (2016). Modeling the Adversary to Evaluate Password Strengh with Limited Samples. [Ph.D. Thesis, Carnegie Mellon University]."},{"key":"ref_15","unstructured":"Melicher, W., Ur, B., Segreti, S., Komanduri, S., Bauer, L., Christin, N., and Cranor, L. (2016, January 10\u201312). Fast, lean and accurate: Modeling password guessability using neural networks. Proceedings of the 25th USENIX Conference on Security Symposium, Austin, TX, USA."},{"key":"ref_16","unstructured":"Ur, B., Segreti, S.M., Bauer, L., Christin, N., Cranor, L.F., Komanduri, S., Kurilova, D., Mazurek, M.L., Melicher, W., and Shay, R. (2015, January 12\u201314). Measuring real-world accuracies and biases in modeling password guessability. Proceedings of the 24th USENIX Conference on Security Symposium (USENIX SEC 2015), Washington, DC, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Wang, D., and Wang, P. (2016, January 26\u201330). On the implications of Zipf\u2019s law in passwords. Proceedings of the European Symposium on Research in Computer Security, Heraklion, Greece.","DOI":"10.1007\/978-3-319-45744-4_6"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Monrose, F., and Reiter, M. (2010, January 4\u20138). The security of modern password expiration: An algorithmic framework and empirical analysis. Proceedings of the 17th ACM conference on Computer and Communications Security (CCS 2010), Chicago, IL, USA.","DOI":"10.1145\/1866307.1866328"},{"key":"ref_19","unstructured":"Wang, C., Jan, S.T.K., Hu, H., and Wang, G. (arXiv, 2017). Empirical analysis of password reuse and modification across online service, arXiv."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Harsha, B., and Blocki, J. (2018, January 24\u201326). Just in Time Hashing. Proceedings of the 2018 IEEE European Symposium on Security and Privacy (EuroS&P), London, UK.","DOI":"10.1109\/EuroSP.2018.00033"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Li, Y., Wang, H., and Sun, K. (2016, January 10\u201314). A study of personal information in human-chosen passwords and its security implications. Proceedings of the 35th Annual IEEE International Conference on Computer Communications (INFOCOM 2016), San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524583"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Oechslin, P. (2003, January 17\u201321). Making a faster cryptanalytic time-memory trade-off. Proceedings of the Annual International Cryptology Conference (CRYPTO 2003), Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-540-45146-4_36"},{"key":"ref_23","unstructured":"Provos, N., and Mazi\u00e8res, D. (1999, January 6\u201311). A future-adaptable password scheme. Proceedings of the USENIX Annual Technical Conference 1999 (FREENIX Track), Monterey, CA, USA."},{"key":"ref_24","unstructured":"Percival, C. (2018, May 10). Stronger Key Derivation via Sequential Memory-Hard Functions. Available online: http:\/\/www.tarsnap.com\/scrypt\/scrypt.pdf."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kaliski, B. (2018, April 06). PKCS #5: Password-Based Cryptography Specification Version 2.0. Available online: http:\/\/tools.ietf.org\/html\/rfc2898.","DOI":"10.17487\/RFC8018"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Biryukov, A., Dinu, D., and Khovratovich, D. (2016, January 21\u201324). Argon2: New generation of memory-hard functions for password hashing and other applications. Proceedings of the 2016 IEEE European Symposium on Security and Privacy (EuroS&P), Saarbrucken, Germany.","DOI":"10.1109\/EuroSP.2016.31"},{"key":"ref_27","unstructured":"Steube, J. (2017, December 16). PRINCE: Modern Password Guessing Algorithm. Available online: https:\/\/hashcat.net\/events\/p14-trondheim\/prince-attack.pdf."},{"key":"ref_28","unstructured":"Malvoni, K., Designer, S., and Knezovic, J. (2014, January 19). Are your passwords safe: Energy-efficient bcrypt cracking with low-Cost parallel hardware. Proceedings of the 8th USENIX Workshop on Offensive Technologies (WOOT 2014), San Diego, CA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Blocki, J., Harsha, B., and Zhou, S. (2018, January 20\u201324). On the economics of offline password cracking. Proceedings of the 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.","DOI":"10.1109\/SP.2018.00009"},{"key":"ref_30","unstructured":"Blocki, J., Harsha, B., Kang, S., Lee, S., Xing, L., and Zhou, S. (2018, May 10). Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions. Available online: https:\/\/eprint.iacr.org\/2018\/944."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Weir, M., Aggarwal, S., Collins, M., and Stern, H. (2010, January 4\u20138). Testing metrics for password creation policies by attacking large sets of revealed passwords. Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS 2010), Chicago, IL, USA.","DOI":"10.1145\/1866307.1866327"},{"key":"ref_32","unstructured":"(2018, May 10). Min-Max Heap. Available online: https:\/\/en.wikipedia.org\/wiki\/Min-max_heap."},{"key":"ref_33","unstructured":"(2018, April 03). Skip List. Available online: https:\/\/en.wikipedia.org\/wiki\/Skip_list."},{"key":"ref_34","unstructured":"(2018, May 10). Levenshtein Distance. Available online: https:\/\/en.wikipedia.org\/wiki\/Levenshtein_distance."},{"key":"ref_35","unstructured":"(2018, April 03). Heapsort. Available online: https:\/\/en.wikipedia.org\/wiki\/Heapsort."},{"key":"ref_36","unstructured":"(2017, December 11). Once Seen as Bulletproof, 11 Million+ Ashley Madison Passwords Already Cracked. Available online: https:\/\/arstechnica.com\/informationtechnology\/2015\/09\/once-seen-as-bulletproof-11-million-ashley-madison-passwords-already-cracked\/."},{"key":"ref_37","unstructured":"(2017, August 22). AWS EC2. Available online: https:\/\/aws.amazon.com\/ec2\/?ft=n."},{"key":"ref_38","unstructured":"(2018, May 10). Amazon EC2 Instance Types. Available online: https:\/\/aws.amazon.com\/ec2\/instance-types\/?nc1=h_ls."},{"key":"ref_39","unstructured":"Ding, Z., Jia, Y., Zhou, B., and Han, Y. (2013). Mining topical influencers based on the multi-relational network in micro-blogging sites. China Commun."},{"key":"ref_40","unstructured":"Wang, P., Lu, K., Li, G., and Zhou, X. (2018). DFTracker: Detecting double-fetch bugs by multi-taint parallel tracking. Front. Comput. Sci., 1\u201317."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/s10766-014-0304-y","article-title":"Collaborative technique for concurrency bug detection","volume":"43","author":"Wu","year":"2015","journal-title":"Int. J. Parallel Program."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Wu, T., and Yang, Y. (2019). Detecting android inter-app data leakage via compositional concolic walking. J. Autosoft.","DOI":"10.31209\/2019.100000079"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1007\/s11227-015-1418-8","article-title":"Detecting harmful data races through parallel verification","volume":"71","author":"Wu","year":"2015","journal-title":"J. Supercomput."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/4\/450\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:42:02Z","timestamp":1760186522000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/4\/450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,1]]},"references-count":43,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["sym11040450"],"URL":"https:\/\/doi.org\/10.3390\/sym11040450","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2019,4,1]]}}}