Dictionary attack on pass-phrases on common algorithms?

Question

I don't yet perfectly understand the difference between brute-force and dictionary attack since this differentiates one attacking the key and another attacking password: apparently attacking passwords can take longer, right?

But it's not necessarily true depending how unaware users can be, and that's where dictionaries shine.

So as the recent XKCD demonstrated, pass phrases are much more secure not because of their bit entropy, but because of their bit length, and even if a pass phrase is done with common words which also are in a dictionary, a dictionary attack of a pass phrase is still "infeasible" if it is at least 3 or 4 words, which makes it still very easy to memorize.

So would it be a good design choice to force users to choose at least 3 words in the dictionary to have a long enough password, for example with some auto-complete feature? What do you think?

PS: I'm asking this not in the context of expensive information requiring design efforts, I'm more thinking into good privacy for public use, considering the attacker has access to the cipher-text (which is not necessarily true on the web).

Answer 1

"Brute force" is a loosely-defined traditional expression to designate a kind of attack of low mathematical cleverness, namely trying all possible values for some unknown. For instance, in the context of symmetric encryption with AES, using a 128-bit key, "bruteforcing" would be trying all possible sequences of 128 bits as possible keys, until one matches (and there are so many such sequences that the average attack cost will be astronomical, hence totally impractical).

A dictionary is a set of "possible passwords", and a dictionary attack is about trying all possible passwords from a dictionary. Thus, a dictionary attack can be called "brute force". However, the expression "brute force" somehow suggests unsubtlety, and there can be quite some psychological finesse in the definition of a dictionary. As I said, "brute force" does not have a well-established mathematically meaning.

In "to force users to choose at least 3 words in the dictionary", the worst word is "force". Enforcing password rules on users tend to be counterproductive. Users should cooperate, and if you antagonize them, then they will actively seek countermeasures with great creativity. You really do not want the users to resent the password as a burden. Remember that almost none of your users will have a mathematically correct notion of password entropy; most will not care, and most of those who care will think about passwords in the same way as passwords are used in movies: witty allusions to some events or objects, supposed to defeat attackers through some "cleverness".

The second worst word in your proposal is "choose". To defeat a dictionary attack, the dictionary (as "the set of potential passwords") should be huge. The set of potential passwords is what users will effectively choose, not the length of the list you gave them. If you give them a list of 1000 words and tell them to "choose" one of them at random, many will pick a word in the first 10. Human beings are simply not good at doing things with uniform randomness. The password selection process should involve a physical device (e.g. dice, or a coin) and -- that's the important point -- the user MUST stick with the randomly selected words. If users are free to choose as they see fit, most will see fit to select words with a meaning (e.g. a sequence of words which "says something") because that's what they will remember best.

Answer 2

A dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its passphrase by searching likely possibilities. It 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 attack, where a large proportion key space is searched systematically, a dictionary attack tries only those possibilities which are most likely to succeed, and are 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 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.

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 (if any exist) that would make the task easier. It involves systematically checking all possible keys until the correct key is found. In the worst case, this would involve traversing the entire search space.

As for answering your question about whether or not it is a good decision to force the user to select three words from a dictionary, I believe the answer to be no, only because there are many password checkers / managers that prevent the user from entering more than 8 characters, say. I know it sucks but that is a reality. What would be better would be to get the user to select a combination of letters, numbers and punctuation marks (if possible), not in consecutive order though. Again, there are some password checkers / managers that prevent punctuation marks from being entered. If possible, you could also force them to use a combination of upper and lower case characters in the password.

Answer 3

In the context of block ciphers like DES, or historical ciphers, the usual terminology is that a brute force attack enumerates all the keys to find one matching all intercepted data; in this context, dictionary attack is sometime used to describe an attack where a number of correspondences between known plaintext and ciphertext are accumulated, forming a growing translation dictionary, which can be reused later without attempting to guess the key, should the same ciphertext reappear.

In the context of human-memorable password, the terminology is less well established. An attack attempting to enumerate all acceptable passwords in lexicographic order would be a brute force attack, but other attacks could qualify, such as one trying all passwords in a dictionary of common passwords, which is also the simplest example of dictionary attack in this context, where the term is used for about any attack that use a list of common words or passwords. With some poor schemes, a pre-computation can be performed on the dictionary of common passwords, the result is called a rainbow table.

In that context of human-memorable password, mechanically "forcing users to take at least 3 words in a dictionary of words" would be very bad, if the dictionary is static: it prevents users to make variations, which increase entropy dramatically; many if not most users would use short words, reducing entropy; and would stick to common words after having one rejected because it is not in the dictionary, further reducing entropy. Also, XKCD#936 misses at least the points that short passwords are faster to type, and contain less typos!

On the other hand, suggesting to the user the use of like 4 words as a basis to form a memorable pass phrase, and using that term rather than password, looks like a reasonable idea.