Dictionary attack
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 likely possibilities.
, 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 for example a dictionary (hence the phrase dictionary attack) or a bible etc. Generally, dictionary attacks succeed because many people have a tendency to choose password
s which are short (7 characters or fewer), single words found in dictionaries or simple, easily-predicted variations on words, such as appending a digit.
of dictionary words, and storing these in a database using the hash as the key
. This requires a considerable amount of preparation time, but allows the actual attack to be executed faster. The storage requirements for the pre-computed tables were once a major cost, but are less of an issue today because of the low cost of disk storage. Pre-computed dictionary attacks are particularly effective when a large number of passwords are to be cracked. The pre-computed dictionary need only be generated once, and when it is completed, password hashes can be looked up almost instantly at any time to find the corresponding password. A more refined approach involves the use of rainbow table
s, which reduce storage requirements at the cost of slightly longer lookup times. See LM hash
for an example of an authentication system compromised by such an attack.
Pre-computed dictionary attacks can be thwarted by the use of salt
, a technique that forces the hash dictionary to be recomputed for each password sought, making precomputation
infeasible provided the number of possible salt values is large enough.
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
and computer security
Computer security
Computer security is a branch of computer technology known as information security as applied to computers and networks. The objective of computer security includes protection of information and property from theft, corruption, or natural disaster, while allowing the information and property to...
, a dictionary attack is a technique for defeating a cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.
Technique
A dictionary attack uses a targeted technique of successively trying all the words in an exhaustive list called a dictionary (from a pre-arranged list of values). In contrast with a brute force attackBrute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
, where a large proportion key space
Key space
In cryptography, an algorithm's key space refers to the set of all possible keys that can be used to initialize it. For example, if an algorithm works using a key that is a string of 10 bits, then its key space is the set of all binary strings of length 10. i.e...
is searched systematically, a dictionary attack tries only those possibilities which are most likely to succeed, typically derived from a list of words for example a dictionary (hence the phrase dictionary attack) or a bible etc. Generally, dictionary attacks succeed because many people have a tendency to choose password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
s which are short (7 characters or fewer), single words found in dictionaries or simple, easily-predicted variations on words, such as appending a digit.
Pre-computed dictionary attack
It is possible to achieve a time-space tradeoff by pre-computing a list of hashesCryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
of dictionary words, and storing these in a database using the hash as the key
Unique key
In relational database design, a unique key can uniquely identify each row in a table, and is closely related to the Superkey concept. A unique key comprises a single column or a set of columns. No two distinct rows in a table can have the same value in those columns if NULL values are not used...
. This requires a considerable amount of preparation time, but allows the actual attack to be executed faster. The storage requirements for the pre-computed tables were once a major cost, but are less of an issue today because of the low cost of disk storage. Pre-computed dictionary attacks are particularly effective when a large number of passwords are to be cracked. The pre-computed dictionary need only be generated once, and when it is completed, password hashes can be looked up almost instantly at any time to find the corresponding password. A more refined approach involves the use of rainbow table
Rainbow table
A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering the plaintext password, up to a certain length consisting of a limited set of characters. It is a form of time-memory tradeoff, using less...
s, which reduce storage requirements at the cost of slightly longer lookup times. See LM hash
LM hash
LM hash, LanMan, or LAN Manager hash was the primary hash that Microsoft LAN Manager and Microsoft Windows versions prior to Windows NT used to store user passwords...
for an example of an authentication system compromised by such an attack.
Pre-computed dictionary attacks can be thwarted by the use of salt
Salt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
, a technique that forces the hash dictionary to be recomputed for each password sought, making precomputation
Precomputation
In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is often used in algorithms that depend on the results of expensive...
infeasible provided the number of possible salt values is large enough.
See also
- Password crackingPassword crackingPassword cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...
- Password strengthPassword strengthPassword strength is a measure of the effectiveness of a password in resisting guessing and brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly...
- Key derivation functionKey derivation functionIn cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function...
- Key stretching
- E-mail address harvestingE-mail address harvestingEmail harvesting is the process of obtaining lists of email addresses using various methods for use in bulk email or other purposes usually grouped as spam.-Methods:...
Examples
Well known examples of dictionary attack software tools:- Cain and Abel
- CrackCrack (software)Crack is a Unix password cracking program designed to allow system administrators to locate users who may have weak passwords vulnerable to a dictionary attack....
by Alec Muffett - John the RipperJohn the RipperJohn the Ripper is a free password cracking software tool. Initially developed for the UNIX operating system, it currently runs on fifteen different platforms...
- L0phtCrackL0phtCrackL0phtCrack is a password auditing and recovery application originally produced by Mudge from L0pht Heavy Industries. It is used to test password strength and sometimes to recover lost Microsoft Windows passwords, by using dictionary, brute-force, hybrid attacks, and rainbow tables...
- Metasploit ProjectMetasploit ProjectThe Metasploit Project is an open-source computer security project which provides information about security vulnerabilities and aids in penetration testing and IDS signature development....
- OphcrackOphcrackOphcrack is a free open source program that cracks Windows passwords by using LM hashes through rainbow tables. The program includes the ability to import the hashes from a variety of formats, including dumping directly from the SAM files of Windows...
- THC Hydra
- Medusa
External links
- RFC 2828 – Internet Security Glossary
- RFC 4949 – Internet Security Glossary, Version 2
- RSA BSAFE Crypto-C Glossary
- US Secret Service use a distributed dictionary attack on suspect's password protecting encryption keys
- Library with several attack Dictionaries
- Testing for Brute Force (OWASP-AT-004)
- Dictionary attack on several leaked accounts and access to comprehensive wordlist