Fast dictionary attacks on passwords using time-space tradeoff

ABSTRACT

Human-memorable passwords are a mainstay of computer security. To decrease vulnerability of passwords to brute-force dictionary attacks, many organizations enforce complicated password-creation rules and require that passwords include numerals and special characters. We demonstrate that as long as passwords remain human-memorable, they are vulnerable to "smart-dictionary" attacks even when the space of potential passwords is large.Our first insight is that the distribution of letters in easy-to-remember passwords is likely to be similar to the distribution of letters in the users' native language. Using standard Markov modeling techniques from natural language processing, this can be used to dramatically reduce the size of the password space to be searched. Our second contribution is an algorithm for efficient enumeration of the remaining password space. This allows application of time-space tradeoff techniques, limiting memory accesses to a relatively small table of "partial dictionary" sizes and enabling a very fast dictionary attack.We evaluated our method on a database of real-world user password hashes. Our algorithm successfully recovered 67.6% of the passwords using a 2 x 10⁹ search space. This is a much higher percentage than Oechslin's "rainbow" attack, which is the fastest currently known technique for searching large keyspaces. These results call into question viability of human-memorable character-sequence passwords as an authentication mechanism.

REFERENCES

• 1: MD5 online cracking using rainbow tables. http://www.passcracking.com/.
• 2: M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key exchange secure against dictionary attacks. In Proc. EUROCRYPT '00, volume 1807 of LNCS, pages 139--155. Springer, 2000.
• 3: Steven M. Bellovin , Michael Merritt, Encrypted Key Exchange: Password-Based Protocols SecureAgainst Dictionary Attacks, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.72, May 04-06, 1992
• 4: A. Booker. The Nth prime algorithm. http://primes.utm.edu/nthprime/algorithm.php, 2005.
• 5: J. Borst, B. Preneel, and J. Vandewalle. On the time-memory tradeoff between exhaustive key search and table precomputation. In Proc. 19th Symposium on Information Theory in the Benelux, pages 111--118, 1998.
• 6: V. Boyko, P. MacKenzie, and S. Patel. Provably secure password-authenticated key exchange using Diffie-Hellman. In Proc. EUROCRYPT '00, volume 1807 of LNCS, pages 156--171. Springer, 2000.
• 7: W. Burr, D. Dodson, and W. Polk. Electronic authentication guideline. NIST Special Publication 800-63, 2004.
• 8: D. Davis, F. Monrose, and M. Reiter. On user choice in graphic password schemes. In Proc. 13th USENIX Security Symposium, pages 151--164. USENIX, 2004.
• 9: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 10: David C. Feldmeier , Philip R. Karn, UNIX Password Security - Ten Years Later, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.44-63, August 20-24, 1989
• 11: Amos Fiat , Moni Naor, Rigorous time/space tradeoffs for inverting functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.534-541, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103473]
• 12: G. D. Forney. The Viterbi algorithm. Proceedings of the IEEE, 61(3):268--278, 1973.
• 13: Craig Gentry , Philip Mackenzie , Zulfikar Ramzan, Password authenticated key exchange using hidden smooth subgroups, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102160]
• 14: 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
• 15: T. L. Griffiths and J. B. Tenenbaum. Probability, algorithmic complexity, and subjective randomness. In Proceedings of the 25th Annual Conference of the Cognitive Science Society, 2003.
• 16: T. L. Griffiths and J. B. Tenenbaum. From algorithmic to subjective randomness. In Advances in Neural Information Processing Systems 16, 2004.
• 17: M. Hellman. A cryptanalytic time-memory tradeoff. IEEE Transactions on Information Theory, 26:401--406, 1980.
• 18: I. Jermyn, A. Mayer, F. Monrose, M. Reiter, and A. Rubin. The design and analysis of graphical passwords. In Proc. 8th USENIX Security Symposium, pages 135--150. USENIX, 1999.
• 19: Jonathan Katz , Rafail Ostrovsky , Moti Yung, Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.475-494, May 06-10, 2001
• 20: B. Kerbs. DNA key to decoding human factor. The Washington Post, March 28, 2005. http://www.washingtonpost.com/wp-dyn/articles/A6098-2005Mar28.html.
• 21: K. Kusuda and T. Matsumoto. Optimization of time-memory trade-off cryptanalysis and its application to DES, FEAL-32 and Skipjack. IEICE Transactions on Fundamentals, E79-A(1):35--48, 1996.
• 22: K. Kusuda and T. Matsumoto. Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size. TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1999.
• 23: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 24: Stefan Lucks, Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys, Proceedings of the 5th International Workshop on Security Protocols, p.79-90, April 07-09, 1997
• 25: G. A. Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological Review, 63:81--97, 1956.
• 26: F. Monrose, M. Reiter, and S. Wetzel. Password hardening based on keystroke dynamics. International Journal of Information Security, 1(2):69--93, 2002.
• 27: 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]
• 28: P. Oechslin. Making a faster cryptanalytic time-memory trade-off. In Proc. CRYPTO '03, volume 2729 of LNCS, pages 617--630. Springer, 2003.
• 29: Openwall Project. John the Ripper password cracker. http://www.openwall.com/john/, 2005.
• 30: Openwall Project. Wordlists collection. http://www.openwall.com/wordlists/, 2005.
• 31: Benny Pinkas , Tomas Sander, Securing passwords against dictionary attacks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586133]
• 32: L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257--286, 1989.
• 33: Zhu Shuanglei. Project RainbowCrack. http://www.antsight.com/zsl/rainbowcrack/, 2005.
• 34: Francois-Xavier Standaert , Gael Rouvroy , Jean-Jacques Quisquater , Jean-Didier Legat, A Time-Memory Tradeoff Using Distinguished Points: New Analysis & FPGA Results, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.593-609, August 13-15, 2002
• 35: S. Stubblebine and P. van Oorschot. Addressing online dictionary attacks with login histories and humans-in-the-loop. In Proc. Financial Cryptography, volume 3110 of LNCS, pages 39--53. Springer, 2004.
• 36: J. Thorpe and P. van Oorschot. Graphical dictionary and the memorable space of graphical passwords. In Proc. 13th USENIX Security Symposium, pages 135--150. USENIX, 2004.

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)
          Subjects: Authentication

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

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

General Terms:
Security

Keywords:
Markov models, cryptanalysis, dictionary attack, passwords, time-space, tradeoff