Dictionary attack

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.

A dictionary attack uses a brute-force technique of successively trying all the words in an exhaustive list (from a pre-arranged list of values). In contrast with a normal brute force attack, where a large proportion key space is searched systematically, a dictionary attack tries only those possibilities which are most likely to succeed, typically derived from a list of words in a dictionary. Generally, dictionary attacks succeed because many people have a tendency to choose passwords which are short (7 characters or fewer), single words found in dictionaries or simple, easily-predicted variations on words, such as appending a digit.

Contents

[edit] Use

Dictionary attacks may be applied in two main situations:

  • in cryptanalysis, in trying to determine the decryption key for a given piece of ciphertext;
  • in computer security, in trying to circumvent an authentication mechanism for accessing a computer system by guessing passwords.

In the latter case, the effect of a dictionary attack can be greatly reduced by limiting the number of authentication attempts that can be performed each minute, and even blocking further attempts after a threshold of failed authentication attempts is reached. Generally, six attempts is considered sufficient to cope with mistakes made by legitimate users; beyond that, one can safely assume that the user is a malicious attacker.

However many systems store a hashed version of the password and make it available under certain circumstances, such as a challenge-response authentication exchange between two parties. If an attacker can obtain the hashed password, they can test guessed passwords rapidly, often at a rate of tens or hundreds of millions of guesses per second. [1] The rate of guessing can be sharply reduced by using a key derivation function that is computationally intensive, such as PBKDF2. Since users often choose easily guessed passwords, this has historically succeeded more than two times out of ten when a reasonably large list is used. Lists of commonly selected passwords are widely available on the Internet as are dictionaries for most human languages (even those no longer used), meaning even the use of foreign words has limited value in preventing dictionary attacks.

Spammers often use a form of dictionary attack, sometimes known as a Directory Harvest Attack, for e-mail address harvesting. For example, a spammer may try sending messages to adam@example.com, barbara@example.com, carl@example.com, etc. Any addresses to which messages are delivered, as opposed to being bounced back, can be added to the spammer's list of known-valid addresses.

Clifford Stoll's book, The Cuckoo's Egg, contains an account of a dictionary attack against the encrypted passwords kept in the passwd file on Unix systems, and of the reaction to the successful attack by the man (Robert Morris) who invented the one-way encryption system used for login passwords.[clarification needed]

[edit] Pre-computed dictionary attack

It is possible to achieve a time-space tradeoff through precomputation by encrypting and storing a list of encrypted dictionary words, sorted by the encrypted value. This requires a considerable amount of preparation time, but makes the actual attack almost instantaneous. The storage requirements for the pre-computed tables were once a major cost, but are less of an issue today due to the rapid improvements in hard drive technology. Pre-computed dictionary attacks are particularly effective when a large number of passwords are to be cracked at once. A more refined approach involves the use of rainbow tables. Salting is a technique that forces the encrypted dictionary to be recomputed for each password sought, potentially making precomputation infeasable, provided the salt value is large enough.

[edit] See also

[edit] Examples

Well known examples of dictionary attack software tools:

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Dictionary_attack"
Personal tools