Human-chosen passwords are the dominant form of authentication systems. Passwords strength estimators are used to help users avoid picking weak passwords by predicting how many attempts a password cracker would need until it finds a given password.
In this paper we propose a novel password strength estimator, called PESrank, which accurately models the behavior of a powerful password cracker. PESrank calculates the rank of a given password in an optimal descending order of likelihood. PESrank estimates a given password’s rank in fractions of a second – without actually enumerating the passwords – so it is practical for online use. It also has a training time that is drastically shorter than previous methods. Moreover, PESrank is efficiently tweakable to allow model personalization in fractions of a second, without the need to retrain the model; and it is explainable: it is able to provide information on why the password has its calculated rank, and gives the user insight on how to pick a better password.
We implemented PESrank in Python and conducted an extensive evaluation study of it. We also integrated it into the registration page of a course at our university. Even with a model based on 905 million passwords, the response time was well under 1 second, with up to a 1-bit accuracy margin between the upper bound and the lower bound on the rank.
D.Agrawal, B.Archambeault, J.R.Rao and P.Rohatgi, The EM side-channel(s), in: Cryptographic Hardware and Embedded Systems-CHES 2002, 2003, pp. 29–45. doi:10.1007/3-540-36400-5_4.
2.
A.Bogdanov, I.Kizhvatov, K.Manzoor, E.Tischhauser and M.Witteman, Fast and memory-efficient key recovery in side-channel attacks, in: Selected Areas in Cryptography (SAC), 2015.
3.
W.Burr, D.Dodson and W.Polk, Electronic authentication guideline, Technical report, National Institute of Standards and Technology, 2004.
4.
Carnegie Mellon University Password Research Group, 2019, Password guessability service (pgs), https://pgs.ece.cmu.edu/.
5.
C.Castelluccia, A.Chaabane, M.Dürmuth and D.Perito, When privacy meets security: Leveraging personal information for password cracking, 2013, arXiv preprint arXiv:1304.6584.
6.
C.Castelluccia, M.Dürmuth and D.Perito, Adaptive password-strength meters from Markov models, in: NDSS, 2012.
7.
A.Das, J.Bonneau, M.Caesar, N.Borisov and X.Wang, The tangled web of password reuse, in: NDSS’14, 2014, pp. 23–26.
8.
L.David and A.Wool, A bounded-space near-optimal key enumeration algorithm for multi-subkey side-channel attacks, in: Proc. RSA Conference Cryptographers’ Track (CT-RSA’17), LNCS, Vol. 10159, Springer Verlag, San Francisco, 2017, pp. 311–327.
9.
L.David and A.Wool, Rank estimation with bounded error via exponential sampling, Journal of Cryptographic Engineering (2021). doi:10.1007/s13389-021-00269-4.
10.
L.David and A.Wool, PESrank Python implementation, 2020, https://github.com/lirondavid/PESrank.
11.
X.de Carné de Carnavalet and M.Mannan, From very weak to very strong: Analyzing password-strength meters, in: NDSS, Vol. 14, 2014, pp. 23–26.
12.
M.Dell’Amico and M.Filippone, Monte Carlo strength evaluation: Fast and reliable password checking, in: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ACM, 2015, pp. 158–169. doi:10.1145/2810103.2813631.
13.
M.Dell’Amico, P.Michiardi and Y.Roudier, Password strength: An empirical analysis, in: 2010 Proceedings IEEE INFOCOM, IEEE, 2010, pp. 1–9.
14.
M.Dürmuth, F.Angelstorf, C.Castelluccia, D.Perito and A.C.Omen, Faster password guessing using an ordered Markov enumerator, in: International Symposium on Engineering Secure Software and Systems, Springer, 2015, pp. 119–132. doi:10.1007/978-3-319-15618-7_10.
15.
P.Gage Kelley, S.Komanduri, M.L.Mazurek, R.Shay, T.Vidas, L.Bauer, N.Christin, L.F.Cranor and J.Lopez, Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms, in: 2012 IEEE Symposium on Security and Privacy, IEEE, 2012, pp. 523–537.
16.
K.Gandolfi, C.Mourtel and F.Olivier, Electromagnetic analysis: Concrete results, in: Cryptographic Hardware and Embedded Systems – CHES 2001, Springer, 2001, pp. 251–261. doi:10.1007/3-540-44709-1_21.
17.
C.Glowacz, V.Grosso, R.Poussier, J.Schueth and F.-X.Standaert, Simpler and more efficient rank estimation for side-channel security assessment, in: Fast Software Encryption, 2015, pp. 117–129. doi:10.1007/978-3-662-48116-5_6.
18.
D.Goodin, Anatomy of a hack: How crackers ransack passwords like “qeadzcwrsfxv1331”, Ars Technica (2013).
19.
P.A.Grassi, J.L.Fenton, E.M.Newton, R.A.Perlner, A.R.Regenscheid, W.E.Burr, J.P.Richer, N.B.Lefkovitz, J.M.Danker, Y.-Y.Choonget al., NIST Special Publication 800-63b: Digital Identity Guidelines, 2017.
20.
Y.Guo and Z.Zhang, LPSE: Lightweight password-strength estimation for password meters, Computers & Security73 (2018), 507–518. doi:10.1016/j.cose.2017.07.012.
B.Hitaj, P.Gasti, G.Ateniese and F.P.-C.Passgan, A deep learning approach for password guessing, in: International Conference on Applied Cryptography and Network Security, Springer, 2019, pp. 217–237. doi:10.1007/978-3-030-21568-2_11.
23.
S.Houshmand and S.Aggarwal, Using personal information for targeted attacks in grammar based probabilistic password cracking, in: IFIP Advances in Information and Communication Technology, Vol. 511, 2017.
24.
Jason, 1.4 billion leaked passwords in over 40GB of data, 2019, http://stuffjasondoes.com/2019/01/30/1-4-billion-leaked-passwords-in-over-40gb-of-data/.
25.
P.Kocher, J.Jaffe and B.Jun, Differential power analysis, in: Advances in Cryptology – CRYPTO’99, Springer, 1999, pp. 388–397. doi:10.1007/3-540-48405-1_25.
26.
P.C.Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, in: Advances in Cryptology – CRYPTO’96, 1996, pp. 104–113. doi:10.1007/3-540-68697-5_9.
27.
S.Komanduri, Modeling the adversary to evaluate password strength with limited samples, PhD thesis, Carnegie Mellon University, 2016.
28.
Y.Li, H.Wang and K.Sun, Personal information in passwords and its security implications, IEEE Transactions on Information Forensics and Security12(10) (2017), 2320–2333. doi:10.1109/TIFS.2017.2705627.
29.
Z.Li, W.Han and W.Xu, A large-scale empirical analysis of Chinese web passwords, in: 23rd USENIX Security Symposium, 2014, pp. 559–574.
30.
D.Liron and A.Wool, Poly-logarithmic side channel rank estimation via exponential sampling, in: Cryptographers’ Track at the RSA Conference, Springer, 2019, pp. 330–349.
31.
D.Liron and A.Wool, An explainable online password strength estimator, in: European Symposium on Research in Computer Security, Springer, 2021, pp. 285–304.
32.
J.Ma, W.Yang, M.Luo and N.Li, A study of probabilistic password models, in: 2014 IEEE Symposium on Security and Privacy, IEEE, 2014, pp. 689–704. doi:10.1109/SP.2014.50.
33.
D.P.Martin, L.Mather and E.Oswald, Two sides of the same coin: Counting and enumerating keys post side-channel attacks revisited, in: Cryptographers’ Track at the RSA Conference, Springer, 2018, pp. 394–412.
34.
D.P.Martin, J.F.O’Connell, E.Oswald and M.Stam, Counting keys in parallel after a side channel attack, in: Advances in Cryptology–ASIACRYPT 2015, Springer, 2015, pp. 313–337. doi:10.1007/978-3-662-48800-3_13.
35.
W.Melicher, B.Ur, S.M.Segreti, S.Komanduri, L.Bauer, N.Christin and L.F.Cranor, Fast, lean, and accurate: Modeling password guessability using neural networks, in: Proc. 25th USENIX Security Symposium, 2016, pp. 175–191.
36.
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, ACM, 2005, pp. 364–372. doi:10.1145/1102120.1102168.
37.
J.OpenWall, the ripper password cracker, 2019, http://www.openwall.com/john.
38.
B.Pal, T.Daniel, R.Chatterjee and T.Ristenpart, Beyond credential stuffing: Password similarity models using neural networks, in: 2019 IEEE Symposium on Security and Privacy (SP), IEEE, 2019, pp. 417–434. doi:10.1109/SP.2019.00056.
39.
R.Poussier, F.-X.Standaert and V.Grosso, Simple key enumeration (and rank estimation) using histograms: An integrated approach, in: Proc. 18th Cryptographic Hardware and Embedded Systems – CHES 2016, Springer, 2016, pp. 61–81. doi:10.1007/978-3-662-53140-2_4.
40.
J.-J.Quisquater and D.Samyde, Electromagnetic analysis (EMA): Measures and counter-measures for smart cards, in: Smart Card Programming and Security, Springer, 2001, pp. 200–210. doi:10.1007/3-540-45418-7_17.
41.
R.Shay, S.Komanduri, P.Gage Kelley, P.Giovanni Leon, M.L.Mazurek, L.Bauer, N.Christin and L.F.Cranor, Encountering stronger password requirements: User attitudes and behaviors, in: Proceedings of the Sixth Symposium on Usable Privacy and Security (SOUPS’10), ACM, 2010, p. 2.
42.
B.Ur, F.Alfieri, M.Aung, L.Bauer, N.Christin, J.Colnago, L.F.Cranor, H.Dixon, P.Emami Naeini, H.Habib, N.Johnson and W.Melicher, Design and evaluation of a data-driven password meter, in: Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems, ACM, 2017, pp. 3775–3786.
43.
B.Ur, P.Gage Kelley, S.Komanduri, J.Lee, M.Maass, M.L.Mazurek, T.Passaro, R.Shay, T.Vidas, L.Baueret al., How does your password measure up? The effect of strength meters on password creation, in: 21st USENIX Security Symposium, 2012, pp. 65–80.
44.
B.Ur, F.Noma, J.Bees, S.M.Segreti, R.Shay, L.Bauer, N.Christin and L.F.Cranor, “i added’!’at the end to make it secure”: Observing password creation in the lab, in: Eleventh Symposium on Usable Privacy and Security ({SOUPS} 2015), 2015, pp. 123–140.
45.
B.Ur, S.M.Segreti, L.Bauer, N.Christin, L.F.Cranor, S.Komanduri, D.Kurilova, M.L.Mazurek, W.Melicher and R.Shay, Measuring real-world accuracies and biases in modeling password guessability, in: Proc. 24th USENIX Security Symposium, 2015, pp. 463–481.
46.
R.Veras, C.Collins and J.Thorpe, On semantic patterns of passwords and their security impact, in: NDSS, 2014.
47.
N.Veyrat-Charvillon, B.Gérard, M.Renauld and F.-X.Standaert, An optimal key enumeration algorithm and its application to side-channel attacks, in: International Conference on Selected Areas in Cryptography, Springer, 2012, pp. 390–406.
48.
D.Wang, Z.Zhang, P.Wang, J.Yan and X.Huang, Targeted online password guessing: An underestimated threat, in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016, pp. 1242–1254.
49.
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, ACM, 2010, pp. 162–175. doi:10.1145/1866307.1866327.
50.
M.Weir, S.Aggarwal, B.De Medeiros and B.Glodek, Password cracking using probabilistic context-free grammars, in: 2009 30th IEEE Symposium on Security and Privacy, IEEE, 2009, pp. 391–405. doi:10.1109/SP.2009.8.
