Fast dictionary attacks on passwords using time-space tradeoff

Arvind Narayanan, Vitaly Shmatikov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

234 Scopus citations

Abstract

Human-memorable passwords are a mainstay of computer security. To decrease vulnerability of passwords to bruteforce 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 × 10 9 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.

Original languageEnglish (US)
Title of host publicationCCS 2005 - Proceedings of the 12th ACM Conference on Computer and Communications Security
Pages364-372
Number of pages9
DOIs
StatePublished - 2005
Externally publishedYes
EventCCS 2005 - 12th ACM Conference on Computer and Communications Security - Alexandria, VA, United States
Duration: Nov 7 2005Nov 11 2005

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Other

OtherCCS 2005 - 12th ACM Conference on Computer and Communications Security
CountryUnited States
CityAlexandria, VA
Period11/7/0511/11/05

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Keywords

  • Cryptanalysis
  • Dictionary Attack
  • Markov Models
  • Passwords
  • Time-Space Tradeoff

Fingerprint Dive into the research topics of 'Fast dictionary attacks on passwords using time-space tradeoff'. Together they form a unique fingerprint.

Cite this