Dictionary attack

From Wikipedia, the free encyclopedia

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 a large number of possibilities. In contrast with a brute force attack, where all possibilities are searched through exhaustively, a dictionary attack only tries possibilities which are most likely to succeed, typically derived from a list of words in a dictionary. Generally, dictionary attacks succeed because most people have a tendency to choose passwords which are easy to remember, and typically choose words taken from their native language.

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 effectiveness 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, 3 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.

There is some commonality between these situations. For instance, an eavesdropper may record a challenge-response authentication exchange between two parties and use a dictionary attack to try to determine what the password was. Or, an attacker may be able to obtain a copy of the list of encrypted passwords from a remote system; assuming the users are mostly English speakers, the attacker could attempt to guess the passwords at their leisure, by encrypting each of a list of English words and comparing each encryption against the stored encrypted version of users' passwords. Since users often choose easily guessed passwords, this has historically succeeded about 4 times out of 10 when a reasonably large list is used. Dictionaries for most human languages (even those no longer used) are easily accessible on the Internet, meaning even the use of foreign words is practically useless in preventing dictionary attacks.

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 large amount of storage and often a considerable amount of preparation time, but makes the actual attack almost instantaneous. It is particularly effective when a large number of passwords are to be cracked at once. Salting is a technique that forces the encrypted dictionary to be recomputed for each password sought, potentially making precomputation impossible, provided the salt is large enough.

An example of a dictionary attack occurred in the Second World War, when British codebreakers working on German Enigma-ciphered messages used the German word eins as part of the attack; eins, the word for the number one, appeared in 90% of all ciphertexts, as the Enigma machine's keyboard had no numerals (some might classify this as a known plaintext attack).

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.