What are the differences between dictionary attack and brute force attack?

Question

Can someone explain the major differences between a Brute force attack and a Dictionary attack. Does the term rainbow table has any relation with these?

Answer 1

Similarities Both a dictionary and brute force attack are guessing attacks; they are not directly looking for a flaw or bypass. Either can be an offline attack or an online attack.

An online attack tries automated routines providing input to a legitimate system. They are not looking to create an exploit in functionality, but to abuse expected functionality.

An offline attack attempts to emulate the encryption/hashing and requires a known output of that process (i.e., you don't attack the system, you already have the hashed/encrypted password)

---

Brute Force Attack

Definition: Attempts to determine a secret by trying every possible combination.

Qualities:

• The number of attempts is limited by the maximum length and the number of characters to try per position (or byte if considering Unicode passwords)
• The time to complete is greater, but there is greater coverage of likely cleartext value (all possibilities only if set to the maximum length and every possible character is considered in every position)

Physical World Example: Given a combination lock which requires three numbers to be taken in sequence, you try every possible combination - e.g., First 1-2-3, then 1-2-4.

Note, a brute force attack may not necessarily try all options in sequential order. An advanced brute force attack may make certain assumptions, e.g., complexity rules require uppercase, first character more likely to be upper than lower case).

---

Dictionary Attack

Definition: Typically a guessing attack which uses precompiled list of options. Rather than trying every option, only try complete options which are likely to work.

Qualities:

• The dictionary or possible combinations is based upon some likely values and tends to exclude remote possibilities. It may be based on knowing key information about a particular target (family member names, birthday, etc.). The dictionary may be based on patterns seen across a large number of users and known passwods (e.g., whats the most globally likely answers). The dictionary is more likely to include real words than random strings of characters.
• The execution time of dictionary attack is reduced because the number of combinations is restricted to those on the dictionary list
• There is less coverage and a particularly good password may not be on the list and will therefore be missed

Real World Examples:

• Access to a secret club requires knowing the owner's name, you guess "Rob" or "Jake" rather than "computer"
• Given the same lock example above, you try a combinations equating to the birthday of the lock owner or the lock owner's friends and family.

---

Trade Off

The main trade off between the two attacks is coverage versus time to complete. If you have a reasonable thought about what the password will be, you can skip unlikely answers and get a response in a faster amount of time. This is important because passwords are often subject to change and because as password length increases the time to guess every possibility grows really, really fast.

Hybrids

There are of course attacks which leverage both techniques in the interest of balancing the tradeoff. For example, if the attacker believes a user is likely to form a password by concatenating a dictionary word and then adding a number (which he increments each time he is required to change his password), then the guesses being executed may combine the word list and then append numbers (e.g., "mypassword2014" and then "mypassword2015"). Hybrids may also combine words in a brute force manner: Consider a requirement for a user to change his password every 90 days, he may form passwords like "mypasswordsummer" and then "mypasswordfall". The attacker then builds a hybrid attack which will take a dictionary word and then append other dictionary terms (potentially the same of different dictionaries) to make guesses.

---

Rainbow Table versus Dictionary/Brute Force

A rainbow table is generally an offline only attack. In a brute force attack or dictionary attack, you need to spend time either sending your guess to the real system to running through the algorithm offline. Given a slow hashing or encryption algorithm, this wastes time. Also, the work being done cannot be reused.

A rainbow table is precomputed listing. You actually work backwards from the hashed/encrypted text. The attacker will run through the algorithm to get every possible output given every possible input. The list of inputs may be brute force, dictionary, or hybrid. Based on the list of outputs, the attacker now has a reuseable table mapping inputs to known outputs.

With the precomputed table, a simple lookup is now possible given the encrypted/hashed version of the password. If you can find the victim's encrypted/hashed version you can easily return the real plaintext password. Rainbow tables are used to reduce redundant work. There is a trade off with doing the work up front and storing the tables. For example, if you were just doing a brute force or a dictionary attack, you can stop as soon as you find your answer. However, the rainbow table must be fully calculated.

If you were to run a a rainbow table attack and the 5th entry out of 500 million entries was your match, then all of the effort and time used to create the other 499,999,995 passwords may be considered wasted. However, if you are looking to break multiple passwords to reuse the table over multiple attacks, the time savings can add up.

Answer 2

A brute force attack means probing the complete keyspace on the algorithm.

A dictionary attack means that you probe only passwords/keys from a dictionary (which does not contain the complete keyspace).

A brute force attack is primarily used against the encryption algorithm itself (you can also use this against passwords but there you use dictionary attacks most time).

A dictionary attack is primarily used against passwords. Encryption algorithms are seldom attacked with a dictionary attack because most times they use a random number as key (is you use a weak PRNG then a dictionary attack could be feasible). A typical dictionary for this attack would contain the most used passwords.

A rainbow table is used to attack a hashed password in reverse. That means I have a table with possible hashes and look up a matching password.

To prevent attacks using rainbow tables each hashed password should be differently salted as then I would need a rainbow table for every hash and every salt.

Answer 3

Dictionary Attack: The attacker tries a list of known or commonly used passwords. Thus, s/he tries a list (dictionary) of passwords. Generally, dictionary attacks succeed because many people have a tendency to choose passwords which are short and easy to remember like superman, harrypotter, etc.

Brute Force Attack: Does not use a list of passwords; instead, it aims at trying all possible combinations in the password space.

For example, let's assume the password is a four-digit PIN code.

In this case the dictionary attack will try to use a list of common used PIN codes such as: 0123, 2000, 4444 and so on (see the list of most common pin codes).

Conversely, a brute force attack will try all possible PIN codes which means it will try 10^4 = 10000 times until it finds the right PIN code with probability 100%. (4 because we have 4 digits and 10 because each digit can be any value between 0 and 9)

In theory, brute force attack will discover the password, however, it could take very long to try all possible combinations. Usually an attacker starts with the dictionary attack and if it fails he moves to the brute force attack.

Rainbow table: Not directly linked to brute force or dictionary attack. It is very important to not store the password (in DB or file) in plain text. The passwords are hashed using secure hash functions like scrypt and this hash is stored. A rainbow table attack is a method that aims at guessing the plain text of the password from the hashed value (to thwart the attack, one adds unique values - salts while hashing).