Dictionary attack
|
|
A dictionary attack refers to the general technique of trying to guess some secret by running through a list of likely possibilities, often a list of words from a dictionary. It contrasts to a brute force attack in which all possibilities are tried. The attack works because users often choose easy-to-guess passwords, even after being exhorted against doing so.
Dictionary (and brute force) attacks may be applied in two main situations:
- in cryptanalysis, in trying to determine the key needed to decrypt a given piece of encrypted data;
- in computer security, in trying to gain unauthorized access to a computer system by guessing passwords, and possibly usernames as well.
The latter case is sometimes known as a Rumpelstiltskin attack, and can be greatly reduced in effectiveness by tarpitting the connection, or even blocking login attempts and disabling the account, after some number of failed authentication attempts. 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 and use a dictionary attack to try to determine what the password was. Or an attacker may be able to get 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 now easily accessible on the Internet so using little known foreign words (eg Maori words) no longer helps prevent dictionary attacks in principle, and to a considerable extent in practice.
It is possible to achieve a time-space tradeoff through precomputation by encrypting and storing a list of encrypted dictionary words, sorting 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 and can make precomputation effectively impossible if 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 a dictionary attack; eins, the word for the number one, appeared in 90% of all Enigma messages, as the Enigma machine's keyboard had no numerals (some might classify this as a known plaintext attack).
Clifford Stoll's book, The Cuckoo's Egg an account of a dictionary attack against the encrypted passwords kept in the passwd file in Unix systems, and of the reaction to the successful attack by the man (Robert Morris, Sr.) who invented the one-way encryption system used for login passwords.
See also
External links
Well known examples of dictionary attack software tools:
- John the Ripper (http://www.openwall.com/john/)
- L0phtCrack (http://www.atstake.com/research/lc3/)
- US Secret Service use a distributed dictionary attack on suspect's password protecting encryption keys (http://www.washingtonpost.com/wp-dyn/articles/A6098-2005Mar28.html)ja:辞書攻撃