Securing passwords against dictionary attacks

ABSTRACT

The use of passwords is a major point of vulnerability in computer security, as passwords are often easy to guess by automated programs running dictionary attacks. Passwords remain the most widely used authentication method despite their well-known security weaknesses. User authentication is clearly a practical problem. From the perspective of a service provider this problem needs to be solved within real-world constraints such as the available hardware and software infrastructures. From a user's perspective user-friendliness is a key requirement.In this paper we suggest a novel authentication scheme that preserves the advantages of conventional password authentication, while simultaneously raising the costs of online dictionary attacks by orders of magnitude. The proposed scheme is easy to implement and overcomes some of the difficulties of previously suggested methods of improving the security of user authentication schemes.Our key idea is to efficiently combine traditional password authentication with a challenge that is very easy to answer by human users, but is (almost) infeasible for automated programs attempting to run dictionary attacks. This is done without affecting the usability of the system. The proposed scheme also provides better protection against denial of service attacks against user accounts.

REFERENCES

• 1: Alta Vista, submission of new urls. http://addurl.altavista.com/sites/addurl/newurl
• 2: Allison L. Coates, Pessimal Print: A Reverse Turing Test, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.1154, September 10-13, 2001
• 3: M., Proactive Password Checking, 4th Workshop on Computer Security Incident Handling, August 1992.
• 4: N. Bohm, I. Brown, B. Gladman, Electronic Commerce: Who Carries the Risk of Fraud?, 2000 (3) The Journal of Information, Law and Technology. http://elj.warwick.ac.uk/jilt/00-3/bohm.html
• 5: Maurizio Kliban Boyarsky, Public-key cryptography and password protocols: the multi-user case, Proceedings of the 6th ACM conference on Computer and communications security, p.63-72, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319719]
• 6: The CAPTCHA Project. http://www.captcha.net/
• 7: The CAPTCHA Project: Gimpy. http://www.captcha.net/gimpy.html
• 8: Hackers find new way to bilk eBay users, CNET news.com, March 25, 2002.
• 9: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 10: K. Fu, E. Sit, K. Smith, and N. Feamster, Dos and Don'ts of Client Authentication on the Web, 10th USENIX Security Symp., August 2001.
• 11: Oded Goldreich , Yehuda Lindell, Session-Key Generation Using Human Passwords Only, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.408-432, August 19-23, 2001
• 12: Shai Halevi , Hugo Krawczyk, Public-key cryptography and password protocols, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.230-268, Aug. 1999 [doi>10.1145/322510.322514]
• 13: I. Jermyn, A. Mayer, F. Monrose, M.K. Reiter and A.D. Rubin. The design and analysis of graphical passwords. 8th USENIX Security Symp., August 1999.
• 14: M.D. Lillibridge, M. Abadi, K. Bharat, and A.Z. Broder. Method for selectively restricting access to computer systems. U.S. Patent 6,195,698 (2001).
• 15: D.V. Klein, Foiling the Cracker: A Survey of, and Improvements to, Password Security, 2nd USENIX Unix Security Workshop, 1990, pp.5--14.
• 16: Philip D. MacKenzie, More Efficient Password-Authenticated Key Exchange, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.361-377, April 08-12, 2001
• 17: 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]
• 18: F. Monrose, M. Reiter and S. Wetzel Password hardening based on keystroke dynamics, to appear in the International Journal of Information Security, Springer, 2002.
• 19: Robert Morris , Ken Thompson, Password security: a case history, Communications of the ACM, v.22 n.11, p.594-597, Nov. 1979 [doi>10.1145/359168.359172]
• 20: M. Naor, Verification of a human in the loop, or Identification via the Turing test, Manuscript (1996). \verb+http://www.wisdom.weizmann.ac.il/naor/PAPERS/+\verb+human_abs.html+
• 21: Paypal, new account reg. http://www.paypal.com.
• 22: J. Xu, R. Lipton, I. Essa, M.-H. Sung, Mandatory human participation: A new scheme for building secure systems, Georgia Institute of Technology Technical Report GIT-CC-01-09, 2001.
• 23: A. Perrig and R, Dhamija, Dj Vu: A User Study Using Images for Authentication, 9th Usenix security Symp., August 2000.
• 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: Workshop on Human Interactive Proofs http://www.parc.xerox.com/istl/groups/did/HIP2002/
• 26: Yahoo!, new account registration.

INDEX TERMS

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

General Terms:
Security