High dictionary compression for proactive password checking

ABSTRACT

The important problem of user password selection is addressed and a new proactive password-checking technique is presented. In a training phase, a decision tree is generated based on a given dictionary of weak passwords. Then, the decision tree is used to determine whether a user password should be accepted. Experimental results described here show that the method leads to a very high dictionary compression (up to 1000 to 1) with low error rates (of the order of 1%). A prototype implementation, called ProCheck, is made available online. We survey previous approaches to proactive password checking, and provide an in-depth comparison.

REFERENCES

• 1: BEIMEL, A., BERGADANO, F., BSHOUTY, N., KUSHILEVITZ, E., AND VARRICCHIO, S. 1996. Learning Sat-k-DNF formulas from membership queries. In Proceedings of the Symposium on Foundations of Computer Science (FOCS).
• 2: F. Bergadano , D. Catalano , S. Varricchio, Learning Sat-k-DNF formulas from membership queries, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.126-130, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237845]
• 3: F. Bergadano , B. Crispo , G. Ruffo, Proactive password checking with decision trees, Proceedings of the 4th ACM conference on Computer and communications security, p.67-77, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266437]
• 4: BISHOP, M. 1990. An extendible password checker. In Proceedings of the USENIX Workshop on Security (Portland, OR). USENIX Assoc., Berkeley, CA.
• 5: BISHOP, M. 1992. Proactive password checking. In Proceedings of the Fourth Workshop on Computer Security Incident Handling.
• 6: BSHOUTY, N. 1993. Exact learning Boolean functions via the monotone theory. In Proceedings of the Symposium on Foundations of Computer Science (FOCS).
• 8: DAVIES, C. AND GANESAN, R. 1993. Bapasswd: A new proactive password checker. In Proceedings of the 16th National Conference on Computer Security (Baltimore, MD, Sept. 20-23). 1-12.
• 9: DIETTERICH, T., KEARNS, M., AND MANSOUR, Y. 1996. Applying the weak learning framework to understand and improve C4.5. In Proceedings of the International Conference on Machine Learning (Bari, Italy), L. Saitta, Ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, 96-104.
• 10: FARMER, D. AND SPAFFORD, E. H. 1990. The COPS security checker system. In Proceedings of the Summer Conference on USENIX (Anaheim, CA). USENIX Assoc., Berkeley, CA, 165-170.
• 11: HAUGH, J. F. 1991. Package including shadow password implementation. USENET News.
• 12: KLEIN, D.V. 1990. "Foiling the cracker:" A survey of, and improvements to, password security. In Proceedings of the USENIX Workshop on Security (Portland, OR). USENIX Assoc., Berkeley, CA.
• 13: Alberto Martelli , Ugo Montanari, Optimizing decision trees through heuristically guided search, Communications of the ACM, v.21 n.12, p.1025-1039, Dec. 1978 [doi>10.1145/359657.359664]
• 14: Fabian Monrose , Aviel Rubin, Authentication via keystroke dynamics, Proceedings of the 4th ACM conference on Computer and communications security, p.48-56, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266434]
• 15: MUFFETT, A. D. 1991. Crack 4.0a. USENETNews.
• 16: NAGLE, J. B. 1988. An obvious password detector. USENET News 16, 60.
• 17: NEUMAN, B. C. AND TSO, T. 1994. Kerberos: An authentication service for computer networks. IEEE Trans. Commun. 32, 33-38.
• 18: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 19: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 20: J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
• 21: J. R. Quinlan, Simplifying decision trees, International Journal of Man-Machine Studies, v.27 n.3, p.221-234, September 1987 [doi>10.1016/S0020-7373(87)80053-6]
• 22: RISSANEN, g. 1986. Stochastic complexity and modeling. Ann. Stat. 14, 3, 1080-1100.
• 23: SAITTA, L., Ed. 1996. Proceedings of the International Conference on Machine Learning. (Bari, Italy). Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 24: Eugene H. Spafford, OPUS: preventing weak password choices, Computers and Security, v.11 n.3, p.273-278, May 1992 [doi>10.1016/0167-4048(92)90207-8]
• 25: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Experimentation, Management, Performance, Security

Keywords:
access control, decision trees, password selection, proactive password checking